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.

  • 4
    $\begingroup$ 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! :) $\endgroup$
    – SEJPM
    Mar 6, 2017 at 16:51
  • $\begingroup$ 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. $\endgroup$
    – Matthew
    Mar 6, 2017 at 19:33
  • $\begingroup$ 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? $\endgroup$
    – Maarten Bodewes
    Mar 6, 2017 at 23:12

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.