Does perfect secrecy imply uniform ciphertext distribution?

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?)

Answer 1

For a nonuniform construction with perfect secrecy, consider this scheme, with 2 bits of plaintext $(b_1, b_0)$, and four bits of key $(k_3, k_2, k_1, k_0)$.

The ciphertext consists of the three bits: $$(k_3 \land k_2) \oplus b_0 \oplus k_0$$ $$b_1 \oplus k_1$$ $$b_0 \oplus k_0$$

This has perfect secrecy, in that for each ciphertexts, there is the same number of keys that map to any particular plaintext. For example, for the ciphertext $(0,0,0)$, there are three keys that it to any plaintext, say, the plaintext $(1,0)$

This is nonuniform; as for random keys, the ciphertext $(0,0,0)$ will occur with probability three times that the ciphertext $(0,0,1)$ occurs at.

Answer 2

You might be trying to keep the ciphertext length equal to the plaintext length.

This is a "Just Do It" construction:
Choose [0 or 1] and [[bit then original output] or [original output then bit]],
modify the encryption algorithm to have it concatenate the chosen bit with the
original encryption algorithm's output in the chosen order, and modify the decryption algorithm
to have it remove the extra bit before applying the original decryption algorithm.

The ciphertexts produced by the modified encryption algorithm will never be
the empty string, and their [[leftmost bit] or [rightmost bit]] will always be [0 or 1].

Answer 3

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.