Progress in verifiable computation
Xue Ru · Scientia Sinica Informationis · 2015
Verifiable computation is an important mechanism for ensuring the soundness(reliability) of function evaluation results produced when delegating computation in distributed computing or cloud computing.We summarize the important achievements about verifiable computation, in particular, from the perspectives of cryptography and computational theory. For verifiable computation in computational theory, we summarize the connection between interactive proofs, PCP theorems, and CS proofs and describe their development and applications. With regard cryptography, we discuss the state-of-the-art verifiable computation schemes that were constructed by applying cryptography tools. In addition, we survey verifiable computation schemes in the outsourced storage setting. Finally, we conclude with a discussion on the future development direction for verifiable computation.