Abstract
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  7 May 2009 
Place of Publication  Eindhoven 
Publisher  
Print ISBNs  9789038617312 
DOIs  
Publication status  Published  2009 
Fingerprint
Cite this
}
Constructive and computational aspects of cryptographic pairings. / Naehrig, M.
Eindhoven : Technische Universiteit Eindhoven, 2009. 141 p.Research output: Thesis › Phd Thesis 1 (Research TU/e / Graduation TU/e)
TY  THES
T1  Constructive and computational aspects of cryptographic pairings
AU  Naehrig, M.
PY  2009
Y1  2009
N2  The security of many publickey 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, nondegenerate 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 pairingfriendly 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 pairingfriendly 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 pairingfriendly 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 pairingfriendly 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 prank 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.
AB  The security of many publickey 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, nondegenerate 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 pairingfriendly 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 pairingfriendly 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 pairingfriendly 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 pairingfriendly 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 prank 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.
U2  10.6100/IR642221
DO  10.6100/IR642221
M3  Phd Thesis 1 (Research TU/e / Graduation TU/e)
SN  9789038617312
PB  Technische Universiteit Eindhoven
CY  Eindhoven
ER 