# Understanding how to proof an encryption scheme is perfectly secret

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?