# 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`

```magma
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`

```magma
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`

```magma
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`

```magma
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`

```magma
CheckPoints: BoolElt                    Default: false
```

The reduced version of the `AteTPairing` function.

### `AteqPairing(P, Q, m, q): PtEll, PtEll, RngIntElt, RngIntElt -> RngElt`

```magma
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.

```magma
> 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:

```magma
> WeilPairing(P, 2*P, n) eq 1;
true

```

and also that the Weil pairing can be obtained from 2 Tate pairing computations:

```magma
> 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

```magma
> 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:

```magma
> 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 \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$.

```magma
> 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:

```magma
> 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 $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$.

```magma
> 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.

```magma
> 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: 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.

```magma
> 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

```