Timeline for Can a perfectly secret scheme have non-uniform ciphertext distribution if the plaintext and ciphertext length is equal?
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 20 at 13:46 | comment | added | Zabbulator | 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$ ? | |
| Apr 18 at 17:13 | comment | added | poncho | @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. | |
| Apr 18 at 15:47 | comment | added | Zabbulator | 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? | |
| Apr 18 at 14:17 | history | answered | poncho | CC BY-SA 4.0 |