Pairing-based cryptography

Bilinear pairings are functions e: G1 × G2 → GT that satisfy e(aP, bQ) = e(P, Q)^ab for all integers a, b. In cryptography, G1 and G2 are typically groups of points on an elliptic curve over a finite field, and GT is a multiplicative subgroup of a finite field extension. The Weil and Tate pairings were originally introduced for mathematical purposes, but their cryptographic use was recognized in the 1990s.

The security of pairing-based schemes relies on the hardness of the Bilinear Diffie-Hellman (BDH) problem and related assumptions. Efficient implementations use special curves such as Barreto-Naehrig (BN) curves and Barreto-Lynn-Scott (BLS) curves, which provide optimal embedding degrees and fast pairing computation.

The most celebrated application is identity-based encryption (IBE), first proposed by Adi Shamir in 1984 and realized by Dan Boneh and Matthew Franklin in 2001 using the Weil pairing. IBE allows any string (e.g., an email address) to serve as a public key, eliminating the need for certificate authorities.

Pairings also enable short signatures (BLS signatures) that are half the length of traditional signatures, and more advanced primitives such as attribute-based encryption, functional encryption, and non-interactive zero-knowledge proofs. These have been used in practical systems like the Boneh-Franklin IBE and in blockchain protocols for aggregate signatures.

Pairing computation is computationally intensive, but modern implementations achieve sub-millisecond times using optimized algorithms and hardware acceleration. The optimal ate pairing is the most efficient algorithm for BN and BLS curves, and libraries such as PBC, RELIC, and MIRACL provide production-ready implementations.

Pairing-friendly curves are chosen to balance security and efficiency, with parameters such as embedding degree k and rho value. The choice of curve affects the security level and the size of the groups, and recent research has focused on post-quantum alternatives, though pairings are not quantum-safe.

Pairing-based cryptography has surprising connections to other areas. For example, the original Boneh-Franklin IBE scheme was preceded by a less efficient identity-based scheme by Sakai, Ohgishi, and Kasahara, which was published in Japanese and remained obscure for years.

Pairings have also been used for non-cryptographic purposes, such as constructing deterministic randomness extractors and in the design of certain zk-SNARKs. The concept of 'pairing-friendly' curves was formalized by Freeman, Scott, and Teske, who classified families of curves with small embedding degree. Additionally, pairings on supersingular elliptic curves were used in the first practical implementation of identity-based encryption, but these curves are now considered insecure for pairing-based cryptography due to the MOV attack.

Bilinear pairing

A function e: G1 × G2 → GT that is linear in each argument, satisfying e(aP, bQ) = e(P, Q)^ab.

Identity-based encryption (IBE)

A public-key encryption scheme where the public key is an arbitrary string, such as an email address.

Bilinear Diffie-Hellman (BDH) problem

The computational problem of deriving e(P, Q)^abc from P, aP, bP, cQ, which underlies the security of many pairing-based schemes.

Embedding degree

The smallest integer k such that the group of points on the curve is contained in the multiplicative group of a finite field extension of degree k.

Pairing-friendly curve

An elliptic curve chosen to have a small embedding degree and other properties that make pairing computation efficient.