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

摘要

Authenticated skip list is an important authenticated data structures. It has been widely used in data authenti cation. 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 ap plied 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 algo rithm has got great improvement on storage cost;communication cost;and time cost.%作为一种重要的认证数据结构,认证跳表在数据认证机制中有着广泛的应用.由于哈希模式对认证跳表的代价有显著的影响,因此提出哈希模式和数据存储模式分离的思想,设计了一种新的认证哈希模式——有向哈希树,并在其基础上设计了新的认证跳表算法.应用分层数据处理、概率分析等数学方法对所提出算法的代价进行了理论分析,并与已有的认证跳表算法做了性能比较.结果表明,本算法在时间、通信和存储代价方面有了较大的改进.