OWSG ⇔ one-time signatures with quantum public keys

Equivalence · quantum setting · MY22 · security loss: a factor 2 from one-way state generators to signatures; none in the other direction

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.