PaperlayerView exact revision on arXiv

Source-linked AI summary

Path-Finding, Orbit State Preparation, and the Security of Invariant Quantum Money

Hans Schmiedel, Jiangshan Yu

arXiv:2609.39774v2cs.CR

TL;DR

The paper asks whether path-finding hardness can support invariant quantum-money security, given that existing proofs add unfalsifiable knowledge-of-path assumptions. It identifies when path-finding hardness is necessary and makes state preparation the central assumption, while proving a limitation on deriving the transfer assumption.

  • Problem

    Path-finding hardness alone has no known security proof for invariant quantum money, while existing proofs add knowledge-of-path assumptions that no attack can refute.

    Source: Invariant quantum money · p. 2, Results · p. 3

  • Method

    The paper analyzes schemes with group actions and, more generally, uses preparation and transfer assumptions to decompose security for rapidly mixing schemes.

    Source: Results · p. 3, §4.3 · p. 16

  • Results

    With an efficiently computable superposable group action containing every move, path-finding hardness is necessary for security; without such a group, a path-finder leaves an equally hard state-preparation problem.

    Source: Results · p. 3

  • Takeaways & Limitations

    Every secure scheme must satisfy the preparation assumption, and no fully black-box reduction limited to the given serial number derives the transfer assumption from it.

    Source: Results · pp. 3–4

    For knot orbits, no suitable group is known, and disentangling a random-walk record requires relabellings not known to be efficiently computable.

    Source: §4.4 · p. 19, §7 · p. 27

Abstract

from arXiv · show

The security of quantum money from knots, and of its generalization to invariant money, is based on the assumption that path-finding, exhibiting a sequence of moves between two equivalent objects, is hard. No proof of security from that assumption alone is known. The existing proofs add knowledge-of-path assumptions, which assert that any efficient algorithm producing two objects with the same invariant implicitly knows a path between them. No attack can refute such an assumption, and it is not known to follow from security. We ask when path-finding is the right assumption. When each equivalence class is the orbit of an efficiently computable action of a group that can be superposed over, and every move acts as a group element, as for graphs, average-case hardness of path-finding is necessary for security. For knots no such group is known, and a path-finder only reduces forgery to an equally hard state-preparation problem. With or without a path-finder, a forger must prepare a state that verification accepts, and we take the hardness of that task as the assumption. For schemes whose verification walk mixes in polynomial time, the preparation assumption states that no efficient algorithm, given the serial number of a freshly minted banknote and one object measured from it, prepares such a state. It is falsifiable, and it is equivalent to security against forgers that measure their banknote first. The transfer assumption, which security implies, states that measuring first costs a forger at most a polynomial factor. Together the two are equivalent to security, so every proof of security must establish the preparation assumption. If the preparation assumption holds, no fully black-box reduction that calls the forger only at the serial number it is given can derive the transfer assumption from the preparation assumption.

1 Introduction

The paper examines what assumptions secure invariant quantum money, where prior proofs rely on knowledge-of-path assumptions and path-finding hardness alone is unproven. It shows when path-finding hardness is necessary, then frames state preparation and transfer as the core security assumptions.

Invariant quantum money.

  • The invariant-money framework mints orbit states and verifies them by checking the invariant and testing whether superposed random moves leave the state unchanged.A forger must produce two states that both pass verification at the same serial number.Source: Invariant quantum money · p. 2
  • Earlier proofs add knowledge-of-path assumptions, which are not falsifiable, while security from path-finding hardness alone has no known proof.The paper asks when path-finding is the right assumption and what can replace knowledge of path.Source: Invariant quantum money · p. 2

Results

  • When orbits have a superposable group action containing every move, path-finding hardness is necessary for security.The graph attack extends to coset parameterizations acting through the moves.Source: Results · p. 3
  • Without such a group, even a deterministic path-finder only reduces orbit-state preparation to preparing a uniform superposition over its paths.No suitable group is known for knot orbits.Source: Results · p. 3
  • Every secure scheme must satisfy the preparation assumption, which requires that a forger given a fresh serial number and measured object cannot prepare a state accepted by verification.The preparation assumption is equivalent to security against forgers that measure their banknote first.Source: Results · p. 3
  • If the preparation assumption holds, no fully black-box reduction calling a forger only at its given serial number can derive the transfer assumption, even with superposition and rewinding.Such a reduction cannot produce a genuine banknote for a forger that refuses to act without one.Source: Results · p. 4

