Delegation with (Nearly) Optimal Time/Space Overhead
Justin Holmgren
Abstract:
Consider a scenario in which a client wants to utilize a powerful, but untrusted, server to perform computations which are beyond the client's ability. Since the client does not trust the server, we would like the server to certify the correctness of the result. We would like the verification procedure to be extremely efficient, whereas the complexity of proving shouldn’t be much larger than that of computing.
Assuming LWE, we construct a one-round argument-system for proving the correctness of any time T and space S computation, in which both the verifier and prover are extremely efficient. In particular, the prover runs in time T*poly(k) and space S + poly(k), where k is a security parameter.
Our result builds on a previous line of work initiated by Kalai et al. (STOC, 2014). The prover in all of these works runs in time T^c for a large constant c (where c is at least 3). As an additional contribution we significantly simplify a central construct that appears in all of these works.
Based on joint work with Ron Rothblum.