A Probabilistic Baby-Step Giant-Step Algorithm

Prabhat Kushwaha; Ayan Mahalanobis

Paper 2017/055 Original: eprint.iacr.org/2017/055 ↗

A Probabilistic Baby-Step Giant-Step Algorithm

Prabhat Kushwaha

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.
History: 2017-01-31: last updated; 2017-01-31: published
Short URL: https://ia.cr/2017/055
License: https://creativecommons.org/licenses/by/4.0/

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},
      url = {https://eprint.iacr.org/2017/055}
}