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 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.
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).
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 tn(P, Q) is computed as fn, P(Q).
Given an n-torsion point P and a point Q on an elliptic curve, this function computes the Tate pairing tn(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 en(P, Q) = tn(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.
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 Fq and n | #E(Fq). The security multiplier k is the smallest positive 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 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] 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.
CheckCurve: BoolElt Default: false
CheckPoints: BoolElt Default: false
Given a supersingular elliptic curve E/Fq 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(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 base field.
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/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: It 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 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.
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.
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(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 base field.
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 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(Fqk) 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.
> 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
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 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: (Tr)(Q) = ∑i = 0k - 1 F(Q) with F the p-power Frobenius. The trace equals k times the component of Q in G1.
> 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 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 one of the supersingular elliptic curves y2 + y = x3 + x + b with b = 0 or 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[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