Succinct Arguments for BatchQMA and Friends under 8 rounds with Professor Rishab Goyal

Wed 2:30pm - 3:30pm Morgridge Hall - 3610 (same time and location every week), Sep 17 

Abstract: 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.