Cryptology ePrint Archive: Report 2020/274

An Optimal Relational Database Encryption Scheme

Seny Kamara and Tarik Moataz and Stan Zdonik and Zheguang Zhao

Abstract: Recently, Kamara and Moataz described the first encrypted relational database solution with support for a non-trivial fraction of SQL that does not make use of property-preserving encryption (Asiacrypt, 2018). More precisely, their construction, called SPX, handles the set of conjunctive SQL queries. While SPX was shown to be optimal for the subset of uncorrelated conjunctive SQL queries, it did not handle correlated queries optimally. Furthermore, it only handles queries in heuristic normal form. In this work, we address these limitations by proposing an extension of SPX that handles all conjunctive SQL queries optimally no matter what form they are in.

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

Date: received 1 Mar 2020, last revised 4 Mar 2020

Contact author: seny at brown edu,tarik@aroki com,sbz@cs brown edu,zheguang zhao@brown edu

Available format(s): PDF | BibTeX Citation

Note: Updated keywords.

Version: 20200304:132805 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]