可认证数据结构综述  

Overview of Authenticated Data Structures

作　　者：孔祥玉[1,2,3,4] 陈宇 KONG Xiang-Yu;CHEN Yu(School of Cyber Science and Technology,Shandong University,Qingdao 266237,China;Quan Cheng Laboratory,Jinan 250103,China;State Key Laboratory of Cryptology,Beijing 100878,China;Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education,Shandong University,Qingdao 266237,China)

机构地区：[1]山东大学网络空间安全学院,青岛266237 [2]泉城实验室,济南250103 [3]密码科学技术全国重点实验室,北京100878 [4]山东大学密码技术与信息安全教育部重点实验室,青岛266237

出　　处：《密码学报（中英文）》2024年第3期545-574,共30页Journal of Cryptologic Research

基　　金：国家重点研发计划(2021YFA1000600);国家自然科学基金(62272269,61932019);泰山学者青年专家;山东省科技厅山东省实验室项目(SYS202201);泉城实验室重点项目(QCLZD202302)。

摘　　要：可认证数据结构是一种利用密码学技术保证分布式环境中远程数据计算正确性的特殊数据结构.近年来,随着分布式计算的发展,可认证数据结构受到广泛关注.本文为可认证数据结构提供了统一框架,并从类别、构造和应用等方面对可认证数据结构进行系统综述.首先,根据数据和计算的类型对可认证数据结构进行分类.其次,针对各类可认证数据结构,分别介绍其发展历程、构造方法和典型应用.再次,梳理各类可认证数据结构之间的关系.最后,探讨可认证数据结构的发展方向.An authenticated data structure(ADS)is a special data structure that uses cryptographic techniques to guarantee the correctness of computation on remote data in the distributed environment.In recent years,with the development of distributed computing,ADSs have received much attention.This paper proposes a unified framework and a comprehensive review of existing works on ADSs from the perspectives of classifications,constructions,and applications.It categorizes ADSs into four families based on the types of data and computation.Based on the classification,this paper introduces ADSs in terms of the history,constructions,and typical applications.The relation among these categorizations is presented.In addition,several future research directions of ADSs are discussed.

关 键 词：可认证数据结构 累加器 向量承诺 多项式承诺 线性函数承诺 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]