Non-Interactive Zero-Knowledge Proofs in the Quantum Random Oracle Model

Abstract

We present a construction for non-interactive zero-knowledge proofs of knowledge in the random oracle model from general sigma-protocols. Our construction is secure against quantum adversaries. Prior constructions (by Fiat-Shamir and by Fischlin) are only known to be secure against classical adversaries, and Ambainis, Rosmanis, Unruh (FOCS 2014) gave evidence that those constructions might not be secure against quantum adversaries in general. To prove security of our constructions, we additionally develop new techniques for adaptively programming the quantum random oracle.