Perfect Secrecy in the Wild: A Characterization

Alice's problem

Let $X$ and $Y$ be two random variables with finitely supported joint distribution on $\mathcal{X} \times \mathcal{Y}$.

Alice knows $X$ and $Y$, Bob knows $Y$, and Eve knows neither.¹ The joint distribution of $X$ and $Y$ is common knowledge.

Alice would like to reveal $X$ to Bob, but wants Eve to learn nothing more about $X$ beyond what she already knows. The problem is that Alice can only speak publicly.

Under what conditions on the joint distribution of $X$ and $Y$ can Alice reveal $X$ to Bob while revealing no information about $X$ to Eve?

Perfect secrecy

The requirement that Eve must not learn anything about $X$ is called perfect secrecy, a term coined by Claude Shannon.

Denote Alice's public message by $Z$ and its message space by $\mathcal{Z}$. Formally, $Z$ satisfies perfect secrecy if Eve's posterior belief about $X$ after observing $Z$ equals her prior belief. That is, if \[ \forall (x, z) \in \mathcal{X} \times \mathcal{Z}, \quad\mathbb{P}( X = x \mid Z = z) = \mathbb{P}(X=x). \]

The one-time pad

A solution to Alice's problem is known in the special case where $Y$ is uniform and independent of $X$. In that case, Alice's problem is feasible if and only if $\# \mathcal{Y} \geq \# \mathcal{X}$ (Shannon, 1949).

Identify $\mathcal{X}$ with $\{0, 1, \ldots, n-1\}$ and $\mathcal{Y}$ with $\{0, 1, \ldots, m-1\}$. If Alice's problem is feasible; that is, if $m \geq n$, Alice sends the public message \[Z := X \oplus Y,\] where $\oplus$ denotes addition modulo $m$. Bob, knowing $Y$, can recover $X$ by computing \[Z \ominus Y = (X \oplus Y) \ominus Y = X,\] whereas Eve, who does not know $Y$, learns nothing about $X$ \[\begin{align*} \forall (x, z) \in \mathcal{X} \times \mathcal{Z}, \quad \mathbb{P}(Z = z \mid X = x) &= \mathbb{P}(X \oplus Y = z \mid X = x) \\ &= \mathbb{P}(x \oplus Y = z) \\ &= \mathbb{P}(Y = z \ominus x) = 1/m, \end{align*}\] where the first equality is the definition of $Z$, the second uses independence of $X$ and $Y$, and the last uses uniformity of $Y$ on $\mathcal{Y}$.

This construction is the one-time pad, introduced by Vernam (1919) and shown to be perfectly secret by Shannon in 1945 (the article was declassified in 1949).² The idea is that Alice and Bob meet beforehand and design $Y$ to be uniform and independent of $X$, to later use it as a cryptographic key.

A characterization

Here we interpret $Y$ as exogenous, rather than as a design choice. What if $Y$ is not uniform and independent of $X$? When is Alice's problem feasible in general?

Notice that if $Y$ is uniform and independent of $X$, condition (1) reduces to $\# \mathcal{Y} \geq \# \mathcal{X}$.³ More generally, $\# \mathcal{Y} \geq \# \mathcal{X}$ remains necessary, but is no longer sufficient.

If you are interested, you can find the proof of Theorem 1 in our paper. Necessity is a simple disjointness argument. Sufficiency follows from the Birkhoff-von Neumann theorem.

¹ By ''Alice knows X'' I mean that Alice can observe the realization of $X$.

² Shannon also showed that Alice's problem has no solution if $\#\mathcal{Y} < \#\mathcal{X}$.

³ If $Y$ is uniform and independent of $X$ then $\forall (x,y) \in \mathcal{X} \times \mathcal{Y}, \mathbb{P}(Y = y \mid X = x) = 1/\#\mathcal{Y}$.