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|&lt;\infty$, and $\mathcal C$ is defined as the set of as possible outputs of $\text{Enc}$.
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.