Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

8-2009

Abstract

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.

Keywords

Aggregate signature, Authentication methods, Concurrency constraints, Construct validity, Construction time, Data update, Dynamic database, Merkle hash tree, Practical solutions, Third parties, Verification techniques

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

Proceedings of the VLDB Endowment: VLDB'09, August 24-28, Lyon, France

Volume

2

Issue

1

First Page

802

Last Page

813

ISSN

2150-8097

Identifier

10.14778/1687627.1687718

Publisher

VLDB Endowment

City or Country

New York

Additional URL

http://dx.doi.org/10.14778/1687627.1687718

Download

Share

COinS