Cryptology ePrint Archive: Report 2021/852

Improved Structured Encryption for SQL Databases via Hybrid Indexing

David Cash and 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.

Category / Keywords: cryptographic protocols / Structured Encryption, Searchable Encryption

Original Publication (with major differences): ACNS 2021

Date: received 22 Jun 2021

Contact author: davidcash at uchicago edu, ring at eng ucsd edu, amrivkin at uchicago edu

Available format(s): PDF | BibTeX Citation

Version: 20210622:143726 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]