Research On The Verifiable Computation In The Outsourcing Model

The rapid progress in the big data field makes people more and more easily access to a variety of data,which shows different features from previous ones:massive,heterogeneous and inferior.The client with resource-constraint is unable to compute the complex functions or store large data locally.At the same time,the continuous development of cloud computing technology lets it meets the needs of outsourcing computing through technical measures easily and economically.Both of them provide a solid foundation for the rise of outsourcing computation.The so-called outsourcing is that the weak client with resource-constraint delegates complex computing tasks or large database(or datasets)to the cloud server,and thus enjoy unlimited resources in computing tasks or querying the database procedures in a pay-per-use manner.The cloud may attack the returned result for some reasons(hardware or software errors occurred in the cloud sever,or the server wants to save resource,etc.).Without verifying the result,the cloud server may abuse its ability to make the client accept the wrong result.So it is necessary to guarantee the verifiability of the result returned by the server.Apart from the verifiability,the verifiable computation(VC)protocol should meet the following basic properties:correctness,security and efficiency.In this paper,we study the outsourcing of computation and database.The main contributions are as follows:(1)We construct three batch verifiable computation schemes with public verifiability.Zhang et al.first proposed the scheme of batch verifiable computation with private verifiability.We retrofit their schemes and use three different pseudorandom functions with closed-form efficiency to design batch verifiable computation with public verifiability(BVCP)schemes,which can be directly applied to outsource three different functions:polynomials with total degree bounded,polynomials with bounded degree in each monomial and matrix functions.In addition,we prove the security of our BVCP schemes under the decisional linear(DLIN)assumption.Besides,we optimize the last two BVCP schemes to meet less storage overhead.When the outsourced functions are tera bytes,less storage overhead means that both client and server can enjoy storage saved.(2)We first propose the notion of threshold verifiable database(TVDB)and construct a concrete scheme.The client shares its identity and secrete key with other cliets,and thus these clients can update the database in a threshold manner.While most of the existed verifiable database schemes only supported modifications over the record,our TVDB scheme meets modification,insertion and deletion operations.What's more,we prove the security of our TVDB scheme under the squ-CDH assumption.