Quantum lightning.

  • Liu, Montgomery and Zhandry obtain unforgeability by running the mint and giving its banknote to the forger, a route outside the serial-fixing reduction class.Their lightning result uses an adversarial-instance assumption requiring hardness at every serial number an efficient algorithm can choose [6, Thm. 12].Source: Quantum lightning · p. 4

2 Preliminaries and security model

This section defines invariant-money schemes, their minting and verification procedures, and the security games. It also situates knot and class-group schemes within the framework.

2.1 Invariant quantum money

  • An invariant-money scheme uses combinatorial objects, efficiently computable reversible moves, and an efficiently computable invariant preserved by every move.Objects connected by moves form an orbit; its uniform superposition is the orbit state.Source: §2.1 · pp. 4–5
  • Minting measures the invariant of a uniform superposition over objects, while verification checks the serial number and tests invariance under random moves applied in superposition.A genuine banknote is fixed by every move and is accepted without disturbance.Source: §2.1 · pp. 5–6
  • The knot scheme uses grid diagrams, grid moves, and the Alexander polynomial; the class-group scheme uses elliptic curves, small-degree isogenies, and point counts.Bounded knot-diagram dimensions can leave multiple move-orbits under one serial number; an ideal class group acts on each class-group orbit, with each move acting as a group element.Source: §2.1 · p. 6

2.2 The security model

  • Money unforgeability gives the adversary a minted banknote, whereas lightning unforgeability lets the adversary choose the serial number; path-finding asks for a move word connecting two objects.The security game requires two output states to pass verification at the same serial number.Source: §2.2 · pp. 6–7, §2.1 · p. 6

3 What verification certifies, and design conditions

Verification certifies accepted weight when the walk mixes rapidly, while three scheme-level design conditions identify necessary properties but do not suffice for security. The forger’s central task after measuring is to prepare an orbit state from its seed.

3.2 Design conditions

  • The design conditions require rapid mixing, dispersed serial numbers, and large orbits; dispersion and large orbits are necessary, but the trio is not sufficient for security.Dispersion does not rule out a non-negligible minted fraction on polynomial-size orbits, which random walks can list.Source: §3.2 · pp. 9–10

3.1 Orbit states and accepted weight

  • Rapid mixing makes verification acceptance approximate accepted weight, preventing states orthogonal to every banknote from passing with high probability.Under the condition, acceptance probability and accepted weight differ by at most e^-2n.Source: §3.2 · p. 9

3.2 Design conditions

  • A small spectral gap is not alone an attack; a listable polynomial-size set that the walk rarely leaves can enable forgery, while large orbits and rapid mixing bound this attack’s acceptance.Two copies of the uniform state on J forge when θ(J) = o(1/r); with large orbits and rapid mixing, acceptance is at most |J|/|Ck(x)| + e^-2n.Source: §3.2 · p. 10
  • A scheme can satisfy all three conditions and still be insecure: the constructed linear scheme lets a forger prepare two orbit states that pass verification with certainty.The graph scheme also satisfies the conditions and is broken, although its invariant is known to be efficiently computable only on average.Source: §3.2 · p. 10

3.3 The forger’s problem: orbit state preparation

  • After measuring a banknote, a forger holds its serial number and a seed object; the relevant generation task is to prepare that seed’s orbit state.The prepared orbit state must be unentangled from any ancilla so that the element register is pure.Source: §3.3 · p. 11

4 Path-finding and forgery

This section examines when path-finding can yield forgery, distinguishing settings with suitable group actions from those without them. For group-parameterized orbits it presents a banknote-forgery construction and a subexponential class-group result under GRH; otherwise, path-finding reduces orbit-state preparation to preparing a uniform superposition over paths, but does not itself yield a forgery.

