Cryptanalysis of Isogeny-Based Quantum Money with Rational Points
Listen
Radio episode about this paper
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>.
Korea University
cs.CR, quant-ph
Submitted: 2025-08-01
Updated: 2026-11-05
Comments: 25 pages; accepted for publication in Quantum. Revised proofs and resource estimates
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 65/100
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…
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
Summary
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. p. 0 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(log
4
p) compared to the bruteforce attack. Since our attack still requires exponential time, it remains
impractical to forge a quantum banknote. 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(log
4
p) compared to the bruteforce attack. Since our attack still requires exponential time, it remains
impractical to forge a quantum banknote. Since our attack still requires exponential time, it remains
impractical to forge a quantum banknote. Interestingly, due to the inherent properties of quantum money, our attack method also results in a
more efficient verification procedure.Where the paper says it
Where the paper says it
Where the paper says it
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>. The first approach involves constructing a uniform superposition of elliptic curves with the given cardinality using the quantum random walk, which is known as the Index Erasure Problem <ref:2508. p. 1 The first approach involves constructing a uniform superposition of elliptic
curves with the given cardinality using the quantum random walk. In order to
use the quantum random walk-based method, the index used in generating the
quantum state must be discarded, which is known as the Index Erasure Problem. The second approach leverages quantum search techniques to sample elliptic
curves of the required cardinality. A straightforward yet computationally expensive method would be to employ the point-counting algorithm as a search oracle. Our main contributions are summarized
as follows:
– Optimized Forgery Attack : We propose a novel attack strategy that efficiently searches for a quantum banknote with a given serial number, outperforming direct brute-force approaches. Our attack method O(log4
p) times
faster than the brute-force attack and requires 12⌈log p⌉
2 qubits, which is
log p times fewer than the brute-force method.Where the paper says it
Where the paper says it
Where the paper says it
Resource Estimation and Complexity
The paper provides concrete security estimation for the quantum resources required to forge quantum money, showing that the approach is significantly simpler than implementing the point-counting algorithm <ref:2508.00351#pg10>. The time complexity analysis shows that our method requires at least 5097 p(1/4) log(p)(log4 p) = O(p(1/4) log 7/2 p) bit operations and at most 8264p(1/4) log 9/2 p = O(p(1/4) log 9/2 p), depending on the class number <ref:2508. p. 8 While the quantum random walk method offers at most a log p improvement in the number of search
iterations compared to our method (note that the actual factor is smaller on
average), the time complexity T1 is significantly greater than T2, more than
offsetting this advantage. 376], Bach showed that the set BK of ideal classes of unramified
primes l of an imaginary quadratic field K, with N(l) < 6 log2
d, generates the
class group Cl(OK). Our attack method O(log4
p) times
faster than the brute-force attack and requires 12⌈log p⌉
2 qubits, which is
log p times fewer than the brute-force method. – Concrete Security Estimation : As our approach is significantly simpler
than implementing the point-counting algorithm, we can provide a more precise estimation of the quantum resources required to forge quantum money.Where the paper says it
Where the paper says it
Verification Improvements
The paper demonstrates how the insights can improve the efficiency of verifying a given serial number, showing that the process becomes O(log4 p) times faster than the original approach <ref:2508.00351#pg10>. The verification algorithm is directly derived from Algorithm 7, which uses Algorithm 6 to compute division polynomials and Euler's criteria <ref:2508.00351#pg10>. This method only applied to checking the validity of the serial number σ and verifying the uniformity of the given quantum money is same as the previous method in [11] <ref:2508. p. 1 By exploiting this relationship, we outline
how our proposed optimization can be applied not only to an attack strategy but
also to an improved verification method. Our main contributions are summarized
as follows:
– Optimized Forgery Attack : We propose a novel attack strategy that efficiently searches for a quantum banknote with a given serial number, outperforming direct brute-force approaches.Where the paper says it
Utilization of Rational Points
The key insight is utilizing rational points on elliptic curves EA,B for efficient computation of division polynomials, exploiting the property of quadratic twists to utilize rational points <ref:2508.00351#pg10>. Specifically, Algorithm 7 computes Fp,σ,τ (A, B, x) by checking annihilation by σ and 2p + 2 - σ using division polynomials <ref:2508. p. 1 For an elliptic curve E defined over Fp, a
division polynomial ψℓ(X, Y ) ∈ Fp[X, Y ] is a polynomial whose roots are the ℓtorsion points (x, y) ∈ E[ℓ]. Using the recurrence relation of division polynomials,
we can compute ψℓ(x, y) in O(log ℓ) multiplications in Fp, which is significantly
faster than the point-counting algorithm when p is a large prime. A straightforward yet computationally expensive method would be to employ the point-counting algorithm as a search oracle. Instead, we propose a more efficient alternative that takes advantage of the fact
that verifying the order of rational points is significantly faster than counting
rational points. Our attack method O(log4
p) times
faster than the brute-force attack and requires 12⌈log p⌉
2 qubits, which is
log p times fewer than the brute-force method. – Concrete Security Estimation : As our approach is significantly simpler
than implementing the point-counting algorithm, we can provide a more precise estimation of the quantum resources required to forge quantum money.Where the paper says it
Where the paper says it
Where the paper says it
Conclusion
In this work, we propose an attack method to forge quantum money in the isogeny-based quantum money scheme presented in [11] and introduce a more efficient verification algorithm <ref:2508.00351#pg10>. We employ the fact that checking the exponent of an elliptic curve group with rational points is more efficient than directly computing its cardinality, achieving a speedup of O(log4 p) compared to the brute-force attack <ref:2508. p. 1 We propose a new way to forge a quantum banknote from
the serial number given, more optimal than brute-force attack. We leverage the
fact that computing division polynomials with rational points is more efficient
than the point-counting algorithm. We leverage the
fact that computing division polynomials with rational points is more efficient
than the point-counting algorithm. For an elliptic curve E defined over Fp, a
division polynomial ψℓ(X, Y ) ∈ Fp[X, Y ] is a polynomial whose roots are the ℓtorsion points (x, y) ∈ E[ℓ]. Our algorithm leverages the properties of quadratic twists to utilize rational points in verifying the cardinality of the superposition of elliptic curves. We expect this approach to
contribute to future research on elliptic-curve-based quantum cryptography.Where the paper says it
Where the paper says it
Where the paper says it
References
-
Aaronson, S.: Quantum copy-protection and quantum money
-
Aaronson, S., Christiano, P.: Quantum money from hidden subspaces
-
Bach, E.: Explicit bounds for primality testing and related problems
-
Biasse, J.F., Song, F.: Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields
-
de Boer, K., Ducas, L., Fehr, S.: On the quantum complexity of the continuous hidden subgroup problem
-
Cohen, H.: A course in computational algebraic number theory
-
Conde Pena, M., Dur´an D´ıaz, R., Faug'ere, J.C., Hern´andez Encinas, L., Perret, L.: Non-quantum cryptanalysis of the noisy version of aaronson–christiano’s quantum money scheme
-
De Feo, L., Kieffer, J., Smith, B.: Towards practical key exchange from ordinary isogeny graphs
-
Kuperberg, G. p. 1
: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problemWhere the paper says it
In order to use the quantum random walk-based method, the index used in generating the quantum state must be discarded, which is known as the Index Erasure Problem. In Section 3, we show that Kuperberg’s algorithm [9] is infeasible for solve this problem in our setting and demonstrate that the quantum random walk-based attack is significantly inefficient.
-
Liu, J., Montgomery, H. p. 0
p. 0Where the paper says it
Quantum money is the cryptographic application of the quantum no-cloning theorem. It has recently been instantiated by Montgomery and Sharif (Asiacrypt ’24) from class group actions on elliptic curves.
, Zhandry, M. p. 0Where the paper says it
Quantum money is the cryptographic application of the quantum no-cloning theorem. It has recently been instantiated by Montgomery and Sharif (Asiacrypt ’24) from class group actions on elliptic curves.
p. 0Where the paper says it
The first instantiation of publicly verifiable quantum money was [2], but it was later broken by [7]. Zhandry subsequently proposed a construction of quantum money/lightning based on the assumption of indistinguishability obfuscation in [19], which was later broken by Roberts [13].
: Another round of breaking and making quantum money: How to not build it from lattices, and moreWhere the paper says it
The first instantiation of publicly verifiable quantum money was [2], but it was later broken by [7]. Zhandry subsequently proposed a construction of quantum money/lightning based on the assumption of indistinguishability obfuscation in [19], which was later broken by Roberts [13].
-
Montgomery, H., Sharif, S. p. 0
: Quantum money from class group actions on elliptic curvesWhere the paper says it
Quantum money is the cryptographic application of the quantum no-cloning theorem. It has recently been instantiated by Montgomery and Sharif (Asiacrypt ’24) from class group actions on elliptic curves.
-
Pomerance, C.: Remarks on the p´olya–vinogradov inequality
-
Roberts, B. p. 0
: Security analysis of quantum lightningWhere the paper says it
The first instantiation of publicly verifiable quantum money was [2], but it was later broken by [7]. Zhandry subsequently proposed a construction of quantum money/lightning based on the assumption of indistinguishability obfuscation in [19], which was later broken by Roberts [13].
-
R¨uck, H.G.: A note on elliptic curves over finite fields
-
Schoof, R.: Counting points on elliptic curves over finite fields
-
Silverman, J.H.: The Arithmetic of Elliptic Curves
-
Tatuzawa, T.: On a theorem of siegel
-
Wiesner, S. p. 0
: Conjugate codingWhere the paper says it
Recently, there has been a growing interest in utilizing quantum computers for security purposes, notably through quantum money. Quantum money was first proposed by Wiesner in [18].
-
Zhandry, M.: Quantum lightning never strikes the same state twice. p. 5
or: quantum money from cryptographic assumptionsWhere the paper says it
Both quantum money and quantum lightning consist of two functions Gen and Ver as follows: – Gen(1λ ). Takes as input a security paramter λ and generate a quantum money state |ψ⟩ and the associated serial number σ.
--- Page 1 ---
Cryptanalysis of Isogeny-Based Quantum Money with Rational Points
Hyeonhak Kim, Donghoe Heo and Seokhie Hong
Keywords: Quantum Money, Quantum Lightning, Class Group Action and Elliptic Curve
Abstract. Quantum money is the cryptographic application of the quantum no-cloning theorem. p. 0 Cryptanalysis of Isogeny-Based Quantum Money
with Rational Points
Hyeonhak Kim
1
, Donghoe Heo
1 and Seokhie Hong
1
⋆
School of Cybersecurity, Korea University, Seoul 02841, South Korea
Keywords: Quantum Money, Quantum Lightning, Class Group Action and
Elliptic Curve
Abstract. Quantum money is the cryptographic application of the quantum no-cloning theorem. Quantum money is the cryptographic application of the quantum no-cloning theorem. It has recently been instantiated by Montgomery and Sharif (Asiacrypt ’24) from class group actions on elliptic
curves. It has recently been instantiated by Montgomery and Sharif (Asiacrypt ’24) from class group actions on elliptic
curves. 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(log
4
p) compared to the bruteforce attack. 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(log
4
p) compared to the bruteforce attack. Since our attack still requires exponential time, it remains
impractical to forge a quantum banknote.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
--- Page 2 ---
H. Kim et al.
Montgomery and Zhandry devised a construction of quantum money which is called walkable invariant money in [10]. p. 1 Montgomery and Zhandry devised a construction of quantum money which is
called walkable invariant money in [10]. This walkable invariant money was concretely instantiated in [11] using class group actions on elliptic curves. p. 1 Montgomery and Zhandry devised a construction of quantum money which is
called walkable invariant money in [10]. This walkable invariant money was concretely instantiated in [11] using class group actions on elliptic curves.Where the paper says it
Where the paper says it
--- Page 3 ---
We propose a new way to forge a quantum banknote from the serial number given, more optimal than brute-force attack. We leverage the fact that computing division polynomials with rational points is more efficient than the point-counting algorithm. p. 1 We propose a new way to forge a quantum banknote from
the serial number given, more optimal than brute-force attack. We leverage the
fact that computing division polynomials with rational points is more efficient
than the point-counting algorithm.Where the paper says it
--- Page 4 ---
For an elliptic curve E defined over Fp, a division polynomial ψl(X, Y) ∈ Fp[X, Y] is a polynomial whose roots are the ltorsion points (x, y) ∈ E[l]. Using the recurrence relation of division polynomials, we can compute ψl(x, y) in O(log l) multiplications in Fp, which is significantly faster than the point-counting algorithm when p is a large prime. p. 1 For an elliptic curve E defined over Fp, a
division polynomial ψℓ(X, Y ) ∈ Fp[X, Y ] is a polynomial whose roots are the ℓtorsion points (x, y) ∈ E[ℓ]. Using the recurrence relation of division polynomials,
we can compute ψℓ(x, y) in O(log ℓ) multiplications in Fp, which is significantly
faster than the point-counting algorithm when p is a large prime.Where the paper says it
--- Page 5 ---
In this work, we analyze the unforgeability of the quantum money scheme proposed in [11] in a concrete manner. We identify two potential approaches to forge a quantum banknote in this scheme. p. 1 1 Contributions
In this work, we analyze the unforgeability of the quantum money scheme proposed in [11] in a concrete manner. We identify two potential approaches to forge
a quantum banknote in this scheme.Where the paper says it
--- Page 6 ---
The first approach involves constructing a uniform superposition of elliptic curves with the given cardinality using the quantum random walk, which is known as the Index Erasure Problem.
--- Page 7 ---
In Section 3, we show that Kuperberg’s algorithm [9] is infeasible for solve this problem in our setting and demonstrate that the quantum random walk-based attack is significantly inefficient.
--- Page 8 ---
By using the quantum search algorithm, we aim to find a group action a such that [a]Eσ = E. The size of the search space is determined by the class number h(d) of an imaginary quadratic number field. p. 8 2 Time Complexity of Solving the Index Erasure Problem
By using the quantum search algorithm, we aim to find a group action a such
that [a]Eσ = E. The size of the search space is determined by the class number
h(d) of an imaginary quadratic number field.Where the paper says it
--- Page 9 ---
The size of the search space is determined by the class number h(d) of an imaginary quadratic number field.
--- Page 10 ---
Since each ideal class appears as an index in the Index Erasure Problem, we need to compute all ideal classes in Cl(OK) using BK. The number of isogeny computations using a prime ideal l ∈ BK is bounded by h(d) 1/BK, which evaluates to Θ(p(1/4) log(log p)) when log d ≈ log p. p. 8 Since each ideal class appears as an index in the Index Erasure Problem, we
need to compute all ideal classes in Cl(OK) using BK. The number of isogeny
computations using a prime ideal l ∈ BK is bounded by h(d)
1/#BK , which
evaluates to Θ(p
1
4 log(log p) ) when log d ≈ log p.Where the paper says it
--- Page 11 ---
The bottleneck in the SEA algorithm is computing the Fp-rational roots of the modular polynomial Φl(x, j0) which is a degree l + 1 polynomial whose roots are the j-invariants of elliptic curves l-isogenous to the curve with j-invariant j0.
--- Page 12 ---
We show that rational points can be used to verify the cardinality based on the properties of the quadratic twists of elliptic curves.
--- Page 13 ---
The lower and upper bound of class numbers that leads to the number of iterations in Grover search algorithm is bounded as follows. The lower bound is approximately 2. p. 2 Section 4 illustrates
our quantum search algorithm and its oracle. In Section 5, we show that the
lower and upper bound of class numbers that leads to the number of iterations
in the quantum search algorithm. It has recently been instantiated by Montgomery and Sharif (Asiacrypt ’24) from class group actions on elliptic
curves. 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(log
4
p) compared to the bruteforce attack. It has recently been instantiated by Montgomery and Sharif (Asiacrypt ’24) from class group actions on elliptic
curves. 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(log
4
p) compared to the bruteforce attack. It has recently been instantiated by Montgomery and Sharif (Asiacrypt ’24) from class group actions on elliptic
curves. 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(log
4
p) compared to the bruteforce attack.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
--- Page 14 ---
In Algorithm 6, we can determine ψl requires O(log l) multiplication in Fp which translates to O(log2 p log l) bit operations.
--- Page 15 ---
The oracle Op,σ consists of the evaluation of division polynomials and the phase rotation via the n-controlled-Z gate Zn.
--- Page 16 ---
We exploit this fact to distinguish the target curve from the others by computing Fp,σ,τ.
--- Page 17 ---
Based on Theorem 9, Fp,σ,τ can be used to filter out all but the target curve of cardinality σ. Corollary 1 states that if the target curve is given, then the probability that Fp,σ,τ (A, B, x) = 0 for all x ∈ Fp is at most 3/4 + Θ(1/√p τ). p. 9 Grover search algorithm consists of the oracle Op,σ, n-bit Walsh-Hadamard gate Wn and the phase rotation gate O0 =
−2 |0
n+3⟩ ⟨0
n+3| + I. The search algorithm requires O(1/
√
r) queries to Op,σ to
obtain a uniform superposition of the target set T when the ratio of the target
among the given set X is r = |T|/|X|.Where the paper says it
--- Page 18 ---
Our method achieves a speedup of O(log4 p) compared to the brute-force attack. We estimate that forging quantum money using our approach requires fewer than 5097 log2 p multiplications in Fp for each search iteration and requires approximately 12⌈log p⌉2 qubits. p. 1 Our attack method O(log4
p) times
faster than the brute-force attack and requires 12⌈log p⌉
2 qubits, which is
log p times fewer than the brute-force method. – Concrete Security Estimation : As our approach is significantly simpler
than implementing the point-counting algorithm, we can provide a more precise estimation of the quantum resources required to forge quantum money.Where the paper says it
--- Page 19 ---
The lower bound is approximately 2.622 p(1/4)√log p + Θ(log log p).
--- Page 20 ---
Each Ψσi accounts for 10⌈log p⌉ qubits.
--- Page 21 ---
In total, by combining the upper and lower bound on the class numbers from Section 5, the process of forging a quantum banknote using our method requires at least 5097 p(1/4) log 4√p log p + Θ(log log p) = O(p(1/4) log 7/2 p) and at most 8264p(1/4) log 9/2 p = O(p(1/4) log 9/2 p) bit operations.
--- Page 13 ---
The lower bound is approximately 2.622 p(1/4)√log p + Θ(log log p).
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
-
Improved Quantum Money Forgery Attack: The new attack method achieves a speedup of O(log 4 p) compared to brute-force attacks, requiring only 12 ceiling log p squared qubits, which is log p times fewer than the brute-force method.
-
Improved Quantum Verification Algorithm: The proposed verification algorithm runs O(log 4 p) times faster than the original approach by leveraging rational points on elliptic curves to verify cardinality based on quadratic twists.
-
Enhanced Quantum Resource Estimation: The paper provides a more precise estimation of quantum resources required to forge quantum money, showing that the attack requires at least 5097 p raised to the power of one over four log four root p log p, and at most 8264 p raised to the power of one over four log nine root p.
-
Faster Serial Number Verification: The improved verification algorithm can check a serial number in O(log 4 p) times faster than the original approach, which is derived from Algorithm 7.
Abstract
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.
Sources
Related papers
- From Strategy Search to Policy Learning: MCTS-Guided Adversarial Co-Evolution for LLM Safety Alignment
- Privacy Leakage from Recurrent State in LLM Inference
- Incrementally Verifiable Oracle Aided Computation
- Privilege and confidentiality in generative AI workflows
- BadMoE: Backdooring Mixture-of-Experts LLMs via Routing-Aware Triggers and Task-Underutilized Experts
- CoVault: Secure, Scalable Analytics of Personal Data