Constructive and computational aspects of cryptographic pairings

The security of many public-key cryptosystems relies on the existence of groups in which the discrete logarithm problem (DLP) is infeasible. Subgroups of the Jacobian varieties of elliptic and hyperelliptic curves over finite fields are widely used to realize such cryptosystems. On these groups, it is possible to define pairings. A cryptographic pairing is a bilinear, non-degenerate map that can be computed efficiently. It maps a pair of points in the Jacobian variety into the multiplicative group of a finite field. Pairings were first used in cryptography to attack the DLP on a supersingular elliptic curve by reducing it to the DLP in a finite field that is easier to solve. Later on, they led to a variety of constructive applications. When aiming at practical implementation of pairings, there are two main problems arising: The first is to find pairing-friendly curves which allow an efficient pairing computation. The second is to make computations more efficient and suitable for different applications. This dissertation addresses aspects of both problems and advances the state of the art in the associated research areas. An important condition for a pairing-friendly curve is to have an embedding degree that is small enough. Curves with this property are rare and need to be constructed. We give a method to construct pairing-friendly elliptic curves with embedding degree 12. The proposed curves have many nice properties favoring very efficient implementation, such as a prime order group of rational points over the ground field and a twist of degree 6. The Jacobian group order of a pairing-friendly curve must have a large prime divisor which satisfies the embedding degree condition. It is therefore necessary to first fix the group order and then construct the curve. As an essential tool for the construction, one uses the complex multiplication (CM) method. We show how to use the CM method to construct curves of genus 2 with p-rank 1. If pairings need to be implemented on devices with restricted memory, it may be interesting to compute pairings in compressed form. Using the fact that pairing values are elements of algebraic tori, they can be represented in a more efficient way, requiring less storage space than general field elements. We show how to do pairing computation in a compressed form. On curves with a twist of degree 6 the proposed variant of Miller’s algorithm can be done without any field inversions. Recently, it has been shown, that in many cases the elliptic curve group law can be implemented most efficiently using Edwards curves. It was an open problem to find advantageous formulas for pairing computation on Edwards curves. We state a geometric interpretation of the group law on twisted Edwards curves, give the corresponding functions, and show how to use them to compute pairings on Edwards curves. We present explicit formulas for the doubling and addition steps in Miller’s algorithm that are more efficient than all previously proposed formulas for pairings on Edwards curves and are competitive with formulas for pairing computation on Weierstraß curves.