Primitives towards verifiable computation： a survey  

作　　者：Haseeb AHMAD Licheng WANG Haibo HONG Jing LI Hassan DAWOOD Manzoor AHMED Yixian YANG 

机构地区：[1]State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China [2]School of Computer Science and Information Engineering, Zhejiang Gongshang University, Hangzhou 310018, China [3]Department of Computer Engineering, University of Engineering and Technology, Taxila 47050, Pakistan [4]Future Internet & Communication Lab, Department of Electronic Engineering, Tsinghua University, Beijing 100084, China

出　　处：《Frontiers of Computer Science》2018年第3期451-478,共28页中国计算机科学前沿（英文版）

摘　　要：Verifiable computation （VC） paradigm has got the captivation that in real term is highlighted by the concept of third party computation. In more explicate terms, VC allows resource constrained clients/organizations to securely outsource expensive computations to untrusted service providers, while acquiring the publicly or privately verifiable results. Many mainstream solutions have been proposed to address the diverse problems within the VC domain. Some of them imposed assumptions over performed computations, while the others took advantage of interactivity /non-interactivity, zero knowledge proofs, and arguments. Further proposals utilized the powers of probabilistic checkable or computationally sound proofs. In this survey, we present a chronological study and classify the VC proposals based on their adopted domains. First, we provide a broader overview of the theoretical advancements while critically analyzing them. Subsequently, we present a comprehensive view of their utilization in the state of the art VC approaches. Moreover, a brief overview of recent proof based VC systems is also presented that lifted up the VC domain to the verge of practicality. We use the presented study and reviewed resuits to identify the similarities and alterations, modifications, and hybridization of different approaches, while comparing their advantages and reporting their overheads. Finally, we discuss implementation of such VC based systems, their applications, and the likely future directions.Verifiable computation （VC） paradigm has got the captivation that in real term is highlighted by the concept of third party computation. In more explicate terms, VC allows resource constrained clients/organizations to securely outsource expensive computations to untrusted service providers, while acquiring the publicly or privately verifiable results. Many mainstream solutions have been proposed to address the diverse problems within the VC domain. Some of them imposed assumptions over performed computations, while the others took advantage of interactivity /non-interactivity, zero knowledge proofs, and arguments. Further proposals utilized the powers of probabilistic checkable or computationally sound proofs. In this survey, we present a chronological study and classify the VC proposals based on their adopted domains. First, we provide a broader overview of the theoretical advancements while critically analyzing them. Subsequently, we present a comprehensive view of their utilization in the state of the art VC approaches. Moreover, a brief overview of recent proof based VC systems is also presented that lifted up the VC domain to the verge of practicality. We use the presented study and reviewed resuits to identify the similarities and alterations, modifications, and hybridization of different approaches, while comparing their advantages and reporting their overheads. Finally, we discuss implementation of such VC based systems, their applications, and the likely future directions.

关 键 词：verifiable computation cloud computation INTERACTIVE NON-INTERACTIVE zero knowledge probabilisticcheckable proofs computationally sound proofs 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP393.08[自动化与计算机技术—计算机科学与技术]