Cryptology ePrint Archive: Report 2021/1471

Efficient Searchable Symmetric Encryption for Join Queries

Charanjit Jutla and Sikhar Patranabis

Abstract: The Oblivious Cross-Tags (OXT) protocol due to Cash et al. (CRYPTO'13) is a highly scalable searchable symmetric encryption (SSE) scheme that allows fast processing of conjunctive and more general Boolean queries over encrypted relational databases. A longstanding open question has been to extend OXT to also support queries over joins of tables without pre-computing the joins. In this paper, we solve this open question without compromising on the nice properties of OXT with respect to both security and efficiency. We propose Join Cross-Tags (JXT) - a purely symmetric-key solution that supports efficient conjunctive queries over (equi) joins of encrypted tables without any pre-computation at setup. JXT is fully compatible with OXT, and can be used in conjunction with OXT to support a wide class of SQL queries directly over encrypted relational databases. We prove the (adaptive) simulation-based security of JXT with respect to a rigorously defined leakage profile.

Category / Keywords: cryptographic protocols / Relational Databases, Encrypted Databases, SQL Queries, Leakage, Pseudorandom Function

Date: received 3 Nov 2021

Contact author: csjutla at us ibm com, sikharpatranabis at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20211106:155246 (All versions of this report)

Short URL: ia.cr/2021/1471