We Can Make Mistakes: Fault-tolerant Forward Private Verifiable Dynamic Searchable Symmetric Encryption
Authors:
- 1 June 2022
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 587-605
Abstract
Verifiable Dynamic Searchable Symmetric Encryption (VDSSE) enables users to securely outsource databases (document sets) to cloud servers and perform searches and updates. The verifiability property prevents users from accepting incorrect search results returned by a malicious server. However, we discover that the community currently only focuses on preventing malicious behavior from the server but ignores incorrect updates from the client, which are very likely to happen since there is no record on the client to check. Indeed most existing VDSSE schemes are not sufficient to tolerate incorrect updates from the client. For instance, deleting a nonexistent keyword-identifier pair can break their correctness and soundness. In this paper, we demonstrate the vulnerabilities of a type of existing VDSSE schemes that fail them to ensure correctness and soundness properties on incorrect updates. We propose an efficient fault-tolerant solution that can consider any DSSE scheme as a black-box and make them into a fault-tolerant VDSSE in the malicious model. Forward privacy is an important property of DSSE that prevents the server from linking an update operation to previous search queries. Our approach can also make any forward secure DSSE scheme into a fault-tolerant VDSSE without breaking the forward security guarantee. In this work, we take FAST [1] (TDSC 2020), a forward secure DSSE, as an example, implement a prototype of our solution, and evaluate its performance. Even when compared with the previous fastest forward private construction that does not support fault tolerance, the experiments show that our construction saves 9× client storage and has better search and update efficiency.Keywords
This publication has 28 references indexed in Scilit:
- Verifiable Auditing for Outsourced Database in Cloud ComputingIEEE Transactions on Computers, 2015
- Practical Dynamic Searchable Encryption with Small Leakage2014
- How to Update Documents Verifiably in Searchable Symmetric Encryption2013
- Verifiable symmetric searchable encryption for semi-honest-but-curious cloud servers2012
- UC-Secure Searchable Symmetric Encryption2012
- The Software Performance of Authenticated-Encryption Modes2011
- Efficient Authenticated Data Structures for Graph Connectivity and Geometric Search ProblemsAlgorithmica, 2009
- Searchable symmetric encryption2006
- OCBACM Transactions on Information and System Security, 2003
- Incremental Multiset Hash Functions and Their Application to Memory Integrity Checking2003