A core security requirement is the integrity and authenticity of outsourced databases. Whenever someone queries a hosted database, the results must be demonstrably authentic (with respect to the actual data owner) to ensure that the data has not been tampered with. Furthermore, the results must carry a proof of completeness which will allow the querier to verify that the server has not omitted any valid tuples that match the query predicate.
Notable prior research (\cite{DpGmMcSs00, McNgDpGmKwSs02, PanTan04}) focused on so-called \textit{Authenticated Data Structures}. Another prior approach involved the use of special digital signature schemes. In this paper, we extend the state-of-the-art to provide both authenticity and completeness guarantees of query replies. Our work also analyzes the new approach for various base query types and compares the new approach with Authenticated Data Structures.\footnote{We also point out some possible security flaws in the approach suggested in the recent work of \cite{PanTan04}.}
Category / Keywords: Date: received 29 Aug 2005 Contact author: mnarasim at ics uci edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20050901:065514 (All versions of this report) Short URL: ia.cr/2005/297 Discussion forum: Show discussion | Start new discussion