Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers

Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers

2010 | Rosario Gennaro, Craig Gentry, and Bryan Parno
This paper introduces a non-interactive verifiable computation scheme that allows a computationally weak client to outsource computation of a function F to untrusted workers. The scheme ensures that the worker returns the result of the function evaluation along with a proof that the computation was performed correctly. The verification of the proof requires significantly less computational effort than computing F from scratch. The proposed protocol enables the worker to return a computationally sound, non-interactive proof that can be verified in O(m·poly(λ)) time, where m is the bit-length of the output of F and λ is a security parameter. The protocol requires a one-time pre-processing stage by the client, which takes O(|C|·poly(λ)) time, where C is the smallest known Boolean circuit computing F. The scheme also provides input and output privacy for the client, meaning that the workers do not learn any information about the inputs or outputs. The scheme is based on Yao's Garbled Circuit Construction and a fully homomorphic encryption scheme. The client preprocesses the circuit, encrypts the input labels, and sends them to the worker. The worker then performs the computation on the encrypted labels and returns the encrypted output labels to the client, who decrypts them to obtain the result. The scheme ensures that the worker cannot learn any information about the inputs or outputs. The scheme is secure and efficient, allowing the client to outsource computation to untrusted workers while maintaining the privacy of the inputs and outputs. The scheme is also resilient against malicious workers, as the client can re-garble the circuit if a malformed response is received. The scheme is proven to be secure under standard cryptographic assumptions and provides a practical solution for outsourcing computation to untrusted workers.This paper introduces a non-interactive verifiable computation scheme that allows a computationally weak client to outsource computation of a function F to untrusted workers. The scheme ensures that the worker returns the result of the function evaluation along with a proof that the computation was performed correctly. The verification of the proof requires significantly less computational effort than computing F from scratch. The proposed protocol enables the worker to return a computationally sound, non-interactive proof that can be verified in O(m·poly(λ)) time, where m is the bit-length of the output of F and λ is a security parameter. The protocol requires a one-time pre-processing stage by the client, which takes O(|C|·poly(λ)) time, where C is the smallest known Boolean circuit computing F. The scheme also provides input and output privacy for the client, meaning that the workers do not learn any information about the inputs or outputs. The scheme is based on Yao's Garbled Circuit Construction and a fully homomorphic encryption scheme. The client preprocesses the circuit, encrypts the input labels, and sends them to the worker. The worker then performs the computation on the encrypted labels and returns the encrypted output labels to the client, who decrypts them to obtain the result. The scheme ensures that the worker cannot learn any information about the inputs or outputs. The scheme is secure and efficient, allowing the client to outsource computation to untrusted workers while maintaining the privacy of the inputs and outputs. The scheme is also resilient against malicious workers, as the client can re-garble the circuit if a malformed response is received. The scheme is proven to be secure under standard cryptographic assumptions and provides a practical solution for outsourcing computation to untrusted workers.
Reach us at info@study.space