Verifiable computing

Verifiable computing (or verified computation or verified computing) enables a computer to offload the computation of some function, to other perhaps untrusted clients, while maintaining verifiable results. The other clients evaluate the function and return the result with a proof that the computation of the function was carried out correctly. The introduction of this notion came as a result of the increasingly common phenomenon of "outsourcing" computation to untrusted users in projects such as SETI@home and also to the growing desire of weak clients to outsource computational tasks to a more powerful computation service like in cloud computing. The concept dates back to work by Babai et al.,[1] and has been studied under various terms, including "checking computations" (Babai et al.), "delegating computations",[2] "certified computation",[3] and verifiable computing. The term verifiable computing itself was formalized by Rosario Gennaro, Craig Gentry, and Bryan Parno,[4] and echoes Micali's "certified computation".[3]

Motivation and overview

The growing desire to outsource computational tasks from a relatively weak computational device (client) to a more powerful computation services (worker), and the problem of dishonest workers who modify their client's software to return plausible results without performing the actual work[5] motivated the formalization of the notion of Verifiable Computation.[4]

Verifiable computing is not only concerned with getting the result of the outsourced function on the client's input and the proof of its correctness, but also with the client being able to verify the proof with significantly less computational effort than computing the function from scratch.

Considerable attention has been devoted in verifying the computation of functions performed by untrusted workers including the use of secure coprocessors,[6][7] Trusted Platform Modules (TPMs),[8] interactive proofs,[9][10] probabilistically checkable proofs,[11][12] efficient arguments,[13][14] and Micali's CS proofs.[15] These verifications are either interactive which require the client to interact with the worker to verify the correctness proof,[13][14] or are non-interactive protocols which can be proven in the random oracle model.[15]

Verification by replication

The largest verified computation (SETI@home) uses verification by replication.

The SETI@home verification process involves one client machine and many worker machines. The client machine sends identical workunits to multiple computers (at least 2).

When not enough results are returned in a reasonable amount of time—due to machines accidentally turned off, communication breakdowns, etc.—or the results do not agree—due to computation errors, cheating by submitting false data without actually doing the work, etc.—then the client machine sends more identical workunits to other worker machines. Once a minimum quorum (often 2) of the results agree, then the client assumes those results (and other identical results for that workunit) are correct. The client grants credit to all machines that returned the correct results.

Verifiable computation

Gennaro et al.[4] defined the notion of verifiable computation scheme as a protocol between two polynomial time parties to collaborate on the computation of a function F: {0,1}ⁿ → {0,1}^m. This scheme consists of three main phases:

1. Preprocessing. This stage is performed once by the client in order to calculate some auxiliary information associated with F. Part of this information is public to be shared with the worker while the rest is private and kept with the client.
2. Input preparation. In this stage, the client calculates some auxiliary information about the input of the function. Part of this information is public while the rest is private and kept with the client. The public information is sent to the worker to compute F on the input data.
3. Output computation and verification. In this stage, the worker uses the public information associated with the function F and the input, which are calculated in the previous two phases, to compute an encoded output of the function F on the provided input. This result is then returned to the client to verify its correctness by computing the actual value of the output by decoding the result returned by the worker using the private information calculated in the previous phases.

The defined notion of verifiable computation scheme minimizes the interaction between the client and the worker into exactly two messages, where a single message sent from each party to the other party during the different phases of the protocol.[4]

An example scheme based on fully homomorphic encryption

Gennaro et al.[4] defined a verifiable computation scheme for any function F using Yao's garbled circuit[16][17] combined with a fully homomorphic encryption system.

This verifiable computation scheme VC is defined as follows:[4]

VC = (KeyGen, ProbGen, Compute, Verify) consists of four algorithms as follows:

1. KeyGen(F, λ) → (PK, SK): The randomized key generation algorithm generates two keys, public and private, based on the security parameter λ. The public key encodes the target function F and is sent to the worker to compute F. On the other hand, the secret key is kept private by the client.
2. ProbGenSK(x) → (σx, τx): The problem generation algorithm encodes the function input x into two values, public and private, using the secret key SK. The public value σx is given to the worker to compute F(x) with, while the secret value τx is kept private by the client.
3. Compute(PK, σx) → σy: The worker computes an encoded value σy of the function's output y = F(x) using the client's public key PK and the encoded input σx.
4. Verify_SK(τx,σy) → y ∪ ⊥: The verification algorithm converts the worker's encoded output σy into the actual output of the function F using both the secret key SK and the secret “decoding” τx. It outputs y = F(x) if the σy represents a valid output of F on x, or outputs ⊥ otherwise.

The protocol of the verifiable computations scheme defined by Gennaro et al.[4] works as follows:

