3 ms·

I think I'm understanding your argument, but I don't think it's correct. A well-encrypted message -- whether pre-compressed or not -- is indistinguishable from

I think I'm understanding your argument, but I don't think it's correct. A well-encrypted message -- whether pre-compressed or not -- is indistinguishable from noise. If it was not pre-compressed, then its information density is lower, which means the S/N is lower. Information theory tells us that the worse the S/N, the harder it is to extract the information.

btilly 16y ago
Whether or not you agree with it, the argument is believable enough to have been presented in a graduate level course that I was in a number of years ago. (The course was on wavelets, but background review on information theory was presented at the beginning.) You are correct that a perfectly encrypted message is indistinguishable from noise. Decryption is the art of distinguishing imperfectly encrypted messages from noise. Anything that makes the message harder to distinguish, makes decryption harder. Which means that the more the message looks like noise, the harder it is to decrypt. Your attempted counter argument fails on the fact that a redundant message has very little noise, and therefore has a high S/N despite having not that much signal per bit. However that said, it is true that if you take a redundant message, remove some redundancy by adding some random noise to it, then encrypt it, the result will be harder to decrypt than if you just encrypted the original redundant message. Of course the fundamental reason behind that is that detecting redundant information is at the heart of decryption. In that light it is interesting to compare the two known perfect encryption mechanisms. The first is the one-time pad. In that case the transmitted message has absolutely no redundancy because the definition of the encryption method contains as much information as the transmitted message. The second is for the two end points to have a list of pre-agreed messages of equal likelyhood, which they will refer to in binary code. This offers perfect compression with absolutely no redundancy, and therefore the attacker again has absolutely no way to guess what the pre-encoded messages are. (This is much harder to do properly in practice than one time pads, which themselves are pretty tricky.)

btilly 16y ago

Whether or not you agree with it, the argument is believable enough to have been presented in a graduate level course that I was in a number of years ago. (The course was on wavelets, but background review on information theory was presented at the beginning.) You are correct that a perfectly encrypted message is indistinguishable from noise. Decryption is the art of distinguishing imperfectly encrypted messages from noise. Anything that makes the message harder to distinguish, makes decryption harder. Which means that the more the message looks like noise, the harder it is to decrypt. Your attempted counter argument fails on the fact that a redundant message has very little noise, and therefore has a high S/N despite having not that much signal per bit. However that said, it is true that if you take a redundant message, remove some redundancy by adding some random noise to it, then encrypt it, the result will be harder to decrypt than if you just encrypted the original redundant message. Of course the fundamental reason behind that is that detecting redundant information is at the heart of decryption. In that light it is interesting to compare the two known perfect encryption mechanisms. The first is the one-time pad. In that case the transmitted message has absolutely no redundancy because the definition of the encryption method contains as much information as the transmitted message. The second is for the two end points to have a list of pre-agreed messages of equal likelyhood, which they will refer to in binary code. This offers perfect compression with absolutely no redundancy, and therefore the attacker again has absolutely no way to guess what the pre-encoded messages are. (This is much harder to do properly in practice than one time pads, which themselves are pretty tricky.)