Construction and applications of elliptic curves with small embedding degree

Pairing-based cryptography relies on a bilinear map, called a pairing, defined from groups of elliptic curves over finite fields to the multiplicative group of a finite field extension. To ensure that such pairings are both efficient and secure, the embedding degree, which determines the degree of the extension, must be chosen with care. The main emphasis of this work is the theory of complex multiplication, which provides a way to construct elliptic curves over finite fields with a prescribed number of rational points. We also explain how pairings are defined and how they can be applied in the design of cryptographic schemes. We present algorithms based on the complex multiplication method that construct elliptic curves suitable for pairing-based cryptography. 1