# 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

## 1 Answer

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
• Point taken. I have the first edition. The chapter on perfect secrecy (Ch 2) doesn't concern itself with complexity. – kodlu Sep 13 '17 at 1:54
• Ah, it's the perfect secrecy chapter, that makes sense. I just checked the 2nd edition and it's the same. The restriction of the honest parties to PPT algorithms appears in chapter 3. – Luis Casillas Sep 13 '17 at 6:23
• I don't see what's wrong with the asker's use of "=" to denote "the event that a random variable takes a certain value". This notation appears to be more common in probability theory than the arrow notation in Katz/Lindell (which isn't even properly defined in the book). – Aleph Sep 13 '17 at 16:18
• I didn't say it was wrong, I used it to distinguish the two cases as in the book, and he may have missed it relax. – kodlu Sep 13 '17 at 19:09