Constructive and computational aspects of cryptographic pairings

M. Naehrig

Research output: ThesisPhd Thesis 1 (Research TU/e / Graduation TU/e)Academic

Abstract

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.
LanguageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • TUE : Department of Mathematics and Computer Science
Supervisors/Advisors
  • Lange, Tanja, Promotor
Award date7 May 2009
Place of PublicationEindhoven
Publisher
Print ISBNs978-90-386-1731-2
DOIs
StatePublished - 2009

Fingerprint

Pairing
Curve
Discrete Logarithm Problem
Elliptic Curves
Galois field
Complex multiplication
Twist
Jacobian Varieties
Order of a group
Degree Condition
P-rank
Public-key Cryptosystem
Hyperelliptic Curves
Rational Points
Cryptosystem
Doubling
Efficient Implementation
Cryptography
Explicit Formula
Open Problems

Cite this

Naehrig, M. (2009). Constructive and computational aspects of cryptographic pairings Eindhoven: Technische Universiteit Eindhoven DOI: 10.6100/IR642221
Naehrig, M.. / Constructive and computational aspects of cryptographic pairings. Eindhoven : Technische Universiteit Eindhoven, 2009. 141 p.
@phdthesis{f51a8285f209490f94cec1b6f35dcbb9,
title = "Constructive and computational aspects of cryptographic pairings",
abstract = "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{\ss} curves.",
author = "M. Naehrig",
year = "2009",
doi = "10.6100/IR642221",
language = "English",
isbn = "978-90-386-1731-2",
publisher = "Technische Universiteit Eindhoven",
school = "TUE : Department of Mathematics and Computer Science",

}

Naehrig, M 2009, 'Constructive and computational aspects of cryptographic pairings', Doctor of Philosophy, TUE : Department of Mathematics and Computer Science, Eindhoven. DOI: 10.6100/IR642221

Constructive and computational aspects of cryptographic pairings. / Naehrig, M.

Eindhoven : Technische Universiteit Eindhoven, 2009. 141 p.

Research output: ThesisPhd Thesis 1 (Research TU/e / Graduation TU/e)Academic

TY - THES

T1 - Constructive and computational aspects of cryptographic pairings

AU - Naehrig,M.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

U2 - 10.6100/IR642221

DO - 10.6100/IR642221

M3 - Phd Thesis 1 (Research TU/e / Graduation TU/e)

SN - 978-90-386-1731-2

PB - Technische Universiteit Eindhoven

CY - Eindhoven

ER -

Naehrig M. Constructive and computational aspects of cryptographic pairings. Eindhoven: Technische Universiteit Eindhoven, 2009. 141 p. Available from, DOI: 10.6100/IR642221