[Cryptography] Summary: compression before encryption

[Jerry Leichter]

On Jan 14, 2015, at 12:52 PM, Jonathan Katz <jkatz at cs.umd.edu> wrote:
> Slightly tangential, but list members may be interested to know that
> in some cases, and under certain assumptions, encrypted data *can* be
> compressed; see:
>  http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1337277
>  http://www.cs.au.dk/%7Ecarmit/compressingAES_journal_revision_1.pdf
Many years ago, Martin Minow got a an article published in a cryptography journal proposing auto-key cryptography.  It was all carefully written in mathematical language to cover up what it was up to, but it amounted to using the message itself as the key for a stream cipher.  This had all kinds of nice properties - e.g., it introduced *exactly* as much randomness as was needed to balance the information content of the message.  Martin inserted an off-hand comment that, with most cryptosystems, you got better results by compressing before encryption, but that his experiments had shown that with this system, compression after encryption did extremely well.

A number of people, of course, wrote in to point out that "didn't he realize that he was just XOR'ing the message with itself so that the result was always all 0's."

Others responded, pointing to the (April 1) date of the issue....

                                                        -- Jerry :-)