Cryptanalysis of Isogeny-Based Quantum Money with Rational Points

Donghoe Heo; Hyeonhak Kim; Seokhie Hong

REVIEW 1 major objections 3 minor 19 references

Cryptanalysis of Isogeny-Based Quantum Money with Rational Points

T0 review · 1 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A Grover-search oracle that checks elliptic-curve orders with division polynomials and quadratic twists forges the isogeny-based quantum banknote with an O(log^4 p) speedup over point-counting brute force.

desk verdict A sober and honest cryptanalysis whose attack and verification speedup both ride on a soundness theorem that the stress-test concern about exponent-vs-order plausibly defeats as stated. read the letter →

arxiv 2508.00351 v1 pith:YKW3V2G3 submitted 2025-08-01 cs.CR

Hyeonhak Kim , Donghoe Heo , Seokhie Hong This is my paper · ORCID

classification cs.CR MSC 14G5014H5281P9494A60

keywords quantummoneylightningclassgroupactionsellipticcurvesdivisionpolynomialsquadratictwistsGroversearchpointcounting

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to show that the quantum money scheme instantiated from class group actions on elliptic curves can be forged more efficiently by replacing the point-counting oracle in a Grover search with a much cheaper division-polynomial test. The proposed oracle evaluates division polynomials at rational points and uses quadratic twists to check whether a curve has the target cardinality $N$, rather than counting all its points. This yields an $O(\log^4 p)$ speedup over brute-force point counting while remaining exponential overall, and the same construction doubles as a faster verification procedure. A sympathetic reader would care because it sharpens the concrete quantum resources needed to forge or verify this type of banknote.

What carries the argument

The central object is the division polynomial $\psi_\ell(x,y)\in\mathbb{F}_p[x,y]$, whose roots are the $\ell$-torsion points; evaluated at a rational point, it tests whether that point is annihilated by $\ell$. The oracle combines this with a quadratic-twist routing rule: depending on whether $x^3+Ax+B$ is a square, the test applies to the curve or to its twist, with annihilation targets $N$ and $2p+2-N$ respectively. The soundness argument rests on a subgroup lemma (if one rational point is not annihilated by $N$, then at least half of the rational points are not) together with a gcd-and-Hasse-bound comparison between $\#E$ and $\#E^t$ showing that a wrong cardinality would create a contradiction.

What would settle it

For a small prime $p$, enumerate every $N$ in the Hasse interval and every curve $E/\mathbb{F}_p$; for each curve with $\#E \neq N$, run the paper's oracle on a rational point $x$ (or on the twist when $x^3+Ax+B$ is a non-residue). If any such curve passes both annihilation checks, Theorem 9's gcd argument cannot be sound, because the oracle would mark a curve of the wrong cardinality as a target.

Watch

Extended reading notes

Core claim

For a target serial number $N$, the mint's state is a uniform superposition of elliptic curves whose cardinality is exactly $N$. The paper's central claim is that a membership oracle for this set can be built from division polynomials: given a Weierstrass curve $E_{A,B}$ over $\mathbb{F}_p$, examine a rational coordinate $x$; if $x^3+Ax+B$ is a quadratic residue, the point lies on $E_{A,B}$ and the oracle tests annihilation by $N$, and otherwise the point lies on the quadratic twist and the oracle tests annihilation by $2p+2-N$. Because evaluating an $\ell$-th division polynomial takes $O(\log \ell)$ multiplications in $\mathbb{F}_p$, this test is much cheaper than point counting. The paper proves that any curve passing both annihilation checks must have cardinality exactly $N$, so Grover search over the class-number-sized space produces the correct banknote state. It estimates fewer than $5097\log^2 p$ multiplications in $\mathbb{F}_p$ per search iteration and about $12\lceil\log p\rceil^2$ qubits.

Load-bearing premise

The whole argument depends on the test being foolproof: a curve whose order is not the target number must fail the annihilation check on itself or on its quadratic twist, so the search oracle never marks a curve of the wrong cardinality.

Editorial extensions

If this is right

