Paul Crowley <[EMAIL PROTECTED]> writes:
> Peter Fairbrother <[EMAIL PROTECTED]> writes:
> > Not so. Perfect compression with encryption works too.
>
> Er, does it? I get a 1k message from you, perfectly compressed and
> then encrypted with some strong algorithm and a 128-bit key. As a
> godlike being unhindered by constraints of computational power, I try
> all 2^128 possible keys, and find due to the perfect compression that
> each of the 2^128 plaintexts is equally likely. From an information
> theoretic point of view, I'm much better off than I was before: I used
> to be missing 8192 bits of entropy, but now I'm only missing 128 - the
> space of possible messages has been vastly reduced. Put it this way,
> if all I want to know is whether you're asking for a ticket to the
> dance, I might well learn the answer since I might find that none of
> the candidate messages include that request.
There's a much easier way to make the point I'm reaching for here: how
long does the encryption have to be before perfect compression with
encryption works? Will 1 bit do? 1 bit is enough that you can't
uniquely identify the correct plaintext, but that's not necessarily a
problem for the attacker.
The problem with my original example is that "perfect compression"
gets very counterintuitive: it has to be perfect WRT the model of
message likelihood that the *attacker* has. So if, on seeing that
your message is 1k long, I still think there's a reasonable chance
you're going to the dance, it's therefore overwhelmingly likely that
I'll find a candidate message that says you are when I get to
decryption.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
