Jump to content

Verifiable computing

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Aialali (talk | contribs) at 14:59, 23 November 2011 (←Created page with ''''Verifiable computing''' is the notion of enabling a computationally weak client to outsource the computation of some function F on dynamic...'). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

Verifiable computing is the notion of enabling a computationally weak client to outsource the computation of some function F on dynamically chosen inputs to one or more workers. The workers then evaluate the function F on the given input and return the result to the client accompanied with a proof that the computation of F on the given input was carried out correctly. The introduction of this notion came as a result of the increasingly common phenomenon of outsourcing computation to untrusted workers, in addition to the growing desire of weak clients to outsource computational tasks to a more powerful computation service. The notion of verifiable computing is introduced by Rosario Gennaro, Craig Gentry, and Bryan Parno[1].

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 [2] motivated the formalization of the notion of Verifiable Computation [3]. 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 to verifying the computation of functions performed by untrusted workers including the use of secure coprocessors [4][5], Trusted Platform Modules (TPMs) [6], interactive proofs [7][8], probabilistically checkable proofs [9][10], efficient arguments [11][12], and Micali’s CS proofs [13]. These verifications are either interactive which require the client to interact with the worker to verify the correctness proof [14][15], or are non-interactive protocols which can be proven in the random oracle model [16].

Verifiable Computation Scheme

Gennaro et al. [17] 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}n → {0,1}m. This scheme consists of three main phases:

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.

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.

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 [18].


A Verifiable Computation Scheme Definition

Gennaro et al.[19]defined a verifiable computation scheme for any function F using Yao’s Garbled Circuit [20][21] combined with a fully homomorphic encryption system [22].

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

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. ComputePK(σ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. VerifySK(τ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. [24] 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.



References

  1. ^ R. Gennaro, C. Gentry, and B. Parno, Non-interactive verifiable computing: outsourcing computation to untrusted workers, CRYPTO ’10: Proceedings of the 30th annual conference on Advances in cryptology, Springer- Verlag, 2010, pp. 465–482.
  2. ^ D. Molnar. The SETI@Home problem. ACM Crossroads, 7(1), 2000.
  3. ^ R. Gennaro, C. Gentry, and B. Parno, Non-interactive verifiable computing: outsourcing computation to untrusted workers, CRYPTO ’10: Proceedings of the 30th annual conference on Advances in cryptology, Springer- Verlag, 2010, pp. 465–482.
  4. ^ S. Smith and S. Weingart. Building a high-performance, programmable secure coprocessor. Computer Networks (Special Issue on Computer Network Security), 31, pp.831–960, 1999
  5. ^ B. Yee. Using Secure Coprocessors. PhD thesis, Carnegie Mellon University, 1994
  6. ^ Trusted Computing Group. Trusted platform module main specification. Version 1.2, Revision 103, July 2007
  7. ^ L. Babai. Trading group theory for randomness. In Proceedings of the ACM Symposium on Theory of Computing (STOC), New York, NY, USA, pp. 421–429, 1985
  8. ^ S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems. SIAM Journal on Computing, 18(1), pp. 186–208, 1989.
  9. ^ S. Arora and S. Safra. Probabilistically checkable proofs: a new characterization of NP. Journal of the ACM, 45, pp.501-555, 1998
  10. ^ O. Goldreich. Modern Cryptography, Probabilistic Proofs and Pseudorandomness. Algorithms and Combinatorics series, 17, Springer, 1998
  11. ^ J. Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In Proceedings of the ACM Symposium on Theory of Computing (STOC) 1992
  12. ^ J. Kilian. Improved efficient arguments (preliminary version). In Proceedings of Crypto, London, UK, pp. 311–324, 1995. Springer-Verlag
  13. ^ S. Micali. CS proofs (extended abstract). In Proceedings of the IEEE Symposium on Foundations of Computer Science, pp. 436-453, 1994
  14. ^ J. Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In Proceedings of the ACM Symposium on Theory of Computing (STOC) 1992.
  15. ^ J. Kilian. Improved efficient arguments (preliminary version). In Proceedings of Crypto, London, UK, pp. 311–324, 1995. Springer-Verlag.
  16. ^ S. Micali. CS proofs (extended abstract). In Proceedings of the IEEE Symposium on Foundations of Computer Science, pp. 436-453, 1994.
  17. ^ R. Gennaro, C. Gentry, and B. Parno, Non-interactive verifiable computing: outsourcing computation to untrusted workers, CRYPTO ’10: Proceedings of the 30th annual conference on Advances in cryptology, Springer- Verlag, 2010, pp. 465–482
  18. ^ R. Gennaro, C. Gentry, and B. Parno, Non-interactive verifiable computing: outsourcing computation to untrusted workers, CRYPTO ’10: Proceedings of the 30th annual conference on Advances in cryptology, Springer- Verlag, 2010, pp. 465–482
  19. ^ R. Gennaro, C. Gentry, and B. Parno,Non-interactive verifiable computing: outsourcing computation to untrusted workers, CRYPTO ’10: Proceedings of the 30th annual conference on Advances in cryptology, Springer- Verlag, 2010, pp. 465–482
  20. ^ A. Yao. Protocols for secure computations. In Proceedings of the IEEE Symposium on Foundations of Computer Science, pp. 160-164, 1982
  21. ^ A. Yao. How to generate and exchange secrets. In Proceedings of the IEEE Symposium on Foundations of Computer Science, pp. 162-167, 1986
  22. ^ C. Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the ACM Symposium on the Theory of Computing (STOC), Bethesda, Maryland, USA, pp. 169-178, 2009
  23. ^ R. Gennaro, C. Gentry, and B. Parno, Non-interactive verifiable computing: outsourcing computation to untrusted workers, CRYPTO ’10: Proceedings of the 30th annual conference on Advances in cryptology, Springer- Verlag, 2010, pp. 465–482
  24. ^ R. Gennaro, C. Gentry, and B. Parno, Non-interactive verifiable computing: outsourcing computation to untrusted workers, CRYPTO ’10: Proceedings of the 30th annual conference on Advances in cryptology, Springer- Verlag, 2010, pp. 465–482
Retrieved from "https://en.wikipedia.org/w/index.php?title=Verifiable_computing&oldid=462110153"