Pairing-based cryptography has become a highly active research area. We define bilinear maps, or pairings, and show how they give rise to cryptosystems with new functionality.; There is only one known mathematical setting where desirable pairings exist: hyperelliptic curves. We focus on elliptic curves, which are the simplest case, and also the only curves used in practice. All existing implementations of pairing-based cryptosystems are built with elliptic curves. Accordingly, we provide a brief overview of elliptic curves, and functions known as the Tate and Weil pairings from which cryptographic pairings are derived.; We describe several methods for obtaining curves that yield Tate and Weil pairings that are efficiently computable yet are still cryptographically secure.; We discuss many optimizations that greatly reduce the running time of a naive implementation of any pairing-based cryptosystem. These techniques were used to reduce the cost of a pairing from several minutes to several milliseconds on a modern consumer-level machine.; Applications of pairings are largely beyond our scope, but we do show how pairings allow the construction of a digital signature scheme with the shortest known signature lengths at typical security levels.
展开▼