Pairing-Based Cryptography

Corresponds to Chapter 15.4–15.8. A bilinear pairing $e: G_1\times G_2\to G_T$ lets you “multiply” two group elements’ discrete logs together in the exponent, which is exactly powerful enough to enable cryptographic primitives with no efficient construction in a plain discrete-log group. The BLS signature scheme is the headline example (short, deterministic signatures, with a direct security proof from a pairing-based assumption), and its signature aggregation property — many different signers’ signatures on possibly-different messages compress into a single short aggregate signature, still individually verifiable — is what makes it central to threshold and multi-signature schemes elsewhere in this vault. Identity-based encryption (IBE) uses a pairing to let anyone encrypt directly to a recipient’s identity string (an email address, say) without first fetching a certificate — a master authority can later issue the matching private key. Closes with the general functional encryption paradigm (decryption reveals a function of the plaintext, not the plaintext itself) and multilinear maps as the natural (if cryptographically fragile in practice) generalization of pairings to more than two inputs.

Outline (TODO — flesh out each)

• Pairing-based cryptography — bilinear pairings
• The BLS signature scheme
• Signature aggregation; secure BLS aggregation
• Signature schemes secure without random oracles
• Identity-based encryption; related security notions
• Identity-based encryption from pairings; applications
• The functional encryption paradigm
• Sample functional encryption schemes from pairings; variations
• Multilinear maps
• Fun application: fair exchange of signatures