Revisiting Shor's quantum algorithm for computing general discrete logarithms

arXiv:1905.09084 · cs.CR, quant-ph · Submitted 2019-05-22 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: We're looking at the paper: "Revisiting Shor's quantum algorithm for computing general discrete logarithms".

Paper summary: Nadia: So this paper, "Revisiting Shor's quantum algorithm for computing general discrete logarithms," it’s looking at how we can actually make this quantum approach work better than just the original version.

Elias: Exactly. The main thing they show is that if you tweak the algorithm slightly—by doing a few more group operations and adding one or two limited searches in the classical part—you can boost that success probability to over ninety-nine percent in a single run, provided you use the semi-classical Fourier transform efficiently.

Priya: But before we get to those high numbers, we need to understand what they're actually claiming about this modification and how it impacts the actual data we get out of the process.

Nadia: Right. They provide these heuristic estimates for that success probability based on things like the group order r and how large you make your classical search space, and they also show that as r gets really big, say approaching infinity, that success probability goes all the way to one.

Elias: And they’re comparing this modified approach to other ways of making tradeoffs—like comparing the number of runs against how many group operations you evaluate quantumly in each run—especially when the group order r is already known.

Priya: So, what does that comparison actually mean for someone who isn't a cryptographer looking at proofs? Does it just make the attack faster or more reliable?

Nadia: It suggests they can find better tradeoffs between how many times you run the algorithm and how much quantum work you put into each run, which is useful when you don't know the group order r beforehand.

Elias: They also look at classical simulation because if both the logarithm d and the order r are known, this modified version might be simulated classically with slightly better performance than earlier methods.

Priya: That’s interesting because it hints that even with these tweaks, we might still need some classical post-processing depending on whether we're making those tradeoffs or not.

Nadia: If you aren't making those tradeoffs, the original post-processing still works by checking if a certain offset is close to zero when you use a specific angle η equal to zero.

Elias: But if you are doing those tradeoffs, they adapt lattice-based post-processing algorithms from earlier work to recover d given r from a set of pairs.

Priya: It sounds like the reliance on that classical post-processing is still a key part of the whole process, even with these quantum improvements.

Nadia: So, what we're hearing here is that while they can get very high success probabilities heuristically—up to ninety-nine percent in some setups—they’re showing us the math behind how those numbers scale with the group order r.

Elias: And they’ve got these supporting lemmas in appendix C proving things like that a specific function equals one, and that the probability tends toward one when r goes to infinity, which is important for the theory.

Priya: I'm wondering about those limitations they state—what the authors flag as not working or what their method stops doing.

Nadia: They mention that they generalize this heuristic to cover algorithms for computing short discrete logarithms in groups where the order r is unknown, and they do show numerical verification that their heuristic expression actually yields results close to exact probabilities for specific parameters.

Elias: And numerically, increasing a parameter called B eta brings the result from the heuristic closer to what they think the exact probability is.

Priya: So it seems like they've done a lot of groundwork on making this approach more robust and providing concrete bounds, even if the core idea still relies on these specific heuristic steps.

Nadia: They are comparing their proposed approach to a related method proposed by Kaliski, which gives them a way to see how their tradeoffs compare.

Elias: The implication is that these results could help us develop estimates for the overall complexity of attacking schemes that rely on the difficulty of the discrete logarithm problem, and it lets us fairly compare different quantum algorithms for computing discrete logarithms.

Priya: So, we’re looking at how these modifications allow us to get tighter bounds on our success probability and understand the scaling as we look at larger group orders.

Nadia: That brings us to the conclusion of this paper, "Revisiting Shor's quantum algorithm for computing general discrete logarithms." The authors show that by modifying Shor's algorithm with a semi-classical Fourier transform and control qubit recycling, they get an expected success probability between sixty percent and eighty-two percent in a single run.

Elias: But if you add more group operations and perform one or two limited searches in the classical post-processing, they show that this probability can heuristically exceed ninety-nine percent in a single run.

Priya: It’s important to remember that these are heuristic estimates, and while they verify well with small instances, the analysis is also generalized to cover algorithms for computing short discrete logarithms in groups of unknown order.

Nadia: So what does this mean for us right now? It means we have a clearer picture of how these modifications affect the success rate as the group size grows, and it gives us tools to compare different attacks on the discrete logarithm problem.

Conclusion: Nadia: So we’re wrapping up our look at "Revisiting Shor's quantum algorithm for computing general discrete logarithms."

