Paper 2019/446
Backward Private DSSE: Alternative Formulations of Information Leakage and Efficient Constructions
Sanjit Chatterjee, Shravan Kumar Parshuram Puria, and Akash Shah
Abstract
Dynamic Searchable Symmetric Encryption ($\mathsf{DSSE}$), apart from providing support for search operation, allows a client to perform update operations on outsourced database efficiently. Two security properties, viz., forward privacy and backward privacy are desirable from a $\mathsf{DSSE}$ scheme. The former captures that the newly updated entries cannot be related to previous search queries and the latter ensures that search queries should not leak matching entries after they have been deleted. These security properties are formalized in terms of the information leakage that can be incurred by the respective constructions. Existing backward private constructions either have a non-optimal communication overhead or they make use of heavy cryptographic primitives. Our main contribution consists of three efficient backward private schemes that aim to achieve practical efficiency by using light weight symmetric cryptographic components only. In the process, we also revisit the existing definitions of information leakage for backward privacy [Bost et al. CCS'17] and propose alternative formulations. Our first construction $\Pi_\mathsf{BP}\text{-}\mathsf{prime}$ achieves a stronger notion of backward privacy whereas our next two constructions $\Pi_\mathsf{BP}$ and $\Pi_\mathsf{WBP}$ achieve optimal communication complexity at the cost of some additional leakage. The prototype implementations of our schemes depict the practicability of the proposed constructions and indicate that the cost of achieving backward privacy over forward privacy is substantially small.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- Dynamic Searchable Symmetric EncryptionBackward PrivacyForward Privacy
- Contact author(s)
- shaha @ iisc ac in
- History
- 2019-05-08: received
- Short URL
- https://ia.cr/2019/446
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/446, author = {Sanjit Chatterjee and Shravan Kumar Parshuram Puria and Akash Shah}, title = {Backward Private {DSSE}: Alternative Formulations of Information Leakage and Efficient Constructions}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/446}, year = {2019}, url = {https://eprint.iacr.org/2019/446} }