# Why can we always assume that $Gen$ algorithm choose key uniformly?

Disclaimer: This is exercise 2.1 in Katz-Lindell book.

Given a (symmetric) encryption scheme $$\Pi=(Gen,Enc,Dec)$$ where $$Gen$$ takes the security parameter $$1^n$$ as input and generates a key $$k$$ of length $$n$$.

Usually we simply assume that $$Gen$$ chooses key uniformly from $$\{0,1\}^n$$ but this is not always the case.

Given $$Gen$$, how would you construct a new generation algorithm $$Gen'$$ that indeed outputs $$k$$ uniformly at random?

• I'm pretty sure you can't prove that, since I've convinced myself that no such proof can relativize. $\hspace{.44 in}$ However, one could easily make it so that the only security loss is due to $Enc$ and $Dec$ taking longer. $\hspace{.54 in}$ – user991 Nov 18 '13 at 6:45
• This is exercise 2.1 in Katz-Lindell book – Javier Nov 12 '18 at 21:01

Are you trying to prove this for a specific encryption scheme or for any scheme?

If you have a specific scheme in mind, you can consider using rejection sampling. In your case, it would be quite straightforward to use :

Let's say each key $k\in \{0,1\}^n$ is output by $Gen$ with a probability $p(k)$, and $p_{min} \overset{def}{=} \min\limits_{k} p(k)$. You can then define $GenU(1^n)$ per example like this :

$GenU(1^n):$

1) $k \leftarrow Gen(1^n)$

2) With probability $p_{min}/p(k)$, output $k$, otherwise restart

You can see that an iteration of $GenU$ outputs each $k$ with probability $p_{min}$, and terminates ($ie$ does not restart) with probability $\sum_{k} p_{min} = 2^n\cdot p_{min}$.

Now, this algorithm assumes that you can efficiently compute each $p(k)$. Moreover, if $p_{min}$ is much smaller than the other values of $p(k)$, then $GenU$ may take an impractical amount of time to terminate ($eg$ if $p_{min} = 2^{-2n}$, then an iteration $GenU$ will terminate with probability $2^{-n}$).

For these reasons, if you want to prove your proposition in the general case, you cannot apply this algorithm as it is. Hope it helps though.

• ff $\mapsto$ if $\;\;$ – user991 Nov 20 '13 at 0:41
• Why it will terminate after SUMk(pmin)? And why is it equal to (2^n)*pmin? – Bush Nov 20 '13 at 20:00
• Because each $k$ has a probability $p(k)$ of being output at the first step, and probability $p_{min}/p(k)$ of passing the second step, giving it a probability $p_{min}$ of being output by GenU. Since there are $2^n$ of them, here is your result. – Thomas Prest Nov 27 '13 at 22:11
• What is p_min in this example? (I don't know how to use subscripts in comments...) – Bubo Mar 29 '15 at 1:10

This depends on the degree of non-uniformity and the ability of $\Pi$ to produce uniform key-independent outputs. For instance, a deterministic encryption scheme that always selects $k=k_0$ is just a fixed permutation and can not be used to build a secure scheme without additional tools. However, if $\Pi$ produces a uniform $IV$, simply take it as a key and do not publish.

• Sorry, I'm talking about a secure encryption scheme. Will edit the question. – Bush Nov 16 '13 at 17:31
• Well, the new scheme can not be more secure, because you can always find the key of the old scheme by exhaustive search. Then the new scheme is no longer secure if I understand your reduction correctly. – Dmitry Khovratovich Nov 16 '13 at 19:02
• Another edit: talking about computationally secured scheme - so extensive search is not a feasible attack.. – Bush Nov 16 '13 at 20:16