Paper 2017/055

A Probabilistic Baby-Step Giant-Step Algorithm

Prabhat Kushwaha and Ayan Mahalanobis

Abstract

In this paper, a new algorithm to solve the discrete logarithm problem is presented which is similar to the usual baby-step giant-step algorithm. Our algorithm exploits the order of the discrete logarithm in the multiplicative group of a finite field. Using randomization with parallelized collision search, our algorithm indicates some weakness in NIST curves over prime fields which are considered to be the most conservative and safest curves among all NIST curves.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Discrete logarithm problembaby-step giant-step algorithmNIST curves over prime fieldsparallelized collision search.
Contact author(s)
prabkush @ gmail com
prabhatkk @ students iiserpune ac in
History
2017-01-31: received
Short URL
https://ia.cr/2017/055
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/055,
      author = {Prabhat Kushwaha and Ayan Mahalanobis},
      title = {A Probabilistic Baby-Step Giant-Step Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2017/055},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/055}},
      url = {https://eprint.iacr.org/2017/055}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.