2
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ $g$ has order $77$, this is probably not what you want. $\endgroup$ – fkraiem Jun 4 '15 at 8:15
  • $\begingroup$ 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. $\endgroup$ – fkraiem Jun 4 '15 at 8:33
  • $\begingroup$ Yes, I know. I am just wondering how to construct a bilinear map e? $\endgroup$ – Michael Jun 4 '15 at 8:35
  • 1
    $\begingroup$ I am currently writing a detailed answer, but using a different curve from yours. $\endgroup$ – fkraiem Jun 4 '15 at 8:36
  • $\begingroup$ Okay, Could you please send me the detailed answer? many thanks. $\endgroup$ – Michael Jun 4 '15 at 8:38
4
$\begingroup$

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
gp > ellmodweilpairing(E,P,elladd(E,P,Q),q)
693*u + 108
|improve this answer|||||
$\endgroup$
  • $\begingroup$ +1, although it would be nice a brief explanation of how the Weil pairing is constructed, which was one of OP's questions. $\endgroup$ – cygnusv Jun 4 '15 at 10:52
  • $\begingroup$ I agree, but sadly I don't know any (and yes, this makes my answer not entirely satisfactory). $\endgroup$ – fkraiem Jun 4 '15 at 10:56
  • 1
    $\begingroup$ Chapter 5.1 from here seems to give a simple example of the Weil pairing. I don't have the background to fully understand it, but maybe you could spell it out for the rest of us :) Maybe it could be more interesting if I ask a new question regarding this? $\endgroup$ – cygnusv Jun 4 '15 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.