[Cryptography] Is there a good algorithm providing both compression and encryption at the same time?

Ray Dillinger bear at sonic.net
Thu May 7 20:15:22 EDT 2015

```
On 05/06/2015 04:08 PM, Jerry Leichter wrote:
> On May 6, 2015, at 4:15 AM, Francois BERENGER <francois.berenger.fun at gmail.com> wrote:

>> I would be interested in scientific articles or any interesting pointer.
> I doubt there's much work on something like this because I don't see how it could be very good.
> A compressor works by removing redundancy from the input.  The compressed text will reveal where the redundancy was.

In the first place, if compression is perfect, then the
compressed text, like encrypted text, is indistinguishable
from random noise.  A compressor, after all, works by removing
redundancy from the input.  When there is no redundancy there
is no way to tell whether an equiprobable sequence of bits
means one thing or another thing -- only that both things were
within 50% of equally likely to be expressed because they both
mapped to the same bit length.  The fact is that compression
we actually have is never perfect but that's what perfect
compression would mean.

In the second place, while given a practical, not-very-good
compression function that symbol-repetition information may
be available in the compressed text, it _certainly_ won't
be available in the encrypted compressed text unless your
encryption is completely broken when considered separately

There is absolutely nothing wrong with the "compress then
encrypt" construction. As folks have pointed out, you must
never rely on imperfect compression to SERVE AS encryption,
but encrypting compressed text using a good encryption
primitive is not worse at hiding its contents than
encrypting uncompressed text using the same good encryption
primitive.

We usually accept the opponent knowing approximately how long
a message is because the encrypted message is that long plus
the length of a known-length IV and rounded up to a block
boundary.  So I'm not concerned that message length information
may be only as well hidden as it is with any kind of encryption.

Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150507/bd249131/attachment.sig>
```