Authentication Of Relational Query Based On Hierarchical Hash Chain

Distributed network storage system is widely applied for its risk deconcentration, load balancing, anti-DDoS attacks and other advantages. However, new chanllenges are brought to query authentication like data modification, counterfeiting and loss during frequent replication and update of data and information. Therefore, as to structured data in relational database, how to guarantee the soundness of query results is becoming an important problem.Some authenticated data structures reduce cost of signatures by adopting signature aggregation, such as Authenticated Skip List, Merkle Tree, etc, but these methods cannot solve authenticated problems of complex query operations. Pang et al present Signature Chain scheme aims at various types of relational query but has high cost. We analyse deficiencies in current scheme and design a new authentication algorithm which named "Hierarchical Hash Chain". Then we present formal definition of Hierarchical Hash Chain as well as the algorithm of searching, proof generation, verify and updating. Furthermore, we analyse complexity of the algorithm and figure out two evaluation parameters of deciding authentication cost. The paper presents relational query authentication model based on Hierarchical Hash Chain, and designs some extensible authentication methods to relationship-oriented database. Moreover, this paper achieves authentication in relational algebra, which includes select, projection, join, aggregate functions and other query operations. In addition, we analyse security of the authentication method and prove that the authentication of relational query based on Hierarchical Hash Chain could detect multiple possible opponents’ behaviors, and thus ensure the soundness of various structural query results.We develop a plototype system of relational query authentication based on Hierarchical Hash Chain, which apply B/S architecture to realize the authentication of soundness to query results from common SQL statements. The research results show that the authentication of relational query based on Hierarchical Hash Chain has important theory and application value.