# Is it right about an example of bilinear map $e$?

The equation for the elliptic curve is $y^{2} = x^{3} + x$ and is defined over the field $F_{q}$ for some prime $q\equiv 3 \pmod 4$, and set $q=307$. Choose random generator $g=[182, 240]$. My question is that how do I construct a bilinear map $e$ and compute $g_{1} = e(g, g)$?

• $g$ has order $77$, this is probably not what you want. – fkraiem Jun 4 '15 at 8:15
• In general, this curve is bad because the largest prime factor of the order of its group is $11$. You want a point of large prime order. – fkraiem Jun 4 '15 at 8:33
• Yes, I know. I am just wondering how to construct a bilinear map e? – Michael Jun 4 '15 at 8:35
• I am currently writing a detailed answer, but using a different curve from yours. – fkraiem Jun 4 '15 at 8:36
• Okay, Could you please send me the detailed answer? many thanks. – Michael Jun 4 '15 at 8:38

The simplest construction that I know of is given in Section 6.9 of the book by Hoffstein, Pipher and Silverman (5.9 in the first edition). I also talk about it in Section 3.3 of this (but I do not claim that it matches the book's quality of exposition).

First, you need a prime $p$ with two properties:

• You want $p\equiv 2\pmod 3$, this allows you to easily construct a supersingular curve over $\mathbf{F}_p$ (as $Y^2 = X^3 + b$ for any $b \ne 0$). Remember that a supersingular curve is one which has $p+1$ points.
• You want $p+1$ to have a large prime factor, ideally $q = (p+1)/6$ should be prime. This allows you to pick a point of large prime order. In fact, it is best to first choose a prime $q$ of appropriate size, and then look for a suitable $p$.

For this example, I take $p = 587$ and $b = 1$. Then $q = (p+1)/6 = 137$ is prime, and the point $P = [332,103]$ has order $q$ on the curve $E$ with equation $Y^2 = X^3 + 1$ over $\mathbf{F}_p$. I note $E(K)$ the goup of points of $E$ with coordinates in $K$ ($K$ will be either $\mathbf{F}_p$ or $\mathbf{F}_{p^2}$.)

The basic tool is the Weil pairing, which I will note $e_q$. All you need to know about it is that it is a bilinear map from the group of $q$-torsion points of the curve (i.e., the group of points $P$ such that $qP = \infty$) to the group of $q$th roots of unity in $\mathbf{F}_p$ (i.e., the group of all $x\in \mathbf{F}_p$ such that $x^q = 1$). You can use many computer algebra systems to compute the Weil pairing, I use Pari/GP:

gp > p = 821;
gp > p%3
2
gp > isprime(p)
1
gp > q = (p+1)/6
137
gp > isprime(q)
1
gp > E = ellinit([0,1]*Mod(1,p));
gp > until(ellorder(E,P) == q, P = random(E));
gp > P
[Mod(332, 821), Mod(103, 821)]
gp > ellweilpairing(E,P,P,q)
Mod(1, 821)


However, the Weil pairing is not suitable as is for cryptographic purposes because it is also alternating, meaning that $e_q(P,P) = 1$ for all $P$, so we need to modify it. What we do is consider the curve as being defined over $\mathbf{F}_{p^2}$, and apply the Weil pairing in this curve. More precisely, it we let $\zeta$ be a primitive $3$rd root of unity in $\mathbf{F}_{p^2}$ (prove that it exists), then for any point $P = [x_P,y_P] \in E(\mathbf{F}_p)$, the point $P' = [\zeta\cdot x_P,y_P]$ is in $E(\mathbf{F}_{p^2})$. Moreover, if $qP = \infty$, then $qP' = \infty$ as well, which means that $P'$ can be an "argument" of $e_q$. Hence, finally, we define our "modified Weil pairing" $\hat{e}_q$ on the original curve (over $\mathbf{F}_p$) as follows: for a point $Q = kP$ (for some integer $k$), we let $$\hat{e}_q(P,Q) = e_q(P,Q'),$$ where $e_q$ is the ordinary Weil pairing, but applied on the curve over $\mathbf{F}_{p^2}$. In practice:

gp > u = ffgen(p^2, u);
gp > until(z != 1, z = random(u)^((p^2-1)/3));
gp > E2 = ellinit([0,1],u);
gp > ellmodweilpairing(E,P,Q,q) = ellweilpairing(E2,P,[z*Q[1],Q[2]],q);
gp > ellmodweilpairing(E,P,P,q)
562*u + 172


We can see that this pairing is bilinear:

gp > Q = ellmul(E,P,99);
gp > ellmodweilpairing(E,P,P,q)*ellmodweilpairing(E,P,Q,q)
693*u + 108