Abstract
Eker{\aa} and H{\aa}stad have introduced a variation of Shor's algorithm for the discrete logarithm problem (DLP). Unlike Shor's original algorithm, Eker{\aa}-H{\aa}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{\aa}-H{\aa}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⁻¹⁰ 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.