How to solve a 112-bit ECDLP using game consoles

In this presentation I will outline two projects which I have been working on during my PhD.
Both projects are related to the elliptic curve discrete logarithm problem (ECDLP): the theoretical foundation of many modern cryptosystems.
First I will outline how we have set a new record by solving the ECDLP over a 112-bit prime field using a cluster of PlayStation 3 game consoles in 2009.
Next, the negation map optimization is discussed: this is an technique to speed up the Pollard rho method when solving the ECDLP. It is well known that the random walks used by Pollard rho when combined with the negation map get trapped in fruitless cycles. I will present that previously published approaches to deal with this problem are plagued by recurring cycles: effective alternative countermeasures are proposed.

Speaker Details

Joppe Bos is a PhD student under supervision of Prof. Arjen Lenstra at the laboratory for cryptologic algorithms, EPFL, Switzerland. His research interest include public-key cryptanalysis, fast arithmetic and efficient implementations of cryptologic algorithms with a focus on elliptic curve cryptography and integer factorization algorithms. Currently he is doing an internship with Peter Montgomery at MSR and works on factoring large integers using graphics cards.

Date:
Speakers:
Joppe Bos
Affiliation:
EPFL
    • Portrait of Joppe Bos

      Joppe Bos

    • Portrait of Jeff Running

      Jeff Running