Cryptanalysis of Isogeny-Based Quantum Money with Rational Points

summary

The gist

Cryptanalysis of Isogeny-Based Quantum Money with Rational Points proposes a concrete cryptanalysis by leveraging division polynomials with rational points to forge a quantum banknote in an…

In short

The paper proposes a cryptanalysis to forge quantum money based on isogeny-based schemes by using division polynomials with rational points on elliptic curves. This method offers an O(log4 p) speedup over brute-force attacks for forgery, though the attack remains exponentially time-consuming. It also introduces a faster verification procedure.

Key concepts

Division Polynomials
These are mathematical polynomials associated with elliptic curves that help determine the torsion points of the curve. The paper exploits their properties to efficiently compute values using rational points, which is much faster than counting all possible points on the curve.
Rational Points
These are specific points on an elliptic curve whose coordinates are rational numbers (fractions). The key insight is that using these rational points allows for a more efficient computation of division polynomials, bypassing slower point-counting algorithms.
Isogeny-Based Quantum Money
This is a type of quantum money scheme where the security relies on the difficulty of finding paths between elliptic curves (isogenies) in a graph structure. The paper analyzes how to break this system by exploiting properties related to these curves.

Terminology used across episodes

This episode discusses

The paper

Cryptanalysis of Isogeny-Based Quantum Money with Rational Points · Read on arXiv

Korea University

Quantum money is a representative application in cryptography that utilizes quantum technology to achieve security that is unattainable with classical systems. Since the theoretical proposal by Wiesner in 1983, the most recent instantiation is the quantum money using class group actions on elliptic curves, proposed by Montgomery and Sharif in Asiacrypt'24. In this work, we propose a concrete cryptanalysis by leveraging the efficiency of evaluating division polynomials with the coordinates of rational points, offering a speedup of O(4p) compared to the brute-force attack. While the resulting attack still runs in exponential time, our method provides the first nontrivial algorithmic insight into their structural hardness. Furthermore, due to the algebraic properties of rational points and quadratic twists, our technique naturally yields a more efficient verification procedure for the underlying quantum money. We believe this new line of analysis opens promising directions for future research in elliptic-curve-based quantum cryptography.

Transcript

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

Nadia: I'm Nadia.

Elias: And I'm Elias, here with Priya.

Nadia: We're looking at the paper: "Cryptanalysis of Isogeny-Based Quantum Money with Rational Points".

Elias: Here's the gist of the paper. Cryptanalysis of Isogeny-Based Quantum Money with Rational Points proposes a concrete cryptanalysis by leveraging division polynomials with rational points to forge a quantum banknote in an isogeny-based quantum money scheme, offering a speedup of O(log4 p) compared to the bruteforce attack <ref:2508.00351#pg12>.

Nadia: Since our attack still requires exponential time, it remains impractical to forge a quantum banknote <ref:2508.00351#pg3>.

Elias: Interestingly, due to the inherent properties of quantum money, our attack method also results in a more efficient verification procedure <ref:2508.00351#pg5>.

Nadia: The Forgery Attack Strategy The paper identifies two potential approaches to forge a quantum banknote in the scheme proposed in

11: <ref:2508.00351#pg10>.

Title and authors: Nadia: We're talking about the paper "Cryptanalysis of Isogeny-Based Quantum Money with Rational Points" by Kim, Heo, and Hong. The title itself tells you they are focusing on using rational points for this kind of attack <ref:2508.00351#pg1>.

Elias: They're building on a construction from Montgomery and Zhandry called walkable invariant money in reference ten and then instantiating that in reference eleven using class group actions on elliptic curves <ref:2508.00351#pg2>.

Priya: So, what's the main focus of this paper? Is it just finding a way to break existing systems or something more fundamental about the security structure?

Nadia: It's focused on concrete cryptanalysis, specifically identifying two potential approaches for forging a quantum banknote in that scheme <ref:2508.00351#pg10>. The first one involves using a quantum random walk for something called the Index Erasure Problem <ref:2508.00351#pg10>.

Elias: And the second approach they mention is leveraging quantum search techniques to sample elliptic curves of the right cardinality, which they think is more efficient because it focuses on verifying the order of rational points instead of just counting them <ref:2508.00351#pg10>.

The paper's summary: Nadia: So, to summarize what they're proposing, this paper aims to find a better way to forge those notes by looking at the serial number given <ref:2508.00351#pg10>. They suggest that computing division polynomials with rational points is faster than the standard point-counting algorithm <ref:2508.00351#pg2>.

Elias: That's the key technical mechanism they are exploiting; they use the recurrence relation of division polynomials to compute them in O log l multiplications in Fp, which is significantly faster when p is a large prime <ref:2508.00351#pg4>.

Priya: But this brings up a question about what's really happening under the hood. If computing these polynomials with rational points is faster, does that mean the underlying structure of the quantum money scheme itself has some weakness we haven't seen yet?

Nadia: It suggests they are using properties of quadratic twists of elliptic curves to verify the cardinality, which they think is a powerful way to use those rational points <ref:2508.00351#pg3>.

The paper's improvements: Elias: The improvements they highlight are twofold: first, a new forgery attack that beats direct brute-force by O log four p times <ref:2508.00351#pg1>, and second, an improved verification process <ref:2508.00351#pg3>.

Nadia: And the verification part is where they really shine; they demonstrate that checking a serial number can become O log four p times faster than the original approach <ref:2508.00351#pg3>.

Priya: So, if we look at what this means for someone who only cares about verifying authenticity, how big of a deal is an O log four p speedup? Is it enough to make the system more robust?

Elias: It's significant because they derive that verification algorithm directly from Algorithm seven which uses Algorithm six to compute division polynomials and Euler's criteria <ref:2508.00351#pg3>.

Conclusion: Nadia: So, wrapping things up on the "Cryptanalysis of Isogeny-Based Quantum Money with Rational Points," they propose an attack method that is faster than brute force but still exponential in time <ref:2508.00351#pg3>.

Elias: The big picture is that they leverage the fact that checking the exponent of an elliptic curve group with rational points is more efficient than just directly computing its cardinality <ref:2508.00351#pg6>.

Priya: From a measurement perspective, it’s interesting because they show how to use these properties of quadratic twists to verify the cardinality <ref:2508.00351#pg3>, which is a more concrete check than just relying on counting points <ref:2508.00351#pg6>.

Nadia: Yeah, that verification efficiency is what they found interesting, showing how the inherent properties of quantum money can be used to make the checking process faster <ref:2508.00351#pg1>.

Elias: So we've seen how they use rational points for forging and verification in this work, which we expect will inspire future research on quantum algorithms for elliptic curve-based cryptography <ref:2508.00351#pg1>.

More episodes

← Home