Paper 2024/635

Organizing Records for Retrieval in Multi-Dimensional Range Searchable Encryption

Mahdieh Heidaripour, Augusta University
Ladan Kian, Augusta University
Maryam Rezapour, University of Connecticut
Mark Holcomb, Augusta University
Benjamin Fuller, University of Connecticut
Gagan Agrawal, University of Georgia
Hoda Maleki, Augusta University
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.