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