Paper 2016/453

SQL on Structurally-Encrypted Databases

Seny Kamara and Tarik Moataz


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.

Available format(s)
Publication info
Preprint. MINOR revision.
encrypted searchsearchable encryptionSQLdatabasesstructured encryption
Contact author(s)
seny @ brown edu
tarik_moataz @ brown edu
2017-09-22: last of 2 revisions
2016-05-10: received
See all versions
Short URL
Creative Commons Attribution


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