Mini-scheme + DS ⇒ Public-key QM
Statement
Let be a quantum money mini-scheme and a signature scheme. The standard construction is the public-key quantum money scheme whose key generation is that of , ; runs and outputs the banknote ; and accepts iff and both accept. If is unforgeable and is unforgeable against efficient quantum forgers that submit one classical list of messages to the signing oracle, then is unforgeable — AC12 (arXiv v3, Theorem 16). In particular, it suffices that is EUF-CMA against efficient quantum adversaries making classical signing queries (Post-quantum DS ⇒ Nonadaptive post-quantum DS) — folklore. If is -correct and is -correct, is -correct, by a union bound over its two verifiers — standard.
Sketch
Let a counterfeiter receive banknotes and output more than valid ones. If a valid output carries a serial number outside the given ones, a forger that mints the banknotes itself, with one list of signing queries for their serial numbers, and outputs the serial number and signature of a uniformly chosen output breaks . Otherwise two valid outputs share a given serial number, by pigeonhole, and a mini-scheme counterfeiter that places its challenge at a uniformly chosen one of the positions, signs all serial numbers under a key pair it samples, and outputs the money states of two uniformly chosen outputs breaks — AC12.
Notes
- The construction, without a security proof, is from LAF+10 and FGH+12 — AC12.
- Conversely, an unforgeable pointwise-complete public-key scheme yields an unforgeable mini-scheme, whose serial number is a fresh public key and whose money state is one banknote minted under it (Public-key QM ⇒ Mini-scheme) — AC12.
- For a secure secret-based mini-scheme, whose samples a uniform classical string and outputs a banknote determined by , with classical serial numbers, the map is one-way against quantum adversaries (Secret-based mini-scheme with classical serial numbers ⇒ OWF), and Rompel’s signatures from such a function 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). The mini-scheme alone therefore suffices for public-key quantum money — AC12 (arXiv v3, Proposition 17).