4.1 The graph example

  • For the graph scheme, canonical labelling coherently supplies paths and lets a forger produce a second banknote copy in polynomial time with probability close to 1 on average.The average-case canonical-labelling algorithm runs in polynomial time when stopped after a fixed polynomial time; its unfinished branches have inverse-polynomially small weight on average.Source: §4.1 · pp. 12–13

4.2 Index sets

  • Relabelling labels within each orbit fibre yields a product state exactly when all fibres map to a common image; then the orbit register is the desired orbit state.Under the label condition, all fibres have equal size.Source: §4.2 · p. 13
  • Given a polynomial-time computable section of an index set, orbit-state preparation is equivalent to preparing the uniform state over the section’s image.The section’s image contains one label per orbit object.Source: §4.2 · p. 14

4.3 Orbits parameterized by a group

  • A path-finder that succeeds on every target in a coset parameterization acting through the moves supplies a section by multiplying the group elements corresponding to its returned paths.A path-finder need only succeed on a random target for the theorem’s necessity result, using the group action to reach every target from a random one.Source: §4.3 · pp. 15–16
  • A coset parameterization with a computable section converts the uniform group state into the stabilizer state tensor the orbit state, using one map evaluation, two section evaluations, and O(1) group operations.The conversion is exact.Source: §4.3 · p. 16
  • With a coset parameterization acting through the moves, an inverse-polynomial-success path-finder on a random target gives orbit-state preparation, so security requires path-finding hardness.The theorem also states that security implies negligible average path-finding success for every quantum polynomial-time algorithm.Source: §4.3 · p. 16
  • Measuring a banknote and running the circuit twice produces two registers each within ε_n = 2e^-n + negl(n) of |ψ_k(x)⟩, with accepted weight at least 1 − ε_n.The two runs are independent, and each register passes with probability at least 1 − ε_n.Source: §4.3 · p. 18
  • Under GRH, a quantum algorithm running in 2^o(n) time outputs two registers from a Montgomery and Sharif class-group banknote.The proposition states this subexponential forgery result; the supplied passage does not specify the registers’ acceptance probability.Source: §4.3 · p. 18

4.4 Orbits without a group

  • A path-finder makes orbit-state preparation equivalent to preparing |Im_x⟩, the uniform superposition over paths it outputs from the seed.For deterministic polynomial-time path-finders, the corollary states orbit state preparation is solvable if and only if |Im_x⟩ can be prepared from each seed.Source: §4.4 · pp. 18–19
  • A path-finder does not itself give a forgery: coherent uncomputation yields |0⟩|Im_x⟩ only for an orbit-state input, while random-walk records remain entangled.The recorded walk leaves the element register with accepted weight 1/|C|, no more than the seed alone; efficient relabellings needed to disentangle it are not known.Source: §4.4 · p. 19
  • A classical randomized path-finder succeeding on every pair with probability at least 2/3 can be fixed to a deterministic one that succeeds on every pair.After repetition and checking, a fixed random string fails on some pair with probability at most 2^-n.Source: §4.4 · p. 19

5 Amplification and bounds for orbit state preparation

The section studies orbit-state preparation through verification-based amplification, generic attacks, and an NP-oracle upper bound for rapidly mixing schemes.

5.1 Amplification

  • Inverse-polynomial accepted weight suffices for verification-based amplification to orbit-state preparation when the output stays in the orbit or the invariant is injective on orbits.For rapidly mixing schemes, the stated conditions yield orbit-state preparation for every seed in the family.Source: §5.1 · p. 19

5.2 Generic attacks

  • A second generic attack rebuilds a banknote from its serial number alone using amplitude amplification on the mint, with expected iteration cost O(wt(p)^-1/2).The output is an orbit state only when the invariant is injective on orbits; under dispersion, the expected time is superpolynomial for every serial number.Source: §5.2 · pp. 20–21
  • For rapidly mixing schemes, a generic attack amplifies the seed in time bounded by q |Ck(x)| · r · poly(n), except with probability 2^-Ω(n).Its output element register is within trace distance 2^-Ω(n) of the orbit state.Source: §5.2 · p. 20

