A Taxonomy of Pairing-Friendly Elliptic Curves

By David Mandell Freeman, Michael Scott, Edlyn Teske. 2010

546 citations recorded by the source corpus.

Elliptic curves with small embedding degree and large prime-order subgroup are key ingredients for implementing pairing-based cryptographic systems. Such “pairing-friendly” curves are rare and thus require specific constructions. In this paper we give a single coherent framework that encompasses all of the constructions of pairing-friendly elliptic curves currently existing in the literature. We also include new constructions of pairing-friendly curves that improve on the previously known constructions for certain embedding degrees. Finally, for all embedding degrees up to 50, we provide recommendations as to which pairing-friendly curves to choose to best satisfy a variety of performance and security requirements.

Subfields: Artificial Intelligence, Geometry and Topology, Information Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Geometry and Topology

In Information Systems

Citations in the corpus

Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups (2010, background): “Further details can be found in the full version of this paper [10, Appendix A]; descriptions of the elliptic curves are in [9].”
DACC: Distributed Access Control in Clouds (2011, background): “If node x=AND, then the left child is (v[x]|1), and the right child is (0, . . . , −1).”
Scalable Zero Knowledge Via Cycles of Elliptic Curves (2014, background): “Since we aim at a security level of 80 bits, we need r4 ≥ 2160 and q4 ≥ 2240 (so that √r4 ≥ 280 and q4 4 ≥ 2960 [48]).”
Optimal Pairings (2010, background): “An excellent overview of pairing friendly curves is given in [9].”
Faster Explicit Formulas for Computing Pairings over Ordinary Curves (2011, methodology): “Even though the techniques are applied on pairings over BN curves at the 128-bit security level, they can be easily extended to other settings using different curves and higher security levels [14].”
On Prime-Order Elliptic Curves with Embedding Degrees k = 3, 4, and 6 (2008, methodology): “In fact, all methods known so far to construct ordinary elliptic curves of any order and small embedding degree use the CM method; see [ 5 ] for a comprehensive survey.”
Compact Proofs of Retrievability (2008, unknown): “For values of λ up to 128, Barreto-Naehrig curves [4] are the right choice; see the survey by Freeman, Scott, and Teske [10].”
New Software Speed Records for Cryptographic Pairings (2010, methodology): “Since the introduction of Miller’s algorithm [28, 29] for computing pairings on elliptic curves, a lot of research has been devoted to finding the most efficient Tate-pairing variants for different security levels by constructing suitable pairingfriendly elliptic curves [20] and by making specific c”