Information Theory in Privacy-Preserving Computation: How to Understand and Measure Information Leakage

Preface

When discussing privacy-preserving computation, we often say “raw data was not uploaded,” “sensitive attributes have been removed from the representation,” or “the attack model failed to guess.” However, these statements do not directly answer one question: exactly how much more does the attacker know after seeing the system’s output?

Information theory provides a way to express this question mathematically. It focuses not only on whether data is displayed exactly as-is, but also on whether the attacker’s uncertainty has decreased, and under what observations and background knowledge this reduction occurs.

This article primarily discusses discrete random variables. For continuous data, mutual information can still be defined via the KL divergence between probability distributions, but differential entropy can be negative, and deterministic mappings may lead to infinite mutual information. Therefore, one cannot mechanically replace every “entropy” in discrete formulas with its continuous counterpart and assume the result is a directly computable measure of leakage.

Clarifying First: Who Observes What?

We describe a basic scenario using four random variables:

A mechanism may transform $X$ into $Z$, but the privacy goal is usually to protect $S$. These two need not be equal: an image may contain content needed for classification as well as identity, location, or other information that should not be leaked.

Different $Z$ correspond to different attack surfaces. Publishing only the final class label differs from publishing the full probability vector; publishing only the final model differs from publishing client gradients for each round. Ignoring $A$ may lead to misjudging a actually recoverable secret as secure.

Entropy: How Uncertain Were We Before Observation?

For a discrete secret $S$, Shannon entropy is defined as

By convention, $0\log_2 0=0$, measured in bits. The entropy of a uniformly random bit is 1; the entropy of a variable that always takes the same value is 0.

Entropy describes uncertainty in an average sense over the distribution, not the byte count of a data file, nor the sensitivity level. A sensitive attribute that is almost always true may have very low entropy, yet still warrant protection.

When the attacker already knows $A$, a more appropriate baseline is conditional entropy:

If the auxiliary information already fully determines the secret, then $H(S\mid A)=0$. In this case, a new publication may not add information, yet this does not mean the secret remains unknown to the attacker.

For basic definitions, refer to Stanford’s Statistics and Information Theory course notes¹.

Mutual Information: How Much More Do We Know After Seeing the Output?

Starting from the Reduction in Uncertainty

After accounting for auxiliary information, the incremental leakage can be written as

Here, $H(S\mid Z,A)$ represents the remaining uncertainty after seeing the output. For discrete variables, conditional mutual information is non-negative; under the corresponding probabilistic model, it equals 0 if and only if $S$ and $Z$ are conditionally independent given $A$.

“Mutual information equals 0” means the output does not further change the attacker’s conditional distribution over the secret; it does not mean the attacker knows nothing, nor does it guarantee security under a different prior or with additional auxiliary information.

Starting from Changes in Posterior and Prior

The same quantity can also be expressed as

Thus, we can interpret it as: on average, how much does the observation shift the attacker’s posterior relative to the prior after having already incorporated the auxiliary information? KL divergence is not a symmetric distance; if $Q(s)=0$ while $P(s)>0$, the corresponding term becomes infinite.

Under log loss, the optimal predictor who knows the true conditional distribution has an expected loss equal to the conditional entropy. Therefore, conditional mutual information also corresponds to the average reduction in optimal log loss before and after observation. This interpretation depends on this loss function and cannot be directly converted into a general classification accuracy metric. ²

An Example: How Much Does Randomized Response Actually Leak?

Let the secret $S$ be a uniformly random bit, the mechanism independently sample $B\sim\operatorname{Bernoulli}(q)$, and publish

where $\oplus$ denotes XOR. In other words, the mechanism flips the true answer with probability $q$. Assuming the attacker has no additional relevant information, $Z$ remains a uniformly random bit, and

This is because $H(S)=1$, and given $Z$, the uncertainty of the secret is the same as that of the flipped variable. An optimal attacker directly guesses $S=Z$, with a success rate of $1-q$.

Note that even after one quarter of the answer has been flipped, the attacker can still guess correctly with 75% probability. Adding randomness does not mean the secret and the output are independent.

You can verify the numbers with the small example below, without needing real personal data:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

from math import isclose, log2


def binary_entropy(q):
    if not 0 <= q <= 1:
        raise ValueError("q must be between 0 and 1")
    if q == 0 or q == 1:
        return 0.0
    return -q * log2(q) - (1 - q) * log2(1 - q)


assert isclose(binary_entropy(0), 0.0)
assert isclose(binary_entropy(0.5), 1.0)
assert isclose(1 - binary_entropy(0.25), 0.18872187554086717)

for q in (0, 0.1, 0.25, 0.5):
    print(q, "leakage bits:", 1 - binary_entropy(q), "success:", 1 - q)

Why auxiliary information and multiple releases matter?

Unconditional mutual information can miss risks

Let $R$ be an independent uniform random bit, and let $Z=S\oplus R$ be released. If the attacker does not know $R$, then $I(S;Z)=0$; but if the auxiliary information is $A=R$, the attacker can directly compute $S=Z\oplus A$, in which case

This is not because XOR fails; rather, the condition under which protection holds has changed. When discussing any privacy metric, one must clearly specify what background knowledge the attacker possesses.

If individual releases do not leak, joint releases may still leak

