Paper 2012/493

Efficient Query Integrity for Outsourced Dynamic Databases

Qingji Zheng, Shouhuai Xu, and Giuseppe Ateniese

Abstract

As databases are increasingly outsourced to the cloud, data owners require various security assurances. This paper investigates one particular assurance, query integrity, by which a database querier (either the data owner or a third party) can verify that its queries were faithfully executed by the cloud server with respect to the outsourced database. Query integrity is investigated in the setting of dynamic databases, where the outsourced databases can be updated by the data owners as needed. We present a formal security definition of query integrity and a provably-secure efficient construction. Our solution improves upon the state-of-the-art solutions by additionally allowing aggregate queries and more flexible join queries. In addition, we provide better performance by eliminating a linear factor in the extra storage complexity for security purpose. Our solution also achieves a trade-off between computational and communication complexities.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. will be published in CCSW'2012
Keywords
Dynamic outsourced databasequery integrityauthenticated data structure
Contact author(s)
qingjizheng @ gmail com
History
2012-09-03: received
Short URL
https://ia.cr/2012/493
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/493,
      author = {Qingji Zheng and Shouhuai Xu and Giuseppe Ateniese},
      title = {Efficient Query Integrity for Outsourced Dynamic Databases},
      howpublished = {Cryptology ePrint Archive, Paper 2012/493},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/493}},
      url = {https://eprint.iacr.org/2012/493}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.