Fault-tolerant Verifiable Dynamic SSE with Forward and Backward Privacy
Open Access
- 13 January 2025
- journal article
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 1 (4)
Abstract
Dynamic Searchable Symmetric Encryption (DSSE) allows users to securely outsource their data to cloud servers while enabling efficient searches and updates. The verifiability property of a DSSE construction ensures that users do not accept incorrect search results from a malicious server while the fault-tolerance property guarantees the construction functions correctly even with faulty queries from the client (e.g., adding a keyword to a document multiple times, deleting a keyword from a document that was never added). There have been very few studies on fault-tolerant verifiable DSSE schemes that achieve forward privacy, and none of the existing constructions achieve backward privacy. In this paper, we aim to design an efficient fault-tolerant verifiable DSSE scheme that provides both forward and backward privacy. First, we propose a basic fault-tolerant verifiable DSSE scheme, dubbed FVS1 , which achieves forward privacy and stronger backward privacy with the update pattern (BPUP). However, the communication complexity for the search operation of this scheme is O ( u ) , where u is the total number of updates for the search keyword. To address this issue, we propose an efficient variant of the previous DSSE scheme, called FVS2 , which achieves the same functionality with an optimized communication complexity of O ( m + u ′ ) for search queries. Here m is the size of the result set and u ′ is the number of update operations made on the queried keyword after the previous search made on the keyword. This improvement comes at the cost of some additional information leakage, but it ensures the construction achieves backward privacy with the link pattern (BPLP).Keywords
This publication has 24 references indexed in Scilit:
- Making searchable symmetric encryption schemes smaller and fasterInternational Journal of Information Security, 2024
- We Can Make Mistakes: Fault-tolerant Forward Private Verifiable Dynamic Searchable Symmetric Encryption2022
- Towards Efficient Verifiable Forward Secure Searchable Symmetric Encryption2019
- How to Record Quantum Queries, and Applications to Quantum Indifferentiability2019
- Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries2013
- How to Update Documents Verifiably in Searchable Symmetric Encryption2013
- UC-Secure Searchable Symmetric Encryption2012
- Privacy Preserving Keyword Searches on Remote Encrypted Data2005
- Incremental Multiset Hash Functions and Their Application to Memory Integrity Checking2003
- Building PRFs from PRPs1998