[Next][Prev] [Right] [Left] [Up] [Index] [Root]

### Pairings on Elliptic Curves

Pairings on elliptic curves over finite fields have many uses, ranging from checking independence of torsion points to more practical applications in cryptography. Both destructive applications (such as the MOV attack), but also constructive applications as pairing based cryptography are worth mentioning. Magma now contains an implementation of the most popular pairings on elliptic curves over finite fields, including the Weil pairing, the Tate pairing and various versions of the Eta and Ate pairings.

All pairings evaluate what is now called a Miller function, denoted by fn, P and defined as any function on E with divisor n(P) - ([n]P) - (n - 1) ∞, where ∞ is the point at infinity of the curve.

#### Weil Pairing

The Weil pairing is a non-degenerate bilinear map from E[n] x E[n] to μn, the n-th roots of unity. The Weil pairing wn(P, Q) is computed as ( - 1)n fn, P(Q)/fn, Q(P).

##### WeilPairing(P, Q, n) : PtEll, PtEll, RngIntElt -> RngElt
Given n-torsion points P and Q on an elliptic curve E. this function computes the Weil pairing of P and Q. Both points need to be in the same point set.

#### Tate Pairing

The Tate pairing (sometimes called the Tate-Lichtenbaum pairing) is a non-degenerate bilinear map from E[n] x E/ n E into K^ * /(K^ * )n, where K is a finite field containing the n-th roots of unity. In practice, one often works with the reduced version of the pairing by mapping into μn using the final exponentiation, i.e. powering by #K^ * /n. The Tate pairing tn(P, Q) is computed as fn, P(Q).

