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

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

Generally speaking we say that $Gen$ choose key uniformly from $\{0,1\}^n$ but this is not always the case.

How can I prove that if there exist a (computationally) secure encryption scheme in which $Gen$ choose $k$ non-uniformly then there exist another (equal or more computationally) secure encryption scheme stems from it in which the keys space does uniformly distributed?

-
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}$ –  Ricky Demer Nov 18 '13 at 6:45

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 $\;\;$ –  Ricky Demer 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

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