1-Round Delegation for Deterministic Computations

Abstract:

We give a 1-round delegation scheme for every language computable in time t=t(n),
where the running time of the prover is poly(t) and
the running time of the verifier is n\cdot polylog(t), where n is the input size.
The soundness of our scheme is computational, and relies on the existence of a sub-exponentially secure (computational) PIR scheme.

The proof exploits a curious connection between the problem of computation
delegation and the model of multi-prover interactive proofs that are sound
against *no-signaling* (cheating) strategies,
a model that was studied in the context of multi-prover interactive proofs with
provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light.

This is joint work with Ran Raz and Ron Rothblum.