Prove that a given encryption scheme is perfectly secret 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] &gt; 0: Pr[\mathcal{M}=m | \mathcal{C}=c] = Pr[\mathcal{M}=m]$.


In this scheme, keys can be reused.
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$$
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 &amp; 0 &amp; 1 &amp; 2 &amp; 3 \\
\hline
0 &amp; 0 &amp; 1 &amp; 2 &amp; 3 \\
1 &amp; 1 &amp; 2 &amp; 3 &amp; 0 \\
2 &amp; 2 &amp; 3 &amp; 0 &amp; 1 \\
3 &amp; 3 &amp; 0 &amp; 1 &amp; 2
\end{array}$$
As you can see, for every $m$, $Pr[Enc(m) = c] = 1/4$, thus given encryption scheme is perfectly secure.