Hierarchical Hash Linklist And Its Application In Authenticating Data Query

Compare to the conventional centralized architecture which the data owner deals with the processing of user queries, the data publishing model in distributed environment has broad application prospects. It has a series of benefits, such as low latency and Anti-DDos. But the publishing is unreliable under such circumstances. Guarantee the correctness of query results has become a hot research spot in this field.The schemes such as Authentication Skiplist showed outstanding properties in dealing with simple queries and authentication, but couldn’t authenticate the results of some complex queries like relational query. Some scholars proposed a Signature Chain Scheme, which makes up the shortage of existing scheme. However, its efficiency is low. This paper analyzes the existing data authentication schemes, proposes a new data authentication scheme: Hierarchical Hash Linklist (HHL) and designs a series of algorithm about the structure, update, query and authenticate of HHL. Besides, this paper presents an improvement of Hierarchical Hash Linklist whose efficiency is better. This paper also analyzes the cost in theory through the statistical methods and points out the cost of this schemes is O(logn). And analysis its safety by listing a variety of destruction on data security. Also, The experimental data show that HHL is superior to Signature Chain Scheme in the aspect of Communication cost and computational cost.This article applies HHL to the authentication on the results of relational query, solves the problem such as the authentication of different types of relational query, designs and implements a prototype authentication system of data query. It guarantees that publishing only returns the results which users want, and all results returned have the characteristics of authenticity and legality. The study reveals that the data authentication base on HHL is high-efficiency in extensity and timeliness.