The function F should be represented as a Boolean circuit on which the key generation algorithm would be applied. The key generation algorithm runs Yao's garbling procedure over this Boolean circuit to compute the public and secret keys. The public key (PK) is composed of all the ciphertexts that represent the garbled circuit, and the secret key (SK) is composed of all the random wire labels. The generated secret key is then used in the problem generation algorithm. This algorithm first generates a new pair of public and secret keys for the homomorphic encryption scheme, and then uses these keys with the homomorphic scheme to encrypt the correct input wires, represented as the secret key of the garbled circuit. The produced ciphertexts represent the public encoding of the input (σx) that is given to the worker, while the secret key (τx) is kept private by the client. After that, the worker applies the computation steps of the Yao's protocol over the ciphertexts generated by the problem generation algorithm. This is done by recursively decrypting the gate ciphertexts until arriving to the final output wire values (σy). The homomorphic properties of the encryption scheme enable the worker to obtain an encryption of the correct output wire. Finally, the worker returns the ciphertexts of the output to the client who decrypts them to compute the actual output y = F(x) or ⊥.

The definition of the verifiable computation scheme states that the scheme should be both correct and secure. Scheme Correctness is achieved if the problem generation algorithm produces values that enable an honest worker to compute encoded output values that will verify successfully and correspond to the evaluation of F on those inputs. On the other hand, a verifiable computation scheme is secure if a malicious worker cannot convince the verification algorithm to accept an incorrect output for a given function F and input x.

Practical verifiable computing

Although it was shown that verifiable computing is possible in theory (using fully homomorphic encryption or via probabilistically checkable proofs), most of the known constructions are very expensive in practice. Recently, some researchers have looked at making verifiable computation practical. One such effort is the work of UT Austin researchers.[18] The authors start with an argument system based on probabilistically checkable proofs and reduce its costs by a factor of 10²⁰. They also implemented their techniques in the Pepper system. The authors note that "Our conclusion so far is that, as a tool for building secure systems, PCPs and argument systems are not a lost cause."

The overall area, which now includes a number of implementations by different groups, has been surveyed.[19]

References

1. Babai, László; Fortnow, Lance; Levin, Leonid A.; Szegedy, Mario (1991-01-01). Checking Computations in Polylogarithmic Time. Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing. STOC '91. New York, NY, US: ACM. pp. 21–32. CiteSeerX 10.1.1.42.5832. doi:10.1145/103418.103428. ISBN 978-0897913973.
2. Goldwasser, Shafi; Kalai, Yael Tauman; Rothblum, Guy N. (2008-01-01). Delegating Computation: Interactive Proofs for Muggles. Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. STOC '08. New York, NY, US: ACM. pp. 113–122. doi:10.1145/1374376.1374396. ISBN 9781605580470.
3. Micali, S. (2000-01-01). "Computationally Sound Proofs". SIAM Journal on Computing. 30 (4): 1253–1298. CiteSeerX 10.1.1.207.8277. doi:10.1137/S0097539795284959. ISSN 0097-5397.
4. Gennaro, Rosario; Gentry, Craig; Parno, Bryan (31 August 2010). Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers. CRYPTO 2010. doi:10.1007/978-3-642-14623-7_25.
5. Molnar, D. (2000). "The SETI@Home problem". ACM Crossroads. 7 (1).
6. Smith, S.; Weingart, S. (1999). "Building a high-performance, programmable secure coprocessor". Computer Networks. 31 (8): 831–960. CiteSeerX 10.1.1.22.8659. doi:10.1016/S1389-1286(98)00019-X.
7. Yee, B. (1994). Using Secure Coprocessors (PhD thesis). Carnegie Mellon University.
8. Trusted Computing Group (July 2007). Trusted platform module main specification. 1.2, Revision 103.
9. L. Babai (1985). "Trading group theory for randomness." In Proceedings of the ACM Symposium on Theory of Computing (STOC), New York, NY, US, pp. 421–429
10. S. Goldwasser, S. Micali, and C. Rackoff (1989). "The knowledge complexity of interactive proof-systems." SIAM Journal on Computing, 18(1), pp. 186–208
11. S. Arora and S. Safra (1998). "Probabilistically checkable proofs: a new characterization of NP." Journal of the ACM, 45, pp.501-555
12. O. Goldreich (1998). Modern Cryptography, Probabilistic Proofs and Pseudorandomness. Algorithms and Combinatorics series, 17, Springer
13. J. Kilian (1992). "A note on efficient zero-knowledge proofs and arguments (extended abstract)." In Proceedings of the ACM Symposium on Theory of Computing (STOC)
14. J. Kilian (1995). "Improved efficient arguments (preliminary version)." In Proceedings of Crypto, London, UK, pp. 311–324. Springer-Verlag
15. S. Micali (1994). "CS proofs (extended abstract)." In Proceedings of the IEEE Symposium on Foundations of Computer Science, pp. 436-453.
16. A. Yao (1982). "Protocols for secure computations." In Proceedings of the IEEE Symposium on Foundations of Computer Science, pp. 160-164
17. A. Yao (1986). "How to generate and exchange secrets." In Proceedings of the IEEE Symposium on Foundations of Computer Science, pp. 162-167
18. Setty, Srinath; McPherson, Richard; Blumberg, Andrew J.; Walfish, Michael (February 2012). Making Argument Systems for Outsourced Computation Practical (Sometimes). Network & Distributed System Security Symposium (NDSS) 2012.
19. Walfish, Michael; Blumberg, Andrew J. (2015-01-01). "Verifying Computations Without Reexecuting Them". Commun. ACM. 58 (2): 74–84. doi:10.1145/2641562. ISSN 0001-0782.