Search Pattern Leakage in Searchable Encryption: Attacks and New Constructions

Chang Liu, Liehuang Zhu, Mingzhong Wang, Yu-an TanIACR ePrint 2013 · OpenReview

Abstract

Searching on remote encrypted data (searchable encryption) has become an important issue in secure data outsourcing, as it allows users to maintain keyword search capabilities on encrypted data stored with untrusted third parties. However, many efficient searchable encryption schemes leak statistical information about the users' search patterns. This paper presents two concrete attack methods demonstrating that an adversary with auxiliary knowledge can uncover underlying keywords. To address this, the authors develop a Grouping-Based Construction (GBC) to hide search patterns. Experiments on real-world datasets demonstrate both the effectiveness of the attacks and the feasibility of the proposed defense.

The Problem: Metadata as a Fingerprint

Searchable Encryption (SE) allows users to store encrypted data on a cloud server while maintaining the ability to search through it. To be efficient, most current SE schemes are "deterministic," meaning the same keyword always generates the same encrypted search token.

While the cloud provider cannot "read" the keyword directly, they can see the search pattern: they know when you search for the same thing twice. This seemingly minor leak is a significant threat. If an adversary (like a curious cloud administrator) has auxiliary knowledge—such as public search statistics or a user's professional background—they can perform statistical matching to de-anonymize the encrypted queries and figure out exactly what the user is looking for.

Attack Methodologies

The paper contributes both on the offensive and defensive sides, starting with two primary attack vectors:

1. The General Attack

The attacker records the frequency of a specific encrypted query over time (e.g., weekly). They then compare this "frequency vector" against public data like Google Trends using similarity measurements (like Euclidean distance) to find the best-matched keyword.

Visualizing search pattern matching: (a) shows an unknown query's frequency over time, while (b) shows the trends for known keywords like 'obama', 'soccer', and 'spring'.

As illustrated in the figure above, the rhythm of search acts as a fingerprint. For example, a spike in a specific query on a certain week strongly suggests a match with keywords that trended during that same period in public datasets.

2. The Adaptive Attack

This is a more sophisticated version where the attacker dynamically adjusts their auxiliary knowledge. If they identify a few keywords related to a specific domain (e.g., "medicine"), they shift their statistical model to focus on medical search habits, increasing the accuracy of future guesses.

The Defense: Grouping-Based Construction (GBC)

The authors demonstrate that simply adding random fake queries to a search doesn't work because an attacker can use "set-intersection" over multiple searches to isolate the real keyword. To fix this, they propose GBC:

  • Dividing: Keywords are sorted by frequency and divided into groups of size $k$.
  • Grouping: When a user searches for a keyword, the system automatically generates queries for every keyword in that group.
  • Result: To the cloud server, every keyword in a group looks identical. The "search pattern" is transformed into a "group pattern," making it much harder to distinguish individual terms.

Experimental Results

The researchers evaluated their work using the Enron Email Dataset (~500,000 emails) and Google Trends as the source of "auxiliary knowledge."

  • Attack Potency: In the General Attack, the researchers achieved nearly 100% accuracy in identifying keywords when the user's search habits closely matched Google Trends. Even with significant "noise," accuracy remained above 90%.
  • Adaptive Success: The Adaptive Attack started with only 20% accuracy but climbed to 65-80% as it "learned" the user's specific category.
  • Defense Strength: GBC proved highly effective. Even if an attacker could correctly guess which sub-query was the "real" one 50% of the time, their final keyword identification accuracy dropped to just 9%.
  • Efficiency: While GBC increases computation, the absolute time is negligible. For a group size of $k=10$, the search execution time remained well under 1 millisecond.

Limitations and Future Work

While GBC hides the search pattern, it still leaks a "group pattern." The authors acknowledge that quantifying exactly how much information this group pattern reveals remains an open research problem. Additionally, users must maintain group mappings locally, which adds a small amount of management overhead. Despite these factors, GBC represents a significant step forward in securing searchable encryption against statistical analysis.

Summary updated

Abstract

Searching on remote encrypted data (commonly known as \textit{searchable encryption}) has become an important issue in secure data outsourcing, since it allows users to outsource encrypted data to an untrusted third party while maintains the capability of keyword search on the data. Searchable encryption can be achieved using the classical method called oblivious RAM, but the resultant schemes are too inefficient to be applied in the real-world scenarios (e.g., cloud computing). Recently, a number of efficient searchable encryption schemes have been proposed under weaker security guarantees. Such schemes, however, still leak statistical information about the users' search pattern. In this paper, we first present two concrete attack methods to show that the search pattern leakage will result in such a situation: an adversary who has some auxiliary knowledge can uncover the underlying keywords of user queries. To address this issue, we then develop a grouping-based construction (GBC) to transform an existing searchable encryption scheme to a new scheme hiding the search pattern. Finally, experiments based on the real-world dataset demonstrate the effectiveness of our attack methods and the feasibility of our construction.
BibTeX
@article{liu2013search,
  author = {Chang Liu and Liehuang Zhu and Mingzhong Wang and Yu-an Tan},
  title = {{Search Pattern Leakage in Searchable Encryption: Attacks and New Constructions}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2013},
  url = {https://openreview.net/forum?id=tEay46YGfP},
}
Figure