Revisiting Shor's quantum algorithm for computing general discrete logarithms

summary

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…

In short

The paper modifies Shor's algorithm for discrete logarithms using a semi-classical Fourier transform to improve efficiency. While the original modification yields 60% to 82% success probability, further modifications—such as increasing quantum operations or adding limited classical searches—heuristically push the single-run success probability above 99%.

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 used across episodes

This episode discusses

The paper

Revisiting Shor's quantum algorithm for computing general discrete logarithms · Read on arXiv

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

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.

More episodes

← Home