CryptoDB
Efficient Searchable Symmetric Encryption for Join Queries
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | ASIACRYPT 2022 |
| Abstract: | The Oblivious Cross-Tags (OXT) protocol due to Cash et al. (CRYPTO 2013) 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. |
Video from ASIACRYPT 2022
BibTeX
@inproceedings{asiacrypt-2022-32394,
title={Efficient Searchable Symmetric Encryption for Join Queries},
publisher={Springer-Verlag},
author={Charanjit Jutla and Sikhar Patranabis},
year=2022
}