# Elliptic curve pairings

$$\gdef\F{\mathbb{F}} \gdef\G{\mathbb{G}} \gdef\g{\mathrm{G}} \gdef\h{\mathtt{H}} \gdef\e{\mathrm{e}}$$

Let $\G_1$, $\G_2$, $\G_3$ be elliptic curve groups with the same scalar field $\F$, generators $\g_1$, $\g_2$, $\g_3$ and a pairing $\e: \G_1 × \G_2 → \G_3$.

A pairing is a function that satisfies $\e(a ⋅ A, b ⋅ B) = a ⋅ b ⋅ \e(A, B)$ and is not the trivial solution $\e(\dummyarg,\dummyarg) = 0$. From this it follows that $\e(A_1 + A_2, B) = \e(A_1, B) + \e(A_2, B)$ and other useful linear properties.

Note. The pairing is symmetrical in $\G_1$ and $\G_2$ so protocols also work with groups and pairing arguments swapped. This is useful if one group has better performance than the other.

Finding a pairing that satisfy the requirements is challenging, especially when there are additional constraints such as having large binary roots of unity in $\F$. Different families of solutions have been found:

• MNT, Miyaji-Nakabayashi-Takano (2001; paper).
• BLS, Barreto-Lynn-Scott (2002; paper).
• BN, Barreto-Naehrig (2005; paper).
• KSS, Kachisa-Schaefer-Scott (2008; paper).

Two important specific solutions are

Note. The 128 in alt_bn128 revers to the target security level, but it was since found that it is "closer to 96 or so". BLS12-381 development was in part motivated to address this and targets 128 bit security.

## Alt-BN128

Also known as BN254.

$$r = 21888242871839275222246405745257275088548364400416034343698204186575808495617 p = 21888242871839275222246405745257275088548364400416034343698204186575808495617 q = 21888242871839275222246405745257275088696311157297823662689037894645226208583$$

Generator $5$.

To quickly check a a large number of pairings of the form $\e(A_i, B) = \e(C_i, \g_2)$ we can take a random linear combination: Generate random $r_i ∈ \F^n$, compute $A = \sum_i r_i ⋅ A_i$ and $C = \sum_i r_i ⋅ C_i$ and check $\e\p{A, B} = \e\p{C, \G_2}$. We can repeat this trick to aggregate multiple values of $B$.

Remco Bloemen
Math & Engineering
https://2π.com