# 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] > 0: Pr[\mathcal{M}=m | \mathcal{C}=c] = Pr[\mathcal{M}=m]$.

In this scheme, keys can be reused.

• Can you please tell us what you have tried and where exactly you got stuck in solving this problem? This will greatly help us to better help you. And welcome to Crypto.SE! :) – SEJPM Mar 6 '17 at 16:51
• To be honest, I just don't know how to approach this problem. I understand what it means to be perfectly secret, but I don't know how to go about applying that to this question. – Matthew Mar 6 '17 at 19:33
• So? If you encrypt a message m=0 and you get ciphertext c=2 then what will you get if you encrypt m=1? What, for that matter, will happen if you encrypt a message valued 0 twice? – Maarten Bodewes Mar 6 '17 at 23:12

## 1 Answer

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.