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.
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.
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 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.
We prove a lower bound on the probability of Shor’s order-finding algorithm successfully recovering the order r in a single run. The bound implies that by performing two limited searches in the classical post-processing part of the algorithm, a high success probability can be guaranteed, for any r , without re-running the quantum part or increasing the exponent length compared to Shor. Asymptotically, in the limit as r tends to infinity, the probability of successfully recovering r in a single run tends to one. Already for moderate r , a high success probability exceeding e.g. 1 - 10 -4 can be guaranteed. As corollaries, we prove analogous results for the probability of completely factoring any integer N in a single run of the order-finding algorithm.
This thesis contains a collection of efficient quantum algorithms and classical pre- and post-processing algorithms for various number- and group-theoretical problems with concrete cryptanalytical applications. More specifically, the focus is on the integer factoring problem (IFP), the discrete logarithm problem (DLP), and the order-finding problem (OFP), and on certain important variations of these problems. It is for example explained how the OFP and complete IFP may be solved efficiently in a single run of a reduced version of Shor's algorithm for the OFP with very high success probability, as evidenced by a lower bound that is 1 − o(1), how the short DLP in groups of unknown order may be solved efficiently and with an advantage over Shor's algorithm for the DLP (that furthermore requires the order to be known), as evidenced by a lower bound on the single-run success probability that is 1 − o(1), how the RSA IFP may be solved efficiently and with an advantage over Shor's algorithm for the IFP, by reducing the RSA IFP to a short DLP, how the DLP may heuristically be solved efficiently, and with high success probability that is 1 − o(1), in a single run of a reduced version of Shor’s algorithm for the DLP that admits efficient implementation, how the DLP may be solved in groups of unknown order, such as Schnorr groups, by jointly solving an OFP and a DLP at lower overall cost but higher per-run cost compared to first solving the OFP and then the DLP, how tradeoffs — between the number of group operations that are evaluated quantumly and the number of runs that are required — may be achieved in all of the aforementioned algorithms, and how all of the aforementioned algorithms may be simulated efficiently classically, for arbitrary large cryptographically relevant problem instances, when the solution to the instance is known, enabling the number of runs required when performing tradeoffs to be tightly estimated. It is furthermore for example explained how Regev's recent quantum algorithm for the IFP may be extended to the DLP and OFP, yielding i) a reduction in the circuit size and depth by a factor compared to Shor for these problems when working in , for N an n-bit integer, at the expense of performing runs, and ii) slight improvements of Regev's orginal algorithm for the IFP, how the above algorithms may be simulated efficiently classically, for large special-form problem instances that are classically tractable, and that Regev’s post-processing, and the post-processing for our extensions, are robust to an arbitrarily large fraction < 1 of the runs being bad. The above has implications for cryptography based on the intractability of the IFP and DLP — including but not limited to for widely used schemes such as RSA, DSA and Diffie–Hellman. The algorithms in this thesis are all derived from, and make notable improvements to, the seminal works of Shor. Some of the contributions are joint works with other authors.
Simulation of Shor Algorithm for Discrete Logarithm Problems With Comprehensive Pairs of Modulo p and Order q
The discrete logarithm problem (DLP) over finite fields, commonly used in classical cryptography, has no known polynomial-time algorithm on classical computers. However, Shor has provided its polynomial-time algorithm on quantum computers. Nevertheless, there are only few examples simulating quantum circuits that operate on general pairs of modulopand orderq. In this paper, we constructed such quantum circuits and solved DLPs for all 1,860 possible pairs ofpandqup to 32 qubits using a quantum simulator with PRIMEHPC FX700. From this, we obtained and verified values of the success probabilities, which had previously been heuristically analyzed by [Ekerå, arXiv:1905.09084 (2019)]. As a result, the detailed waveform shape of the success probability of Shor's algorithm for solving the DLP, known as a periodic function of orderq, was clarified. Additionally, we generated 1,015 quantum circuits for larger pairs ofpandq, extrapolated the circuit sizes obtained, and compared them forp=2048bits between safeprime groups and Schnorr groups. While in classical cryptography, the cipher strength of safe-prime groups and Schnorr groups is the same ifpis equal, we quantitatively demonstrated how much the strength of the latter decreases to the bit length ofpin the former when using Shor's quantum algorithm. In particular, it was experimentally and theoretically shown that when a basic adder is used in the addition circuit, the cryptographic strength of a Schnorr group withp=2048bits under Shor's algorithm is almost equivalent to that of a safe-prime group withp=1024bits.
We heuristically show that Shor's algorithm for computing general discrete logarithms achieves an expected success probability of approximately 60% to 82% in a single run when modified to enable efficient implementation with the semi-classical Fourier transform. By slightly increasing the number of group operations that are evaluated quantumly and performing a single limited search in the classical post-processing, or by performing two limited searches in the post-processing, we show how the algorithm can be further modified to achieve a success probability that heuristically exceeds 99% in a single run. We provide concrete heuristic estimates of the success probability of the modified algorithm, as a function of the group order r, the size of the search space in the classical post-processing, and the additional number of group operations evaluated quantumly. In the limit as r→∞, we heuristically show that the success probability tends to one. In analogy with our earlier works, we show how the modified quantum algorithm may be heuristically simulated classically when the logarithm d and r are both known. Furthermore, we heuristically show how slightly better tradeoffs may be achieved, compared to our earlier works, if r is known when computing d. We generalize our heuristic to cover some of our earlier works, and compare it to the non-heuristic analyses in those works.
Solving the discrete logarithm problem (DLP) with quantum computers is a fundamental task with important implications. Beyond Shor's algorithm, many researchers have proposed alternative solutions in recent years. However, due to current hardware limitations, the scale of DLP instances that can be addressed by quantum computers remains insufficient. To overcome this limitation, we propose a distributed quantum discrete logarithm algorithm that reduces the required quantum register size for solving DLPs. Specifically, we design a distributed quantum algorithm to determine whether the solution is contained in a given set. Based on this procedure, our method solves DLPs by identifying the intersection of sets containing the solution. Compared with Shor's original algorithm, our approach reduces the register size and can improve the success probability, while requiring no quantum communication.