On post-processing in the quantum algorithm for computing short discrete logarithms
- PDF / 475,759 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 44 Downloads / 188 Views
On post-processing in the quantum algorithm for computing short discrete logarithms Martin Ekerå1,2 Received: 31 March 2020 / Revised: 24 June 2020 / Accepted: 29 June 2020 © The Author(s) 2020
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 postprocessing algorithm that is considerably more efficient, 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 Ekerå–Håstad achieves an advantage over Shor, not only in each individual run, but also overall, when targeting cryptographically relevant instances of RSA and Diffie–Hellman with short exponents. Keywords Discrete logarithms · Factoring · RSA · Shor’s algorithms Mathematics Subject Classification 68Q12 · 81P68 · 94A60
1 Introduction As in [4,5], let G under be a group of order r generated by g, and let x = [d] g = g g · · · g . d times
Given g and x the discrete logarithm problem (DLP) is to compute d = logg x. In the general DLP 0 ≤ d < r , whereas d is smaller than r by some order of magnitude in the
Communicated by D. Stebila.
B
Martin Ekerå [email protected]
1
KTH Royal Institute of Technology, 100 44 Stockholm, Sweden
2
Swedish NCSA, Swedish Armed Forces, 107 85 Stockholm, Sweden
123
M. Ekerå
short DLP. The order r may be assumed to be known or unknown. Both cases are cryptographically relevant.
1.1 Earlier works In 2016 Ekerå [4] introduced a modified version of Shor’s algorithm [16,17] for computing discrete logarithms that is more efficient than Shor’s original algorithm when the logarithm is short. This work was originally motivated by the use of short discrete logarithms in instantiations of cryptographic schemes based on the computational intractability of the DLP in finite fields. A concrete example is the use of short exponents in the Diffie–Hellman key exchange protocol when instantiated with safe-prime groups. This work was subsequently generalized by Ekerå and Håstad [5] so as to enable tradeoffs between the number of times that the algorithm needs to be executed, and the requirements it imposes on the quantum computer. These ideas parallel earlier ideas by Seifert [15] for making tradeoffs in Shor’s order finding algorithm; the quantum part of Shor’s general factoring algorithm. Ekerå and Håstad furthermore explained how the RSA integer factoring problem may be expressed as a short DLP. This gives rise to a new algorithm for factoring RSA integers that does not rely directly on order-finding, and that imposes less requiremen
Data Loading...
