Modern cryptography: exercises chapter 2

These are some solved exercises of chapter 2 of the book “Introduction to modern cryptography” by Jonathan Katz and Yehuda Lindell.

I’m not sure are correct but if anyone find any error let me know. It’s a work in progress and more exercises will follow in future, when I finally find time to solve more. Also, enjoy my hand made diagrams :).

Definitions

An encryption scheme \((\hbox{Gen}, \hbox{Enc}, \hbox{Dec})\) with message space \(M\) is perfectly secret if for every probability distribution over \(M\), every message \(m\in M\), and every ciphertext \(c\in C\) for which \(\hbox{Pr}\left[C = c\right] > 0\):

This is equivalent to a prior indistinguishibility:

i.e. the ciphertext’s probability distribution is independent from the message’s probability distribution.

For notation purpose take in mind this way of writing:

Exercises

2.1: Prove that, by redefining the key space, we may assume that the key generation algorithm \(Gen\) choose a key uniformly at random from the key space, without changing \(\hbox{Pr}\left[C = c | M = m\right]\) for any \(m, c\).

solution

The encryption scheme can be described using the following diagram:

where the \(\hbox{Gen}\) algorithm creates a key using a random tape \(r\) from the space \(R\). Redefining \(\hbox{Enc}\) to include \(\hbox{Gen}\) and using \(r\) as new key we have that

This means that we simply shift the key to be the random tape that provides random values to the Turing machine implementing the probabilistic algorithm \(\hbox{Gen}\).

we can verify


2.2: Prove that, by redefining the key space, we may assume that \(Enc\) is deterministic without changing \(\hbox{Pr}\left[C = c \,|\, M = m\right]\) for any \(m, c\).

solution

\(\hbox{Enc}\) can become deterministic using the random tape as a component of the key;

Expanding the relation \(k^\prime=(k, r)\) we obtain


2.3: Prove or refute: an encryption scheme with message space \(M\) is perfectly secret if and only if (\(\iff\)) for every probability distribution over \(M\) and every \(c_0,\,c_1\in C\) we have \(\hbox{Pr}\left[C = c_0\right] = \hbox{Pr}\left[C = c_1\right]\).

solution

For this one I have not yet a solution but I think has to do with the dimension of the cipher and message space: the iff holds if we take the conditions from the Shannon’s theorem, i.e. if the all the spaces have the same dimensions.


2.4: Prove the second direction of Lemma 2.4

solution

We must proof that perfect secrecy implies perfect indistinguishibility; this can be done using the Bayes’ theorem

together with perfect secrecy

to obtain


2.5: Prove Lemma 2.6.

solution

We need to proof that

\(\Rightarrow\)) If we have one half as probability of success in the experiment, then this means that the ciphertext is indipendent from the message, stated with maths

\(\Leftarrow\))


2.6: For each of the following encryption schemes, state wheter the scheme is perfectly secret. Justify your answer in each case.

solution

For the (a) part I can start saying that because of the particular that the value \(0\) and \(5\) under the module operation give the same result, when we use these keys the ciphertext is equal to the original message we can have perfect secrecy