clarify perfect secrecy definition

Question

One of the notes defined perfect secrecy (PS) as

Let E = (E,D) be a Shannon cipher defined over (K,M, C). Consider a probabilistic experiment in which the random variable k is uniformly distributed over K. If for all m0, m1 , and all c, we have

Pr[E(k, m0) = c] = Pr[E(k, m1) = c]

it is perfectly secret.

My only concern with definition is that I think it lacks to say "for all K", isn't it? Or I am missing something?

Answer 1

The question's definition is OK, and must not be changed by adding "for all $k$" as considered.

---

The quantity $\operatorname{Pr}[E(k,m_0)=c]$ is the probability that $m_0$ encrypted by $E$ under key $k$ is $c$, where $k$ is taken as uniformly distributed over the set $K$ of possible keys. The nature of $k$ is told well enough by

Consider a probabilistic experiment in which the random variable $k$ is uniformly distributed over $K$.

The equality $\operatorname{Pr}[E(k,m_0)=c]\,=\,\operatorname{Pr}[E(k,m_1)=c]$ is about two probabilities being equal. These probabilities are real numbers between $0$ and $1$, that are a proportion of $k$ in $K$ verifying the bracketed property. These probability are computed independently.

In other words, for finite $K$, the property tells that for any choice of $m_0$ , $m_1$ , and $c$ , there are as many $k$ in the (non-empty) set $K$ such that $E(k,m_0)=c$ , as there are $k$ in $K$ such that $E(k,m_1)=c$ .

Addition per comment: In the definition's $\operatorname{Pr}[E(k,m_0)=c]\,=\,\operatorname{Pr}[E(k,m_1)=c]$ , variable $k$ has the same meaning on both sides, but takes independent values for separate evaluation of the two probabilities over the hypothesized distribution of $k$ in $K$ . We know this because $k$ is not fixed, rather we are told $k$ has a certain distribution, hence that must be the distribution used to compute the probability. Some would write $$\operatorname{Pr}_{k\in K}[E(k,m_0)=c]\,=\,\operatorname{Pr}_{k\in K}[E(k,m_1)=c]$$ with $\operatorname{Pr}_{k\in K}[\dots]$ to be understood/read as probability for $k$ uniformly random in $K$ that $\dots$

---

If we changed the question's

$\forall m_0\in M$ , $\forall m_1\in M$ , $\forall c\in C$ , $\ \operatorname{Pr}[E(k,m_0)=c]\,=\,\operatorname{Pr}[E(k,m_1)=c]$

into

$\forall k\in K$ , $\forall m_0\in M$ , $\forall m_1\in M$ , $\forall c\in C$ , $\ \operatorname{Pr}[E(k,m_0)=c]\,=\,\operatorname{Pr}[E(k,m_1)=c]$

then the meaning would change radically. The value $k$ would be fixed (and the same on both sides of the equality) when computing the probabilities, which would be without a relevant variable. $\operatorname{Pr}[E(k,m_0)=c]$ would be either $1$ or $0$ depending on if $E(k,m_0)=c$ or not for the particular value of $(k,m_0,m_1,c)$ considered (same for $\operatorname{Pr}[E(k,m_1)=c]$ ). In the end, the whole property would mean: the choice of $m$ does not influence $E(k,m)$ for any value of $k$. If decryption is possible (and $C$ and $K$ are non-empty), this implies that the set $M$ has at most a single element, which is dull.

Answer 2

"For all $k$, ..." would be a statement of the form that is formalized by first-order logic, but what's going on here is different, we're talking about probability theory, and if you're better accustomed to mathematical logic you'll find the way that people write these things rather informal. Note that in the formula:

$$ Pr\big[E_k(m_0) = c \big] = Pr\big[E_k(m_1) = c \big] $$

...the two separate, seemingly free occurrences of $k$ cannot be read as they would in logic, as free variables in the same scope, but rather as if each was individually bound by the $Pr[\dots]$ operator that scopes over it. If both occurrences of $k$ were bound in the same scope they would have the same value, and that would make the proposition trivially false (counterexample: choose any $m_0 ≠ m_1$).

And in contrast to $k$, the two occurrences of $c$ are in fact intended to denote the same value. Nothing in the notation explicitly distinguishes these two treatments; you're expected to infer it from the accompanying text.

A more logically rigorous formulation might look a bit like this. Imagine that the notation $Pr_{x \in X}[P(x)]$ stands for "the probability of $P(x)$ when $x$ is sampled at random from the distribution $X$." Then we could write something like this (somewhat made up) notation:

$$ \forall_{m_0, m1, c \in M} \bigg[ Pr_{k \in K}\big[E_k(m_0) = c \big] = Pr_{k \in K}\big[E_k(m_1) = c \big] \bigg] $$

But in real life you're just going to have to get used to "reading between the lines" when dealing with crypto textbooks or papers (or math in general):

• Which variables are bound by universal or existential quantifiers, vs. which ones are bound to random samples.
• When variables are bound to samples, which probability distribution the sample is drawn from.
• The scope of each occurrence of a variable. And as seen in this example, sometimes you have to infer that two occurrences of the same variable must be read in different scopes, sometimes that it is the same scope.