Conference Proceeding Article
Query answers from servers operated by third parties need to be verified, as the third parties may not be trusted or their servers may be compromised. Most of the existing authentication methods construct validity proofs based on the Merkle hash tree (MHT). The MHT, however, imposes severe concurrency constraints that slow down data updates. We introduce a protocol, built upon signature aggregation, for checking the authenticity, completeness and freshness of query answers. The protocol offers the important property of allowing new data to be disseminated immediately, while ensuring that outdated values beyond a pre-set age can be detected. We also propose an efficient verification technique for ad-hoc equijoins, for which no practical solution existed. In addition, for servers that need to process heavy query workloads, we introduce a mechanism that significantly reduces the proof construction time by caching just a small number of strategically chosen aggregate signatures. The efficiency and efficacy of our proposed mechanisms are confirmed through extensive experiments.
Aggregate signature, Authentication methods, Concurrency constraints, Construct validity, Construction time, Data update, Dynamic database, Merkle hash tree, Practical solutions, Third parties, Verification techniques
Databases and Information Systems | Numerical Analysis and Scientific Computing
Data Management and Analytics
Proceedings of the VLDB Endowment: VLDB'09, August 24-28, Lyon, France
City or Country
PANG, Hwee Hwa; ZHANG, Jilian; and MOURATIDIS, Kyriakos.
Scalable Verification for Outsourced Dynamic Databases. (2009). Proceedings of the VLDB Endowment: VLDB'09, August 24-28, Lyon, France. 2, (1), 802-813. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/876
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.