Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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 :


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.

share|improve this answer
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. – ThomasP 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.

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.