Delegation Paradigm

Delegation Paradigm

In an emerging computing paradigm, computational capabilities, from processing power to storage capacities, are offered to users over communication networks as a service. This new paradigm holds enormous promise for increasing the utility of computationally weak devices. A natural approach is for weak devices to delegate expensive tasks, such as storing a large file or running a complex computation, to powerful servers connected to the same network. While the delegation approach seems promising, it raises an immediate concern: when and how can a weak device verify that a computational task was completed correctly? This practically motivated question touches on foundational questions in cryptography and complexity theory.


Goldwasser, S., Gutfreund, D., Healy, A., Kaufman, T., and Rothblum, G.N. “A (De)constructive Approach to Program Checking.” 40th ACM Symposium on Theory of Computing (STOC 2008), pages 143-152, Victoria, (BC), Canada, May 2008.

Goldwasser, S., Tauman Kalai, Y., and Rothblum, G. “Delegating Computation: Interactive Proofs for Muggles.” 40th ACM Symposium on Theory of Computing (STOC 2008), pages 113-122, Victoria, (BC), Canada, May 2008.


Goldwasser, S., Lin, H., and Rubinstein, A. “Delegation of Computation without Rejection Problem from Designated Verifier CS-Proofs.” IACR Cryptology ePrint Archive 2011: 456, 2011.