##### TatePairing(P, Q, n) : PtEll, PtEll, RngIntElt -> RngElt
Given an n-torsion point P and a point Q on an elliptic curve, this function computes the Tate pairing tm(P, Q) by returning a random representative of the coset. Both points need to be in the same point set; the field K is the field of definition of this point set.
##### ReducedTatePairing(P, Q, n) : PtEll, PtEll, RngIntElt -> RngElt
Given an n-torsion point P and a point Q on an elliptic curve, this function computes the reduced Tate pairing em(P, Q) = tm(P, Q)(#K - 1)/m. Both points need to be in the same point set; the field K is the field of definition of this point set and n should divide #K - 1.

#### Eta Pairing

The Eta pairing is only defined on supersingular curves and can be considered as an optimised version of the Tate pairing. It works as follows.

E is a supersingular elliptic curve defined over Fq and n | #E(Fq). k >= 1, the security multiplier, is the smallest integer such that qk = 1 mod n. Here, in the supersingular case, k divides 6. Now, E[n] ⊆E(Fqk) is a free Z/nZ-module of rank 2 which splits into the direct sum of 2 rank one eigenspaces under the action of F, q-Frobenius, with eigenvalues 1 and q (as long as (n, k)=1 and k > 1).

The Eta pairing is defined on the subgroup of E[n] x E[n] given by the product of the two F-eigenspaces G1 x G2, where P ∈G1 iff F(P) = P and Q ∈G2 iff F(Q) = [q] Q. G1 is just E(Fq)[n]. If R is an arbitrary n-torsion point in E(Fqk), k times its G1-component is just the F-trace of R. This can be used to find non-trivial points in G2 - see the example below.

There are three versions of the Eta pairing, one unreduced and two reduced versions. The Eta pairing eT(P, Q) is defined as fT, P(Q) where T = t - 1 and #E(Fq) = q + 1 - t or T = q.

As for the Tate pairing, the unreduced version takes values in K^ * /(K^ * )n and the reduced versions in μn(K) where K is Fqk.

##### EtaTPairing(P, Q, n, q) : PtEll, PtEll, RngIntElt, RngIntElt -> RngElt
`    CheckCurve: BoolElt                 Default: false`
`    CheckPoints: BoolElt                Default: false`
Given a supersingular elliptic curve E/Fq, two points P, Q in E[n] such that P = F(P) and F(Q) = [q]Q with F the q-power Frobenius, this function computes the Eta pairing with T=t - 1, where #E(Fq) = q + 1 - t. The result is non-reduced and thus a random representative of a whole coset. Both points need to be in the same point set E(Fqk) and q should be the size of the basefield.
##### ReducedEtaTPairing(P, Q, n, q) : PtEll, PtEll, RngIntElt, RngIntElt -> RngElt
`    CheckCurve: BoolElt                 Default: false`
`    CheckPoints: BoolElt                Default: false`
The reduced version of the EtaTPairing function.
##### EtaqPairing(P, Q, n, q) : PtEll, PtEll, RngIntElt, RngIntElt -> RngElt
`    CheckCurve: BoolElt                 Default: false`
`    CheckPoints: BoolElt                Default: false`
Given a supersingular elliptic curve E/Fq, two points P, Q in E[n] such that P = F(P) and F(Q) = [q]Q with F the q-power Frobenius, this function computes the Eta pairing with T=q. This pairing is automatically reduced, i.e. maps directly into n-th roots of unity. Both points need to be in the same point set E(Fqk) and q should be the size of the basefield.

One can explicitly check that the curve is supersingular and that the input points are indeed in the eigenspaces of Frobenius. By default Magma does not perform these checks for efficiency reasons.

#### Ate Pairing

The Ate pairing generalises the Eta pairing to all elliptic curves, but is defined on G2 x G1, i.e. the arguments are swapped with respect to the Eta pairing. Like the Eta pairing, there are three versions, one unreduced and two reduced. The Ate pairing aT(Q, P) with Q ∈G2 and P ∈G1 is defined as fT, Q(P), where T = t - 1 and #E(Fq) = q + 1 - t or T = q.

##### AteTPairing(Q, P, n, q) : PtEll, PtEll, RngIntElt, RngIntElt -> RngElt
`    CheckPoints: BoolElt                Default: false`
Given two points Q, P in E[n] such that F(Q) = [q]Q and P = F(P) with F the q-power Frobenius, this function computes the Eta pairing with T=t - 1, where #E(Fq) = q + 1 - t. The result is non-reduced and thus a random representative of a whole coset. Both points need to be in the same point set E(Fqk) and q should be the size of the basefield.
##### ReducedAteTPairing(Q, P, n, q) : PtEll, PtEll, RngIntElt, RngIntElt -> RngElt
`    CheckPoints: BoolElt                Default: false`
The reduced version of the AteTPairing function.
##### AteqPairing(P, Q, m, q) : PtEll, PtEll, RngIntElt, RngIntElt -> RngElt
`    CheckPoints: BoolElt                Default: false`
Given two points Q, P in E[n] such that F(Q) = [q]Q and P = F(P) with F the q-power Frobenius, this function computes the Eta pairing with T=q. This pairing is automatically reduced, i.e. maps directly into n-th roots of unity. Both points need to be in the same point set E(Fqk) and q should be the size of the basefield.

One can explicitly check that the input points are indeed in the eigenspaces of Frobenius. By default Magma does not perform these checks for efficiency reasons.

### Example CrvEllFldFin_PairingsFiniteFields (H117E7)

In this example, we first create a so called BN-curve, which is an elliptic curve of the form E: y2 = x3 + b defined over Fp of prime order n and embedding degree k=12. These curves can be found easily by testing for which s both p(s) = 36s4 + 36s3 + 24s2 + 6s + 1 and n(s)=36s4 + 36s3 + 18s2 + 6s + 1 are prime. Finding the parameter b is equally easy by testing a few random values, since there are only 6 isogeny classes. The point G = (1, y) can be used as base point.

```> Zs<s> := PolynomialRing(Integers());
> ps := 36*s^4 + 36*s^3 + 24*s^2 + 6*s + 1;
> ns := 36*s^4 + 36*s^3 + 18*s^2 + 6*s + 1;
> z := 513235038556;  // some random start value
> repeat
>   z := z+1; p := Evaluate(ps, z); n := Evaluate(ns, z);
> until (IsProbablePrime(p) and IsProbablePrime(n));
> p;
2497857711095780713403056606399151275099020724723
> n;
2497857711095780713403055025937917618634473494829
> Fp := FiniteField(p);
> b := Fp ! 0;
> repeat
>   repeat b := b + 1; until IsSquare(b + 1);
>   y := SquareRoot(b + 1);  E := EllipticCurve([Fp ! 0,b]); G := E![1,y];
> until IsZero(n * G);
> E;
Elliptic Curve defined by y^2 = x^3 + 18 over
GF(2497857711095780713403056606399151275099020724723)
> #E eq n;  // just to verify
true
> t := p + 1 - n;
> t;
1580461233656464547229895
> k := 12; // security multiplier
> (p^k-1) mod n; // check on p, n and k
0
> Fpk := GF(p,k);
> N := Resultant(s^k - 1, s^2 - t*s + p);  // number of points over big field
> Cofac := N div n^2;
> P := E(Fpk) ! G;
> Q := Cofac*Random(E(Fpk));  // Q has order n now
```

Up to this point we have constructed a BN-curve and two points of order n. As such we can test for instance that P and 2 P are linearly dependent:

```> WeilPairing(P, 2*P, n) eq 1;
true
```
and also that the Weil pairing can be obtained from 2 Tate pairing computations:

```> WeilPairing(P, Q, n) eq (-1)^n*TatePairing(P, Q, n)/TatePairing(Q, P, n);
true
```
or test the bilinearity of the reduced Tate pairing

```> ReducedTatePairing(P, 2*Q, n) eq ReducedTatePairing(P, Q, n)^2;
true
```
and that the corresponding test for the Tate pairing would fail since the result is a random representative of the coset:

```> TatePairing(P, 2*Q, n) eq TatePairing(P, Q, n)^2;
false
```

Since the curve is ordinary, we cannot use the Eta pairing on this curve. We can use the Ate pairing, but this is defined on G2 x G1 and up to this point, we only have a generator of G1. To find a generator of G2, we need to remove the component in Q that lies in G1. This can be done easily by using the trace of the point Q, i.e. ∑i = 0k - 1 F(Q) with F the p-power Frobenius. The trace Tr(Q) equals k times the component of Q in G1.

```> TrQ := &+[ E(Fpk) ! [Frobenius(Q, Fp, i), Frobenius(Q, Fp, i)] : >                      i in [0..k-1]];
> Q := k*Q - TrQ;
```

At this point Q is in G2 and we can compute the Ate pairing of Q and P. For instance we can test compatibility of the reduced Ate pairing with the reduced Tate pairing:

```> T := t-1;
> L := (T^k-1) div n;
> c := &+[ T^(k-1-i)*p^i : i in [0..k-1] ] mod n;
> ReducedAteTPairing(Q, P, n, p)^c eq ReducedTatePairing(Q, P, n)^L;
true
> Frobenius(AteqPairing(Q, P, n, p)^k, Fp, k-1) eq ReducedTatePairing(Q, P, n);
true
```

To test the Eta pairing computations we will use the following supersingular elliptic curve E : y2 + y = x3 + x + b with b = 0, 1 over a finite field F2m and m odd. These curves have security parameter k = 4.

```> F2m := GF(2,163);
> q := #F2m;
> E := EllipticCurve([F2m ! 0,0,1,1,1]);
> #E;
11692013098647223345629483497433542615764159168513
> IsPrime(\$1);
true
> n := #E;
> t := TraceOfFrobenius(E);
> P := Random(E);
> k := 4;
> F2m4 := ExtensionField<F2m, X | X^4 + X + 1>;
> N := Resultant(s^k - 1, s^2 - t*s + q);  // number of points over big field
> Cofac := N div n^2;
> P := E(F2m4) ! P;
> Q := Cofac*Random(E(F2m4));  // Q has order n now
> TrQ := &+[ E(F2m4) ! [Frobenius(Q, F2m, i), Frobenius(Q, F2m, i)] : >                       i in [0..k-1]];
> Q := k*Q - TrQ;
```

After this setup, we can now compute the Eta pairing and test compatibility with the Tate pairing.

```> d := GCD(k, q^k-1);
> Frobenius(EtaqPairing(P, Q, n, q)^(k div d), F2m, k-1) eq
>                                       ReducedTatePairing(P, Q, n);
true
```

### Example CrvEllFldFin_MOVWithWeilPairing (H117E8)

The following example demonstrates the Menezes, Okamoto, and Vanstone (MOV) reduction of the discrete logarithm on a supersingular elliptic curve to a discrete logarithm in a finite field using the Weil Pairing. The group structure of a supersingular curve E over a finite prime field Fp for p > 3 can be Z/nZ or Z/2Z x Z/(n/2)Z, where n = p + 1, and the group structure over a degree 2 extension is Z/nZ x Z/nZ. The nontrivial Weil pairing on this is the basis for this reduction.

```> p := NextPrime(2^131);
> n := p + 1;
> n;
2722258935367507707706996859454145691688
> Factorization(n);
[ <2, 3>, <3, 2>, <37809151880104273718152734159085356829, 1> ]
> E0 := SupersingularEllipticCurve(GF(p));
> G<x>, f := AbelianGroup(E0);
> G;
Abelian Group isomorphic to Z/2722258935367507707706996859454145691688
Defined on 1 generator
Relations:
2722258935367507707706996859454145691688*x = 0
> n eq #G;
true
> P0 := f(x);
> E1 := BaseExtend(E0,GF(p^2));
> P1 := E1!P0;
> repeat
>    Q1 := Random(E1);
>    z1 := WeilPairing(P1, Q1, n);
> until Order(z1) eq n;
> IsOrder(Q1, n);
true
> r := 1234567;
> z2 := WeilPairing(r*P1, Q1, n);
> z1^r eq z2;
true
> WeilPairing(P1, r*P1, n);
1
```

[Next][Prev] [Right] [Left] [Up] [Index] [Root]

Version: V2.17 of Wed Dec 8 14:24:27 EST 2010