How to solve a 112-bit ECDLP using game consoles

Speaker  Joppe Bos

Host  Peter Montgomery

Affiliation  EPFL

Duration  01:00:14

Date recorded  13 October 2011

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.

©2011 Microsoft Corporation. All rights reserved.
> How to solve a 112-bit ECDLP using game consoles