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 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 achieves asymptotically optimal query complexity under very natural conditions on the database and queries.

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

Date: received 9 May 2016, last revised 30 May 2016

Contact author: tarik moataz at colostate edu

Available format(s): PDF | BibTeX Citation

Version: 20160530:210653 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]