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: The defined notion of verifiable computation scheme minimizes the interaction between the client and the worker into exactly two messages, where a single message is sent from each party to the other party during the different phases of the protocol.
[4] 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.
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.
This is done by recursively decrypting the gate ciphertexts until arriving to the final output wire values (σy).
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.
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.
[18] The authors start with an argument system based on probabilistically checkable proofs and reduce its costs by a factor of 1020.