Elias: Yeah, it’s about taking that original Shor’s method and seeing how you can actually make it work better than just the basic version.

Nadia: The authors, they’re looking at how to boost the success probability by making small tweaks to the setup.

Elias: They show that by slightly increasing a few group operations and adding limited searches in the classical part, you can push that success chance past ninety-nine percent in one go.

Nadia: That high number is what’s really interesting, but we have to keep an eye on those conditions they set for it to happen.

Elias: Exactly. They give you these heuristic estimates based on the group order and how much extra quantum work you do, and they show that as the order gets huge, that success probability heads right toward one hundred percent.

Nadia: So for someone who just listens to this, it means they’re trying to find a way to make this attack much more reliable when you're dealing with really big math problems.

Elias: It changes how we think about the practical side of these quantum algorithms, showing that small adjustments can make a real difference in the chance of success.

Nadia: They also show that they can simulate parts of this process classically if you already know both the logarithm and the group order, which is a nice detail for understanding complexity.

Elias: And they’re laying out exactly how you handle those classical steps, whether you’re doing it without any extra tradeoffs or when you are.

Nadia: It really boils down to seeing how these small changes affect the overall attack strategy when you're trying to break a discrete logarithm problem in the real world.

Elias: And that leads us into what happens if we try those modifications on different kinds of groups, which is what we’ll be looking at next.

Martin Eker, KTH Royal Institute of Technology, Swedish National Cyber Security Agency, Swedish Armed Forces

KTH Royal Institute of Technology · Swedish National Cyber Security Agency · Swedish Armed Forces

cs.CR, quant-ph

Submitted: 2019-05-22

Updated: 2026-11-16

Comments: Added an exact analysis of the probability distribution induced by the quantum algorithm, and used it to rigorously prove the lower bound on the success probability (which was previously heuristically derived). Also generalized the exact analysis, and added a novel exact simulator and other material; see the updated abstract and the paper for further details

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 79/100

The gist: 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…

Key concepts

Semi-classical Fourier Transform
This is a technique used in the modified Shor's algorithm to enable efficient implementation. It bridges the gap between purely quantum operations and classical computation by using mathematical tools derived from classical Fourier analysis, making the algorithm more practical for real-world use.
Classical Post-Processing
This refers to the steps taken after the quantum part of Shor's algorithm runs. The paper explores different ways to perform these steps, such as a simple search or more complex lattice-based algorithms, depending on whether tradeoffs are made for better performance.
Bη-B∆-good pairs
These are specific pairs of values (j, k) that the algorithm looks for. The probability of observing such a pair is analyzed by summing over various angles (eta), which helps in deriving closed-form expressions to approximate the overall success probability.
Group Order r
The group order 'r' is a crucial parameter in the algorithm, representing the size of the mathematical group being analyzed. The analysis shows how success probability changes as this order grows, indicating that for very large orders, the algorithm approaches certainty.

Terminology

Summary

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 classical post-processing, we show how the algorithm can be further modified to achieve a success probability that heuristically exceeds 99% in a single run

Algorithm Modification and Success Probability Estimates

The paper analyzes Shor’s algorithm for computing discrete logarithms when modified to enable efficient implementation with the semi-classical Fourier transform. The authors heuristically demonstrate that the modified algorithm achieves a success probability exceeding 99% in a single run if the number of group operations is slightly increased and a limited search is performed in the classical post-processing, or if two limited searches are performed. p. 0 They provide concrete heuristic estimates of this success probability as a function of the group order r, the size of the search space in the classical postprocessing, and additional quantum operations. p. 0 In the limit as r → ∞, they heuristically show that the success probability tends to one. p. 0

Classical Simulation and Tradeoffs

The modified quantum algorithm may be heuristically simulated classically when both the logarithm d and order r are known. They also show that slightly better tradeoffs may be achieved compared to earlier works if r is known when computing d. p. 0 This comparison is made with a related approach proposed by Kaliski. p. 1

Analysis of Probability Distribution

The probability distribution induced by the quantum algorithm is analyzed through arguments and angles, leading to the definition of Bη-B∆-good pairs (j, k). The probability of observing such a pair is given by a heuristic expression derived from summing over all angles η. p. 9 The authors derive closed-form expressions for the functions fη(θr) and h(ϕη) which are used to approximate the probability P(θd, θr). p. 9

Classical Post-Processing Methods