Continuing with the previous example, release $Z_1=R$ and $Z_2=S\oplus R$ separately. Viewed individually, both are independent of $S$; viewed together, they allow recovery of $S$.

In general, the leakage of the full record $Z_{1:T}$ satisfies the chain rule:

Each term on the right must be conditioned on previous release results; one cannot simply sum unconditional single-release mutual informations. This is why federated learning analyses that consider only the gradients of a single round, ignoring prior models and communication content, yield incomplete conclusions.

What does the data processing inequality tell us?

If, given $A$, $S\to X\to Z$ forms a Markov chain, then

The Markov condition means: once $X$ and $A$ are known, the generation of $Z$ no longer depends additionally on $S$. Therefore, post-processing based solely on existing observations cannot create new information about the secret out of thin air. ³

But this is not a proof that “compressing makes it secure.” If $Z$ retains almost all content related to the secret from $X$, the inequality may still hold while leakage remains large. Conversely, a representation that is easier to use might enable attackers with limited computational power to perform inference more easily, even if its information-theoretic leakage has not increased.

If post-processing also accesses new auxiliary information, those data must be included in the model; one cannot continue using a Markov chain that omits the new inputs.

Fano’s inequality: from residual uncertainty to guessing error

Let the size of the secret’s value set be $M\ge2$, let the attacker construct an estimate $\widehat S$ based on $(Z,A)$, and let the error probability be $P_e=P(\widehat S\ne S)$. Fano’s inequality gives

If $S$ is uniformly distributed and independent of $A$, and we use $h_2(P_e)\le1$, we can derive a looser bound:

This shows: for this finite secret space, when leakage is small and the number of candidates is large, the error probability of any estimator has a lower bound. It is not an experimental result of a specific attack algorithm; in binary classification problems, this simplified form usually has no practical constraint and cannot be used to prove that membership inference is close to random guessing. ³

Privacy vs. utility: not about removing all information

If the output is completely independent of the input, privacy may be excellent, yet the task may become impossible. Let $Y$ be a useful prediction target; one information-theoretic modeling approach is

This is a schematic privacy–utility problem: we wish to reduce secret leakage while retaining task-relevant information. Practical systems may define utility using accuracy, reconstruction error, or other metrics, rather than directly using $I(Y;Z)$. If $S$ is strongly correlated with $Y$, these two objectives may inherently conflict. ²

A common experimental approach is to use a neural-network-based attacker to estimate sensitive attributes, then train an encoder to make the attacker fail. However, the cross-entropy of a finite model is typically larger than the optimal conditional entropy; an underpowered attacker will also yield high loss. Therefore, making an attacker fail does not prove that the true mutual information is small.

What is the difference between information-theoretic privacy and differential privacy?

Differential Privacy (DP) compares the output distributions of adjacent datasets. For a specified adjacency relation, and for all adjacent $D,D’$ and output events $E$, it is required that

The logarithm here uses the natural base, whereas the information quantity mentioned earlier uses $\log_2$. $\varepsilon$ constrains the distinguishability of the output distribution, while $\delta$ is the additive relaxation term for approximate DP and cannot be directly interpreted as “the probability that the system leaks all data is $\delta$”. The definition also needs to clarify whether adjacent datasets differ by adding/deleting one record, replacing one record, or adding/deleting all records of a user. ⁴

There is a theoretical connection between the two, but they are not the same definition. A small mutual information under a given prior does not automatically imply DP with specified parameters; nor does DP require that the model not learn any overall statistical patterns.

The aforementioned binary randomized response mechanism satisfies pure local DP on single-bit inputs when $0<q\le1/2$, with parameters

This is obtained by directly comparing the two output probabilities corresponding to the two inputs. When $q=1/2$, $\varepsilon=0$; when $q\to0$, the privacy parameter tends to infinity. Its DP parameters do not depend on a uniform prior, whereas the specific value of $I(S;Z)=1-h_2(q)$ mentioned earlier depends on the assumption of a uniform secret.

How to Use These Concepts in Machine Learning Experiments

First specify the secret, then specify the complete content visible to the attacker. For example, membership status, a specific attribute, and an entire training sample are different secrets and cannot be uniformly replaced by a single reconstruction error.

Subsequently, distinguish three levels: the distribution and mechanism analyzed theoretically, the mutual information or other proxy quantities estimated numerically, and the results obtained by a specific attacker implementation. These three can provide evidence for one another but cannot be arbitrarily interchanged.

Estimating mutual information for high-dimensional continuous data is particularly difficult. Discretization, sample size, estimator bias, and the training process all affect the results; numerical values obtained under different discretization schemes should not be directly compared horizontally. In federated learning, one must also incorporate multi-round interactions and auxiliary information into the analysis, rather than selecting only a single update that appears “non-leaking”.

Conclusion

Information theory shifts the privacy question from “whether raw data was sent” to “how much more is known after observation”. It is particularly well-suited for explaining average leakage, the role of auxiliary information, and the relationship with multiple releases.

However, an information quantity formula itself is not a complete security proof. Clearly specifying the secret, distribution, attack surface, and assumptions, and distinguishing between theoretical bounds, estimated values, and actual attack results, is key to applying these concepts in research.

References and Further Reading

Sources: ⁵.