TY - JOUR
T1 - How to Delegate Computations
T2 - The Power of No-Signaling Proofs
AU - Kalai, Yael Tauman
AU - Raz, Ran
AU - Rothblum, Ron D.
N1 - Funding Information:
A preliminary version of this work appeared in STOC 2014 [47]. Ran Raz parts of this research were conducted while the author was a visiting professor at the Institute for Advanced Study, Princeton, NJ. Research supported by a Israel Science Foundation grant, by the I-CORE Program of the Planning and Budgeting Committee and the Israel Science Foundation, by the Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award, and by NSF grant numbers CCF-0832797, DMS-0835373, CCF-1714779. Ron D. Rothblum parts of this research were conducted while the author was a student at the Weizmann Institute and while visiting Microsoft Research. This research was partially supported by the Minerva Foundation with funds from the Federal German Ministry for Education and Research. Authors’ addresses: Y. T. Kalai, Microsoft Research and MIT; email: yael@microsoft.co; R. Raz, Princeton University and the Weizmann Institute of Science Israel; email: ran.raz.mail@gmail.com; R. D. Rothblum, Technion - Israel Institute of Technology; email: rothblum@cs.technion.ac.il. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2021 Association for Computing Machinery. 0004-5411/2021/11-ART1 $15.00 https://doi.org/10.1145/3456867
Publisher Copyright:
© 2021 Association for Computing Machinery.
PY - 2022/2
Y1 - 2022/2
N2 - We construct a 1-round delegation scheme (i.e., argument-system) 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 · polylog(t). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval (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.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.
AB - We construct a 1-round delegation scheme (i.e., argument-system) 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 · polylog(t). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval (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.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.
KW - Delegating computations
KW - no-signaling proofs
UR - http://www.scopus.com/inward/record.url?scp=85124872219&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85124872219&partnerID=8YFLogxK
U2 - 10.1145/3456867
DO - 10.1145/3456867
M3 - Article
AN - SCOPUS:85124872219
SN - 0004-5411
VL - 69
JO - Journal of the ACM
JF - Journal of the ACM
IS - 1
M1 - 1
ER -