Consider a block cipher $E_k$ where $k$ is an arbitrary key. $E_k$ takes input messages from $\{0,1\}^n$ and outputs a ciphertext $c\in\{0,1\}^n$. Let $m$ be an input message which is uniformly drawn from $\{0,1\}^n$ and let $c = E_k(m)$.

My question is simple - is $c$ also uniformly distributed in $\{0,1\}^n$?

Note: I know that $c$ has to be indistinguishable from a uniform distribution, but I ask if it is actually uniformly distributed. I'd appreciate a proof (or proof sketch) in case it is.



The answer is yes.
While I can't provide a rigorous proof (because I don't know for now how to make one for such distributions), I can give an intuitive argument, which you can formalize I hope.

The main reason is simple: $E_k$ is a permutation for all choices of $k$.
This means that essentially all the encryption function does is "re-label" the given input message, there are no collisions (which would change the distribution) and input- and output space are equal in size so, every value in the input space is mapped to precisely one value in the output space and vice-versa.

So if you have probability $1/2^n$ of drawing $m$ you have probability of $1/2^n$ of ending up with $E_k(m)=c$ and so $c$ is distributed uniformly at random.

| improve this answer | |
  • 1
    $\begingroup$ I guess formally one could argue using a contrapositive and show that a non-uniform distribution would follow from a non-uniform distribution among the ciphertexts. $\endgroup$ – SEJPM Nov 29 '17 at 23:49
  • $\begingroup$ Thanks! I'm quite new to the terminology too, but is cipher block always a PRP (pseudo-random permutation)? $\endgroup$ – noamgot Nov 30 '17 at 10:10
  • $\begingroup$ @noamgot actually you don't need to assume that you have pseudorandom permutation because you don't need this property anywhere in the proof. You just need that it's a permutation and that follows from the functional correctness and from the equal, finite size of message and ciphertext space. $\endgroup$ – SEJPM Nov 30 '17 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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