Finalist EPFL doctorate Award 2013 - Joppe Willem Bos

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. 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 countermeasures. We have solved a 112-bit elliptic curve discrete logarithm problem using a cluster of PlayStation 3 (PS3) 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 small factors of large integers. From a cryptanalytic point of view 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). Our implementation on a PS3-cluster set a new record by finding a 241-bit prime factor of 2^1181-1.