Quantum-secure OWF ⇒ Nonadaptive post-quantum DS
Statement
If there is a classical function that is one-way against quantum adversaries, there is a signature scheme that is secure against nonadaptive quantum chosen-message attacks — AC12 (arXiv v3, Theorem 2). The scheme is Rompel’s construction of signatures from any one-way function — Rom90 — and its security reduction is black-box, so nothing in it depends on the forger being classical — AC12. Honest signatures in Rompel’s scheme always verify, so it is perfectly correct — standard.
Notes
- Against classical forgers, the same construction gives EUF-CMA signatures from any one-way function (OWF ⇒ DS) — Rom90.
- The reduction relativizes, so relative to a random oracle, which gives a one-way function secure against quantum inverters, there is a signature scheme secure against nonadaptive quantum chosen-message attacks — AC12 (arXiv v3, Theorem 3).