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 f_{n, 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.

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 w_{n}(P, Q) is computed as
( - 1)^{n} f_{n, P}(Q)/f_{n, Q}(P).

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.

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 t_{n}(P, Q) is computed as f_{n, P}(Q).

Given an n-torsion point P and a point Q on an elliptic curve, this function computes the Tate pairing t_{m}(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.

Given an n-torsion point P and a point Q on an elliptic curve, this function computes the reduced Tate pairing e_{m}(P, Q) = t_{m}(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.

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 F_{q} and n | #E(F_{q}).
k >= 1, the security multiplier, is the smallest integer such that
q^{k} = 1 mod n. Here, in the supersingular case, k divides 6.
Now, E[n] ⊆E(F_{qk}) 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 G_{1} x G_{2},
where P ∈G_{1} iff F(P) = P
and Q ∈G_{2} iff F(Q) = [q] Q. G_{1} is just E(F_{q})[n].
If R is an arbitrary n-torsion point in E(F_{qk}), 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(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 μ_{n}(K) where K is F_{qk}.

CheckCurve: BoolElt Default:false

CheckPoints: BoolElt Default:false

Given a supersingular elliptic curve E/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=t - 1, where #E(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(F_{qk}) and q should be the size of the basefield.

CheckCurve: BoolElt Default:false

CheckPoints: BoolElt Default:false

The reduced version of the EtaTPairing function.

CheckCurve: BoolElt Default:false

CheckPoints: BoolElt Default:false

Given a supersingular elliptic curve E/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, i.e. maps directly into n-th roots of unity. Both points need to be in the same point set E(F_{qk}) 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.

The Ate pairing generalises the Eta pairing to all elliptic curves, but
is defined on G_{2} x 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 ∈G_{2} and P ∈G_{1} is defined as f_{T, Q}(P),
where T = t - 1 and #E(F_{q}) = q + 1 - t or T = q.

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(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(F_{qk}) and q should be the size of the basefield.

CheckPoints: BoolElt Default:false

The reduced version of the AteTPairing function.

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(F_{qk}) 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.

> 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; trueand 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); trueor test the bilinearity of the reduced Tate pairing

> ReducedTatePairing(P, 2*Q, n) eq ReducedTatePairing(P, Q, n)^2; trueand 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 G_{2} x 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, i.e. ∑_{i = 0}^{k - 1} F(Q) with F the p-power Frobenius.
The trace Tr(Q) 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;

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

To test the Eta pairing computations we will use the following supersingular
elliptic curve E : y^{2} + y = x^{3} + x + b with b = 0, 1
over a finite field F_{2m} 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;

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

> 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