Abstract
Searchable Symmetric Encryption (SSE) and its dynamic counterpart (DSSE) are designed to allow secure searching over encrypted data. However, these systems leak patterns that can be exploited. This paper introduces Peekaboo, a framework that breaks DSSE privacy even when an attacker can only observe the system intermittently. By reconstructing search patterns across disconnected observation rounds using co-occurrence logic and solving a Quadratic Assignment Problem (QAP), Peekaboo achieves up to 90% query recovery accuracy, significantly outperforming existing attacks that rely on continuous monitoring.
What Problem Does This Paper Address?
Searchable Symmetric Encryption (SSE) allows users to store encrypted data on a server and search through it without the server knowing the query content. Dynamic SSE (DSSE) adds the ability to update (add/delete) files. While these systems hide content, they leak "patterns"—such as which files are accessed (Access Pattern, AP) or the number of matching files (Volume Pattern, VP).
Most existing attacks assume a persistent attacker who monitors every query. In reality, attackers are often intermittent—they may go offline to avoid detection, or their view may be reset by database re-encryption or massive updates. Previous attacks fail here because they cannot link queries across these gaps. The authors ask: Can an attacker recover queries if they only see fragments of the leakage profile?
Methods: The Peekaboo Framework
The authors propose Peekaboo, which operates in two main phases:
1. Search Pattern Inference (P1)
This is the core innovation. The attacker groups queries within a single observation round (Internal SP) based on response similarity. To link these groups across different rounds (External SP), Peekaboo builds a "co-occurrence graph."
The framework assumes that even if file IDs change, the semantic relationship between keywords (e.g., "searchable" and "encryption" often appearing in the same files) remains stable. It matches these graphs across rounds by solving a Quadratic Assignment Problem (QAP).
2. Query Recovery (P2)
Once patterns are linked, Peekaboo uses auxiliary knowledge (e.g., public word frequency data or a similar unencrypted dataset) to map the observed patterns to specific keywords. The authors instantiated this by upgrading existing attacks into Sap+ and Jigsaw+.
Datasets
Peekaboo was evaluated using realistic datasets:
- Enron & Lucene Email Datasets: Standard corpora for corporate and technical communications.
- Wikipedia: Demonstrates scalability on large-scale, non-email data.
- PageViews: Real-world daily search trends used to simulate realistic query frequencies.
Key Insights
- Semantic Stability: While DSSE updates change file IDs and sizes, the semantic co-occurrence of words is a persistent signal that allows "stitching" together disconnected observation periods.
- Internal vs. External SP: Distinguishing between identical queries in the same round versus matching queries across different rounds is the key to defeating intermittent observation.
- Weakening the Attacker Model: Showing that an intermittent-observation attacker (IOA) is nearly as dangerous as a persistent one proves that "security through obscurity" tactics like periodic re-encryption are less effective than previously thought.
Key Results
- High Precision: Peekaboo achieved an Adjusted Rand Index (ARI) of >0.9 for search pattern recovery, clustering queries with near-perfect accuracy.
- Superior Recovery: Jigsaw+ reached ~90% accuracy using Access Pattern (AP) leakage. In contrast, the previous state-of-the-art (FMA) achieved only ~30% in the same intermittent setting.
- Resilience: Peekaboo maintained >40% accuracy against file size padding and >80% accuracy against obfuscation (dummy traffic), scenarios where previous attacks typically fail.
- Efficiency: The inference phase completes in just a few minutes, unlike statistical attacks that can take hours.
Limitations and Future Work
The attack's accuracy drops if the number of observed queries is very low (e.g., <500 per round). While robust, aggressive padding (e.g., padding all files to a uniform size) still degrades performance for attacks relying on File Volume Patterns (FVP). Future work may explore stronger padding or obfuscation techniques, like ORAM or PIR, to thwart co-occurrence-based matching without excessive overhead.
Summary updated