Efficient Searchable Symmetric Encryption for Join Queries

Charanjit Jutla; Sikhar Patranabis

Paper 2021/1471

Efficient Searchable Symmetric Encryption for Join Queries

Charanjit Jutla, IBM Research - Thomas J. Watson Research Center

Sikhar Patranabis, IBM Research India

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. JXT incurs a storage cost (over OXT) of a factor equal to the number of potential join-attributes in a table, which is usually compensated by the fact that JXT is a fully symmetric-key solution (as opposed to OXT which relies on discrete-log hard groups). We prove the (adaptive) simulation-based security of JXT with respect to a rigorously defined leakage profile.

Note: This version of the paper contains a more detailed comparison with related work and additional discussions based on feedback from the anonymous reviewers at IACR Asiacrypt 2022.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A major revision of an IACR publication in ASIACRYPT 2022
Keywords: Relational Databases Encrypted Databases SQL Queries Leakage Pseudorandom Function
Contact author(s): csjutla @ us ibm com
sikharpatranabis @ gmail com
History: 2022-08-30: last of 3 revisions; 2021-11-06: received; See all versions
Short URL: https://ia.cr/2021/1471
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1471,
      author = {Charanjit Jutla and Sikhar Patranabis},
      title = {Efficient Searchable Symmetric Encryption for Join Queries},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1471},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1471}
}