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:

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.


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