Paper 2015/605

Computing Elliptic Curve Discrete Logarithms with Improved Baby-step Giant-step Algorithm

Steven D. Galbraith, Ping Wang, and Fangguo Zhang

Abstract

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 in small groups or small intervals. 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. Furthermore, for the discrete logarithm problem in an interval, the interleaved BSGS algorithm is considerably faster than the Pollard kangaroo or Gaudry-Schost methods.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
baby-step giant-stepelliptic curve discrete logarithmnegation map
Contact author(s)
s galbraith @ auckland ac nz
History
2016-02-11: revised
2015-06-28: received
See all versions
Short URL
https://ia.cr/2015/605
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/605,
      author = {Steven D.  Galbraith and Ping Wang and Fangguo Zhang},
      title = {Computing Elliptic Curve Discrete Logarithms with Improved Baby-step Giant-step Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2015/605},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/605}},
      url = {https://eprint.iacr.org/2015/605}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.