Your Keywords Know Each Other: Breaking SSE with <1% Leaked Documents

Searchable symmetric encryption (SSE) schemes inevitably leak search, access, and volume patterns, which adversaries can exploit along with partial knowledge of the data to recover documents and queries. Prior passive attacks rely on document-keyword occurrence matching, but under realistic low leakage, many keywords induce identical patterns, forming large ambiguous groups that sharply limit recovery.

We observe this failure arises from missing relational signals among keywords. Keywords, however, exhibit stable semantic regularities across corpora even when direct co-occurrence is sparse, allowing external linguistic knowledge to augment observed leakage. Based on this insight, we present Whisper, a staged co-occurrence augmented query recovery framework that weaves LLM-synthesized corpora with pre-trained embeddings to densify co-occurrence matrices and disambiguate otherwise indistinguishable candidates.

We evaluate Whisper on six diverse real-world datasets, including three collected in late 2025 to test generalization beyond LLM training cutoffs. At 0.1% leakage, previously considered safe, Whisper boosts correct query recovery from 17-27% under current SOTA to 36-49% across all datasets, a 2-2.5× improvement. Even at 1% leakage, Whisper approaches near-complete recovery, exceeding 80% on most datasets and peaking at 95%, while remaining effective against padding and volume hiding defenses, exposing a previously underestimated vulnerability in SSE.

Unique Match Found?