[Cryptography] coding for compression or secrecy or both or neither

[John Denker]

On 01/16/2015 08:03 AM, ianG wrote:

> It occurs to me that what we need, and I may be talked out my
> posterior here, is keyed compression.

People have been doing that for centuries.  Some
codes provide compression or secrecy or both or
neither.

A Lempel-Ziv code provides compression but not secrecy.

At one opposite extreme, a code such as Reed-Solomon 
results in expansion, not compression, but provides 
for error detection and/or correction.

The Bentley Phrase Code provides compression, but not
secrecy, since the key is widely known.  Back in the
day, clerks could recognize common codewords without 
looking them up.  The code also provides a tiny bit
of resistance against transmission errors, although 
it also magnifies some errors.

Encoding a 64-bit float as 22 characters of ascii
decimal results in enormous expansion, but provides
for legibility and portability.

In yet another category, for centuries embassy codebooks
provided both a modicum of compression and a modicum of 
secrecy.

It is certainly possible to subject the output of such
an encoding to further compression.  Compressing a code
is *not* equivalent to breaking it.

It is also possible to subject the output of such a
code to further encryption.  Enciphered code was the
state of the art for a long, long time.  If Enigma
has been superenciphered by something even modestly
secure. the combination would have been unbreakable.
There is no particular reason to think such a case
will never arise again.

It may be that as of today, every state-of-the-art 
electronic crypto system produces incompressible output, 
but there is no deep reason why that has to be so.

It may be that the length of a compressed message leaks
information about the contents ... but so does the length
of an uncompressed message!  Consider for example the
website  https://firstlook.org/theintercept/.  This is
one of the few media web sites that offers https.  On
the other hand, the length of each article is known, so
any eavesdropper with an IQ greater than 37 can figure 
out what article you are reading.  AFAICT in such a 
situation, https without tor is mostly(*) security theater
... for reasons having nothing to do with compression.

Yes, CRIME makes things /worse/ in some cases, but 
things are already so bad that it's hard to notice.

The claim that hoovering up "only" the metadata is
somehow not spying is beyond ludicrous.

(*) The "https everywhere" campaign is still a good 
idea, even if most people derive no benefit from it,
because it creates a useful ecosystem and creates
useful cover traffic that may come in handy in
special circumstances.  Still, though, it's a long
way from doing what needs to be done ... for reasons
having nothing to do with compression.