QROM ⇒ zk-SNARK (Micali’s construction in the QROM)

Free reduction · random oracle model · CMS19

Statement

In the quantum random-oracle model, Micali’s construction is unconditionally secure against quantum provers making polynomially many superposition queries to the oracle, and it inherits the zero knowledge and the proof of knowledge of the underlying PCP; instantiated with a zero-knowledge PCP of knowledge it is a zk-SNARK with no setup, the first shown secure in the QROM — CMS19. The same lifting lemma shows that SNARGs obtained from IOPs with round-by-round soundness are unconditionally secure in the QROM — CMS19.

Notes

• Proof length and prover and verifier costs are those of the classical construction, ROM ⇒ SNARK (CS proofs) — standard; CMS19 prove explicit soundness bounds tight up to small factors — CMS19.
• The quantum random-oracle model gives the adversary superposition access to the oracle; a scheme secure against classical oracle access can be insecure there — BDF+11.