Programming ECC

Central to pairing-based cryptosystems is a bilinear nondegenerate map, originally given as $$f:G\times G\to G_T$$ where $G,G_T$ are both cyclic groups of prime order $r$, and the discrete log problem is hard in $G$.

The Weil Pairing

Let $E/{𝔽}_q$ be an elliptic curve whose group of points contains a cyclic group of order $r$. Let $k$ be the smallest integer such that ${𝔽}_{q^k}$ contains the $r$th roots of unity. (If $k>1$ then by the BK Theorem $E[r]\subset E({𝔽}_{q^k})$.) Recall $f_P$ denotes the rational function with divisor $l(P)-l(O)$, and ${𝒜}_P$ denotes a divisor equivalent to $(P)-(O)$. The Weil pairing $e:E[r]\times E[r]\to {𝔽}_{q^k}^{*}$ is defined as $$e(P,Q)=\frac{f_P({𝒜}_Q)}{f_Q({𝒜}_P)}$$ for choices of divisors that avoid the zeroes and poles of $f_P,f_Q$ thus allow $e(P,Q)$ to lie in ${𝔽}_{q^k}^{*}$. Miller's algorithm is used to compute $f_P({𝒜}_Q)$. The Weil pairing is nondegenerate and bilinear. Thus if we can find some point $P$ and a homomorphism $\varphi :⟨P⟩\to E[r]$ such that $\varphi (P)$ and $P$ are linearly independent then taking $G=⟨P⟩$ and $G_T$ to be the $r$th roots of unity (which lie in ${𝔽}_{q^k}^{*}$) gives a bilinear pairing suitable for cryptography, where we define $$f(P,Q)=e(P,\varphi (Q))$$ However, in practice it is better to use the Tate pairing.

Examples

Suppose $q$ is a prime and $q=3\mathrm{mod}4$, so $-1$ is a quadratic residue in ${𝔽}_q$. Let $E$ be the curve $$E:y^2=x^3+x$$ It turns out that $\#E({𝔽}_q)=q+1$ and $\#E({𝔽}_{q^2})=(q+1{)}^2$, thus the embedding degree is 2. Let $r$ be the largest prime dividing $q+1$, and define $h$ by $r\cdot h=q+1$. Then $E({𝔽}_q)$ contains a cyclic subgroup of order $r$ which we call $G$, and $E({𝔽}_{q^2})$ contains a group isomorphic to ${\mathbb{Z}}_r\times {\mathbb{Z}}_r$. Consider the homomorphism $\varphi :E({𝔽}_q\to E({𝔽}_{q^2})$ given by $$\varphi (x,y)=(-x,iy)$$ where $i$ is a square root of -1. Clearly $\varphi$ maps to points that are linearly independent of the input points, since the output points lie over a different field. (And since $\varphi$ is a homomorphism, the output point has the same order as the input point.)

Thus with $G$, and $\varphi$ as above, if we set $G_T$ to the subgroup of ${𝔽}_{q^2}^{*}$ that has order $r$, we have a concrete example of a bilinear nondegenerate pairing on groups where it is widely believed discrete log is hard.

A similar example is the curve $E:y^2=x^3+1$ over ${𝔽}_q$ for any prime $q=2\mathrm{mod}3$. (For implementation purposes it is convenient to take $q=11\mathrm{mod}12$ so that $-1$ is guaranteed to be a quadratic nonresidue.) As above, it turns out $\#E({𝔽}_q)=q+1$ and $\#E({𝔽}_{q^2})=(q+1{)}^2$, and if we use the map $\varphi$ given by $\varphi (x,y)=(\zeta x,y)$ where $\zeta$ is a primitive cube root of unity we have another concrete instantiation of a pairing suitable for cryptography.

Note that these two examples fall in the first two classes of supersingular curves. TODO: link

Implementation note: $r$ can be chosen so that it is a Solinas prime, allowing Miller's algorithm to be optimized greatly.

Using Different Curves

In general a map $\varphi$ may not exist. In fact if any curve except for the two examples given above is used, there is no known way to construct a suitable map $\varphi$. To rectify the situation, we must change what it means to be a pairing suitable for cryptography.