Paper 2019/834

Succinct Arguments in the Quantum Random Oracle Model

Alessandro Chiesa, Peter Manohar, and Nicholas Spooner


Succinct non-interactive arguments (SNARGs) are highly efficient certificates of membership in non-deterministic languages. Constructions of SNARGs in the random oracle model are widely believed to be post-quantum secure, provided the oracle is instantiated with a suitable post-quantum hash function. No formal evidence, however, supports this belief. In this work we provide the first such evidence by proving that the SNARG construction of Micali is unconditionally secure in the *quantum* random oracle model. We also prove that, analogously to the classical case, the SNARG inherits the zero knowledge and proof of knowledge properties of the PCP underlying the Micali construction. We thus obtain the first zero knowledge SNARG of knowledge (zkSNARK) that is secure in the quantum random oracle model. Our main tool is a new lifting lemma that shows how, for a rich class of oracle games, we can *generically* deduce security against quantum attackers by bounding a natural classical property of these games. This means that in order to prove our theorem we only need to establish *classical* properties about the Micali construction. This approach not only lets us prove post-quantum security but also enables us to prove explicit bounds that are tight up to small factors. We additionally use our techniques to prove that SNARGs based on interactive oracle proofs (IOPs) with round-by-round soundness are unconditionally secure in the quantum random oracle model. This result establishes the post-quantum security of many SNARGs of practical interest.

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2019
succinct argumentsquantum random oracle modelprobabilistically checkable proofs
Contact author(s)
alexch @ berkeley edu
2020-01-14: last of 4 revisions
2019-07-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alessandro Chiesa and Peter Manohar and Nicholas Spooner},
      title = {Succinct Arguments in the Quantum Random Oracle Model},
      howpublished = {Cryptology ePrint Archive, Paper 2019/834},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.