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.
For any language computable in time t=t(n), we construct a multi-prover interactive proof (MIP) that is sound against no-signaling strategies, where the running time of the provers is poly(t), the number of provers is polylog(t), and the running time of the verifier is n*polylog(t).
In particular, this shows that the class of languages that have polynomial-time MIPs that are sound against no-signaling strategies, is exactly EXP. Previously, this class was only known to contain PSPACE.
To convert our MIP into a 1-round delegation scheme, we use the method suggested by Aiello et-al (ICALP, 2000), which makes use of a PIR scheme. This method lacked a proof of security. We prove that this method is secure assuming the underlying MIP is secure against no-signaling provers.Category / Keywords: Delegation, Probabilistic Proof Systems, Interactive Arguments Date: received 22 Dec 2013, last revised 1 May 2015 Contact author: ron rothblum at weizmann ac il Available format(s): PDF | BibTeX Citation Note: Corrected minor error in verifier's running time. Version: 20150501:061254 (All versions of this report) Discussion forum: Show discussion | Start new discussion