International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: ECC2K-130 on Cell CPUs

Joppe W. Bos
Thorsten Kleinjung
Ruben Niederhagen
Peter Schwabe
Search ePrint
Search Google
Abstract: This paper describes an implementation of Pollard's rho algorithm to compute the elliptic curve discrete logarithm for the Synergistic Processor Elements of the Cell Broadband Engine Architecture. Our implementation targets the elliptic curve discrete logarithm problem defined in the Certicom ECC2K-130 challenge. We compare a bitsliced implementation to a non-bitsliced implementation and describe several optimization techniques for both approaches. In particular, we address the question whether normal-basis or polynomial-basis representation of field elements leads to better performance. Using our software, the ECC2K-130 challenge can be solved in one year using the Synergistic Processor Units of less than 2700 Sony Playstation~3 gaming consoles.
  title={ECC2K-130 on Cell CPUs},
  booktitle={IACR Eprint archive},
  keywords={implementation / Cell Broadband Engine Architecture, elliptic curve discrete logarithm problem, binary-field arithmetic, parallel Pollard rho},
  note={ 14652 received 11 Feb 2010},
  author={Joppe W. Bos and Thorsten Kleinjung and Ruben Niederhagen and Peter Schwabe},