On the success probability of the quantum algorithm for the short DLP
This work addresses the reliability of quantum algorithms for cryptography, providing concrete guarantees for security applications, though it is incremental as it builds on an existing algorithm.
The paper proves a lower bound on the success probability of the Ekerå-Håstad quantum algorithm for the short discrete logarithm problem, showing it can reach nearly 1 (e.g., 1 - 10^{-10}) for any short logarithm, with applications to Diffie-Hellman and RSA.
Ekerå and Håstad have introduced a variation of Shor's algorithm for the discrete logarithm problem (DLP). Unlike Shor's original algorithm, Ekerå-Håstad's algorithm solves the short DLP in groups of unknown order. In this work, we prove a lower bound on the probability of Ekerå-Håstad's algorithm recovering the short logarithm $d$ in a single run. By our bound, the success probability can easily be pushed as high as $1 - 10^{-10}$ for any short $d$. A key to achieving such a high success probability is to efficiently perform a limited search in the classical post-processing by leveraging meet-in-the-middle or random-walk techniques. These techniques may be generalized to speed up other related classical post-processing algorithms. Asymptotically, in the limit as the bit length $m$ of $d$ tends to infinity, the success probability tends to one if the limits on the search space are parameterized in $m$. Our results are directly applicable to Diffie-Hellman in safe-prime groups with short exponents, and to RSA via a reduction from the RSA integer factoring problem (IFP) to the short DLP.