Events at Physics |
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 communication 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.