International Association
for Cryptologic Research

We study the problem of minimizing round complexity in the context of succinct classical argument systems for quantum computation. All prior works either require at least 8 rounds of interaction between the quantum prover and classical verifier, or rely on the idealized quantum random oracle model (QROM). We design: 1. A 4-round public-coin (except for the first message) argument system for batchQMA languages. Under the post-quantum hardness of functional encryption and learn- ing with errors (LWE), we achieve optimal communication complex- ity (i.e., all messages sizes are independent of batch size). If we only rely on the post-quantum hardness of LWE, then we can make all messages except the verifier’s first message to be independent of the batch size. 2. A 6-round private-coin argument system for monotone policy batchQMA languages, under the post-quantum hardness of LWE. The commu- nication complexity is independent of the batch size as well as the monotone circuit size. Unlike all prior works, we do not rely on “state-preserving” succinct arguments of knowledge (AoKs) for NP for proving soundness. Our main technical contribution is a new approach to prove soundness without rewinding cheating provers. We bring the notion of straight-line partial extractability to argument systems for quantum computation.