Understanding how to proof an encryption scheme is perfectly secret

Question

Consider each of the following encryption schemes and state whether the scheme is perfectly secret or not. Justify your answer by giving a detailed proof if your answer is Yes, and a counterexample if your answer is No.

Consider an encryption scheme whose plaintext space is $\mathcal{M}=\{m\in\{0,1\}^\ell \mathrel{|} \text{the last bit of $m$ is $0$}\}$ and key generation algorithm chooses a uniform key from the key space $\mathcal{K}=\{0,1\}^{\ell-1}$. Suppose $\mathit{Enc}_k(m)=m \oplus (k\parallel 0)$ and $\mathit{Dec}_k(c)=c\oplus (k\parallel 0)$.

$\newcommand{\given}{\mathrel{|}}$The definition of perfectly secret which states: An encryption scheme $(\mathit{Gen}, \mathit{Enc}, \mathit{Dec})$ with message space $\mathcal{M}$ is perfectly secret if for every probability distribution over $\mathcal{M}$, every message $m\in \mathcal{M}$, and every ciphertext $c\in \mathcal{C}$ for which $\Pr[C=c]>0$: $$\Pr[M=m\given C=c]=\Pr[M=m].$$

We first compute $\Pr[C=c\given M=m']$ for arbitrary $c\in \mathcal{C}$ and $m'\in \mathcal{M}$. \begin{equation*} \begin{aligned} \Pr[C=c\given M=m'] & =\Pr[\mathit{Enc}_K(m')=c]=\Pr[m' \oplus (K\parallel 0)=c] \\ & =\Pr[(K\parallel 0) = c\oplus m']=2^{1-\ell}\quad (1) \end{aligned} \end{equation*} where the final equality holds because the key $K$ is a uniform $\ell-1$-bit string. Fix any distribution over $\mathcal{M}$. For any $c\in \mathcal{C}$, we have \begin{equation*} \begin{aligned} \Pr[C=c] & = \sum_{m'\in\mathcal{M}} \Pr[C=c\given M=m'] \cdot \Pr[M=m'] \\ & = 2^{1-\ell} \cdot \sum_{m'\in \mathcal{M}} \Pr[M=m']=2^{1-\ell}\cdot 1=2^{1-\ell}\quad (2) \end{aligned} \end{equation*} where the sum is over $m'\in \mathcal{M}$ with $\Pr[M=m']\neq 0$. Bayes' Theorem gives: \begin{equation*} \begin{aligned} \Pr[M=m\given C=c] & = \dfrac{\Pr[C=c\given M=m]\cdot \Pr[M=m]}{\Pr[C=c]} \\ & = \dfrac{2^{1-\ell} \cdot \Pr[M=m]}{2^{1-\ell}} = \Pr[M=m] \end{aligned} \end{equation*} Hence we conclude that this encryption scheme is perfectly secret.

MY QUESTION: I tried to follow the set up for the proof of the One-Time Pad being perfectly secure. However, I don't really understand the logic behind the proof (assuming what I did was correct). Can someone clear up why this technique is correct?

Answer 1

Where is the problem? Your reasoning seems correct, but you obviously are uncomfortable with probability (at least).

You used the definition of the encryption scheme in (1) and then the standard expression of a probability with respect to the set of messages forming a partition in (2), which is valid since it includes all the messages with nonzero probability and their probabilities must sum to 1.

You then applied Bayes theorem. Standard stuff, really. Maybe you need a refresher in probability.