Abstract
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.
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 Dive into the research topics of 'Constructive and computational aspects of cryptographic pairings'. Together they form a unique fingerprint.
Cite this
Naehrig, M. (2009). Constructive and computational aspects of cryptographic pairings. Eindhoven: Technische Universiteit Eindhoven. https://doi.org/10.6100/IR642221