The per-iteration cost of forging a banknote drops to fewer than $5097\log^2 p$ multiplications in $\mathbb{F}_p$, with about $12\lceil\log p\rceil^2$ qubits, making the quantum resource estimate concrete.
Verification of a serial number becomes $O(\log^4 p)$ faster than the original point-counting check, since the same division-polynomial annihilation tests replace full cardinality computation.
The number of Grover iterations is set by the class number of an imaginary quadratic field, bounded between roughly $\Omega(\sqrt{p}/\log p)$ and about $\sqrt{p}\log p$, so the attack remains exponential in $\log p$.
The dihedral hidden-subgroup random-walk route to forging is infeasible in this setting, so quantum search with the new oracle is the most viable attack strategy.
If the soundness theorem holds, the oracle marks exactly the curves of cardinality $N$, so Grover search converges to the uniform superposition that constitutes the banknote.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same division-polynomial-plus-twist oracle could be reused in other isogeny-based protocols that need to sample or verify curves of a prescribed order, not only quantum money; the paper does not explore those applications.
One could benchmark the oracle on cryptographic-size primes to test whether the theoretical $5097\log^2 p$ constant holds in practice and whether the subgroup lemma's one-half bound is tight on random non-target curves.
Adapting the annihilation targets may detect finer group-structure properties than cardinality, such as the presence of a large torsion subgroup, though the quadratic-twist routing would need modification for fields where twists behave differently.
Because the speedup is only polylogarithmic inside an exponential search, the practical significance depends on whether the division-polynomial recurrence beats optimized point counting at the actual field sizes used by the scheme.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick read: this is a serious, honest paper, and the authors deserve credit for saying plainly that their attack stays exponential. The genuinely new pieces are the concrete oracle built from division polynomials at rational points, the quadratic-twist routing, the class-number bounds bounding the Grover iteration count, and the observation that the same oracle gives a polylog verification speedup. The resource estimates (fewer than 5097 log^2 p multiplications per iteration, about 12 log^2 p qubits) are explicit and falsifiable. Citation pattern looks fine: standard number theory facts, target scheme from a different group, no fitted constants.

The soft spot is exactly Theorem 9. The pass condition is that every rational point is annihilated by N. That is the statement exp(E(F_p)) | N, not #E(F_p) = N. A finite abelian group like C2 x C6 has order 12 and exponent 6, so it passes an N=6 annihilation test. The proof as excerpted bounds gcds of cardinalities via Hasse, but it never seems to use the invariant-factor decomposition or cyclicity, and the paper never says N is prime or that E(F_p) is cyclic. The 2-torsion issue is real too: for even N, rational 2-torsion is annihilated automatically, so the "at least half not annihilated" lemma loses its punch. Since this theorem backs both the forgery oracle and the faster verifier, a false positive would sink both.

I can't be fully certain: the text is corrupted exactly at the critical gcd/Hasse lines, so it's possible the argument relies on a structural fact that got mangled in transcription. But on what is visible, the stress-test concern lands. This is not a reason to desk-reject; it's a reason to send to a referee who knows elliptic curve group structures over finite fields and ask whether Theorem 9 is true or a counterexample exists. If it gets fixed, the paper is a solid contribution to the cryptanalysis of class-group quantum money. If not, the main claims go with it.

Who should read it: people working on quantum money and isogeny-based assumptions, and anyone estimating quantum attack costs. I would bring it to a reading group as a "find the flaw in the oracle" exercise, but I would not cite it until Theorem 9 is settled. Recommendation: accept for peer review, with the soundness theorem as the sole focus of the first round.

Referee Report

1 major / 3 minor

Summary. The paper proposes a concrete cryptanalysis of the Montgomery–Sharif isogeny-based quantum money scheme. Instead of using Schoof point counting as the Grover oracle, it suggests testing annihilation of rational points by the serial number N via division polynomials, combined with a quadratic-twist check, obtaining an O(log^4 p) speedup and a faster verification procedure. The correctness of the attack and of the improved verifier rests on Theorem 9/Corollary 1, which asserts that a curve passes the oracle iff its rational-point group has cardinality N.

