For decades, elliptic curve groups were viewed strictly as additive Abelian groups where computing discrete logarithms was hard. In the early 2000s, an extraordinary paradigm shift occurred: by exploiting Bilinear Pairings (originally developed as destructive tools for the MOV attack), cryptographers transformed pairings into constructive foundations for revolutionary primitives: Identity-Based Encryption (IBE), Boneh-Lynn-Shacham (BLS) signature aggregation, and modern zk-SNARK polynomial commitments.
1. Mathematical Definition of Bilinear Maps
Let (G_1, G_2) be additive cyclic groups of prime order (r), and let (G_T) be a multiplicative cyclic group of the same order (r). A Bilinear Map (Pairing) is a function:
[
e: G_1 imes G_2 o G_T
]
satisfying three fundamental axioms:
- Bilinearity: For all (P in G_1), (Q in G_2) and all scalars (a, b in mathbb{Z}_r):
[
e([a]P, [b]Q) = e(P, Q)^{ab} = e([b]P, [a]Q)
] - Non-Degeneracy: If (P) generates (G_1) and (Q) generates (G_2), then (e(P, Q)) generates (G_T) (i.e., (e(P, Q)
eq 1)). - Computability: There exists an efficient polynomial-time algorithm to evaluate (e(P, Q)) for all (P, Q).
Pairings are classified into three architectural types:
- Type 1 (Symmetric): (G_1 = G_2). Implemented on supersingular curves, but limited by large field sizes to resist discrete log attacks.
- Type 2: (G_1
eq G_2), with an efficiently computable homomorphism (psi: G_2 o G_1). - Type 3 (Asymmetric): (G_1
eq G_2), with no efficiently computable isomorphism in either direction. Type 3 pairings (e.g., Barreto-Naehrig BN254 and BLS12-381) offer the highest efficiency and optimal group element sizes for zero-knowledge systems.
2. The Weil and Tate Pairings & Miller’s Algorithm
In algebraic geometry, the Weil Pairing is constructed from divisor theory on an elliptic curve (E(overline{mathbb{F}}_q)). Let (E[r]) denote the (r)-torsion subgroup. For (P in E[r]), there exists a rational function (f_P) whose divisor is ( ext{div}(f_P) = r(P) – r(mathcal{O})). The Weil pairing evaluates the ratio of functions across divisors:
[
e_W(P, Q) = rac{f_P(D_Q)}{f_Q(D_P)} in mu_r subset mathbb{F}_{q^k}^*
]
where (k) is the embedding degree (the smallest integer such that (r mid (q^k – 1))). While mathematically symmetric, the Weil pairing requires evaluating two rational functions. Practical systems use the Reduced Tate Pairing or Optimal Ate Pairing:
[
e_{ ext{Tate}}(P, Q) = left( f_{r, P}(Q)
ight)^{rac{q^k – 1}{r}}
]
Victor Miller (1986) invented Miller’s Algorithm: a double-and-add algorithm that constructs (f_{r, P}) in (mathcal{O}(log r)) steps by iteratively composing secant and tangent lines, followed by a final exponentiation to project into the unique target subfield (mu_r).
3. BLS Signature Scheme and Non-Interactive Aggregation
Invented in 2001 by Dan Boneh, Ben Lynn, and Hovav Shacham, BLS Signatures provide the shortest signatures in modern cryptography and support non-interactive aggregation across thousands of validators (the engine behind Ethereum proof-of-stake consensus):
- KeyGen: Sample private key (x leftarrow mathbb{Z}_r^*). Public key is (pk = [x]g_2 in G_2).
- Sign: Hash message (m) to a point (H(m) in G_1) using a hash-to-curve algorithm. Signature is:
[
sigma = [x] H(m) in G_1
] - Verify: Check the single pairing equation:
[
e(sigma, g_2) stackrel{?}{=} e(H(m), pk)
]
Proof of correctness: (e([x]H(m), g_2) = e(H(m), g_2)^x = e(H(m), [x]g_2) = e(H(m), pk)).
Aggregation: Given (n) signatures (sigma_1, dots, sigma_n) on distinct messages (m_i) under public keys (pk_i), any party can aggregate them via simple group addition: (sigma_{ ext{agg}} = sum_{i=1}^n sigma_i in G_1). The verifier checks all (n) signatures in a single operation:
[
e(sigma_{ ext{agg}}, g_2) = prod_{i=1}^n e(H(m_i), pk_i)
]
The aggregate signature remains a single constant-size group element (e.g., 48 bytes on BLS12-381), reducing blockchain block validation bandwidth by orders of magnitude.
