Source-linked AI summary
Hiding the Access Pattern is Not Enough: Exploiting Search Pattern Leakage in Searchable Encryption
Simon Oya, Florian Kerschbaum
TL;DR
Search-pattern leakage may undermine SSE defenses that primarily hide access patterns. The paper develops a maximum-likelihood query-recovery attack combining access and search-pattern leakage, and finds that two of three evaluated defenses fail to provide significant protection even at high privacy settings.
Problem
Existing SSE defenses focus on hiding access patterns, but assessing their practical protection is difficult and search-pattern leakage remains insufficiently addressed.
Method
The attack formulates query recovery as a maximum likelihood estimation problem, combining access-pattern volume information, search-pattern frequency information, and weak auxiliary information.
Results
Two of three evaluated defenses fail to provide significant protection at high privacy settings, while the third still permits 23% recovery from 250 possibly repeated queries among 1000 keywords.
Takeaways & Limitations
Hiding access patterns or response volumes alone may not prevent query recovery because combined volume and frequency information can yield surprisingly high recovery rates.
Takeaways & Limitations
For SEAL, the analysis assumes distinct keywords generate distinct access patterns because hiding the search pattern may require a value of α that significantly reduces efficiency.
Abstract
from arXiv · showhide
Recent Searchable Symmetric Encryption (SSE) schemes enable secure searching over an encrypted database stored in a server while limiting the information leaked to the server. These schemes focus on hiding the access pattern, which refers to the set of documents that match the client's queries. This provides protection against current attacks that largely depend on this leakage to succeed. However, most SSE constructions also leak whether or not two queries aim for the same keyword, also called the search pattern. In this work, we show that search pattern leakage can severely undermine current SSE defenses. We propose an attack that leverages both access and search pattern leakage, as well as some background and query distribution information, to recover the keywords of the queries performed by the client. Our attack follows a maximum likelihood estimation approach, and is easy to adapt against SSE defenses that obfuscate the access pattern. We empirically show that our attack is efficient, it outperforms other proposed attacks, and it completely thwarts two out of the three defenses we evaluate it against, even when these defenses are set to high privacy regimes. These findings highlight that hiding the search pattern, a feature that most constructions are lacking, is key towards providing practical privacy guarantees in SSE.
1 Introduction
SSE enables private searches over encrypted databases but commonly leaks both document matches and whether queries repeat keywords. This work develops and evaluates an MLE attack that combines these leakages to recover query keywords and undermine several defenses.
- Background: SSE lets clients query encrypted databases through server-evaluated search indexes, while point queries retrieve documents matching specified keywords.The client encrypts the database, generates an index and query tokens, and sends them to the server.
- Background: Access patterns reveal matching document identifiers, whereas search patterns reveal which queries in a sequence are identical.Servers can use either leakage source for query or database recovery attacks.
- Contributions: The proposed MLE attack combines access and search pattern leakage with weak auxiliary information to identify queried keywords and can be adapted to particular defenses.The attack does not require the true document or keyword distribution and is tailored to three privacy-preserving SSE schemes.
- Results: The attack is orders of magnitude faster and more accurate than graph matching when clients do not query every possible keyword, and it outperforms a search-pattern-only attack.Its advantage comes from combining volume and frequency leakage information.
- Results: Against three recent defenses, adapted attacks restore accuracy from 1.4%, 2.4%, and 2.7% to 30%, 35%, and 23%, respectively, at high privacy settings.Two defenses fail to provide meaningful protection despite more than 400% communication overhead; the third still leaks a non-trivial amount of keywords.
2 Related Work
Related work distinguishes query and database recovery attacks by their goals and leakage requirements. Existing attacks use access patterns, search patterns, or both, while defenses trade privacy against communication or computational efficiency.
- Attack Taxonomy: SSE attacks include active file-injection attacks and passive database- or query-recovery attacks.Query recovery may also enable database recovery when recovered queries identify documents matching keywords.
- Query Recovery: Point-query recovery attacks separately exploit access-pattern leakage or search-pattern leakage to infer the client’s queried keywords.IKK uses keyword co-occurrence and strong ground-truth assumptions, while graph matching improves robustness to imperfect auxiliary distributions.
- Query Recovery: Search-pattern-only attacks track frequencies of repeated query tags over time and match their trends against keyword trend information.This approach uses frequency information without access-pattern data.
- Combined Leakage: This paper introduces the first point-query SSE attack that jointly leverages access and search pattern leakage through maximum likelihood estimation.The attack targets query recovery rather than frequency-based database recovery.
- Defenses: Existing defenses hide access patterns or query frequencies, while ORAM-based approaches can impose significant communication overhead and may still leak response volume.Other schemes add false positives and negatives, use ORAM relaxations, or pad response volumes with noise or powers of a constant.
3 Preliminaries
The system model treats an honest-but-curious server as observing encrypted point-query executions and assigning tags to repeated access patterns. The attack maps those tags to keywords using leakage-derived structures and auxiliary background information.
- System Model: The client outsources a symmetrically encrypted database and query index, while the honest-but-curious server seeks to identify each query’s underlying keyword.The model focuses on point queries over documents associated with keywords.
- Observed Leakage: The adversary observes timestamped access patterns, where response volume is the number of documents returned by a query.Access patterns are vectors indicating the positions of matching documents.
- Observed Leakage: Search-pattern leakage identifies repeated queries, either through identical query tokens or identical access patterns generated by the same keyword.The adversary assigns a tag to each distinct observed access pattern and maps tags injectively to keywords.
- Attack Inputs: The model records query volume, co-occurrence, query counts, and interval-based tag frequencies, then compares them with keyword-level auxiliary structures.Auxiliary volume and co-occurrence data come from a disjoint training set, while query trends use public information with a time offset.
- Prior Attack: Graph matching maps tag and keyword graphs by optimizing similarity between their co-occurrence structures, but standard implementations require equal graph sizes.When m < n, dummy nodes are added, which hampers performance when m is much smaller than n.
4 Search and Access Pattern-Based Query Recovery Attack
The attack recovers query keywords by maximizing the likelihood of observed volumes and frequencies under auxiliary keyword information, using a model of client behavior and database responses. It reduces the estimation to an efficiently solvable assignment problem and can weight frequency and volume evidence differently.
- Attack formulation: The attack combines observed keyword volumes and query frequencies with auxiliary volume and frequency information in a pure maximum likelihood estimation framework.It deliberately avoids co-occurrence matrices and instead estimates the keyword-to-tag mapping from volume and frequency evidence.
- Observation model: The model assumes independent query choices governed by observed frequencies and independently generated document keywords governed by auxiliary keyword volumes.Query counts follow a Multinomial model, while response volumes follow a Binomial model.
- Maximum likelihood estimator: The estimator maximizes the logarithm of Pr(F,η,v,ND|˜F,˜v,P), discarding additive terms independent of the keyword assignment P.Taking logarithms avoids precision issues without changing the optimization problem.
- Optimization: The frequency and volume likelihood terms are represented as two n×m cost matrices and combined into an unbalanced assignment problem.The matrices encode the respective frequency and volume contributions to assigning observed tags to keywords.
- Optimization: The unbalanced assignment problem can be solved with the Hungarian algorithm in O(n·m+m^2·logm) time.A coefficient α ∈[0,1] can adjust the relative weight of frequency and volume information.
5 Adapting the Attack against Privacy-Preserving SSE Schemes
The attack is adapted to privacy-preserving SSE defenses by modeling how each defense transforms response volumes or access patterns, then modifying the likelihood calculation accordingly. The adaptations cover randomized access-pattern obfuscation, noisy volume padding, and quantized response volumes, while SEAL may still leak the search pattern under its typical parameter choices.
- Adaptation methodology: The attack adapts to three privacy-preserving SSE schemes by characterizing the probability of each observed keyword response volume under the defense.The methodology is intended to apply to other defenses that partially hide access patterns.
- CLRZ: CLRZ obfuscates the inverted index by independently adding false positives and false negatives according to FPR and TPR.The attack substitutes the post-obfuscation document-match probability for the original keyword volume in its likelihood calculation.
- PPYY: PPYY hides access-pattern structure by storing independent document-keyword pairs, but uses keyword-specific response volumes and adds Laplacian noise with scale 2/ε.For ε < 1, the noisy volumes can make keywords differing by one document indistinguishable to an adversary.
- PPYY: PPYY adds a constant padding term whose size grows with the number of keywords to keep negative noisy volumes unlikely.The attack computes the resulting volume likelihood by convolving Binomial and shifted Laplace distributions and discretizing with the ceiling function.
- SEAL: SEAL hides exact access patterns with ORAM blocks and pads response volumes to the nearest power of x.The attack models the probability that a Binomial response volume falls within each quantization interval.
- SEAL: SEAL can obscure the search pattern through access-pattern collisions only with sufficiently small α, which may significantly reduce efficiency.The original work uses large α values close to log2 ND, so the attack treats distinct keywords as producing distinct access patterns.
6 Evaluation
The evaluation tests sap on two real email datasets, compares it with prior attacks, and measures its behavior against three privacy-preserving SSE defenses. Combining volume and frequency information improves recovery, while defense-aware adaptation restores substantial accuracy against two defenses and leaves meaningful residual accuracy against another.
- Experimental Setup: Experiments use Enron and Lucene email datasets, with randomly selected keyword universes and Google Trends query information over 50 weeks.Each dataset is split between the client and adversary for auxiliary information; query counts are generated from popularity data.
- Preliminary Experiments: Combining volume and frequency information more than doubles accuracy compared with using either source alone, leading to the α = 0.5 configuration.Using only volume or frequency gives below 15% accuracy for n = 1000 in Enron.
- Comparison with Other Attacks: Sap is approximately four times more accurate than graphm and freq when clients perform few queries, while graphm takes roughly two orders of magnitude longer.At ¯η = 500 in Enron, graphm slightly exceeds sap in average accuracy, but remains far slower.
- Comparison with Other Attacks: Graphm relies heavily on observing almost all possible keywords, whereas sap outperforms it when the client does not query every keyword.The authors attribute graphm’s behavior to the structure of its graph-matching formulation when m ≪ n.
- Performance against Defenses: Against CLRZ, adapting sap raises accuracy from ≈1% to 30% for n = 1000 in Lucene at FPR = 0.1, despite the defense’s high overhead.The cited setting returns around 10% of the dataset per query and incurs approximately 400%–500% overhead.
- Performance against Defenses: Against PPYY with ε = 0.1, defense-aware sap recovers 35% accuracy after the naive attack falls from 37% to ≈2% in Lucene with n = 1000.The paper notes that this high differential privacy regime does not prevent the tailored attack from recovering queries at near-undefended accuracy.
- Performance against Defenses: Multiplicative volume padding reduces accuracy from 37% to 3% at x = 4, while a defense-aware attack restores it to 23%.The paper characterizes this technique as more protective than the other evaluated defenses with less bandwidth overhead.
- Performance against Defenses: Both volume and frequency information contribute to sap’s success across the defense experiments.The paper identifies this contribution by comparing combined-attack accuracy with the frequency-only baseline.
7 Discussion: Preventing Frequency Leakage
The discussion examines defenses against frequency leakage by hiding repeated-query information, randomizing access patterns, or adding dummy queries. Each option faces practical privacy or efficiency challenges.
- Hiding the Search Pattern with Collisions: Search-pattern hiding prevents the adversary from identifying repeated queries and computing observed query frequencies.
- Hiding the Search Pattern with Collisions: Grouping keywords through access-pattern collisions can reduce leakage, but semantically similar keywords may remain identifiable within each group.
- Hiding the Search Pattern with Fresh Randomness: Fresh randomized access patterns may still reveal keyword groups because queries for the same keyword can produce statistically similar patterns that are clusterable.
- Hiding the Query Frequencies with Dummy Queries: Dummy queries could obscure query frequencies, but timing, keyword-storage, and attack-adaptation problems make effective deployment challenging.
8 Conclusions
The paper presents a query-recovery attack that combines volume and frequency leakage through maximum likelihood estimation. Across privacy-preserving SSE defenses, two fail to provide significant protection at high privacy settings, while the third still permits non-trivial recovery.
- The attack formulates query recovery as maximum likelihood estimation and solves it as an unbalanced assignment problem.
- Combining access-pattern volume information with search-pattern frequency information enables high recovery rates even when either source alone is not threatening.
- Two evaluated defenses fail to provide significant protection against the adapted attack even in high privacy regimes.
- The findings motivate reducing search-pattern leakage as well as access-pattern leakage in privacy-preserving SSE.
A Results as Percentage of Distinct Keywords Recovered
This appendix reports recovery accuracy by distinct keywords rather than query frequency. The unweighted results preserve the qualitative comparison among attacks and defenses, although recovered-keyword counts are lower than recovered-query counts.
- Unweighted accuracy measures the percentage of unique keywords correctly identified, without weighting keywords by query frequency.
- sap and freq achieve lower unweighted than regular accuracy because they more often recover frequently queried keywords.
- The unweighted results against the three defenses are qualitatively the same as the regular-accuracy results, despite recovering fewer unique keywords than queries.
- Unweighted accuracy is evaluated against the CLRZ defense with TPR = 0.999 while varying FPR over 50 weeks at 5 queries per week.
- Unweighted accuracy is also evaluated against PPYY and SEAL across their respective privacy or padding settings over 50 weeks.