Impossible compression still not possible. [was RE: Debunking the PGP backdoor myth for good. [was RE: Hypothesis: PGP backdoor (was: A security bug in PGP products?)]]

[Dave Korn]

On 28 August 2006 17:12, Ondrej Mikle wrote:

> We are both talking about the same thing :-)

  Oh!
 
> I am not saying there is a finite deterministic algorithm to compress
> every string into "small space", there isn't. BTW, thanks for "There
> is ***NO*** way round the counting theory." :-)
> 
> All I wanted to say is:
> For a specific structure (e.g. movie, picture, sound) there is some
> "good" compression algorithm.
> 
> E.g.: if you take a GIF 65536x65536, all white, with just one pixel
> black, it can be compressed into 35 bytes, see here:
> http://i.iinfo.cz/urs-att/gif3_6-115626056883166.gif
> If you wanted to compress the same picture using JPEG (i.e. discrete
> cosine transform), then two things would happen:
> 
> The compressed jpeg file would be a) much bigger b) decompressed image
> would have "artifacts", because Fourier transform of a pulse is sync
> (infinitely many frequencies). Sure, JPEG is a lossy compression, but
> good enough for photos and images that don't have a lot of high
> frequencies.

  Absolutely, absolutely!  

  A compression algorithm achieves the best results if it is designed with
statistical knowledge of the target domain taken into account.  In any
compression scheme you're balancing the set of inputs that grow smaller on
compression against the necessary counterpart of inputs that grow larger.
Whatever you gain in the first set, you lose in the second.  The secret is to
arrange that the inputs that tend to grow larger are the ones that are
less-common in real-world usage, and thus that the ones that are more common
tend to grow smaller.  In practice, this means eliminating 'redundancy', where
'redundancy' is defined as 'whatever similar properties you can tease out from
the more-common-real-world cases'.

  Of course, I could point out that there is precisely *1* bit of information
in that huge GIF, so even compressing it to 35 bytes isn't a great
achievement... it's one of the set of less-common inputs that grow bigger as a
compromise so that real pictures, which tend to have at least *some*
variation, grow smaller.


    cheers,
      DaveK
-- 
Can't think of a witty .sigline today....


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com