{"id":"8e109203-775e-4a5a-be61-945623f51d5b","arxiv_id":"2508.00351","paper_version":1,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Forging Montgomery-Sharif quantum money can be attacked with a Grover search whose oracle checks curve cardinalities via division polynomials at rational points and quadratic twists, an O(log^4 p) speedup over point counting at still-exponential total cost.","lead":"Quantum money notes cannot be copied in principle, and a recent scheme builds them from elliptic curve math. This paper finds a faster way to search for a matching forged note, a polylogarithmic speedup over brute force, and shows the same technique can make the scheme's verification step cheaper.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The oracle's soundness theorem (Thm 9) equates annihilation by N with #E=N; this only forces the group exponent to divide N, not the order, so composite-N counterexamples may pass the oracle.","rationale":"The paper's contribution is a concrete resource model for forging Montgomery-Sharif quantum money and a faster verifier; both rest on the oracle that identifies exactly the curves of cardinality N. The oracle's predicate is the all-points annihilation test of Section 6.3. The visible proof of Theorem 9 is heavily corrupted, but the surrounding text shows the intended invariant is the N-torsion subgroup: 'if at least one rational point is not annihilated by N, then at least half remain unannihilated' is the standard subgroup/coset bound. That lemma is true, but the converse used by the theorem is not automatic. 'All rational points annihilated by N' states E(F_p)=E(F_p)[N], i.e. the exponent of E(F_p) divides N. For a rank-two finite abelian group this does not force its order to equal N unless additional hypotheses are imposed, such as N prime or the group cyclic. The twist condition exp(E^t) | (2p+2-N) narrows the gap, but the provided gcd/Hasse argument, using only m=#E and N, does not reconstruct the invariant factors n1|n2 whose product is m. I could not rule out, from the supplied text, curves with #E != N satisfying both exponent divisibilities; if such a curve exists, the oracle marks it good, the Grover state is not a valid banknote, and the verification speedup is unsound. The paper states N only as a positive integer in the Hasse interval and never states that N is prime or that E(F_p) is cyclic. The reader's weakest_assumption points to the same theorem; my check sharpens it to the exponent-versus-order gap and proposes an exhaustive small-prime search to settle it. I agree with a CONDITIONAL verdict: the central claim should not be taken as proven until Theorem 9 is repaired with explicit hypotheses or a counterexample is excluded. I also credit the authors for being honest that the attack remains exponential and for giving concrete resource estimates; the concern is not about novelty but about the unproven soundness of the central oracle.","tokens_in":9716,"tokens_out":25493,"duration_ms":266159,"concrete_test":"Run an exhaustive search over small primes p (say 5 <= p <= 200) using SageMath or PARI/GP: enumerate all isomorphism classes of elliptic curves over F_p, and compute the group structures of E(F_p) and of the quadratic twist E^t(F_p). For every integer N in the Hasse interval, test whether any curve with #E != N satisfies exp(E(F_p)) | N and exp(E^t(F_p)) | 2p+2-N. A single such triple is a concrete counterexample to Theorem 9 as read; if none is found, the test should be repeated at larger p or paired with an independent re-derivation of the theorem that makes the cyclicity or primality assumption explicit.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central oracle is sound only if Theorem 9/Cor. 1 is correct: a curve passes iff #E(F_p)=N. The visible proof is corrupted at the exact lines, but the group-theoretic meaning of the test is clear from the surrounding text. 'All rational points are annihilated by N' means every P in E(F_p) satisfies NP=O, i.e. E(F_p)=E(F_p)[N]. This is equivalent to exp(E(F_p)) | N, not to #E(F_p)=N. For a finite abelian group that is not cyclic, the order can be a proper multiple of the exponent; for example C2 x C6 has order 12 and exponent 6, so every point is annihilated by N=6 although 12 is not 6, and such a group structure is compatible with the invariant-factor constraint for p = 1 mod 6. The twist condition adds exp(E^t) | (2p+2-N), but the proof as excerpted bounds only gcd(m,N) and gcd(m,2p+2-N) via Hasse; it never uses the invariant factors n1|n2 whose product is m. Consequently the argument does not rule out curves with #E != N whose full rational-point group and twist group both have exponents dividing the two target integers. The paper does not state that N is prime (Section 4 calls it 'a positive integer satisfying 0<=N<=p+1+2*sqrt(p)') nor that E(F_p) is cyclic. Even the 2-torsion issue is unresolved: for even N, all rational 2-torsion is annihilated by N automatically, so the subgroup H is always nontrivial and the distinguishing power is smaller than the half-points lemma suggests. If a false-positive curve exists, the Grover output is not a valid banknote and the claimed O(log^4 p) verification speedup is unsound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":9885,"tokens_out":54160,"duration_ms":521079,"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":[{"comment":"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.","section":"§6, Theorem 9 / Corollary 1"}],"minor_comments":[{"comment":"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.","section":"§6, Theorem 9 proof"},{"comment":"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.","section":"§1 and §8"},{"comment":"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.","section":"§5"}],"recommendation":"major_revision","confidential_remarks":"The central theorem is false as stated, and my counterexample uses parameters (p=11, N=6) that may be outside the scheme's intended squarefree-discriminant domain. If the intended theorem is restricted to that domain, the authors must state the restriction explicitly and supply a complete proof that uses the invariant-factor structure; the current proof is neither complete nor verifiable. Given that the main contribution depends entirely on this theorem, this is a load-bearing issue, not a presentation issue. The idea is potentially salvageable, so I recommend major revision rather than outright rejection, but the rewritten Section 6 must be reviewed carefully."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nI 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.\n\nWho 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.","headline":"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.","tokens_in":10612,"tokens_out":3964,"would_cite":false,"duration_ms":40375,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["14G50","14H52","81P94","94A60"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["quantum money","quantum lightning","class group actions","elliptic curves","division polynomials","quadratic twists","Grover search","point counting"],"falsifier":"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.","tokens_in":9328,"feed_emoji":"💰","tokens_out":8588,"duration_ms":89110,"temperature":0.7,"pith_summary":"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.","feed_headline":"Forging quantum money gets a log^4 p speedup via rational points","feed_subtitle":"Division polynomials and quadratic twists replace point counting in the oracle and improve verification.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the quantum money scheme under attack, whose serial number is an elliptic-curve cardinality and whose mint uses point counting.","marker":"[11]"},{"why":"Supplies the Hasse bound and basic elliptic-curve group facts used in the soundness proof.","marker":"[16]"},{"why":"Provides the point-counting algorithm that serves as the brute-force baseline being improved.","marker":"[15]"},{"why":"Gives the explicit character-sum bound used to upper-bound the class number and hence the number of Grover iterations.","marker":"[12]"},{"why":"Supplies the Dirichlet L-function lower bound used to lower-bound the class number.","marker":"[17]"},{"why":"Shows class numbers can be computed in quantum polynomial time, so the search-space size can be treated as known.","marker":"[4]"},{"why":"Tightens the quantum cost estimate for the continuous hidden subgroup problem used in the class-number computation.","marker":"[5]"},{"why":"Is the dihedral hidden-subgroup algorithm whose infeasibility here motivates choosing quantum search over quantum random walk.","marker":"[9]"}],"fun_headline_variants":["Quantum money forging gets log^4 p speedup via rational points","Rational points give log^4 p speedup for quantum money forgery","Quadratic twists and rational points accelerate quantum money forgery","Quantum money forgery: rational points cut time by log^4 p","Rational points yield log^4 p faster forgery of quantum money"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Quantum money forging gets log^4 p speedup via rational points","Rational points give log^4 p speedup for quantum money forgery","Quadratic twists and rational points accelerate quantum money forgery","Quantum money forgery: rational points cut time by log^4 p","Rational points yield log^4 p faster forgery of quantum money"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001338,"raw_usage":{"total_tokens":5423,"prompt_tokens":911,"completion_tokens":4512,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":527,"completion_tokens_details":{"reasoning_tokens":4421}},"tokens_in":527,"tokens_out":4512,"duration_ms":27823,"temperature":1.0,"reasoning_tokens":4421,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T10:15:59.030551+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"In: International Conference on the Theory and Application of Cryptology and Information Security","cited_arxiv_id":null,"evidence_quote":"Defines the quantum money scheme under attack, whose serial number is an elliptic-curve cardinality and whose mint uses point counting."},{"cited_title":"Graduate texts in mathemat- ics, Springer, Dordrecht (2009)","cited_arxiv_id":null,"evidence_quote":"Supplies the Hasse bound and basic elliptic-curve group facts used in the soundness proof."},{"cited_title":"Journal de th´ eorie des nombres de Bordeaux �(1), 219–254 (1995)","cited_arxiv_id":null,"evidence_quote":"Provides the point-counting algorithm that serves as the brute-force baseline being improved."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the explicit character-sum bound used to upper-bound the class number and hence the number of Grover iterations."},{"cited_title":"In: Japanese journal of mathematics: trans- actions and abstracts","cited_arxiv_id":null,"evidence_quote":"Supplies the Dirichlet L-function lower bound used to lower-bound the class number."},{"cited_title":"In: Proceed- ings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms","cited_arxiv_id":null,"evidence_quote":"Shows class numbers can be computed in quantum polynomial time, so the search-space size can be treated as known."},{"cited_title":"In: Annual International Conference on the Theory and Applications of Cryptographic Techniques","cited_arxiv_id":null,"evidence_quote":"Tightens the quantum cost estimate for the continuous hidden subgroup problem used in the class-number computation."}],"review_version":1}