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) and constructive applications (such 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 \(f_{n,P}\) and defined as any function on \(E\) with divisor \(n(P) - ([n]P) - (n-1) \infty\), where \(\infty\) is the point at infinity of the curve.

Weil Pairing#

The Weil pairing is a non-degenerate bilinear map from \(E[n] \times E[n]\) to \(\mu_n\), the \(n\)-th roots of unity. The Weil pairing \(w_n(P,Q)\) is computed as \((-1)^n f_{n,P}(Q)/f_{n,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] \times 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 \(\mu_n\) using the final exponentiation; i.e., powering by \(\#K^*/n\). The Tate pairing \(t_n(P, Q)\) is computed as \(f_{n,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 \(t_n(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 \(e_n(P,Q) = t_n(P,Q)^{(\#K-1)/n}\). 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.

Let \(E\) be a supersingular elliptic curve defined over \({\mathbb{F}}_q\) and \(n | \#E({\mathbb{F}}_q)\). The security multiplier \(k\) is the smallest positive integer such that \(q^k \equiv 1\) mod \(n\). Here, in the supersingular case, \(k\) divides 6. Now, \(E[n] \subseteq E({\mathbb{F}}_{q^k})\) is a free \({\mathbb{Z}}/n{\mathbb{Z}}\)-module of rank 2 which splits into the direct sum of 2 rank one eigenspaces under the action of \(q\)-Frobenius (denoted by \(F\) in the following), 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] \times E[n]\) given by the product of the two \(F\)-eigenspaces \(G_1 \times G_2\), where \(P \in G_1\) iff \(F(P) = P\) and \(Q \in G_2\) iff \(F(Q) = [q] Q\). \(G_1\) is just \(E({\mathbb{F}}_q)[n]\). If \(R\) is an arbitrary \(n\)-torsion point in \(E({\mathbb{F}}_{q^k})\), \(k\) times its \(G_1\)-component is just the \(F\)-trace of \(R\). This can be used to find non-trivial points in \(G_2\) (see the example below).

There are three versions of the Eta pairing: one unreduced and two reduced versions. The Eta pairing \(e_T(P,Q)\) is defined as \(f_{T,P}(Q)\) where \(T = t-1\) and \(\#E({\mathbb{F}}_q) = 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 \(\mu_n(K)\) where \(K\) is \({\mathbb{F}}_{q^k}\).

EtaTPairing(P, Q, n, q): PtEll, PtEll, RngIntElt, RngIntElt -> RngElt#

CheckCurve : BoolElt                    Default: false
CheckPoints: BoolElt                    Default: false

Given a supersingular elliptic curve \(E/{\mathbb{F}}_q\) and 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({\mathbb{F}}_q) = 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({\mathbb{F}}_{q^k})\) and \(q\) should be the size of the base field.

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/{\mathbb{F}}_q\), 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: It maps directly into \(n\)-th roots of unity. Both points need to be in the same point set \(E({\mathbb{F}}_{q^k})\) and \(q\) should be the size of the base field.

In the previous intrinsics one can explicitly check that the curve is supersingular by setting the parameter CheckCurve to true, and that the input points are indeed in the eigenspaces of Frobenius by setting the parameter CheckPoints to true. 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 \(G_2 \times G_1\). 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 \(a_T(Q,P)\) with \(Q \in G_2\) and \(P \in G_1\) is defined as \(f_{T,Q}(P)\), where \(T = t-1\) and \(\#E({\mathbb{F}}_q) = 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 Ate pairing with \(T=t-1\) where \(\#E({\mathbb{F}}_q) = 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({\mathbb{F}}_{q^k})\) and \(q\) should be the size of the base field.

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 Ate pairing with \(T=q\). This pairing is automatically reduced: It maps directly into \(n\)-th roots of unity. Both points need to be in the same point set \(E({\mathbb{F}}_{q^k})\) and \(q\) should be the size of the base field.

In the previous intrinsics one can explicitly check that the input points are indeed in the eigenspaces of Frobenius by setting the parameter CheckPoints to true. By default Magma does not perform these checks for efficiency reasons.

Example: Pairings Finite Fields (ex-cdc875)#

In this example, we first create a so-called BN-curve, which is an elliptic curve of the form \(y^2 = x^3 + b\) defined over \({\mathbb{F}}_p\) of prime order \(n\) and embedding degree \(k=12\). These curves can be found easily by testing for which \(s\) both \(p(s) = 36s^4 + 36s^3 + 24s^2 + 6s +1\) and \(n(s)=36s^4+ 36s^3 + 18s^2 +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;  // arbitrary initial 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

Run in calculator

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

Run in calculator

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

Run in calculator

or test the bilinearity of the reduced Tate pairing

> ReducedTatePairing(P, 2*Q, n) eq ReducedTatePairing(P, Q, n)^2;
true

Run in calculator

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

Run in calculator

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 \(G_2 \times G_1\) and up to this point we only have a generator of \(G_1\). To find a generator of \(G_2\) we need to remove the component in \(Q\) that lies in \(G_1\). This can be done easily by using the trace of the point \(Q\): \({\rm Tr}(Q) = \sum_{i = 0}^{k-1} F(Q)\) with \(F\) the \(p\)-power Frobenius. The trace equals \(k\) times the component of \(Q\) in \(G_1\).

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

Run in calculator

At this point \(Q\) is in \(G_2\) 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

Run in calculator

To test the Eta pairing computations we will use one of the supersingular elliptic curves \(y^2 + y = x^3 + x + b\) with \(b = 0\) or 1 over a finite field \({\mathbb{F}}_{2^m}\) 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[1], F2m, i), Frobenius(Q[2], F2m, i)]  :
>                       i in [0..k-1]];
> Q := k*Q - TrQ;

Run in calculator

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

Run in calculator

Example: MOV With Weil Pairing (ex-a16e5c)#

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 \({\mathbb{F}}_p\) for \(p > 3\) can be \({\mathbb{Z}}/n{\mathbb{Z}}\) or \({\mathbb{Z}}/2{\mathbb{Z}}\times {\mathbb{Z}}/(n/2){\mathbb{Z}}\), where \(n = p+1\), and the group structure over a degree \(2\) extension is \({\mathbb{Z}}/n{\mathbb{Z}}\times {\mathbb{Z}}/n{\mathbb{Z}}\). 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

Run in calculator