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^{-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 techniques. 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.

翻译：Ekerå 和 Håstad 提出了一种针对离散对数问题（DLP）的 Shor 算法变体。与 Shor 原始算法不同，Ekerå-Håstad 算法能够在阶未知的群中求解短离散对数问题。本文中，我们证明了 Ekerå-Håstad 算法在单次运行中恢复短对数 $d$ 的概率下界。根据我们的界，对于任意短 $d$，成功概率可轻松提升至 $1 - 10^{-10}$。实现如此高成功概率的关键在于，通过利用中间相遇技术，在经典后处理中高效执行有限搜索。渐近地，当 $d$ 的比特长度 $m$ 趋于无穷时，若搜索空间限制以 $m$ 为参数化，则成功概率趋于 1。我们的结果可直接应用于具有短指数的安全素数群中的 Diffie-Hellman 协议，并通过从 RSA 整数分解问题（IFP）到短 DLP 的归约应用于 RSA 密码体系。