# How can the identity $\textbf{Pr}[\textbf{y}=y|\textbf{x}=x] = \sum_{\lbrace K:x=d_K(y)\rbrace}\textbf{Pr}[\textbf{K}=K]$ be verified to hold?

How can the identity $\textbf{Pr}[\textbf{y}=y|\textbf{x}=x] = \sum_{\lbrace K:x=d_K(y)\rbrace}\textbf{Pr}[\textbf{K}=K]$ be verified to hold for any cryptosystem?

In his book Cryptography, Theory and Practice (3rd edition), Stinson states the equality for $\textbf{Pr}[\textbf{x}=x|\textbf{y}=y]$, which can be seen in the snippet below.

Intuitively, this seems just fine... But given that $\textbf{Pr}[\textbf{x}=x|\textbf{y}=y] = \textbf{Pr}[\textbf{x}=x,\textbf{y}=y] / \textbf{Pr}[\textbf{y}=y]$ by definition, how can I verify that the claim does indeed hold for any cryptosystem?

• At a glance, this does not seem correct, unless we're assuming the encryption to be deterministic (so that $x = d_K(y)$ implies that $y = e_K(x)$ with probability 1). – Ilmari Karonen Sep 22 '16 at 19:14
• It is deterministic - Can you prove it then? – Shuzheng Sep 22 '16 at 19:21
• I believe I can prove the claim stated in the book. But note that the claim you've written yourself is not the same as the one in the book: in general, $\textbf{Pr}[\textbf{x}=x|\textbf{y}=y] \ne \textbf{Pr}[\textbf{y}=y|\textbf{x}=x]$ (unless it just happens that $\textbf{Pr}[\textbf{x}=x] = \textbf{Pr}[\textbf{y}=y]$). – Ilmari Karonen Sep 22 '16 at 21:12
• Ok, I've edited the question to fix my typo. Please give it a try - I am curious! :) – Shuzheng Sep 23 '16 at 5:43

The operation of the function is completely described by $P(X,Y,K)$ which factorizes as $P(Y|X,K)P(X)P(K)$ under the assumption that $X$ and $K$ are independent and leads to

$$P(Y) = \sum_X\sum_K P(Y|X,K)P(X)P(K)$$

If you restrict $X$ to only the particular one that $K$ maps onto $Y$ (by writing $X = D_k(y)$) then $P(Y|X,K) = 1$ under the assumption that the function is a bijection, then you end up with

$$P(Y=y) = \sum_K P(K=k)P(X=D_k(y))$$

Using the same approach you can prove the conditional statement:

$$P(Y|X) = \sum_K P(Y|X,K)P(K) = \sum_K P(K)$$

• Thank you. But there is a typo in the last formula? – Shuzheng Sep 23 '16 at 14:40
• Would you also elaborate on last formula? Especially how you get first equality? – Shuzheng Sep 23 '16 at 14:42