5.3 An upper bound from approximate counting

  • For every rapidly mixing invariant money scheme, orbit-state preparation is solvable by a quantum polynomial-time algorithm with an NP oracle.The construction uses approximate prefix counts to prepare a state with sufficient accepted weight for verification-based amplification.Source: §5.3 · pp. 21–22

6 The preparation assumption and security

The section replaces path-finding with an average-case orbit-state preparation assumption and relates it to measure-first and full security. For rapidly mixing schemes, preparation plus a transfer assumption is equivalent to security, but serial-fixing reductions cannot derive transfer from preparation.

6.1 The preparation assumption

  • The preparation assumption is an average-case, inverse-polynomial orbit-state preparation assumption, and under stated conditions a non-negligible violation yields a solver on seeds of non-negligible minting weight.The stated conditions are rapid mixing and either output containment in the seed’s orbit or injectivity of the invariant on orbits.Source: §6.1 · p. 23
  • For rapidly mixing schemes, a public verification challenger accepts with probability within e^-2n of the preparation advantage, making the assumption falsifiable.The challenger samples a minted serial number and measured object, runs the candidate preparer, then verifies its output.Source: §6.1 · p. 24

6.2 Measuring first

  • The preparation assumption is equivalent to security against measure-first adversaries, and a violation yields a measure-first forger even without rapid mixing.The equivalence from the assumption to measure-first security uses rapid mixing.Source: §6.2 · p. 24

6.3 The transfer assumption and the decomposition of security

  • For rapidly mixing schemes, security is equivalent to the preparation and transfer assumptions together, and security implies the preparation assumption.The transfer assumption compares general forgers with measure-first adversaries, which may differ from simply measuring the original forger.Source: §6.3 · p. 25

6.4 A barrier for serial-fixing reductions

  • No serial-fixing reduction that calls a forger only at its given serial number is sound under the preparation assumption, so none derives transfer from preparation.The theorem’s counterexample forger wins with probability 1 while every such reduction produces only negligible accepted weight.Source: §6.4 · p. 26

6.5 Quantum lightning

  • The adversarial-instance assumption implies preparation, and together with rapid mixing it suffices for quantum lightning.Unlike preparation, the adversarial-instance assumption quantifies over serial numbers chosen by an efficient generator.Source: §6.5 · p. 27

7 Conclusion

The conclusion leaves open whether the transfer assumption holds and whether stronger reductions can establish it. It also identifies unresolved questions about orbit-state preparation, design conditions, and extending preparation hardness to adversarially chosen serial numbers.

Open questions

  • Whether mint-serial reductions can derive the transfer assumption remains open; under preparation and rapid mixing, refuting transfer is equivalent to exhibiting a forger.The known serial-fixing reductions cannot derive transfer from preparation.Source: §7 · p. 27
  • No unconditional query lower bound is known for orbit-state preparation when moves are given as an oracle.The cited black-box lower bound is conditional on an orbit-membership query lower bound that is itself open.Source: §7 · p. 28
  • For the knot scheme, both the move-graph spectral gap and dispersion of the Alexander polynomial remain open combinatorial questions.The graph and linear schemes for which all three design conditions are verified are both broken.Source: §7 · p. 28
  • It is open whether preparation implies the adversarial-instance assumption for schemes where no efficient algorithm can list an orbit.The adversarial-instance assumption covers every serial number an efficient algorithm can choose, while preparation averages over minted serial numbers.Source: §7 · p. 28

A Design conditions for the graph scheme

The graph scheme satisfies dispersion, large-orbit, and rapid-mixing conditions. Its verification walk has spectral gap at least 1/(v −1).

Design conditions

Spectral gap

  • The graph scheme’s verification walk has spectral gap at least 1/(v −1).The appendix establishes r∆ ≥ nv/(v −1) ≥ n.Source: A Design conditions for the graph scheme · pp. 30–31
  • For a graph x, the orbit-walk gap follows by identifying its orbit with left cosets of Aut(x) and comparing non-trivial eigenvalues with those of the walk on Sym(v).The appendix states that every non-trivial eigenvalue of the orbit walk is a non-trivial eigenvalue of the corresponding walk on Sym(v).Source: A Design conditions for the graph scheme · p. 31

