I'm trying to solve problem 2.4 in "Introduction to Modern Cryptography" (2nd edition) for self-study.
The problem asks to prove that perfect secrecy $$ Pr[M = m | C = c] = Pr[M = m] $$
implies
$$ Pr[Enc_k(m) = c] = Pr[Enc_k(m') = c] $$
The solution goes as follows:
Fix two messages $m, m'$ and a ciphertext $c$ that occurs with nonzero probability, and consider the uniform distribution over $\{m, m'\}$. Perfect secrecy implies that $Pr[M = m | C = c] = \frac{1}{2} = Pr[M = m' | C = c]$ So
$$ \frac{1}{2} = Pr[M = m| C = c] = \frac{Pr[C = c| M = m] * Pr[M = m]}{Pr[C = c]} $$
simplifies to
$$ \frac{\frac{1}{2}Pr[C = c | M = m]}{Pr[C = c]} $$
and so $Pr[C = c | M = m]$ = $Pr[Enc_k(m) = c]$ = $Pr[C = c]$. Since an analogous calculations holds for $m'$ as well, we conclude that $Pr[Enc_k(m) = c]$ = $Pr[Enc_k(m') = c]$
My issue is that this solution assumes a message space of 2, which is not generalizable.
Is there something I'm missing that makes this solution generalizable?
Edit: To be clear, here is the full problem text.
Lemma 2.4: An encryption scheme (Gen, Enc, Dec) with message space $M$ is perfectly secret if and only if Equation (2.1) holds for every $m,m' \in M$ and every $c \in C$. Where equation 2.1 is the 2nd equality in this post.
The problem asks to prove "other direction", which in this case means proving perfect secrecy => equation 2.1. (In the textbook, the reverse direction is already proved).