Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Designs Codes and Cryptography

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

Martin Ekerå

Published Aug 6, 2020• 22 citations
Publisher

Abstract

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.

DOI
10.1007/s10623-020-00783-2

Related papers

On the success probability of the quantum algorithm for the short DLP

Martin Ekerå

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.

arXiv:2309.01754•IACR Communications in Cryptology•May 4, 2026•3 citations

Quantum algorithms for computing general discrete logarithms and orders with tradeoffs

Martin Ekerå

Abstract We generalize our earlier works on computing short discrete logarithms with tradeoffs, and bridge them with Seifert's work on computing orders with tradeoffs, and with Shor's groundbreaking works on computing orders and general discrete logarithms. In particular, we enable tradeoffs when computing general discrete logarithms. Compared to Shor's algorithm, this yields a reduction by up to a factor of two in the number of group operations evaluated quantumly in each run, at the expense of having to perform multiple runs. Unlike Shor's algorithm, our algorithm does not require the group order to be known. It simultaneously computes both the order and the logarithm. We analyze the probability distributions induced by our algorithm, and by Shor's and Seifert's order-finding algorithms, describe how these algorithms may be simulated when the solution is known, and estimate the number of runs required for a given minimum success probability when making different tradeoffs.

Journal of Mathematical Cryptology•Jan 1, 2021•3 citations

Revisiting Shor's quantum algorithm for computing general discrete logarithms

Martin Ekerå

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 \rightarrow \infty$, 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.

arXiv:1905.09084•May 22, 2019•9 citations

Quantum algorithms for computing general discrete logarithms and orders with tradeoffs

Martin Ekerå

We generalize our earlier works on computing short discrete logarithms with tradeoffs, and bridge them with Seifert's work on computing orders with tradeoffs, and with Shor's groundbreaking works on computing orders and general discrete logarithms. In particular, we enable tradeoffs when computing general discrete logarithms. Compared to Shor's algorithm, this yields a reduction by up to a factor of two in the number of group operations evaluated quantumly in each run, at the expense of having to perform multiple runs. Unlike Shor's algorithm, our algorithm does not require the group order to be known. It simultaneously computes both the order and the logarithm. We analyze the probability distributions induced by our algorithm, and by Shor's and Seifert's order-finding algorithms, describe how these algorithms may be simulated when the solution is known, and estimate the number of runs required for a given minimum success probability when making different tradeoffs.

•Apr 1, 2021•29 citations

The Present and Future of Discrete Logarithm Problems on Noisy Quantum Computers

Yoshinori Aono, Sitong Liu, Tomoki Tanaka +4 more

The discrete logarithm problem (DLP) is the basis for several cryptographic primitives. Since Shor’s work, it has been known that the DLP can be solved by combining a polynomial-size quantum circuit and a polynomial-time classical post-processing algorithm. The theoretical result corresponds the situation where a quantum device working with a medium number of qubits of very small errors can solve DLP. However, all the quantum devices that we can use have a limited number of noisy qubits, as of the noisy intermediate-scale quantum (NISQ) era. Thus, evaluating the instance size that the latest quantum device can solve, and give a future prediction of the size along the progress of quantum devices are emerging research topics. This paper contains two proposal to discuss the performance of quantum devices against DLP in the NISQ era. (1) A quantitative measure based on the success probability of the post-processing algorithm to determine whether an experiment on a quantum device (or a classical simulator) succeeded. (2) A procedure to modify bit strings observed from a Shor’s circuit to increase the success probability of a lattice-based post-processing algorithm. We conducted our experiments with theibm_kawasakidevice and discovered that the simplest circuit (7 qubits) from a 2-bit DLP instance achieves a sufficiently high success probability to proclaim the experiment successful. Experiments on another circuit from a slightly harder 2-bit DLP instance, on the other hand, did not succeed, and we determined that reducing the noise level by half is required to achieve a successful experiment. Finally, we give a near-term prediction based on required noise levels to solve some selected small DLP and integer factoring instances.

arXiv:2111.06102•IEEE Transactions on Quantum Engineering•Jan 1, 2022•11 citations

Pre-Quantum to Post-Quantum Cryptography Transition

Sayan Das, Arnav Das

