A Probabilistic Baby-Step Giant-Step Algorithm
This work addresses cryptographic security for users relying on NIST curves, but it is incremental as it builds on an existing algorithm.
The authors tackled the discrete logarithm problem by introducing a probabilistic variant of the baby-step giant-step algorithm, which identified vulnerabilities in NIST curves over prime fields, showing they are not as secure as previously thought.
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.