Cryptology ePrint Archive: Report 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.

Category / Keywords: encrypted search, searchable encryption, SQL, databases, structured encryption

Date: received 9 May 2016, last revised 22 Sep 2017

Contact author: seny at brown edu, tarik_moataz at brown edu

Available format(s): PDF | BibTeX Citation

Version: 20170922:160437 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]