B The verification walk as an index set

The appendix represents the verification walk as an index set: move-index sequences map a seed to orbit elements, with endpoint probabilities given by the walk. It then bounds how relabelings can help prepare accepted states and shows that recording the path alone does not help.

Index-set construction

  • A T-step verification walk can be indexed by move-register sequences, whose endpoint fibers have sizes determined by the walk probabilities.Under rapid mixing, the appendix chooses T polynomial in n and each endpoint probability is close to 1/|C|.Source: B The verification walk as an index set · pp. 31–32

Relabeling construction

  • Relabelings that align each endpoint fiber with a common index subset of weight ε yield an element register with accepted weight at least ε^2(1 − 2^-n).The bound applies to the state formed by applying the relabeling construction to the walk state.Source: B The verification walk as an index set · p. 32

What the walk does not provide

  • Recording the walk path does not improve the accepted weight of the element register over the walk’s endpoint distribution alone.No polynomial-time family of relabelings with ε ≥ 1/poly(n) is known; such a family would solve orbit-state preparation.Source: B The verification walk as an index set · p. 32
  • The appendix identifies the obstacle as computational: suitable relabelings exist, but no polynomial-time family of them is known.Concatenating fixed-length move-index sequences does not supply such a family because those sequences do not form a group acting on the orbit.Source: B The verification walk as an index set · p. 32

C Subexponential forgery of the class-group scheme

For the class-group scheme, forging can be reduced to computing a discrete logarithm, but the known algorithms are subexponential rather than polynomial time. Under the generalized Riemann hypothesis, a coherent construction yields a banknote that passes verification with probability exponentially close to one.

C Subexponential forgery of the class-group scheme

  • With trivial stabilizers, finding the class-group element mapping one curve to another is the group-action discrete logarithm, and solving it would forge the scheme [11, §2.2, §9.2].The class-group action makes each isogeny class a single orbit under the generalized Riemann hypothesis; the best known algorithms are subexponential, [10, §1.5].Source: C Subexponential forgery of the… · p. 33
  • Under the generalized Riemann hypothesis, the construction uses coherent class-group action and section subroutines taking 2^o(n) time, plus polynomial-time preparation of |W⟩.The action and section subroutines are run with error reduced to 2^-Ω(n) on every input.Source: C Subexponential forgery of the… · p. 33
  • Each of two registers passes verification with probability at least 1 − 2^-Ω(n), so both pass with probability at least 1 − 2^-Ω(n).The registers are each within trace distance 2^-Ω(n) of the target banknote state.Source: C Subexponential forgery of the… · p. 33

D Proof of Lemma 5.1

The lemma uses a coherent verifier to approximate a rotation about the target state, then applies fixed-point amplitude amplification. An overlap lower bound controls the number of amplification steps and the required verifier accuracy.

D Proof of Lemma 5.1

  • The initial state |Ω⟩ has squared overlap at least η with the target subspace Π′, and the proof works within V = span{|Ω⟩, Π′|Ω⟩}.Here Π′ projects onto the target banknote state together with the ancilla register.Source: D Proof of Lemma 5.1 · p. 33
  • The verifier computes the invariant into a fresh register and runs the mixing test coherently, flagging invariant mismatches or rejected rounds.Each round uses a fresh copy of the move register, without measurement.Source: D Proof of Lemma 5.1 · p. 33
  • The coherent verifier implements the target rotation up to O(ξ) error on inputs with fresh ancillas.Fixed-point amplitude amplification uses N = O(η^-1/2 log(1/δ)) steps; setting ξ := δη^1/2 / log(1/δ) controls accumulated error.Source: D Proof of Lemma 5.1 · p. 34
  • After amplification, the normalized target component has the form |ψk⟩⊗|ax⟩, with the ancilla state obtained by projecting the initial state onto |ψk⟩.The resulting circuit is uniform and depends on x only through its input.Source: D Proof of Lemma 5.1 · p. 34
Loading 2609.39774v2…