An Improved Authenticated Skip List for Relational Query Authentication

Some authenticated data structures (ADS) can reduce authentication cost with using signature aggregation method, such as authenticated skip list, merkle hash tree etc. But these ADS cannot solve the complicated authenticated problems, such as relational query authentication. Pang et al present signature chain scheme aims at various types of relational query but has high cost. Therefore an improved authenticated skip list (I-ASL for short) which is a new authenticated data structure is proposed in this paper. The formal definition of I-ASL and the construction method is presented. Based on the I-ASL, the paper presents the new relational query authentication methods to outsourced database. Moreover, our new relational query authentication methods achieve authentication in relational algebra, which includes select, projection, join, aggregate functions and other query operations. In addition, we analyze the security of our methods and prove that our methods could detect multiple possible adversaries´ behaviors, and thus ensure the soundness of various relational query results.