Bayesian Leakage Analysis, Part 1: What Does It Mean to Exploit Leakage?

Leakage profiles are now standard in encrypted-search security definitions, and rightly so. They make explicit what an adversary can observe, they enable meaningful comparisons between schemes, and they give designers concrete targets. But once a profile is written down, a natural question follows: how exploitable is it?

That question turns out to be harder than it looks. A leakage profile describes what is observable. Exploitability depends on what an adversary can do with those observations, which in turn depends on the adversary’s auxiliary information, the structure of the hidden variables, and the objective the adversary is trying to achieve. Two profiles that look equally revealing can have very different exploitability characteristics under realistic conditions. Two profiles that look harmless can become damaging when paired with the right auxiliary distribution.

This post describes a framework that makes these dependencies precise. The core idea is that leakage exploitation is a Bayesian inference problem, and that treating it as one gives us both a useful metric for exploitability and structural bounds that separate the different sources of inferential difficulty. A companion second post covers the automation layer that turns this framework into a reusable attack engine.

The Problem with Recovery Rate

Consider a concrete scenario. An adversary attacks an encrypted database using query-equality leakage and achieves 85% recovery of the underlying queries. Is that a lot? The answer depends entirely on what would have happened without the leakage.

Suppose the adversary has strong auxiliary information about the query distribution — say, a Zipf model with good parameter estimates. In many realistic regimes, the mode of that distribution is already quite peaked. A baseline adversary that ignores leakage entirely and simply guesses from the auxiliary distribution might already achieve 75% recovery. In that case, the leakage contributed only 10 percentage points of additional success, not 85.

This is not an edge case. In encrypted search, auxiliary information often comes from public corpora, known-data fractions, or structural priors, and these can be strong. Raw recovery rate confounds two effects: the strength of the prior and the incremental value of leakage. If we want to understand what leakage itself contributes — which is the question a scheme designer actually needs to answer — we need to subtract the baseline.

We define advantage as the absolute gap in success probability between an adversary that uses both leakage and auxiliary information, and one that uses auxiliary information alone. This is a simple change, but its consequences are significant. It means that a high-advantage leakage profile is one that genuinely helps an adversary beyond what they could do with prior knowledge, and a low-advantage profile is one where leakage adds little even if raw recovery numbers look impressive.

The Inference Model

To make advantage precise, we need to say what the adversary’s inference problem actually looks like. We model a leakage setting as a joint random variable [ \mathbf{X}=(\mathbf{S},\mathbf{H},\mathbf{L}), ] where (\mathbf{S}) is the secret (the thing the adversary wants to recover), (\mathbf{H}) captures hidden structure (such as a random permutation that maps queries to leakage symbols), and (\mathbf{L}) is the observed leakage. The adversary brings an auxiliary distribution (\alpha) over the secret space, which represents its prior beliefs.

The reason for writing things this way is not formalism for its own sake. It forces every leakage analysis to be explicit about what is secret, what is hidden, what is observed, and what the adversary assumes. In practice, many attack papers mix these assumptions implicitly — they sample data one way, generate auxiliary information another way, and define success in a way that makes it hard to tell what caused recovery. When ((\mathbf{S}, \mathbf{H}, \mathbf{L}, \alpha)) are written down together, assumptions become testable.

Given observed leakage (\ell), the adversary computes a posterior over secrets by combining the likelihood (which comes from the leakage model) with the prior (which comes from auxiliary information). The attack is then whatever decision rule the adversary applies to that posterior. For full recovery, the natural choice is MAP estimation — guessing the secret with the highest posterior probability. For functional recovery (recovering some function of the secret rather than the secret itself), we define analogous MAP-test estimators. These are not the only possible adversaries, but they are strong, standard, and structured enough to support precise analysis.

Three Sources of Difficulty

The central technical result for these adversaries is a bound that decomposes MAP advantage into three terms: [ \operatorname{Adv} \le 2^{-\Lambda_\infty} + 2^{-\Sigma} + 2^{-\chi}. ] Each term captures a distinct mechanism that makes leakage exploitation harder.

Leakage entropy ((\Lambda_\infty)) measures how ambiguous the leakage is about the secret, once auxiliary information is accounted for. When the leakage strongly concentrates the posterior on one candidate, leakage entropy is high and this term is small. When many candidates remain plausible under the posterior, this term dominates.

Singular entropy ((\Sigma)) measures the extent to which the leakage model permits direct inversion — whether the mapping from secrets to leakage is one-to-one or many-to-one. When the leakage function is injective (every secret produces a different observation), this term vanishes. When many secrets map to the same leakage symbol, singular entropy contributes real difficulty.

Modal entropy ((\chi)) captures the alignment between the true secret distribution and the adversary’s auxiliary distribution. Even if the adversary has a good model of the distribution shape, if the ranking of the most likely values is wrong, the MAP estimator’s mode-seeking behavior can lead it astray.

The decomposition matters because these three effects are often conflated in informal arguments. A claim like “this leakage is hard to exploit” could mean any of: the leakage is ambiguous, the secret-to-leakage mapping has large fibers, or realistic auxiliary information tends to be misaligned with the true distribution. These are different failure modes with different practical implications, and the bound separates them.

Query Equality: A Worked Case

To see what this decomposition buys concretely, consider query-equality leakage — probably the most-studied leakage pattern in encrypted search. An encrypted database processes a sequence of queries (q_1, \ldots, q_n) from an (m)-element alphabet. The leakage reveals which queries are equal (the equality pattern) but not their actual values. We can model this as applying a hidden random bijection (\pi) that maps each query value to a leakage symbol: the adversary sees (\pi(q_1), \ldots, \pi(q_n)) and knows the equality structure but not the labeling.

Suppose queries follow a Zipf distribution with parameter (\gamma) and the adversary’s auxiliary distribution is also Zipf (the matched-parameter setting). What does the bound say?

The first term (leakage entropy) depends on how many distinct bijections are consistent with the observed equality pattern. When the sequence is long enough to produce many distinct symbols, most bijections are ruled out and this term shrinks. The third term (modal entropy) depends on how well the adversary’s Zipf ranking matches the true ranking. In the matched case it vanishes, because the most-likely assignment under the auxiliary distribution is the correct one. But under mismatch — where the adversary uses the wrong Zipf parameter or gets the ranking wrong — this term can dominate the bound and make it vacuous.

Two things emerge from the instantiation. First, scaling helps the adversary: as the number of queries grows relative to the alphabet size, the leakage-entropy term decays. This formalizes the intuition that longer transcripts are more revealing, but it does so quantitatively. Second, auxiliary quality matters in a structured way: ranking mismatch (getting the relative frequency ordering wrong) is a more severe failure mode than parameter mismatch (getting the Zipf exponent wrong). The bound captures this distinction explicitly, which is something raw recovery-rate comparisons cannot do.

Looking Forward

The framework through this point gives us a precise language for stating what leakage does and does not contribute to attack success, and structural bounds that reveal where inferential difficulty comes from. But there is a practical limitation: the analysis is still per-model and per-leakage-pattern. Every new profile requires its own instantiation, its own bound calculation, and often its own attack implementation.

The next post addresses that limitation directly. Once leakage models are explicit probabilistic objects with the structure described here, they can be encoded as Bayesian networks and attacked through a reusable inference engine. That is where the framework moves from analytical tool to automated methodology.