Paper 2024/635
Organizing Records for Retrieval in Multi-Dimensional Range Searchable Encryption
Abstract
Storage of sensitive multi-dimensional arrays must be secure and efficient in storage and processing time. Searchable encryption allows one to trade between security and efficiency. Searchable encryption design focuses on building indexes, overlooking the crucial aspect of record retrieval. Gui et al. (PoPETS 2023) showed that understanding the security and efficiency of record retrieval is critical to understand the overall system. A common technique for improving security is partitioning data tuples into parts. When a tuple is requested, the entire relevant part is retrieved, hiding the tuple of interest. This work assesses tuple partitioning strategies in the dense data setting, considering parts that are random, $1$-dimensional, and multi-dimensional. We consider synthetic datasets of $2$, $3$ and $4$ dimensions, with sizes extending up to $2$M tuples. We compare security and efficiency across a variety of record retrieval methods. Our findings are: 1. For most configurations, multi-dimensional partitioning yields better efficiency and less leakage. 2. 1-dimensional partitioning outperforms multi-dimensional partitioning when the first (indexed) dimension is any size as long as the query is large in all other dimensions except the (the first dimension can be any size). 3. The leakage of 1-dimensional partitioning is reduced the most when using a bucketed ORAM (Demertiz et al., USENIX Security 2020).
Metadata
- Available format(s)
- Category
- Applications
- Publication info
- Published elsewhere. Major revision. secrypt
- Keywords
- System-wide Searchable EncryptionMulti-dimensional DatabasesRange Queries
- Contact author(s)
-
mheidaripour @ augusta edu
lkian @ augusta edu
maryam rezapour @ uconn edu
mholcomb @ augusta edu
benjamin fuller @ uconn edu
gagrawal @ uga edu
hmaleki @ augusta edu - History
- 2024-04-26: approved
- 2024-04-25: received
- See all versions
- Short URL
- https://ia.cr/2024/635
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/635, author = {Mahdieh Heidaripour and Ladan Kian and Maryam Rezapour and Mark Holcomb and Benjamin Fuller and Gagan Agrawal and Hoda Maleki}, title = {Organizing Records for Retrieval in Multi-Dimensional Range Searchable Encryption}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/635}, year = {2024}, url = {https://eprint.iacr.org/2024/635} }