Private Stream Search at Almost the Same Communication Cost as a Regular Search

Matthieu Finiasz, Kannan RamchandranSelected Areas in Cryptography 2012 · DOI

Introduction

Private Stream Search (PSS) is a cryptographic protocol that allows a user to retrieve documents matching secret keywords from a server's stream or database without revealing the search criteria. Historically, PSS has faced a significant "privacy tax" in terms of communication bandwidth. Early schemes required the server to return a buffer significantly larger than the actual results—often $O(m \log m)$ times the document size for $m$ matches—to ensure successful reconstruction. This paper, presented at SAC 2012, introduces two new constructions that reduce this expansion factor to near unity, making private search communication costs comparable to non-private searches.

Problem Statement: The Communication Gap

The fundamental challenge in PSS is ensuring the user can reconstruct matching documents from an encrypted response without the server knowing which documents were selected. In a standard search, the server simply sends $m$ documents. In a private search, the server must provide a structure that hides the identity of the matches while still allowing their recovery. The authors aim to close the efficiency gap by treating PSS as a sparse recovery problem in the encrypted domain.

Methodology

The authors utilize Additive Homomorphic Encryption (AHE), specifically the Paillier cryptosystem and its Damgård-Jurik extension. AHE allows the server to perform linear operations (additions and scalar multiplications) on ciphertexts. The core innovation lies in applying coding theory principles—Reed-Solomon and irregular LDPC codes—to the encrypted data.

Reed-Solomon (RS) Construction

The first construction is a deterministic, "zero-error" approach suitable for a moderate number of matches. The server treats the document stream as a vector and computes a syndrome using an RS parity-check matrix. Since RS codes are Maximum Distance Separable (MDS), any $m$ documents can be perfectly reconstructed if the buffer size is at least $m$.

To minimize overhead, the authors employ a sophisticated bit-packing technique. This method embeds document indices and content into the same encrypted elements, effectively transforming the search problem into an erasure-correction problem once the indices are identified.

Bit-packing structure for the Reed-Solomon construction, embedding document indices and content into encrypted elements.

Irregular LDPC Construction

For scenarios involving a large number of matches, the authors propose a randomized approach using Low-Density Parity-Check (LDPC) codes. By generating a sparse matrix based on the documents, the server creates a compact return buffer. To ensure high recovery probability, they introduce an "Enhanced Harmonic Distribution" for column weights. This distribution allows the user to iteratively "peel off" and recover documents even when the buffer size is only slightly larger than the number of matches, effectively solving the collision problem where multiple documents map to the same buffer slot.

Offline-Online Querying

To address the issue of large query sizes (typically linear in the dictionary size), the authors suggest shifting the dictionary-dependent portion of the query to an offline phase. This allows the online query to remain logarithmic relative to the dictionary size, further improving practical efficiency.

Key Results and Insights

The research yields several significant advancements:

  • Asymptotic Optimality: By leveraging the Damgård-Jurik extension, the expansion factor (the ratio of private to non-private response size) approaches 1 as document size increases.
  • Efficiency Gains: Simulations show that for 200 results from a massive database, the expansion ratio is approximately 2.25 using standard Paillier encryption, a substantial improvement over the $O(\log m)$ overhead of previous methods.
  • Search as Syndrome Computation: The paper demonstrates that the server's task is fundamentally the computation of a syndrome for a sparse vector, allowing the application of mature error-correction coding techniques to cryptography.

Conclusion and Future Work

While this work significantly optimizes communication costs, challenges remain. The server's computational load is still high, requiring $O(mt)$ modular exponentiations for a database of size $t$. Furthermore, while the response is compact, the initial query remains large unless advanced primitives like Fully Homomorphic Encryption (FHE) are used, which are currently computationally prohibitive. Future research may focus on extending these techniques to complex "AND" queries and further reducing server-side processing requirements.

Summary updated

BibTeX
@inproceedings{finiasz2012private,
  author = {Matthieu Finiasz and Kannan Ramchandran},
  title = {{Private Stream Search at Almost the Same Communication Cost as a Regular Search}},
  booktitle = {Selected Areas in Cryptography},
  year = {2012},
  doi = {10.1007/978-3-642-35999-6\_24},
}
Figure