[8409] in cryptography@c2.net mail archive
Re: Perfect compression and true randomness
daemon@ATHENA.MIT.EDU (David Wagner)
Tue Jan 9 17:45:10 2001
To: cryptography@c2.net
From: daw@mozart.cs.berkeley.edu (David Wagner)
Date: 9 Jan 2001 01:06:41 GMT
Message-ID: <93do71$521$1@abraham.cs.berkeley.edu>
Reply-To: daw@cs.berkeley.edu (David Wagner)
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.
