Quantum-secure OWF ⇒ Nonadaptive post-quantum DS

Fully-black-box reduction · quantum setting · AC12

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).