Hierarchical Hash List for Distributed Query Authentication

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.