Nicholas Spooner

An important challenge in quantum cryptography is the construction of publicly-verifiable NIZKs for QMA. Classically, one can construct NIZKs for NP in the random oracle model (and sometimes in the standard model) by compiling an honest-verifier ZK (HVZK) Σ-protocol for NP using the Fiat-Shamir transformation. Broadbent and Grilo introduced a quantum analog of a Σ-protocol (which they call a Ξ-protocol) in which the prover's first message is quantum, and show that HVZK Ξ-protocols exist for QMA. However, it is not clear how to compile such protocols into NIZKs in the (Q)ROM, because the Fiat-Shamir transformation seems to be incompatible with quantum messages. In this work we give formal evidence that this is indeed the case: we show that if generic "Fiat--Shamir-like" transformations for quantum protocols exist in the QROM (with small constant completeness error) then NP ⊆ BQP.

We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model when instantiated with any probabilistically checkable proof and any collapsing hash function (which in turn exist based on the post-quantum hardness of Learning with Errors). At the heart of our proof is a new "measure-and-repair" quantum rewinding procedure that achieves asymptotically optimal knowledge error.