1-Round Delegation for Deterministic Computations

Tuesday, October 22, 2013 - 4:15pm to 5:15pm
Refreshments: 
3:45pm in 32-G449 (Patil/Kiva)
Location: 
G449
Speaker: 
Yael Kalai, Microsoft Research

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.