# 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
Commented Nov 18, 2013 at 6:45
• This is exercise 2.1 in Katz-Lindell book Commented Nov 12, 2018 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
Commented Nov 20, 2013 at 0:41
• Why it will terminate after SUMk(pmin)? And why is it equal to (2^n)*pmin?
– Bush
Commented Nov 20, 2013 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. Commented Nov 27, 2013 at 22:11
• What is p_min in this example? (I don't know how to use subscripts in comments...)
– Bubo
Commented Mar 29, 2015 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
Commented Nov 16, 2013 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. Commented Nov 16, 2013 at 19:02
• Another edit: talking about computationally secured scheme - so extensive search is not a feasible attack..
– Bush
Commented Nov 16, 2013 at 20:16