Secret-based mini-scheme with classical serial numbers ⇒ OWF

Fully-black-box reduction · quantum setting · AC12

Statement

Let be a secret-based mini-scheme, whose samples a uniform classical string and runs a generation algorithm on , which outputs a banknote determined by , with classical serial numbers: the scheme includes a deterministic classical polynomial-time algorithm with . If is unforgeable and has completeness error at most , then is one-way against efficient quantum adversaries — AC12 (arXiv v3, Proposition 14).

Sketch

A counterfeiter given that recovers from can mint further banknotes — AC12. Any with serves as well: the banknote minted from has serial number and passes with probability at least , so two independent such banknotes break unforgeability — standard.

Notes

  • Rompel’s signatures from a function one-way against quantum adversaries are secure against quantum forgers that submit one classical list of messages, since Rompel’s reduction is black-box (Quantum-secure OWF ⇒ Nonadaptive post-quantum DS) — AC12 (arXiv v3, Theorem 2). Together with Mini-scheme + DS ⇒ Public-key QM, they make a secure secret-based mini-scheme with classical serial numbers alone sufficient for public-key quantum money — AC12 (arXiv v3, Proposition 17).
  • is a quantum algorithm, so a secret-based mini-scheme guarantees only that is computable in quantum polynomial time. AC12 obtain the signatures above from a classical one-way function secure against quantum inverters, so that step applies when a classical polynomial-time algorithm computes from , as in the oracle mini-scheme of AC12, whose reads off a classical oracle — AC12.