A General Model for Authentic Data Publication
Chip Martel, Glen Nuckolls, Prémkumar Dévanbu, Michael Gertz, April Kwong, Stuart G. Stubblebine · 2001
Query answers from on-line databases can easily be corrupted by hackers or malicious intent by the database publisher. Thus it is important to provide mechanisms which allow clients to trust the results from on-line queries. Authentic publication is a novel scheme which allows untrusted publishers to securely answer queries from clients on behalf of trusted off-line data owners. Publishers validate answers using compact, unforgeable verification objects (VOs), which clients can check efficiently. To make authentic publication attractive it is important for the VOs to be small, efficiently computable and verifiable. This has led to the development of a number of data representations for efficient VO computation. In this paper, we prove the security of VOs for a new general data model called Search DAGs. Our security theorem for Search DAGS gives simple security proofs and efficient VOs for a broad range of known structures including binary trees, multi-dimensional range trees, and skip lists. Our approach also helps to provide a clean separation between the proof of security and efficiency. We also use search DAGs to prove the security of two new and much more complex data models for efficient multi-dimensional range searches. This allows compact VOs to be computed (size O(log N + T)) for typical 1D and 2D range queries, where the query answer is of size T and the database is of size N. We also show I/O efficient schemes to construct the VOs. For a system with disk blocks of size B, we answer 1D and 3-sided range queries and compute the VOs with O(log BN + T/B) I/O operations using linear size data structures.