Paper 2024/950
DISCO: Dynamic Searchable Encryption with Constant State
Abstract
Dynamic searchable encryption (DSE) with forward and backward privacy reduces leakages in early-stage schemes. Security enhancement comes with a price -- maintaining updatable keyword-wise state information. State information, if stored locally, incurs significant client-side storage overhead for keyword-rich datasets, potentially hindering real-world deployments. We propose DISCO, a simple and efficient framework for designing DSE schemes using constant client state. DISCO combines range-constrained pseudorandom functions (RCPRFs) over a global counter and leverages nice properties from the underlying primitives and index structure to simultaneously achieve forward-and-backward privacy and constant client state. To configure DISCO concretely, we identify a set of RCPRF properties that are vital for the resulting DISCO instantiations. By configuring DISCO with different RCPRFs, we resolve efficiency and usability issues in existing schemes. We further optimize DISCO's concrete efficiency without downgrading security. We implement DISCO constructions and report performance, showing trade-offs from different DISCO constructions. Besides, we compare the practical efficiency of DISCO with existing non-constant-state DSE schemes, demonstrating DISCO's competitive efficiency.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Published elsewhere. Minor revision. AsiaCCS 2024
- DOI
- 10.1145/3634737.3637674
- Keywords
- Searchable encryptionForward privacyBackward privacyClient storage
- Contact author(s)
-
bintasong @ gmail com
yuzheng404 @ link cuhk edu hk
jbai795 @ aucklanduni ac nz
changyu dong @ gmail com
liuzheli @ nankai edu cn
changec @ comp nus edu sg - History
- 2024-06-14: approved
- 2024-06-13: received
- See all versions
- Short URL
- https://ia.cr/2024/950
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/950,
author = {Xiangfu Song and Yu Zheng and Jianli Bai and Changyu Dong and Zheli Liu and Ee-Chien Chang},
title = {{DISCO}: Dynamic Searchable Encryption with Constant State},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/950},
year = {2024},
doi = {10.1145/3634737.3637674},
url = {https://eprint.iacr.org/2024/950}
}