Computer Science/Discrete Mathematics Seminar I

We construct very efficient argument systems for proving the correctness of bounded-space computations, based on the existence of one-way functions. Our argument system applies to general computations running in time T and space S. The communication and verification time are poly-logarithmic in T and linear in S. The honest prover's running time is polynomial in T, so the protocol is doubly-efficient. All complexities are polynomial in the security parameter of the one-way function, and verification is also linear in the input length.

Prior to this work, doubly-efficient argument systems with poly-logarithmic dependence on T required assuming (at least) the existence of collision-resistant hash functions [Kilian, STOC 1992]. For unconditionally sound doubly-efficient protocols, the RRR protocol for bounded-space computations [Reingold, Rothblum and Rothblum, STOC 2016] has communication and verification complexities that grow with an arbitrarily small constant power of T.