Prove that a given encryption scheme is perfectly secret

Question

I'm studying for an upcoming test and I can't figure out the following sample question:

Let $\Pi = (\operatorname{Gen}, \operatorname{Enc}, \operatorname{Dec})$ be an encryption scheme with key space $\mathcal K$, message space $\mathcal M$, and ciphertext space $\mathcal C$ where $\mathcal K =\mathcal M =\mathcal C = \{0, 1, 2, 3\}$. Algorithm $\operatorname{Gen}$ returns a uniformly random key $k$ in $\mathcal K$. For any key $k$ in $\mathcal K$ and any message $m$ in $\mathcal M$, $\operatorname{Enc}(m)$ using key $k$ is defined as $(m + k) \bmod 4$. For any key $k$ in $\mathcal K$ and ciphertext $c$, $\operatorname{Dec}(c)$ using key $k$ is defined as $(c - k) \bmod 4$.

a) Prove that $\operatorname{Dec}(\operatorname{Enc}(m)) = m$ using key $k$ holds for any key $k$ in $\mathcal K$ and any message $m$ in $\mathcal M$.

b) Prove or disprove: $\Pi$ is perfectly secret.

The formal definition of "perfectly secret" used is:

An encryption scheme (Gen, Enc, Dec) over a 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[\mathcal{C} =c] > 0: Pr[\mathcal{M}=m | \mathcal{C}=c] = Pr[\mathcal{M}=m]$.

In this scheme, keys can be reused.

Answer 1

1. For every key $k \in \mathcal K$ $$Dec(Enc(m)) \overset{\underset{\mathrm{def}}{}}{=} (Enc(m) - k) \bmod 4,$$ where $$Enc(m) \overset{\underset{\mathrm{def}}{}}{=} (m + k) \bmod 4,$$ so, combining it, we have $$Dec(Enc(m)) = (((m + k) \bmod 4) - k) \bmod 4,$$ which, by properties of modular arithmetic (or, more precisely, congruences), is equivalent to $$(m \bmod 4) + (k \bmod 4) - (k \bmod 4) = m + k - k = m$$

2. This is actually a great example, as it demonstrates the ultimate elegance of the mathematical definition of security. Encryption scheme $(E, D)$ over $(\mathcal K, \mathcal M, \mathcal C)$ is perfectly secret, if for all $m_i, m_j \in \mathcal M, c \in \mathcal C$ $$Pr[E(k, m_i) = c] = Pr[E(k, m_j) = c],$$ where $k$ is uniform in $\mathcal K$. Here is a table of encryptions of $m$ with key $k$ for all $m \in \{0, 1, 2, 3\}$ and $k \in \{0, 1, 2, 3\}$: $$ \begin{array}{c|lc} m/k & 0 & 1 & 2 & 3 \\ \hline 0 & 0 & 1 & 2 & 3 \\ 1 & 1 & 2 & 3 & 0 \\ 2 & 2 & 3 & 0 & 1 \\ 3 & 3 & 0 & 1 & 2 \end{array}$$ As you can see, for every $m$, $Pr[Enc(m) = c] = 1/4$, thus given encryption scheme is perfectly secure.