基于有向哈希树的认证跳表算法  

Algorithm of Authenticated Skip List Based on Directed Hash Tree

作　　者：徐剑[1,2] 陈旭[1] 李福祥[1] 周福才[1] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110819 [2]东北大学软件学院,沈阳110819

出　　处：《计算机科学》2011年第9期32-35,63,共5页Computer Science

基　　金：国家高技术研究发展计划863项目(2009AA01Z122);沈阳市自然科学基金项目(F10-205-1-12)资助

摘　　要：作为一种重要的认证数据结构,认证跳表在数据认证机制中有着广泛的应用。由于哈希模式对认证跳表的代价有显著的影响,因此提出哈希模式和数据存储模式分离的思想,设计了一种新的认证哈希模式——有向哈希树,并在其基础上设计了新的认证跳表算法。应用分层数据处理、概率分析等数学方法对所提出算法的代价进行了理论分析,并与已有的认证跳表算法做了性能比较。结果表明,本算法在时间、通信和存储代价方面有了较大的改进。Authenticated skip list is an important authenticated data structures.It has been widely used in data authentication.Since the hash scheme has the important influence on the cost of the authenticated skip list,a new hash scheme which is based on the idea of separating the hash scheme and data storage scheme was proposed in this paper.And the new algorithm of authenticated skip list（ASL-DHT for short） based on directed hash tree was also proposed.We applied hierarchical data processing and probability analysis methods to analyze the cost of ASL-DHT,and also made an algorithm simulation to compare with that of the original authenticated skip list.The results show that,ASL-DHT algorithm has got great improvement on storage cost,communication cost,and time cost.

关 键 词：认证跳表 认证哈希模式 有向哈希树 认证数据结构 

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