Paul Crowley wrote:
>This supports your main point: perfect compression is a *much* less
>realistic idea than true randomness!
Yeah.
Now that you mention it, it's not entirely clear what perfect compression
means, but it seems that it would at a minimum require ability to break
every cryptosystem in existence. In other words, perfect compression is
apparently utterly unrealistic, unless cryptography is impossible.
Consider a very long file which contains
AES_k(0), AES_k(1), AES_k(2), AES_k(3), ...
for some random key k that is not mentioned in the file. Of course, the
optimal compression of this file is just 128 bits for the key k, plus a
brief description of the algorithm (AES in counter mode). However, finding
k is infeasible unless AES is insecure.
In other words, perfect compression of this file requires breaking the AES!
A similar example shows that if there is any secure cryptosystem at all,
then perfect compression is infeasible.
Hence, perfect compression seems to be entirely unrealistic, unless
cryptography is impossible.
