Paper 2017/1122

On post-processing in the quantum algorithm for computing short discrete logarithms

Martin Ekerå

Abstract

We revisit the quantum algorithm for computing short discrete logarithms that was recently introduced by Ekerå and Håstad. By carefully analyzing the probability distribution induced by the algorithm, we show its success probability to be higher than previously reported. Inspired by our improved understanding of the distribution, we propose an improved post-processing algorithm that is practical, enables better tradeoffs to be achieved, and requires fewer runs, than the original post-processing algorithm. To prove these claims, we construct a classical simulator for the quantum algorithm by sampling the probability distribution it induces for given logarithms. This simulator is in itself a key contribution. We use it to demonstrate that our quantum algorithm achieves an advantage over Shor's algorithms, not only in each individual run, but also overall, when targeting cryptographically relevant instances of RSA and Diffie-Hellman with short exponents.

Note: This is a revised version of report 2017/1122 originally submitted to the IACR ePrint archive on the 20th of November 2017. The revised report has been condensed and simplified in preparation for publication. It has furthermore been extended with an appendix illustrating the advantage that may be achieved for RSA, and for FF-DH with short exponents in the safe-prime groups that are now recommended by NIST as of the 3rd revision of NIST SP 800-56A released in April 2018. For ease of comparison, the revised report uses the same method for computing probability distributions as is used in report 2018/797 on making tradeoffs when computing general discrete logarithms.