International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at) iacr.org.

Details

David Mandell Freeman (#232)
Name David Mandell Freeman
Personal Homepage http://cs.stanford.edu/~dfreeman
Topic of his/her doctorate. Constructing abelian varieties for pairing-based cryptography
Category public-key cryptography
Keywords elliptic curves, hyperelliptic curves, pairings, complex multiplication
Ph.D. Supervisor(s) Kenneth Ribet, Edward Schaefer
Year of completion 2008
Abstract

Abelian varieties that have small embedding degree with respect to a large prime-order subgroup are key ingredients for implementing pairing-based cryptographic systems. Such "pairing-friendly" abelian varieties are rare and thus require specific constructions.

We begin by giving a single coherent framework that classifies the known constructions of pairing-friendly ordinary elliptic curves. This abstract framework leads us to discover several new constructions of such curves. Our most important contribution in this regard is the construction of elliptic curves of prime order with embedding degree 10, which solves an open problem posed by Boneh, Lynn, and Shacham. We also describe a procedure for generating families of pairing-friendly elliptic curves with variable CM discriminant, which can be used to increase the degree of randomness in cryptosystem parameters.

We then consider higher-dimensional abelian varieties. We provide two algorithms that, given a CM field K, construct Frobenius elements of pairing-friendly ordinary abelian varieties with complex multiplication by K. Both algorithms generalize existing constructions of pairing-friendly ordinary elliptic curves. The first generalizes the method of Cocks and Pinch, while the second generalizes that of Brezing and Weng and leads to varieties over smaller fields than the first. Given the output of either algorithm, one can then use complex multiplication methods to construct explicitly an abelian variety with that Frobenius element.

Finally, we turn to the question of the complex multiplication methods used to construct explicit examples of pairing-friendly abelian varieties. We focus on the Chinese remainder theorem algorithm of Eisentraeger and Lauter for computing Igusa class polynomials of quartic CM fields. One of the steps of this algorithm requires determining whether endomorphism rings of Jacobians of genus 2 curves over small prime fields are isomorphic to the ring of integers in a given quartic CM field. We provide an efficient probabilistic algorithm that carries out this computation. Using our algorithm to determine endomorphism rings, we have implemented a probabilistic version of the full Eisentraeger-Lauter algorithm in MAGMA and used it to compute Igusa class polynomials for several quartic CM fields K.

E-Mail Address dfreeman (at) cs.stanford.edu
Last Change 2011-02-16 01:21:37
To provide an update on this entry, please click .

Contact: phds (at) iacr.org

[ IACR home page ] [ IACR PhDs page ] © IACR