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

Joppe W. Bos (#772)
Name Joppe W. Bos
Topic of his/her doctorate. On the Cryptanalysis of Public-Key Cryptography
Category public-key cryptography
Keywords cryptanalysis, factoring, discrete logarithm problem
Ph.D. Supervisor(s) Arjen K. Lenstra
Year of completion 2012
Abstract Nowadays, the most popular public-key cryptosystems are based on either the integer factorization or the discrete logarithm problem. The feasibility of solving these mathematical problems in practice are studied and techniques are presented to speed-up the underlying arithmetic on parallel architectures.

The fastest known approach to solve the discrete logarithm problem in groups of elliptic curves over finite fields is the Pollard rho method. The negation map can be used to speed up this calculation by a factor sqrt(2). It is well known that the random walks used by Pollard rho when combined with the negation map get trapped in fruitless cycles. We show that previously published approaches to deal with this problem are plagued by recurring cycles, and we propose effective alternative countermeasures. Furthermore, fast modular arithmetic is introduced which can take advantage of prime moduli of a special form using efficient "sloppy reduction." The effectiveness of these techniques is demonstrated by solving a 112-bit elliptic curve discrete logarithm problem using a cluster of PlayStation 3 game consoles: breaking a public-key standard and setting a new world record.

The elliptic curve method (ECM) for integer factorization is the asymptotically fastest method to find relatively small factors of large integers. From a cryptanalytic point of view the performance of ECM gives information about secure parameter choices of some cryptographic protocols. We optimize ECM by proposing carry-free arithmetic modulo Mersenne numbers (numbers of the form 2^M-1) especially suitable for parallel architectures. Our implementation of these techniques on a cluster of PlayStation 3 game consoles set a new record by finding a 241-bit prime factor of 2^1181-1.

A normal form for elliptic curves introduced by Edwards results in the fastest elliptic curve arithmetic in practice. Techniques to reduce the temporary storage and enhance the performance even further in the setting of ECM are presented. Our results enable one to run ECM efficiently on resource-constrained platforms such as graphics processing units.
Last Change 2012-03-29 07:16:39
To provide an update on this entry, please click .

Contact: phds (at) iacr.org

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