Re: Compression and crypto

In article <Xns97CB53FF1BD20H110W296LC45WIN3030R@xxxxxxxxxxxx>, "David A. Scott" <daVvid_a_scott@xxxxxxxxx> writes:
briggs@xxxxxxxxxxxxxxxxx wrote in
news:7SK5kUAZeQLB@xxxxxxxxxxxxxxxxxxxxxxxx:

In article <Xns97CA48986DB9H110W296LC45WIN3030R@xxxxxxxxxxxx>, "David
A. Scott" <daVvid_a_scott@xxxxxxxxx> writes:
"JR" <NoMail@xxxxxxxxx> wrote in
news:e4onvp$818$1@xxxxxxxxxxxxxxxxxxxxxx:


The original file and the compressed file contain the same
information. If lossless compression is used, the exact same.



Sorry but your wrong most add extra data and the crypto
community has a whole never seems to never worry about this.

If the compression algorithm is considered to be unknown then
compressed files contain more information than uncompressed files.


I think this is true of most compressors but not all

I think you don't understand what I'm saying. The statement is only
even meaningful about suites of compressors that might have been
chosen.

This is irrespective of any fixed header information that one may
fear, although fixed headers are one obvious way that this information
may manifest.


Again I agree with you for most compressors but not all.

And again, you don't know what I'm talking about.

If you have a 10Kbit plaintext message that that is compressible to
1.5K using a perfect compression algorithm that is tuned to the exact
characteristics of the transmitter and that is compressed to 2K by
the generic algorithm that you have chosen then there is room for 512
bits of information in the resulting plaintext. If the white hats
had chosen between 64 possible generic compression algorithms
then from the point of view of the black hats we have:

Original message size: 10,000 bits.
Original message information: 1500 bits

Compressed message size: 2,000 bits
Compressed message information: 1506 bits

Unless the compression algorithm is perfect, there will always be more
information in the resulting compressed text than there was in the
original plain text.


The problem is what is a "perfect compressor" since at most compression
is just a reordering of the possible output files.

A perfect compressor is one that minimizes average output length.
This will neccessarily depend on the source model.

It is a natural consequence of this definition that the information
content of a message will closely match the length to which a
perfect compressor would compress it.

The fact that a compression algorithm is merely an example of an
encoding scheme and an [efficient, reversible] encoding scheme is
merely an example of a permutation changes nothing.

But you are correct if I can compress 10k bits to 1,5k and send
2k bits one can put alot of info in that 512 bits of extra space.

This comment reflects a lack of understanding.

You don't have control over that 512 bits of extra space. The control
you get to exert is in your choice of which compression algorithm to
use. That choice leaks information to the opposition (information
about which compression algorithm you chose).

I don't belive there is extra info always there when you compress a file
bijectively here is why. You can take files than appear suited for my
bijective huffman you can find the entropy of such files. When you compress
you will often get longer files but sometimes you get shorter files.
You have just beaten a perfect compressor whatever that is,

Perfect compression is a statement about average behavior. Not behavior
in the case when you happened to choose to encode the complete works
of William Shakespeare in 1 bit and then happened to want to compress
that particular plaintext.

But reality

Remainder snipped since youre not addressing anything I'm talking about.
.

Relevant Pages

  • Re: Compression and crypto
    ... Now suppose that we have 64 possible compression algorithms, ... of trial decompression that's pretty conclusive evidence that ... That's the possibility that bijectivity eliminates. ... No compression algorithm is length-preserving. ...
    (sci.crypt)
  • Re: Attention Sean - question about CSI
    ... Maybe the degree of compression can serve as a measure ... If I am allowed to choose the compression algorithm *after* ... which compresses that string to a single bit. ... Yet, for a truly random sequence of numbers, you won't find any ...
    (talk.origins)
  • Re: Compression and crypto
    ... about which compression algorithm you chose). ... information to the compressed output. ... You have just beaten a perfect compressor whatever ...
    (sci.crypt)
  • Re: compression algorithm is NP complete problem?
    ... polynomial time) into this problem. ... > I heard someone say compression algorithm is NP complete problem. ... I still don't understand how compression algorithm is NP ... what is the shortest packed string that expands to the desired ...
    (comp.theory)
  • Re: DASD Compression Question
    ... compressing "may foul up the compression algorithm" did not ... with just 'DASD Compression' for search argument. ... For IBM-MAIN subscribe / signoff / archive access instructions, ... send email to listserv@xxxxxxxxxxx with the message: GET IBM-MAIN INFO ...
    (bit.listserv.ibm-main)