International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 28 June 2015

Steven D. Galbraith, Ping Wang, Fangguo Zhang
ePrint Report ePrint Report
The negation map can be used to speed up the computation of elliptic curve discrete logarithms using either the baby-step-giant-step algorithm (BSGS) or Pollard rho. Montgomery\'s simultaneous modular inversion can also be used to speed up Pollard rho when running many walks in parallel. We generalize these ideas and exploit the fact that for any two elliptic curve points $X$ and $Y$, we can efficiently get $X-Y$ when we compute $X+Y$. We apply these ideas to speed up the baby-step-giant-step algorithm. Compared to the previous methods, the new methods can achieve a significant speedup for computing elliptic curve discrete logarithms.

Another contribution of our paper is to give an analysis of the average-case running time of Bernstein and Lange\'s ``grumpy giants and a baby\'\' algorithm, and also to consider this algorithm in the case of groups with efficient inversion.

Our conclusion is that, in the fully-optimised context, both the interleaved BSGS and grumpy-giants algorithms have superior average-case running time compared with Pollard rho.

Expand

Additional news items may be found on the IACR news page.