# Katz/Lindell Problem 2.2

2.2 Prove that, by redefining the key space, we may assume that $\text{Enc}$ is deterministic without changing $\text{Pr}[\text{Enc}_k(m)=c]$ for any $m, c$.

After banging my head against this problem for a few hours, I honestly don't see a modification of the key space that gives the desired result. For all $k,m,$ and $c$ we have $\text{Enc}_k(m)=c$ with a certain probability $p(k,m,c)\geq 0$. What can we do with that?

Note: Katz/Lindell assume that $|\mathcal M|<\infty$, and $\mathcal C$ is defined as the set of as possible outputs of $\text{Enc}$.

• Do not assume that everybody has access to the book. Add the relevant definitions to your question in order to make it self-contained. – fkraiem Sep 12 '17 at 0:58
• I edited the question. Is anything unclear now? @fkraiem – CRYPTONEWBIE Sep 12 '17 at 15:59

You neglected the most important part, I believe; the encryption map itself may be probabilistic which means we might have $$c \leftarrow \mathrm{Enc}_k(m),$$ instead of $$c =\mathrm{Enc}_k(m),$$ which is deterministic. In the first case a second encryption with the same key and message might result in a different ciphertext. Once you realise this and given that the key space is finite consider for each fixed key message pair $(k,m)$ the distribution of the random variable $$\mathrm{Enc}_k(m)$$ over $\mathcal{C}$ and note that this distribution where each probability is a real number can be approximated arbitrarily closely by a rational distribution with rational probabilities.
Let us say $p_i=a_i/b_i,$ is the rational arbitrarily accurate approximate probability for the ciphertext $c_i$ belonging to the set of texts that appear with nonzero probability for the given $(k,m).$ Rewriting the probabilities as fractions with denominator $\mathrm{LCM}(b_i)$ we can now replace the key $k$ with $$\mathrm{LCM}(b_i) a_i/b_i$$ keys all of which will now map deterministically to the single ciphertext $c_i.$
Proceeding this way for each $(k,m)$ pair we obtain a deterministic scheme.
• I don't have Katz & Lindell's book at hand right now, but does their definition of an encryption scheme stipulate that such a scheme must be PPT-computable algorithms? And if so, shouldn't there be some concern whether the construction you offer runs afoul of that? If I'm reading your answer right, actually computing the encryptions for your constructed scheme would require memory proportional to $|\mathcal{K}| \times |\mathcal{M}|$. – Luis Casillas Sep 13 '17 at 0:04