Quantum cryptography is a promising field for securing information against quantum computers. Shor's algorithm, a quantum algorithm, can factor large prime numbers in polynomial time and solve the discrete logarithm problem, which is the basis for classical cryptographic algorithms like Rivest-Shamir-Adleman algorithm (RSA), Diffie-Hellman key exchange (DHKE), and Elliptic Curve Diffie-Hellman algorithm(ECDH). These algorithms pose a significant threat to their security and reliability. Post-quantum cryptography techniques are being implemented by all industries to address the threat posed by quantum supremacy. The chapter discusses the potential threat of Shor's algorithm on classical cryptographic algorithms and discusses post-quantum cryptographic algorithms like lattice-based, multivariate, code-based, and Hash-based cryptography. It also discusses recent advancements that have improved the security and usefulness of these algorithms.

Advances in mechatronics and mechanical engineering (AMME) book series•Oct 29, 2024•1 citation
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.
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 generalize our earlier works on computing short discrete logarithms with tradeoffs, and bridge them with Seifert's work on computing orders with tradeoffs, and with Shor's groundbreaking works on computing orders and general discrete logarithms. In particular, we enable tradeoffs when computing general discrete logarithms. Compared to Shor's algorithm, this yields a reduction by up to a factor of two in the number of group operations evaluated quantumly in each run, at the expense of having to perform multiple runs. Unlike Shor's algorithm, our algorithm does not require the group order to be known. It simultaneously computes both the order and the logarithm. We analyze the probability distributions induced by our algorithm, and by Shor's and Seifert's order-finding algorithms, describe how these algorithms may be simulated when the solution is known, and estimate the number of runs required for a given minimum success probability when making different tradeoffs.
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 rrr, 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→∞r \rightarrow \inftyr→∞, 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 ddd and rrr are both known. Furthermore, we heuristically show how slightly better tradeoffs may be achieved, compared to our earlier works, if rrr is known when computing ddd. We generalize our heuristic to cover some of our earlier works, and compare it to the non-heuristic analyses in those works.
We generalize our earlier works on computing short discrete logarithms with tradeoffs, and bridge them with Seifert's work on computing orders with tradeoffs, and with Shor's groundbreaking works on computing orders and general discrete logarithms. In particular, we enable tradeoffs when computing general discrete logarithms. Compared to Shor's algorithm, this yields a reduction by up to a factor of two in the number of group operations evaluated quantumly in each run, at the expense of having to perform multiple runs. Unlike Shor's algorithm, our algorithm does not require the group order to be known. It simultaneously computes both the order and the logarithm. We analyze the probability distributions induced by our algorithm, and by Shor's and Seifert's order-finding algorithms, describe how these algorithms may be simulated when the solution is known, and estimate the number of runs required for a given minimum success probability when making different tradeoffs.
The discrete logarithm problem (DLP) is the basis for several cryptographic primitives. Since Shor’s work, it has been known that the DLP can be solved by combining a polynomial-size quantum circuit and a polynomial-time classical post-processing algorithm. The theoretical result corresponds the situation where a quantum device working with a medium number of qubits of very small errors can solve DLP. However, all the quantum devices that we can use have a limited number of noisy qubits, as of the noisy intermediate-scale quantum (NISQ) era. Thus, evaluating the instance size that the latest quantum device can solve, and give a future prediction of the size along the progress of quantum devices are emerging research topics. This paper contains two proposal to discuss the performance of quantum devices against DLP in the NISQ era. (1) A quantitative measure based on the success probability of the post-processing algorithm to determine whether an experiment on a quantum device (or a classical simulator) succeeded. (2) A procedure to modify bit strings observed from a Shor’s circuit to increase the success probability of a lattice-based post-processing algorithm. We conducted our experiments with theibm_kawasakidevice and discovered that the simplest circuit (7 qubits) from a 2-bit DLP instance achieves a sufficiently high success probability to proclaim the experiment successful. Experiments on another circuit from a slightly harder 2-bit DLP instance, on the other hand, did not succeed, and we determined that reducing the noise level by half is required to achieve a successful experiment. Finally, we give a near-term prediction based on required noise levels to solve some selected small DLP and integer factoring instances.
Quantum cryptography is a promising field for securing information against quantum computers. Shor's algorithm, a quantum algorithm, can factor large prime numbers in polynomial time and solve the discrete logarithm problem, which is the basis for classical cryptographic algorithms like Rivest-Shamir-Adleman algorithm (RSA), Diffie-Hellman key exchange (DHKE), and Elliptic Curve Diffie-Hellman algorithm(ECDH). These algorithms pose a significant threat to their security and reliability. Post-quantum cryptography techniques are being implemented by all industries to address the threat posed by quantum supremacy. The chapter discusses the potential threat of Shor's algorithm on classical cryptographic algorithms and discusses post-quantum cryptographic algorithms like lattice-based, multivariate, code-based, and Hash-based cryptography. It also discusses recent advancements that have improved the security and usefulness of these algorithms.