Significance. If the central oracle were sound, the paper would provide a meaningful, concrete improvement over brute-force forgery and a useful optimization of the verification procedure. The authors are transparent about the exponential residual cost and give explicit circuit estimates and class-number bounds using standard tools. However, the load-bearing soundness theorem is false as stated, and the proof as printed is too corrupt to verify. The claimed forgery and verification improvements are therefore unsupported, and the paper cannot be accepted in its present form.

major comments (1)

[§6, Theorem 9 / Corollary 1] The description of the oracle is ambiguous in a way that affects correctness. Section 6 says the oracle verifies that 'all rational points' are annihilated by N, but the implementation described uses a single x-coordinate selected by a quadratic-residue test and evaluates one division polynomial. A single point cannot certify that the whole group is annihilated; the subgroup argument in Section 6 only shows that if the annihilated points form a proper subgroup, then at least half the points are not annihilated, which gives a probabilistic test, not a deterministic Grover oracle. If the intention is to run over all x or to use a superposition of points, the claimed cost of fewer than 5097 log^2 p multiplications per iteration must account for that. This gap is independent of the counterexample in the previous comment and also needs to be resolved.

minor comments (3)

[§6, Theorem 9 proof] The proof as typeset is unreadable at exactly the load-bearing point: equations (3)–(4) contain corrupted symbols (e.g., '� 2 1�1', '� 1�1 � � 2�2 / gcd(...)') and the theorem statement itself is partially garbled. The authors should provide a clean, machine-checkable version of the statement and proof.
[§1 and §8] The text references 'Table 6.3' for the quantum resource analysis, but no such table is present in the provided manuscript; the resource counts in the introduction and conclusion (5097 log^2 p multiplications, 12 log^2 p qubits) should be reconciled with the table and with the stated O(log^4 p) speedup.
[§5] The class-number upper bound derivation contains several typographical inconsistencies (e.g., missing parentheses and unclear constants in inequality (1)); please rewrite it with all terms defined.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the oracle's soundness and the speedup estimates are derived from external theorems and analytical cost counts, not from the paper's own conclusions.

full rationale

The paper's claimed derivation chain is self-contained against external results and contains no step that reduces to its own inputs by construction. The oracle does not fit any parameter to a subset of data: its input N is the public serial number (the target cardinality) from the Montgomery–Sharif scheme, and the acceptance condition—annihilation by N on E(F_p) and by 2p+2−N on the quadratic twist—is justified by Theorem 9/Corollary 1 using Hasse bounds, the twist relation #E + #E^t = 2p+2, and gcd arguments, rather than by assuming #E=N. The speedup claim is an analytical comparison between division-polynomial evaluation (O(log l) multiplications in F_p) and the cited point-counting complexity (Schoof, O(log^8 p) bit operations); the class-number bounds used for the Grover iteration count are quoted from Tatuzawa and Pomerance/Polyá–Vinogradov, not from the authors' own prior work. There are no self-citations by the present authors, and no fitted-input-called-prediction, ansatz-smuggling, or renaming pattern is present. The excerpted proof of Theorem 9 is garbled and should be corrected before the soundness claim is relied upon, but a garbled proof is a correctness risk, not circularity.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The central claim rests on standard number-theoretic and cryptographic background: Deuring correspondence, Hasse bound, quadratic twist identities, division polynomial recurrences, and explicit class number estimates, all cited to standard references. No numbers are fitted to data; the 5097 constant is an analytical circuit count and the class number constants come from cited theorems. The only item the reader must accept from inside the paper is Theorem 9, the soundness of the annihilation-based oracle, which I could not fully verify from the corrupted excerpt; everything else is standard.

assumptions (8)

