Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint. Minor revision.
- Keywords
- Relational DatabasesEncrypted DatabasesSQL QueriesLeakagePseudorandom Function
- Contact author(s)
-
csjutla @ us ibm com
sikharpatranabis @ gmail com - History
- 2021-11-06: received
- 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}, note = {\url{https://eprint.iacr.org/2021/1471}}, url = {https://eprint.iacr.org/2021/1471} }