Post-quantum iO + Post-quantum injective OWF ⇒ QM mini-scheme
Statement
If post-quantum indistinguishability obfuscation for all polynomial-size circuits and post-quantum injective one-way functions exist, then a secure quantum money mini-scheme exists — Zha19.
Given an injective one-way function, iO applied to suitably padded circuits is a subspace-hiding obfuscator : for all efficient that choose a subspace of dimension , the advantage of in distinguishing from , for a uniformly random subspace of dimension , is negligible whenever is exponential — Zha19. In the mini-scheme, for a prime , is a uniformly random subspace of dimension , the banknote is with serial number , and verification runs the first program on the state, applies the quantum Fourier transform over , which maps to , runs the second program, and undoes the transform. If is secure against quantum adversaries for and some with and exponential, then for all efficient quantum given one banknote, the probability that outputs two possibly entangled registers that both pass verification under its serial number is negligible, so the hidden-subspace scheme is a secure mini-scheme — Zha19. The honest banknote passes both obfuscated membership tests with certainty, since iO preserves functionality, and the inverse transform restores it exactly, so the mini-scheme is perfectly correct — Zha19 (arXiv v3, Section 6.3).
Notes
- Injectivity enters in the proof that iO is a subspace-hiding obfuscator: for , the program accepting iff differs from the all-zero program only at , and iO is a differing-inputs obfuscator for pairs of circuits differing on one input, so the two obfuscations are indistinguishable while is hard to find — Zha19, who attribute the differing-inputs step to BCP14.
- Signing serial numbers turns the mini-scheme into a public-key quantum money scheme (Mini-scheme + DS ⇒ Public-key QM): a secure mini-scheme and a digital signature scheme unforgeable by quantum adversaries making nonadaptive classical chosen-message queries give a secure public-key scheme, whose bank key pair is the signature key pair and whose banknotes are fresh mini-scheme banknotes with a signature on their serial numbers — AC12. A one-way function secure against quantum adversaries, such as the injective one, gives such a signature scheme by the construction of Rom90, whose security reduction is black-box — AC12.