Mini-scheme + DS ⇒ Public-key QM

Fully-black-box reduction · quantum setting · AC12 · security loss: polynomial: a counterfeiter that receives banknotes and outputs succeeds with probability at most times the forger’s advantage plus times the mini-scheme counterfeiter’s

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