We Can Make Mistakes: Fault-tolerant Forward Private Verifiable Dynamic Searchable Symmetric Encryption

Dandan Yuan, Shujie Cui, Giovanni Russello

TL;DR

This paper introduces a novel approach to Verifiable Dynamic Searchable Symmetric Encryption (VDSSE) that addresses a critical vulnerability: client-side errors during database updates. By building upon existing forward-private DSSE schemes, their method ensures data integrity and privacy even when clients make mistakes, offering a more robust solution for secure cloud data outsourcing.

What Problem Does This Paper Address?

Searchable Symmetric Encryption (SSE) allows users to store encrypted data on a cloud server and search it efficiently. Dynamic SSE (DSSE) extends this by enabling updates (adding/deleting keywords from documents). Verifiable DSSE (VDSSE) adds a crucial layer of security, allowing clients to verify that the server returns correct search results and rejects malicious ones. However, existing VDSSE schemes primarily focus on preventing malicious server behavior. They often fail when the client makes errors, such as attempting to delete a non-existent keyword-document pair or adding a duplicate pair. These "incorrect updates" can break the correctness and soundness guarantees of the VDSSE system, leaving clients vulnerable to accepting wrong results or rejecting correct ones. This paper tackles this gap by proposing a VDSSE scheme that is fault-tolerant to client-side update errors while maintaining forward privacy.

Methods

The authors propose a generic solution that can transform any DSSE scheme (especially forward-private ones) into a fault-tolerant VDSSE. Their core idea is to securely record the update history on the server side and append a proof to each update operation, rather than just to keywords. This is achieved using:

  • Authenticated Encryption (AE): To encrypt proofs, ensuring their integrity and authenticity. If the server tampers with a proof, the AE decryption will fail.
  • Pseudorandom Functions (PRFs) and Hash Functions: Used for generating various keys, tokens, and update identifiers.
  • Update History Recording: The server maintains a record of all updates for each keyword, including the operation (add/delete), document identifier, and a sequence number.
  • Client-Side Counters: The client keeps track of update sequence numbers for each keyword to detect incorrect operations.
  • Proof Renewal Mechanism: To manage the growing size of update histories and proofs, the client can periodically renew proofs by integrating verified update records into a single, new proof. This optimizes performance, especially when the number of updates exceeds the number of matching documents.

The authors demonstrate their approach by integrating it with the FAST [1] forward-secure DSSE scheme, creating a fault-tolerant VDSSE prototype.

Datasets

The paper evaluates their approach using five diverse datasets:

  • One real-world dataset from Wikimedia, containing 470,483 keywords and 8,388,608 keyword-identifier pairs.
  • Four synthetic datasets with varying numbers of keywords and keyword-identifier pairs, ranging from 5x10⁴ keywords and ~1 million pairs to 3.2x10⁶ keywords and ~65 million pairs.

Key Insights and Ideas

  • Client Errors are a Real Threat: The paper highlights that overlooking client-side update errors is a significant oversight in current VDSSE research, despite the potential for accidental mistakes in outsourced environments.
  • Update-Centric Proofs are Key: Shifting from keyword-centric proofs to proofs for each update operation is crucial for tracking and verifying the entire history, enabling fault tolerance.
  • AE is Essential for Proof Integrity: Using authenticated encryption for proofs is vital to detect tampering by a malicious server.
  • Proof Renewal Balances Security and Performance: The mechanism for renewing proofs is a clever way to manage the overhead associated with storing extensive update histories, striking a balance between security guarantees and practical efficiency.

Key Results

  • Fault Tolerance: The proposed scheme successfully tolerates incorrect client updates, such as deleting non-existent entries or adding duplicates, while maintaining correctness and soundness.
  • Storage Efficiency: Compared to Zhang et al.'s [7] scheme, their construction saves approximately 9x client storage.
  • Performance:
    • Update Efficiency: Their update protocol is efficient, with experiments showing it takes about 0.5 times longer than Zhang et al.'s scheme in a local setting, and slightly slower (0.4 times) when network latency is considered due to proof transmission.
  • Search Efficiency: With renewed proofs, their scheme is significantly faster (7-9x) than Zhang et al.'s scheme, especially when delete operations are frequent. Even without renewed proofs, their search efficiency is competitive.
  • Communication Overhead: While their scheme incurs higher communication overheads than Zhang et al.'s due to transmitting proofs, the use of renewed proofs significantly reduces this overhead.

Limitations and Future Work

  • Single-Keyword Search: The current solution only supports single-keyword searches.
  • Single-User Scenario: The scheme is designed for a single-user environment.

The authors suggest future work to address these limitations by extending their scheme to support complex queries and to multi-user scenarios.

Summary updated

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.
BibTeX
@article{yuan2022we,
  author = {Dandan Yuan and Shujie Cui and Giovanni Russello},
  title = {{We Can Make Mistakes: Fault-tolerant Forward Private Verifiable Dynamic Searchable Symmetric Encryption}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2022},
}

Loading related content...

Figure