Paper 2021/852

Improved Structured Encryption for SQL Databases via Hybrid Indexing

David Cash, Ruth Ng, and Adam Rivkin

Abstract

We introduce a new technique for indexing joins in encrypted SQL databases called partially precomputed joins which achieves lower leakage and bandwidth than those used in prior constructions. These techniques are incorporated into state-of-the-art structured encryption schemes for SQL data, yielding a hybrid indexing scheme with both partially and fully precomputed join indexes. We then introduce the idea of leakage-aware query planning by giving a heuristic that helps the client decide, at query time, which index to use so as to minimize leakage and stay below a given bandwidth budget. We conclude by simulating our constructions on real datasets, showing that our heuristic is accurate and that partially-precomputed joins perform well in practice.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACNS 2021
DOI
10.1007/978-3-030-78375-4_19
Keywords
Structured EncryptionSearchable Encryption
Contact author(s)
davidcash @ uchicago edu
ring @ eng ucsd edu
amrivkin @ uchicago edu
History
2021-06-22: received
Short URL
https://ia.cr/2021/852
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/852,
      author = {David Cash and Ruth Ng and Adam Rivkin},
      title = {Improved Structured Encryption for SQL Databases via Hybrid Indexing},
      howpublished = {Cryptology ePrint Archive, Paper 2021/852},
      year = {2021},
      doi = {10.1007/978-3-030-78375-4_19},
      note = {\url{https://eprint.iacr.org/2021/852}},
      url = {https://eprint.iacr.org/2021/852}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.