1
$\begingroup$

I've seen this question asking if perfect secrecy implies uniform ciphertext distribution, and I understand that this is not the case. However, all given counterexamples seem to require a construction where the ciphertext length is larger than the plaintext length.

So I'm wondering if perfect secrecy, of a scheme with the additional requirement that the ciphertext must have the same length as the plaintext, would then imply a uniform ciphertext distribution.

Edit: Please add a proof or counterexample!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Would perfect secrecy, of a scheme with the additional requirement that the ciphertext must have the same length as the plaintext, imply a uniform ciphertext distribution.

No; however for the ciphertext to be nonuniform, then the plaintext must have 'illegal values' that it can never take on.

For example, suppose we restrict the plaintext to consist only of the letters 'A' through 'Z'. Then, if we consider a OTP-style encryption method, where the key stream consists of values between 0 and 25, and the combination method is modular addition (mod 26), then the ciphertext (which consists of letters between 'A' and 'Z') is obviously nonuniform (when considered as a binary sequence), but perfect secrecy still holds (the attacker knows that the plaintext consists of the letters 'A' through 'Z', but he already knew that before he saw the ciphertext, so the ciphertext didn't leak anything).

However, if we disallow that sort of thing (which might be considered a bit of a cheat by playing around with the definition of 'uniform'), then it is impossible; if all binary patterns of plaintext are possible, then the ciphertext must be uniformly distributed.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Well, you of course have to properly define your key, plaintext, and ciphertext space prior to any statements about perfect secrecy and uniformity. So I indeed don't think it's valid to define the ciphertext space in one way to argue it's non-uniform, and then in another way to say it is perfectly secret. You say at the end that perfect secrecy does imply a uniform ciphertext distribution in the scenario of my question (if we don't re-define the ciphertext space halfway through); can you prove this? $\endgroup$
    – Zabbulator
    Commented Apr 18 at 15:47
  • $\begingroup$ @Zabbulator: "can you prove this?"; yes (if we also assume the encryption is invertible; we can decrypt). If we denote the set of possible plaintexts as $P$ (where every plaintext has nonzero probability of occurring), the number of ciphertexts as $C$, and $|P| = |C|$. Then, for perfect secrecy to hold, the conditional probability of any output has to be independent of the plaintext (that is, $\forall c \in C, p_1, p_2 \in P: P(c | p_1) = P(c | p_2)$ and because for any key, any ciphertext output would correspond to a possible plaintext input, the ciphertext probabilities must be equal. $\endgroup$
    – poncho
    Commented Apr 18 at 17:13
  • $\begingroup$ Thanks for the proof. I do however not quite understand the last step ("because for any key, any ciphertext would correspond to a plaintext, the ciphertext probabilities must be equal."). I understand that fixing a key and a ciphertext will yield a uniquely determined corresponding plaintext, but not how this would affect any probabilities. What exactly contradicts $P(c_1|p) \neq P(c_2|p)$ for $p\in P, c_1,c_2\in C$ ? $\endgroup$
    – Zabbulator
    Commented Apr 20 at 13:46

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.