Cryptology ePrint Archive: Report 2015/351
Database Outsourcing with Hierarchical Authenticated Data Structures
Mohammad Etemad and Alptekin Küpçü
Abstract: In an outsourced database scheme, the data owner delegates the data management tasks to a remote service provider. At a later time, the remote service is supposed to answer any query on the database. The essential requirements are ensuring the data integrity and authenticity with efficient mechanisms. Current approaches employ authenticated data structures to store security information, generated by the client and used by the server, to compute proofs that show the answers to the queries are authentic. The existing solutions have shortcomings with multi-clause queries and duplicate values in a column.
We propose a hierarchical authenticated data structure for storing security information, which alleviates the mentioned problems. Our solution handles many different types of queries, including multi-clause selection and join queries, in a dynamic database. We provide a unified formal definition of a secure outsourced database scheme, and prove that our proposed scheme is secure according to this definition, which captures previously separate properties such as correctness, completeness, and freshness. The performance evaluation based on our prototype implementation confirms the efficiency of our proposed scheme, showing about 3x to 5x enhancement in proof size and proof generation time in comparison to previous work, and about only 4% communication overhead compared to the actual query result in a real university database.
Category / Keywords: Databases outsourcing, Hierarchical authenticated data structures, Authenticated join processing
Date: received 20 Apr 2015, last revised 26 Apr 2015
Contact author: metemad at ku edu tr
Available format(s): PDF | BibTeX Citation
Version: 20150426:161331 (All versions of this report)
Short URL: ia.cr/2015/351
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]