Paper 2026/1287
Towards a Doubly Efficient IP=PSPACE
, Massachusetts Institute of Technology, Massachusetts Institute of Technology, Massachusetts Institute of Technology, Massachusetts Institute of TechnologyAbstract
We show that every language in PSPACE decidable by a Turing machine in time $T(n)=n^{O(\log n)}$ admits a doubly efficient interactive proof system: the prover runs in time polynomial in T(n), and the verifier runs in time polynomial in n. This extends the best previously known regime for such proof systems from $T(n)=n^{O(\sqrt{\log n / \log\log n})}$, established by Berger, Goyal, Hong, and Kalai (FOCS 2025), to $T(n)=n^{O(\log n)}$. Beyond improving the range of T, our protocol is substantially simpler than previous doubly efficient proofs for time-bounded PSPACE. Earlier constructions proceed indirectly: they first build batch interactive proofs and then invoke them as a black box to obtain doubly efficient protocols. In contrast, we give a direct construction. This not only simplifies the proof but also points to a more promising route for future improvements.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Doubly Efficient IP
- Contact author(s)
-
cliyan @ mit edu
matthong @ mit edu
yaelism @ gmail com
zoexi @ mit edu - History
- 2026-06-22: approved
- 2026-06-19: received
- See all versions
- Short URL
- https://ia.cr/2026/1287
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/1287,
author = {Liyan Chen and Matthew M. Hong and Yael Tauman Kalai and Zoe Xi},
title = {Towards a Doubly Efficient {IP}={PSPACE}},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1287},
year = {2026},
url = {https://eprint.iacr.org/2026/1287}
}
