Title: How to Delegate Computations: The Power of No-Signaling Proofs
Speaker: Ran Raz, IAS
Date: Wednesday, March 26, 2014 11:00-12:00pm
Location: CoRE Bldg, Room 301A, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The Martians built an amazingly fast computer and they run it to answer the great question of life, the universe and everything. They claim that the answer is 42. Will they be able to convince us that 42 is the right answer, assuming that we do not have sufficient computational power to run the computation ourselves, and that we do not trust Martians?
The problem of delegating computation is a central problem in cryptography. It considers a setting where one party, the delegator, wishes to delegate the computation of a function to another party, the worker. The challenge is that the delegator may not trust the worker, and thus it is desirable to have the worker ``prove'' that the computation was done correctly.
We show a curious connection between that problem and the model of multi-prover interactive proofs that are sound against no-signaling (cheating) strategies, a model that was studied in relation to multi-prover interactive proofs with provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light.
We prove that the class of languages that have polynomial-time multi-prover interactive proofs, that are sound against no-signaling strategies, is exactly EXP. We use this to give a 1-round delegation protocol for every language in EXP.
Joint work with Yael Tauman Kalai and Ron Rothblum
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S14/