Multi-Client Verifiable Computation Service for Outsourced Data
The introduction of verifiable computation came as a result of the increasingly common phenomenon of "outsourcing" computation to untrusted servers and also to the growing desire of weak clients to outsource computational tasks to more powerful computation services like in cloud computing. Verifiable computation enables a computer to offload the computation of some function, to other perhaps untrusted cloud servers, while maintaining verifiable results. The servers evaluate the function and return the result with a proof that the computation of the function was carried out correctly. In the previous setting of verifiable computation, there is only one data provider. But in practice, there exist scenarios such as a network of sensors where each sensor collects data (e.g. air temperature in a certain area of a city) and stores them on servers. A control unit performs computation (e.g. the average air temperature of the city in certain period) on the outsourced data on the cloud (e.g. Amazon Cloud). When the control unit receives the results, it wants to verify the correctness of the computation results returned by the servers. For this scenario, we define a novel two-server multiclient verifiable computation service framework for outsourced data. An efficient construction is proposed, whose security is based on the existence of one-way functions. There are two advantages in our construction: (1) The size of the proof vouching for the correctness of computation result is independent with the number of data providers. (2) The verification only needs two equality tests executed by one who wants to get the computation result. We also experimentally analyze our construction and show our construction is very efficient in practice.