A supposedly easy problem in information theory. .

[Chu]

Here is the problem I am having trouble with:

Prove that for any cipher that has perfect secrecy, the size of the key space is at least as large as the size of the cyphertext space.

For those rusy with information security, this essentially means proving that for each message p in Plaintext space P, and each encrypted message c in Cyphertext space C :

P[p|c] = P[p]
----------------

For some reason I am pretty much completely stuck. From the birthday problem it is trivial to show that more then one mapping from p->c uses the same key, and if the probabilities of choosing a specific key is different then choosing any other key, the problem is pretty trivial.

The case where all the keys can be chosen with the same probability (for example |K| = 1/2 |C| = 1/2 |P| ) is driving me nuts. Can someone give me some nudge in the right direction on solving this problem?

 

[Jhero]

The proof of this statement revolves around the concept of perfect secrecy. Perfect secrecy means that for any message p in the plaintext space, P, and any encrypted message c in the ciphertext space, C, the probability of a specific plaintext message, p, being encrypted into a specific ciphertext message, c, is equal to the probability of any other plaintext message, p', being encrypted into c, regardless of the key used. Mathematically, this is expressed as: P[p|c] = P[p'] From this, it follows that the size of the key space must be at least as large as the size of the ciphertext space, since each plaintext message can be encrypted into each ciphertext message with the same probability regardless of the key used. Thus, for any given ciphertext message, c, there must be at least one key, k, such that P[p|c] = P[p|ck]. Since the size of the key space must be at least as large as the size of the ciphertext space, it follows that the size of the key space is at least as large as the size of the ciphertext space.

 

[tacman]

It seems like you are on the right track with considering the probability of choosing a specific key. One way to approach this problem is to think about what perfect secrecy means in terms of the key space and the cyphertext space.

In a cipher with perfect secrecy, the probability of obtaining a specific plaintext message p is the same whether you know the corresponding ciphertext c or not. This means that the probability distribution of the plaintext space P is preserved when encrypted with any key. In other words, for any given p in P, the probability of obtaining c in C is the same for all keys.

Now, let's consider the size of the key space. If the key space is smaller than the cyphertext space, then there must be some c in C that has multiple corresponding keys. However, since the probability distribution of P is preserved for all keys, this would mean that there are multiple ways to encrypt p, which contradicts the assumption of perfect secrecy. Therefore, the key space must be at least as large as the cyphertext space in order for perfect secrecy to hold.

To prove this, you can use a proof by contradiction. Assume that the key space is smaller than the cyphertext space, and then show that this leads to a contradiction. This would prove that the key space must be at least as large as the cyphertext space in order for perfect secrecy to hold.

I hope this helps nudge you in the right direction. Good luck with your problem!