面向分布式查询认证的分层Hash链表

Hierarchical Hash List for Distributed Query Authentication

针对认证跳表、签名链等方案所存在的不足,对分布式查询认证展开研究.提出分布式查询认证的定义,给出其应满足的认证性的形式化描述.以认证跳表为基础,在考虑完备性和边界隐私保护的前提下,设计一种新的认证数据结构——分层Hash链表(hierarchical Hash list,HHL),给出了HHL的定义以及构建、认证和更新算法.通过对HHL中冗余Hash节点的分析,提出了效率更高的改进分层Hash链表(N-HHL),利用统计学方法和分层数据处理对HHL的代价进行分析,得出其拥有O(log n)代价.通过模拟敌手多种破坏数据认证性的手段,对HHL的安全性进行分析,结果表明HHL能够检测出多种破坏查询结果认证性的行为,从而证明其安全性.将HHL与已有的典型分布式查询认证方案——签名链方案——进行比较,实验数据表明HHL在认证代价方面优于签名链方案.

Our research on the distributed query authentication aims at decreasing the authentication cost of the existing schemes, such as authenticated skiplist and signature chaining. Both the definition of the distributed query authentication and the formalized description of the authenticity, which has to be satisfied, are proposed in this paper. A new authenticated data structure called hierarchical Hash list （HHL）, is designed to guarantee the integrity and authenticity of the answers to the query, while decreasing the computation and authentication cost as much as possible. The algorithms for its construction, authentication and updating, as well as its definition, are also designed. According to the analysis of the redundant Hash nodes in the HHL, the basic HHL is improved to be more efficient on the cost. For that reason, statistical methods and hierarchical data processing are used and the cost decreases to O（log n）. The security analysis is carried out by simulating adversaries＇ attacks against the authenticity of the data. The analysis results show that the HHL could detect different kinds of behaviors which could destroy the authenticity of the query answers, and this also proves the proposed scheme＇s security. Experiments show that compared with the typical distributed query authentication scheme signature chaining, our scheme is proved more efficient on the authentication cost.