Constructing abelian varieties for pairing-based cryptography

Abelian varieties that have small embedding degree with respect to a large prime-order subgroup are key ingredients for implementing pairing-based cryptographic systems. Such "pairing-friendly" abelian varieties are rare and thus require specific constructions.;We begin by giving a single coherent framework that classifies the known constructions of pairing-friendly ordinary elliptic curves. This abstract framework leads us to discover several new constructions of such curves. Our most important contribution in this regard is the construction of elliptic curves of prime order with embedding degree 10, which solves an open problem posed by Boneh, Lynn, and Shacham. We also describe a procedure for generating families of pairing-friendly elliptic curves with variable CM discriminant, which can be used to increase the degree of randomness in cryptosystem parameters.;We then consider higher-dimensional abelian varieties. We provide two algorithms that, given a CM field K, construct Frobenius elements pi of pairing-friendly ordinary abelian varieties with complex multiplication by K. Both algorithms generalize existing constructions of pairing-friendly ordinary elliptic curves. The first generalizes the method of Cocks and Pinch, while the second generalizes that of Brezing and Weng and leads to varieties over smaller fields than the first. Given the output pi of either algorithm, one can then use complex multiplication methods to construct explicitly an abelian variety with Frobenius element pi.;Finally, we turn to the question of the complex multiplication methods used to construct explicit examples of pairing-friendly abelian varieties. We focus on the Chinese remainder theorem algorithm of Eisentrager and Lauter for computing Igusa class polynomials of quartic CM fields. One of the steps of this algorithm requires determining whether endomorphism rings of Jacobians of genus 2 curves over small prime fields are isomorphic to the ring of integers in a given quartic CM field. We provide an efficient probabilistic algorithm that carries out this computation. Using our algorithm to determine endomorphism rings, we have implemented a probabilistic version of the full Eisentrager-Lauter algorithm in MAGMA and used it to compute Igusa class polynomials for several quartic CM fields K.