Efficiently Batching Unambiguous Interactive Proofs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915569528209408 |
|---|---|
| author | Berger, Bonnie Goyal, Rohan Hong, Matthew M. Kalai, Yael Tauman |
| author_facet | Berger, Bonnie Goyal, Rohan Hong, Matthew M. Kalai, Yael Tauman |
| contents | We show that if a language $L$ admits a public-coin unambiguous interactive proof (UIP) with round complexity $\ell$, where $a$ bits are communicated per round, then the batch language $L^{\otimes k}$, i.e. the set of $k$-tuples of statements all belonging to $L$, has an unambiguous interactive proof with round complexity $\ell\cdot\mathsf{polylog}(k)$, per-round communication of $a\cdot \ell\cdot\mathsf{polylog}(k) + \mathsf{poly}(\ell)$ bits, assuming the verifier in the $\mathsf{UIP}$ has depth bounded by $\mathsf{polylog}(k)$. Prior to this work, the best known batch $\mathsf{UIP}$ for $L^{\otimes{k}}$ required communication complexity at least $(\mathsf{poly}(a)\cdot k^ε + k) \cdot \ell^{1/ε}$ for any arbitrarily small constant $ε>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})^δ}$ for a small $δ>0$ significantly smaller than $1/2$ (Reingold-Rothblum-Rothblum, STOC 2016). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_19075 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficiently Batching Unambiguous Interactive Proofs Berger, Bonnie Goyal, Rohan Hong, Matthew M. Kalai, Yael Tauman Computational Complexity Cryptography and Security We show that if a language $L$ admits a public-coin unambiguous interactive proof (UIP) with round complexity $\ell$, where $a$ bits are communicated per round, then the batch language $L^{\otimes k}$, i.e. the set of $k$-tuples of statements all belonging to $L$, has an unambiguous interactive proof with round complexity $\ell\cdot\mathsf{polylog}(k)$, per-round communication of $a\cdot \ell\cdot\mathsf{polylog}(k) + \mathsf{poly}(\ell)$ bits, assuming the verifier in the $\mathsf{UIP}$ has depth bounded by $\mathsf{polylog}(k)$. Prior to this work, the best known batch $\mathsf{UIP}$ for $L^{\otimes{k}}$ required communication complexity at least $(\mathsf{poly}(a)\cdot k^ε + k) \cdot \ell^{1/ε}$ for any arbitrarily small constant $ε>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})^δ}$ for a small $δ>0$ significantly smaller than $1/2$ (Reingold-Rothblum-Rothblum, STOC 2016). |
| title | Efficiently Batching Unambiguous Interactive Proofs |
| topic | Computational Complexity Cryptography and Security |
| url | https://arxiv.org/abs/2510.19075 |