standard math Deuring correspondence between ideal classes of an imaginary quadratic order and isogeny classes of elliptic curves with that endomorphism ring
Invoked in Section 2 (Theorem 4 area) to equate the number of F_p-isomorphism classes of curves of cardinality N with the class number h(d), which sets the Grover search space size and the banknote serial structure.
standard math Hasse bound: p+1-2*sqrt(p) <= #E(F_p) <= p+1+2*sqrt(p)
Cited as Theorem 2 and used throughout, especially in Theorem 9 to restrict possible cardinalities to a window of width 4*sqrt(p), enabling the gcd bounds that make the oracle sound.
standard math Quadratic twist cardinality identity #E(F_p) + #E_t(F_p) = 2p+2
Theorem 3; the oracle routes each sample x to E or its twist depending on a Legendre symbol and checks annihilation by N or 2p+2-N, so both oracle soundness and the verification speedup rest on this identity.
standard math Explicit class number bounds from Dirichlet class number formula, Tatuzawa's theorem, and Polya-Vinogradov type estimates
Section 5 uses these to bound Grover iterations as roughly p^(1/4) sqrt(log p); a wrong bound would shift the iteration count, not the oracle itself.
standard math Division polynomial recurrence allows evaluating Psi_l at a point in O(log l) multiplications in F_p
Section 6; this is the base of the claimed polylogarithmic oracle cost and of the 5097 log^2 p per-iteration multiplication count.
domain assumption Schoof's point-counting algorithm requires O(log^8 p) bit operations (cited to [15]) and is the brute-force baseline
The claimed O(log^4 p) speedup is the ratio between this baseline and the paper's oracle cost; if the baseline exponent is wrong, the speedup factor shifts, though the qualitative conclusion (still exponential attack) does not.
domain assumption A polynomial-time quantum algorithm computes class numbers, with tight CHSP cost estimates (cited to [4,5])
Section 4 invokes these to compute h(d) for the Grover iteration count; the paper's own analysis uses the class number bounds instead, so this is a supporting input rather than a core premise.
domain assumption The annihilation-based oracle has negligible false-accept probability for curves of cardinality other than N (Theorem 9, Corollary 1)
This is the paper's own soundness claim, the load-bearing premise of both the attack and the verification improvement; the provided text is corrupted at the proof, so I treat it as an assumption pending independent verification.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Cryptanalysis of Isogeny-Based Quantum Money with Rational Points." pith.science (2026). https://pith.science/paper/YKW3V2G3

@misc{pith2026250800351,
  author       = {Pith},
  title        = {Pith review of: Cryptanalysis of Isogeny-Based Quantum Money with Rational Points},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YKW3V2G3}},
  note         = {Machine review of arXiv:2508.00351}
}

read the original abstract

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. 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^4p) compared to the brute-force attack. 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. 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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 17 canonical work pages

[1]

In: 2009 24th Annual IEEE Conference on Computational Complexity

Aaronson, S.: Quantum copy-protection and quantum money. In: 2009 24th Annual IEEE Conference on Computational Complexity. pp. 229–242. IEEE (2009)

work page 2009
[2]

In: Pro- ceedings of the forty-fourth annual ACM symposium on Theory of computing

Aaronson, S., Christiano, P.: Quantum money from hidden subspaces. In: Pro- ceedings of the forty-fourth annual ACM symposium on Theory of computing. pp. 41–60 (2012)

work page 2012
[3]

Mathematics of Computation �� (191), 355–380 (1990)

Bach, E.: Explicit bounds for primality testing and related problems. Mathematics of Computation �� (191), 355–380 (1990)

work page 1990
[4]

In: Proceed- ings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms

Biasse, J.F., Song, F.: Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In: Proceed- ings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms. pp. 893–902. SIAM (2016)

work page 2016
[5]

In: Annual International Conference on the Theory and Applications of Cryptographic Techniques

de Boer, K., Ducas, L., Fehr, S.: On the quantum complexity of the continuous hidden subgroup problem. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 341–370. Springer (2020)

work page 2020
[6]

Cohen, H.: A course in computational algebraic number theory, vol. 138. Springer Science & Business Media (2013)

2013
[7]

IET Information Security �� (4), 362–366 (2019)

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. IET Information Security �� (4), 362–366 (2019)

work page 2019
[8]

De Feo, L., Kieffer, J., Smith, B.: Towards practical key exchange from ordinary isogeny graphs. In: Advances in Cryptology–ASIACRYPT 2018: 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2–6, 2018, Proceedings, Part III 24. pp. 365–

work page 2018

Show all 19 references

[9]

arXiv preprint arXiv:1112.3333 (2011) 22 H

Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. arXiv preprint arXiv:1112.3333 (2011) 22 H. Kim et al

2011 arXiv
[10]

