Paper 2013/814

RDAS: A Symmetric Key Scheme for Authenticated Query Processing in Outsourced Databases

Lil Maria Rodriguez-Henriquez and Debrup Chakraborty

Abstract

In this paper we address the problem of authenticated query processing in outsourced databases. An authenticated query processing mechanism allows a client to verify the validity of the query responses that it gets from an untrusted and remote server, who stores the client's database on its behalf. We introduce a general framework called RDAS for the problem of authenticated query processing, and define the security goals for this task in line with concrete provable security. We propose several schemes which enable a client to verify both the completeness and correctness of the query responses of a server. All the schemes follow the proposed framework and are provably secure in terms of the proposed security definition. The novelty of the proposed schemes is that they use bitmap indexes as a main component for providing authentication. Bitmap indexes have recently seen lot of applications for accelerated query processing and many commercial databases implement such indexes. Bitmaps have not been previously used for a security goal. We show that the proposed schemes can match in both functionality and efficiency compared to the existing schemes. We also implement the schemes on a real database and provide extensive experimental studies on the schemes

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. MAJOR revision.RDAS: A Symmetric Key Scheme for Authenticated Query Processing in Outsourced Databases. Workshop on Security and Trust Management, STM 2013, Lecture Notes in Computer Science, vol. 8203, pp. 115-130, 2013
Keywords
AuthenticationAuthenticated query processingmessage authentication codesaggregate message authentication codesbitmap index
Contact author(s)
lrodriguez @ computacion cs cinvestav mx
History
2013-12-09: last of 2 revisions
2013-12-06: received
See all versions
Short URL
https://ia.cr/2013/814
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/814,
      author = {Lil Maria Rodriguez-Henriquez and Debrup Chakraborty},
      title = {RDAS: A Symmetric Key Scheme for Authenticated Query Processing in Outsourced Databases},
      howpublished = {Cryptology ePrint Archive, Paper 2013/814},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/814}},
      url = {https://eprint.iacr.org/2013/814}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.