The classical post-processing can be performed in several ways depending on whether tradeoffs are made.

  1. When not making tradeoffs (s = 1), Shor’s original post-processing recovers d given r from any pair (j, k) for which the offset ∆ = 2l(k - kη,0) is close to zero when η = 0. p. 2

  2. For tradeoffs s ≥ 1, they adapt lattice-based post-processing algorithms from earlier works to recover d given r from a set of n pairs. p. 6

Conclusion and Verification

The paper concludes that Shor’s original algorithm, modified with semi-classical QFT and control qubit recycling, achieves an expected success probability of approximately 60% to 82%. They also verify this heuristic by comparing it to exact probabilities for small instances. p. 5 The analysis is generalized to cover algorithms for computing short discrete logarithms in groups of unknown order. p. 6

Appendix A Summary

Appendix A contains tabulated lower bounds and expectation values derived from the heuristic. Table 1 shows the probability for Bη = 0, while Table 2 shows it for Bη = 0 and a random choice of r. p. 3 Appendix A.2 provides heuristically derived expected probabilities in Tables 3–4. p. 0 The numerical verification confirms that the heuristic expression (11) yields results close to exact probabilities for specific parameters. p. 6

Appendix C Summary

Appendix C contains proofs of supporting lemmas and claims. Lemma C.1 shows that the function h(2π/2l (∆ - δ)) equals 1. p. 8 Lemma C.2 provides a lower bound for the probability of observing a Bη-B∆-good pair. p. 6 p. 6 Lemma C.3 proves that the limit of the heuristic expression tends to one as Bη and/or ς tend to infinity. p. 0 p. 0 Lemma C.5 bounds the probability of observing a given z' in a single run. The proof for Lemma C. p. 33 shows that the probability tends to one when r → ∞. p. 3

Appendix B Summary

Appendix B provides numerical verification of the heuristic. Section B.1 details the generalization of the heuristic to cover algorithms for computing short discrete logarithms in groups of unknown order. p. 5 The numerical examples verify that increasing ς stabilizes the heuristic. p. 0

Appendix A.2 Summary

Appendix A.2 presents heuristically derived expected probabilities in Tables 3–4. p. 0 Table 3 shows the probability for s = 1, while Table 4 shows it for Bη = 0 and a random choice of r. p. 3

Appendix A.2.1 Summary

Appendix A.2.1 presents a supplementary table for a random choice of r. p. 1 Table 5 shows the probability for a random order r. p. 3

Appendix B Numerical Verification Summary

Numerical verification confirms that the heuristic expression (11) yields results close to exact probabilities for small instances. The comparison shows that increasing Bη brings the probability yielded by the heuristic closer to the exact probability. p. 6

Appendix C Supporting Lemmas Summary

Appendix C contains proofs of supporting lemmas and claims. Lemma C.1 proves that h(2π/2l (∆ - δ)) equals 1. p. 8 Lemma C.2 provides a lower bound for the probability of observing a Bη-B∆-good pair. Lemma C.3 proves that the limit of the heuristic expression tends to one as Bη and/or ς tend to infinity.

Appendix A Tabulated Bounds Summary

Table 1 shows the probability for Bη = 0, while Table 2 shows it for Bη = 0 and a random choice of r. These tables are created by evaluating the bound using Mathematica and rounding down. p. 1

Appendix A.2 Expected Probabilities Summary

Table 3 shows the probability for s = 1, while Table 4 shows it for Bη = 0 and a random choice of r. These tables are created by evaluating (21) using Mathematica and rounding to the closest decimal. p. 1

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved Success Probability Estimation: The AI system can now provide concrete heuristic estimates of success probability as a function of group order r, search space size in classical postprocessing, and additional quantum operations evaluated quantumly.

  2. Enhanced Tradeoff Analysis: The system can heuristically show how slightly better tradeoffs may be achieved between the number of runs and the number of group operations evaluated quantumly when the group order is known.

  3. Classical Simulation Capability: The AI system can heuristically simulate the modified quantum algorithm classically when both d and r are known, enabling verification of classical postprocessing success probability.

  4. Targeted Postprocessing Recovery: The system can recover d given r from Beta-BDelta-good pairs (j, k) by performing limited searches over t and eta, with complexity feasible for small to moderate tradeoff factors s.

  5. Lattice-Based Solving: The system can use a lattice-based postprocessing algorithm to solve for d given r from n independent runs of the quantum algorithm, reducing the required number of group operations per run compared to previous methods.

  6. Asymptotic Performance Guarantee: In the limit as r approaches infinity, the system heuristically shows that success probability tends to one when using Pohlig-Hellman decomposition and searching within bounded parameters Beta and BDelta.

Sources

Related papers