OWSG ⇔ one-time signatures with quantum public keys
Statement
One-way state generators exist if and only if one-time-secure digital signatures with quantum public keys exist — MY22. From a generator , a scheme for one-bit messages samples two keys as , outputs as , signs with , and verifies on by running on the -th state of . From a scheme for one-bit messages, the generator uses as the key and as the state, and accepts on a state if the signature on the message verifies under it.
Sketch
From signatures to generators: an inverter that outputs from copies of gives a forger that queries a signature on and outputs on the message . From generators to signatures: given a forger that asks for a signature on and forges on , the reduction embeds the challenge states of the generator at a uniformly random position , generates the other position itself, answers the query with its own key when , aborts otherwise, and outputs the forged signature as the inverse; it succeeds with half the forger’s probability.
Notes
- MY22a gave the construction of signatures from pure generators with uniformly random keys and verification by projection, and, with PRS ⇒ OWSG, one-time-secure signatures with quantum public keys from PRS generators with output length , .
- One-time signatures with weak security, whose forgers succeed with probability at most for a fixed polynomial , already give one-way state generators — MY22.