1
$\begingroup$

Following up on a similar question, Does perfect secrecy imply uniform ciphertext distribution?, the answer seems to be that in a perfectly secret encryption scheme, the distribution of the ciphertext space is not necessarily uniform because the message space is not always uniformly distributed (although the key space is assumed to be uniform).

Question: If we say that the message space and key space are uniformly distributed, this seems to me to imply that the ciphertext space must also be uniform. How would one go about proving this fact?

Improve this question
$\endgroup$
3
  • $\begingroup$ No. In the top answer to your citing question, the message space is uniformly distributed. It's just that some keys can never generate particular ciphertexts. $\endgroup$
    – Shan Chen
    Commented Oct 15, 2018 at 2:03
  • $\begingroup$ @ShanChen then in that example the key space is not uniformly distributed? $\endgroup$
    – jessli
    Commented Oct 15, 2018 at 2:33
  • $\begingroup$ Both the message and key spaces are uniformly distributed. Since each ciphertext's first and last bit determine the number of potential values for k3 and k4, some ciphertexts (more precisely, those with the same first and last bits) are three-time more likely to be generated that others. $\endgroup$
    – Shan Chen
    Commented Oct 15, 2018 at 2:42

1 Answer 1

Reset to default
2
$\begingroup$

Question: If we say that the message space and key space are uniformly distributed, this seems to me to imply that the ciphertext space must also be uniform. How would one go about proving this fact?

You don't because this statement is false.
Here's a simple counter-example:

Let $k,m\in\{0,1\}$ be a key and a message bit, both chosen uniformly at random. Then let the ciphertext $c=m\oplus k\parallel 0$, that is you do the standard OTP encryption and append a zero bit. Obviously this scheme is perfectly secret because the OTP is and the zero bit is completely independent of the key and the message. Also obviously the ciphertext doesn't have a uniform distribution from the set $\{00,01,10,11\}$ because $11$ cannot occur.

A more interesting (new!) question though would be though whether for each length-preserving perfectly-secret encryption scheme the ciphertext follows a uniform distribution.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is not a valid counter example. You cannot assume the ciphertext space consists of all 2-bit strings. Those ciphertexts that never happen should not be counted. $\endgroup$
    – Shan Chen
    Commented Oct 15, 2018 at 17:17
  • 1
    $\begingroup$ @ShanChen In general it is not required for encryption schemes to be surjective. Also if you feel better then, you can imagine my counter-example with a random 1% chance of appending a 1 bit instead of a 0 bit. $\endgroup$
    – SEJPM
    Commented Oct 15, 2018 at 17:23
  • $\begingroup$ The answer is correct as the question stands. The question asked if any encryption scheme with certain properties on key and message distribution yielded uniform ciphertexts and the answer demontrated a counterexample. $\endgroup$
    – kodlu
    Commented Oct 16, 2018 at 4:31
  • $\begingroup$ @kodlu Well, I don't want to be very insistent on this. But if the ciphertext space can be anything, then you can get a very trivial counterexample by adding a weird string to the ciphertext space as long as that string (or whatever) can never be generated by a perfect secret encryption scheme. $\endgroup$
    – Shan Chen
    Commented Oct 16, 2018 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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