Paper 2016/453

SQL on Structurally-Encrypted Databases

Seny Kamara and Tarik Moataz

Abstract

We show how to encrypt a relational database in such a way that it can efficiently support a large class of SQL queries. Our construction is based solely on structured encryption (STE) and does not make use of any property-preserving encryption (PPE) schemes such as deterministic and order-preserving encryption. As such, our approach leaks considerably less than PPE-based solutions which have recently been shown to reveal a lot of information in certain settings (Naveed et al., CCS '15). Our construction is efficient and---under some conditions on the database and queries---can have asymptotically-optimal query complexity. We also show how to extend our solution to be dynamic while maintaining the scheme's optimal query complexity.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
encrypted searchsearchable encryptionSQLdatabasesstructured encryption
Contact author(s)
seny @ brown edu
tarik_moataz @ brown edu
History
2017-09-22: last of 2 revisions
2016-05-10: received
See all versions
Short URL
https://ia.cr/2016/453
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/453,
      author = {Seny Kamara and Tarik Moataz},
      title = {SQL on Structurally-Encrypted Databases},
      howpublished = {Cryptology ePrint Archive, Paper 2016/453},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/453}},
      url = {https://eprint.iacr.org/2016/453}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.