$\require{begingroup} \begingroup \newcommand{\P}{\textbf{Pr}} \newcommand{\b}[1]{\textbf{#1}}$ The joint probability distribution of $\b x$, $\b y$ and $\b K$ is uniquely defined by: $$\P[\b x = x, \b y = y, \b K = k] = \P[\b y = y \mid \b x = x, \b K = K]\cdot \P[\b x = x, \b K = K],$$ where the conditional probability $\P[\b y = y \mid \b x = x, \b K = K] = \P[\b E_K(x) = y]$ gives the probability that the plaintext $x$ encrypts to the ciphertext $y$ under the key $k$.

(Here, I've denoted the encryption function with a bold $\b E$ to highlight that, in general, it could be stochastic, whereas the decryption function $D$ must surely be deterministic in any sensible cryptosystem.)

To calculate the conditional marginal probability $\P[\b y = y \mid \b x = x]$ of $y$ given $x$ (but not $K$), we can (by the definition of marginal probability) sum up the probabilities of $y$ and $K$ given $x$ over all possible keys $K$:

\begin{aligned} \P[\b y = y \mid \b x = x] &= \sum_K \P[\b y = y, \b K = K \mid \b x = x] \\ &= \sum_K \P[\b y = y \mid \b x = x, \b K = K] \cdot \P[\b K = K \mid \b x = x]. \end{aligned}

Now, since in your case encryption is deterministic, we have: $$\P[\b y = y \mid \b x = x, \b K = K] = \begin{cases} 1 & \text{if } D_K(y) = x, \text{ and} \\ 0 & \text{otherwise.} \end{cases}$$ Therefore we can simplify the formula by only summing over those keys $K$ that decrypt $y$ to $x$, for which $\P[\b y = y \mid \b x = x, \b K = K] = 1$, and thus we get: $$\P[\b y = y \mid \b x = x] = \sum_{K:\ D_K(y) = x} \P[\b K = K \mid \b x = x].$$

If we further assume that $\b K$ is independent of $\b x$, then $\P[\b K = K \mid \b x = x] = \P[\b K = K]$, and the conditional probability of $y$ given $x$ thus simplifies to just: $$\P[\b y = y \mid \b x = x] = \sum_{K:\ D_K(y) = x} \P[\b K = K].$$

Ps. Similarly, to calculate the unconditional marginal probability $\P[\b y = y]$, we can start by summing over all possible keys $K$ and plaintexts $x$: \begin{aligned} \P[\b y = y] &= \sum_{x,K} \P[\b x = x, \b y = y, \b K = K] \\ &= \sum_{x,K} \P[\b y = y \mid \b x = x, \b K = K] \cdot \P[\b x = x, \b K = K]. \end{aligned}

Again assuming that the keys and plaintexts are independent, this simplifies to: $$\P[\b y = y] = \sum_{x,K} \P[\b y = y \mid \b x = x, \b K = K] \cdot \P[\b x = x]\cdot \P[\b K = K],$$ and again assuming that encryption is deterministic, the first term is $1$ if and only if $x = D_K(y)$ and $0$ otherwise, so we can drop it by restricting the summation, and get:

\begin{aligned} \P[\b y = y] &= \sum_{x,K:\ x = D_K(y)} \P[\b x = x]\cdot \P[\b K = K] \\ &= \sum_{K} \P[\b x = D_K(y)]\cdot \P[\b K = K]. \end{aligned}

(This assumes that the decryption $D_K(y)$ is defined for all $K$ and $y$; if it's not, we'll need to additionally restrict the sum to only those keys for which it is defined, as the book does. Or we could simply define $D_K(y) = \bot$ whenever the ciphertext $y$ is not decryptable by the key $K$, where $\bot$ represents as arbitrary "error indicator" value such that $\P[\b x = \bot] = 0$.)

BTW, as a slight definitional digression, I'd like to note that defining conditional probability as $\P[A \mid B] = \P[A, B] / \P[B]$ is a bit problematic, because there are many natural situations where one would wish to condition on an event $B$ for which $\P[B] = 0$. (For example, consider the event $\b x = x$, where $\b x$ is a continuous random variable and $x$ is a constant.)

Rephrasing the definition as $\P[A, B] = \P[A \mid B]\cdot \P[B] = \P[B \mid A]\cdot \P[A]$ avoids some of the problems with division by zero, but still leaves us with the fundamental issue that there can be meaningful non-zero conditional and marginal probabilities that cannot be determined from the joint probability distribution of all the relevant variables. The standard mathematical solution to these issues is to instead formally define probabilities via a $\sigma$-algebra of events, but this formalism is rather abstract, not to mention notationally cumbersome.

Also, expressions like $\P[A,B]/\P[B]$ still appear naturally in many calculations involving conditional probabilities, e.g. in showing that $\P[A,B\mid C] = \P[A\mid B,C]\cdot\P[B\mid C]$, and avoiding them can get very awkward. Often, if one does not insist on absolute technical rigor, it's a lot more convenient to simply treat probability ratios like $\P[A,B]/\P[B]$ as formal expressions which, even though they may not always have a well defined numerical value, still satisfy algebraic rules like $\P[X]/\P[Y] \cdot \P[Y] = \P[X]$.

Of course, in crypto, we are rather fortunate in that usually our random variables range over finite (even if possibly very large) sets, and that events occurring with probability $0$ really can usually be considered impossible. But even here, zero-probability events can sometimes sneak in, e.g. when considering something like an infinite sequence of coin flips or, as here, a probability distribution over a set of messages of potentially unbounded length.

$\endgroup$