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.
