I suspect the answer is no, but I am not able to either prove it, or provide an
ID: 647484 • Letter: I
Question
I suspect the answer is no, but I am not able to either prove it, or provide an example. In Katz and Lindell's book, it is only said that with a perfectly secret encryption scheme, the plain and ciphertext distributions are independent. But when I try to construct an example with a non-uniform ciphertext distribution, (using say, 4 plaintexts as a message space), I cannot devise a plaintext and key distribution such that the resulting ciphertext distribution is not uniform.
What I am getting wrong? (or can anyone provide such an example?)
Explanation / Answer
A distribution of the ciphertext depends on the distribution of the plaintexts. If you assume implicitly a uniform distribution on the plaintext, you automatically should get a uniform distribution on the image of the encryption function (which can be less than the ciphertext space, if you actually have an expanding ciphertext).
Let's assume OTP on a 1 bit message, where the message and key are from {0,1}. The ciphertext will then also be from {0,1}. Now, if you have a non-uniform distribution on the plaintexts, e.g. p(0)=0.8,p(1)=0.2, then you also get a non-uniform distribution of the ciphertexts. And depending on the key, you get either the 0.8 probability either on the ciphertext 0 or 1.
'Independent' might be the wrong choice of term there, because based on the plaintext distribution, the key distribution and some potential random coins (e.g. if you pad the ciphertext with randomness, and just ignore that part at decryption) and the scheme you will get a specific distribution.