Efficiently Batching Unambiguous Interactive Proofs

We show that if a language $\mathcal{L}$ admits a public-coin unambiguous interactive proof (UIP) with round complexity $\ell$, where a bits are communicated per round, then the batch language ${\mathcal{L}}^{\otimes k}$, i. e. the set of k-tuples of statements all belonging to $\mathcal{L}$, has an unambiguous interactive proof with round complexity $\ell \cdot$ polylog $(k)$, per-round communication of $a \cdot \ell \cdot$ polylog $(k)+$ poly $(\ell)$ bits, assuming the verifier in the UIP has depth bounded by polylog $(k)$. Prior to this work, the best known batch UIP for ${\mathcal{L}}^{\otimes k}$ required communication complexity at least ($\operatorname{poly}(a) \cdot k^{\epsilon}+k$) $\cdot \ell^{1 / \epsilon}$ for any arbitrarily small constant $\epsilon\gt 0$ (Reingold-Rothblum-Rothblum, STOC 2016). As a corollary of our result, we obtain a doubly efficient proof system, that is, a proof system whose proving overhead is polynomial in the time of the underlying computation, for any language computable in polynomial space and in time at most $n^{O\left(\sqrt{\frac{\log n}{\log \log n}}\right)}$. This expands the state of the art of doubly efficient proof systems: prior to our work, such systems were known for languages computable in polynomial space and in time $n^{(\log n)^{\delta}}$ for a small $\delta\gt 0$ significantly smaller than 1/2 (Reingold-Rothblum-Rothblum, STOC 2016).

Authors

• Bonnie Berger
• Rohan Goyal
• Matthew M. Hong
• Yael Tauman Kalai

Keywords

• Computer science
• Polynomials
• Complexity theory
• Computational efficiency
• Complex Communication
• Space Of Polynomials
• High Probability
• Characteristic Zero
• Hamming Distance
• Multilinear
• False Claims
• Finite Field
• Representative Subset
• End Of Each Iteration
• Transition Step
• Bit Length
• Turing Machine
• Message Length
• Notion Of Distance
• Time Machine
• Reduction Protocol
• Folding Step
• Succinct Description
• interactive proofs
• delegation
• doubly efficient interactive proofs