Bilinear Pairings

Elliptic curves are used in cryptography mainly because of DLP i.e. it’s infeasible to calculate $x$ from $X=Gx$.

Pairing helps to compute certain complicated equations on EC points. Traditional EC math lets anyone check linear constraints on the number (eg. $P=Gp,Q=Gq,R=Gr,$ checking $5P+7Q=11R$), but pairing lets you check quadratic constraints ($e(P,Q)\times e(G,G5)=1$ is checking $p\ast q+5=0$).

This makes DDH (Decision Diffie-Hellman) problem very easy to compute using pairings. Also DLog reduction becomes computably feasible if not done on extension fields of Finite Field as we want the target group to be sufficiently bigger so that it’s not possible to do DLog reduction.

$e(P,Q)$ is a function defined on EC points. This is the pairing. Also known as bilinear map. It is called as bilinear because it satisfies following constraints, i.e. it doesn’t matter if we apply group law first and then map, or map then group law:

• $e(P,Q+R)=e(P,Q)+e(P,R)$
• $e(P+S,Q)=e(P,Q)+e(S,Q)$
• $e(G_1,G_2)\ne 1$: This property is called Non-Degeneracy. If whenever ${\mathbb{G}}_3$ is neutral element, then either ${\mathbb{G}}_1\vee {\mathbb{G}}_2$ is neutral.

The pairing is linear in both constraints. So, EC Pairing is a function that takes a pair of points on an elliptic curve and returns an element of some other group, called the target group.

Example: $e(x,y)=2^{xy}$, where $x=3,y=9$ → $P=3,Q=4,R=5$

Note: $+$ and $\cdot$ can be any arbitrary operators. It doesn’t matter what symbols are used in abstract mathematics as long as they obey the properties of associativity, commutativity and reflexivity.

• $a+b=b+a$
• $(a\cdot b)\cdot c=a\cdot (b\cdot c)$
• $(a\cdot c)+(b\cdot c)=(a+b)\cdot c$

However, such simple pairings are not suitable for cryptography as its trivial to divide, compute logarithms and other computations. Simple integers can’t be used in a field having terms like public-private keys or one-way functions because anyone can go back to $y$ knowing $x$ and $e(x,y)$. Thus, we require numbers that can essentially function as “black boxes” or it’s only possible to do simple arithmetic like addition, subtraction, multiplication and division on them and nothing else. That’s where ECs and EC-points come in.

Frobenius endomorphism

Frobenius endomorphism maps EC point to another point:

$$\begin{array}{c}\pi :E(\mathbb{F})\to E(\mathbb{F}):\{\begin{array}{l}(x,y)\to (x^p,y^p)\\ \\ \mathcal{O}\to \mathcal{O}\end{array}\end{array}$$

full r-torsion groups has two interesting subgroups: namely,

• ${\mathbb{G}}_1[r]:=\left\{(x,y)\in E[r]|\pi (x,y)=(x,y)\right\}$ can also be seen as $r$-tosion group given by mapping un-extended elliptic curve point to itself.
• $G_2[r]:=\left\{(x,y)\in E[r]|\pi (x,y)=[p](x,y)\right\}$

Pairing groups

$e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_T$

${\mathbb{G}}_1$ and ${\mathbb{G}}_2$ are subgroups given from Frobenius endomorphism on torsion subgroups of ECs.

The reason why Bilinear map works?

First, we look into the concept of divisors.

Weil Pairing

$$e(\cdot ,\cdot ):{\mathbb{G}}_1[r]\times {\mathbb{G}}_2[r]\to {\mathbb{F}}_{p^k}^{\ast }:(P,Q)\to (-1)\frac{{}^r{f}_{r,P}(Q)}{f_{r,Q}(P)}$$

Tate Pairing

Miller’s Algorithm

MOV Attack

MOV attack refers to the transfer of DLP over EC to finite field ${\mathbb{F}}_{p^{\mathbb{k}}}$ where it’s much easier to solve. This is related to the embedded degree of the EC.

Embedded Degree of an EC refers to the minimum value of k for which $p^k\equiv 1(\mathrm{mod}n)$, where p = prime used for the field and n = order of the curve. This is actually called an attack because DLP shouldn’t be solvable on ECs and thus for curves used throughout the cryptographic primitives, value of k is unreasonably large such that pairings are computably infeasible to compute.

Complexities Assumptions on Bilinear Groups

• Discrete Log problem is still difficult if target group is sufficiently large.
• CDH (Computation Diffie-Hellman) is still hard as we can’t find $g^{xy}$ if we know $g$, $g^x$, $g^y$.
• Bilinear Diffie-Hellman Problem: Given $P,aP,bP,cP\in G_1$, compute $e(P,P{)}^{abc}$

Prerequisites

1. Fermat’s Little Theorem: for a prime p, and any positive integer a, $a^p\equiv amodp$
2. Additive Group: set of numbers with operation defined on addition
3. Multiplicative group: set of numbers with operation defined on multiplication
4. Order of Multiplicative group

Resources

• Vitalik: Exploring Elliptic Curve Pairings
• Statebox’s Elliptic Curve Pairings
• https://crypto.stanford.edu/pbc/thesis.pdf
• https://people.csail.mit.edu/alinush/6.857-spring-2015/papers/bilinear-maps.pdf
• Fundamental Concepts Underlying Elliptic Curves (Level 2): Divisors and Pairings
• Why pairings are used?
• Basics of Pairings - Dan Boneh
• Pairings for beginners
• Intro to Pairings