In: Annual Interna- tional Conference on the Theory and Applications of Cryptographic Techniques

Liu, J., Montgomery, H., Zhandry, M.: Another round of breaking and making quantum money: How to not build it from lattices, and more. In: Annual Interna- tional Conference on the Theory and Applications of Cryptographic Techniques. pp. 611–638. Springer (2023)

2023
[11]

In: International Conference on the Theory and Application of Cryptology and Information Security

Montgomery, H., Sharif, S.: Quantum money from class group actions on elliptic curves. In: International Conference on the Theory and Application of Cryptology and Information Security. pp. 33–64. Springer (2025)

2025
[12]

Pomerance, C.: Remarks on the p´ olya–vinogradov inequality (2011)

2011
[13]

In: Annual International Con- ference on the Theory and Applications of Cryptographic Techniques

Roberts, B.: Security analysis of quantum lightning. In: Annual International Con- ference on the Theory and Applications of Cryptographic Techniques. pp. 562–567. Springer (2021)

2021
[14]

Mathematics of Computation �� (179), 301–304 (1987)

R¨ uck, H.G.: A note on elliptic curves over finite fields. Mathematics of Computation �� (179), 301–304 (1987)

1987
[15]

Journal de th´ eorie des nombres de Bordeaux �(1), 219–254 (1995)

Schoof, R.: Counting points on elliptic curves over finite fields. Journal de th´ eorie des nombres de Bordeaux �(1), 219–254 (1995)

1995
[16]

Graduate texts in mathemat- ics, Springer, Dordrecht (2009)

Silverman, J.H.: The Arithmetic of Elliptic Curves. Graduate texts in mathemat- ics, Springer, Dordrecht (2009). �� , ��

2009
[17]

In: Japanese journal of mathematics: trans- actions and abstracts

Tatuzawa, T.: On a theorem of siegel. In: Japanese journal of mathematics: trans- actions and abstracts. vol. 21, pp. 163–178. The Mathematical Society of Japan (1952)

1952
[18]

ACM Sigact News �� (1), 78–88 (1983)

Wiesner, S.: Conjugate coding. ACM Sigact News �� (1), 78–88 (1983)

1983
[19]

or: quantum money from cryptographic assumptions

Zhandry, M.: Quantum lightning never strikes the same state twice. or: quantum money from cryptographic assumptions. Journal of Cryptology �� , 1–56 (2021)

2021

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

In: 2009 24th Annual IEEE Conference on Computational Complexity

Aaronson, S.: Quantum copy-protection and quantum money. In: 2009 24th Annual IEEE Conference on Computational Complexity. pp. 229–242. IEEE (2009)

work page 2009

[2] [2]

In: Pro- ceedings of the forty-fourth annual ACM symposium on Theory of computing

Aaronson, S., Christiano, P.: Quantum money from hidden subspaces. In: Pro- ceedings of the forty-fourth annual ACM symposium on Theory of computing. pp. 41–60 (2012)

work page 2012

[3] [3]

Mathematics of Computation �� (191), 355–380 (1990)

Bach, E.: Explicit bounds for primality testing and related problems. Mathematics of Computation �� (191), 355–380 (1990)

work page 1990

[4] [4]

In: Proceed- ings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms

Biasse, J.F., Song, F.: Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In: Proceed- ings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms. pp. 893–902. SIAM (2016)

work page 2016

[5] [5]

In: Annual International Conference on the Theory and Applications of Cryptographic Techniques

de Boer, K., Ducas, L., Fehr, S.: On the quantum complexity of the continuous hidden subgroup problem. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 341–370. Springer (2020)

work page 2020

[6] [6]

Cohen, H.: A course in computational algebraic number theory, vol. 138. Springer Science & Business Media (2013)

2013

[7] [7]

IET Information Security �� (4), 362–366 (2019)

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. IET Information Security �� (4), 362–366 (2019)

work page 2019

[8] [8]

De Feo, L., Kieffer, J., Smith, B.: Towards practical key exchange from ordinary isogeny graphs. In: Advances in Cryptology–ASIACRYPT 2018: 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2–6, 2018, Proceedings, Part III 24. pp. 365–

work page 2018