Verifiable computing

Last updated

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 to enable computationally-weak devices to outsource computational tasks to a more powerful computation service, as 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]

Contents

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}n → {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. ProbGen(SK, 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. 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. [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 1020. 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]

In the 2010s, verifiable computing techniques have seen an increase of practical applications in blockchain technology. [20]

Related Research Articles

<span class="mw-page-title-main">Interactive proof system</span>

In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a prover and a verifier. The parties interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover possesses unlimited computational resources but cannot be trusted, while the verifier has bounded computation power but is assumed to be always honest. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct.

A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value while keeping it hidden to others, with the ability to reveal the committed value later. Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes are binding. Commitment schemes have important applications in a number of cryptographic protocols including secure coin flipping, zero-knowledge proofs, and secure computation.

In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party can prove to another party that a given statement is true, while avoiding conveying to the verifier any information beyond the mere fact of the statement's truth. The intuition underlying zero-knowledge proofs is that it is trivial to prove the possession of certain information by simply revealing it; the challenge is to prove this possession without revealing the information, or any aspect of it whatsoever.

Secure multi-party computation is a subfield of cryptography with the goal of creating methods for parties to jointly compute a function over their inputs while keeping those inputs private. Unlike traditional cryptographic tasks, where cryptography assures security and integrity of communication or storage and the adversary is outside the system of participants, the cryptography in this model protects participants' privacy from each other.

In cryptography, a semantically secure cryptosystem is one where only negligible information about the plaintext can be feasibly extracted from the ciphertext. Specifically, any probabilistic, polynomial-time algorithm (PPTA) that is given the ciphertext of a certain message , and the message's length, cannot determine any partial information on the message with probability non-negligibly higher than all other PPTA's that only have access to the message length. This concept is the computational complexity analogue to Shannon's concept of perfect secrecy. Perfect secrecy means that the ciphertext reveals no information at all about the plaintext, whereas semantic security implies that any information revealed cannot be feasibly extracted.

In cryptography, a verifiable random function (VRF) is a public-key pseudorandom function that provides proofs that its outputs were calculated correctly. The owner of the secret key can compute the function value as well as an associated proof for any input value. Everyone else, using the proof and the associated public key, can check that this value was indeed calculated correctly, yet this information cannot be used to find the secret key.

The Goldwasser–Micali (GM) cryptosystem is an asymmetric key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982. GM has the distinction of being the first probabilistic public-key encryption scheme which is provably secure under standard cryptographic assumptions. However, it is not an efficient cryptosystem, as ciphertexts may be several hundred times larger than the initial plaintext. To prove the security properties of the cryptosystem, Goldwasser and Micali proposed the widely used definition of semantic security.

In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: no efficient algorithm can distinguish between a function chosen randomly from the PRF family and a random oracle. Pseudorandom functions are vital tools in the construction of cryptographic primitives, especially secure encryption schemes.

In cryptography, a secret sharing scheme is verifiable if auxiliary information is included that allows players to verify their shares as consistent. More formally, verifiable secret sharing ensures that even if the dealer is malicious there is a well-defined secret that the players can later reconstruct. The concept of verifiable secret sharing (VSS) was first introduced in 1985 by Benny Chor, Shafi Goldwasser, Silvio Micali and Baruch Awerbuch.

Homomorphic encryption is a form of encryption that allows computations to be performed on encrypted data without first having to decrypt it. The resulting computations are left in an encrypted form which, when decrypted, result in an output that is identical to that produced had the operations been performed on the unencrypted data. Homomorphic encryption can be used for privacy-preserving outsourced storage and computation. This allows data to be encrypted and out-sourced to commercial cloud environments for processing, all while encrypted.

A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes. This often requires coordinating processes to reach consensus, or agree on some data value that is needed during computation. Example applications of consensus include agreeing on what transactions to commit to a database in which order, state machine replication, and atomic broadcasts. Real-world applications often requiring consensus include cloud computing, clock synchronization, PageRank, opinion formation, smart power grids, state estimation, control of UAVs, load balancing, blockchain, and others.

The Benaloh Cryptosystem is an extension of the Goldwasser-Micali cryptosystem (GM) created in 1985 by Josh (Cohen) Benaloh. The main improvement of the Benaloh Cryptosystem over GM is that longer blocks of data can be encrypted at once, whereas in GM each bit is encrypted individually.

Secure two-party computation (2PC) a.k.a. Secure function evaluation is sub-problem of secure multi-party computation (MPC) that has received special attention by researchers because of its close relation to many cryptographic tasks. The goal of 2PC is to create a generic protocol that allows two parties to jointly compute an arbitrary function on their inputs without sharing the value of their inputs with the opposing party. One of the most well known examples of 2PC is Yao's Millionaires' problem, in which two parties, Alice and Bob, are millionaires who wish to determine who is wealthier without revealing their wealth. Formally, Alice has wealth , Bob has wealth , and they wish to compute without revealing the values or .

Byzantine fault tolerant protocols are algorithms that are robust to arbitrary types of failures in distributed algorithms. The Byzantine agreement protocol is an essential part of this task. The constant-time quantum version of the Byzantine protocol, is described below.

Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems — which could, theoretically, be defeated using Shor's algorithm on a quantum computer — some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.

<span class="mw-page-title-main">Functional encryption</span>

Functional encryption (FE) is a generalization of public-key encryption in which possessing a secret key allows one to learn a function of what the ciphertext is encrypting.

Datain use is an information technology term referring to active data which is stored in a non-persistent digital state typically in computer random-access memory (RAM), CPU caches, or CPU registers.

Garbled circuit is a cryptographic protocol that enables two-party secure computation in which two mistrusting parties can jointly evaluate a function over their private inputs without the presence of a trusted third party. In the garbled circuit protocol, the function has to be described as a Boolean circuit.

HEAAN is an open source homomorphic encryption (HE) library which implements an approximate HE scheme proposed by Cheon, Kim, Kim and Song (CKKS). The first version of HEAAN was published on GitHub on 15 May 2016, and later a new version of HEAAN with a bootstrapping algorithm was released. Currently, the latest version is Version 2.1.

The Hidden Matching Problem is a computation complexity problem that can be solved using quantum protocols: Let be a positive even integer. In the Hidden Matching Problem, Alice is given and Bob is given ( denotes the family of all possible perfect matchings on nodes). Their goal is to output a tuple such that the edge belongs to the matching and .

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. STOC '91. New York, NY, US: ACM. pp. 21–32. CiteSeerX   10.1.1.42.5832 . doi:10.1145/103418.103428. ISBN   978-0897913973. S2CID   16965640.
  2. ↑ Goldwasser, Shafi; Kalai, Yael Tauman; Rothblum, Guy N. (2008-01-01). "Delegating computation". 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. S2CID   47106603.
  3. 1 2 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. 1 2 3 4 5 6 7 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. 1 2 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. 1 2 J. Kilian (1995). "Improved efficient arguments (preliminary version)." In Proceedings of Crypto, London, UK, pp. 311–324. Springer-Verlag
  15. 1 2 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.
  20. ↑ Šimunić, Silvio; Bernaca, Dalen; Lenac, Kristijan (2021). "Verifiable Computing Applications in Blockchain". IEEE Access. 9: 156729–156745. doi: 10.1109/ACCESS.2021.3129314 . S2CID   244923818.{{cite journal}}: CS1 maint: multiple names: authors list (link)
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.