[Cryptography] Summary: compression before encryption

Alfonso De Gregorio alfonso.degregorio at gmail.com
Thu Jan 15 12:02:07 EST 2015

On Thu, Jan 15, 2015 at 12:56 PM, Stephan Neuhaus
<stephan.neuhaus at zhaw.ch> wrote:
> Absolutely right. The article in question appeared in Cryptologia
> Volume 10, Issue 2, 1986. DOI: 10.1080/0161-118691860912 URL:
> http://www.tandfonline.com/doi/abs/10.1080/0161-118691860912
> Fun,
> Stephan

The work by Demijan Klinc et al. is also germane to this thread.

Klinc investigated the compression of data encrypted with block
ciphers without knowledge of the key. In [1] they propose a
compression method based on Slepian-Wolf coding, exploiting the
symbol-wise correlation between successive blocks of data produced by
block chaining modes of operation, a la CBC.

[1] Demijan Klinc and Carmit Hazay and Ashish Jagmohan and Hugo
Krawczyk and and Tal Rabin, "On Compression of Data Encrypted with
Block Ciphers", DCC 2009, http://eprint.iacr.org/2010/477

This paper investigates compression of data encrypted with block
ciphers, such as the Advanced Encryption Standard (AES). It is shown
that such data can be feasibly compressed without knowledge of the
secret key. Block ciphers operating in various chaining modes are
considered and it is shown how compression can be achieved without
compromising security of the encryption scheme. Further, it is shown
that there exists a fundamental limitation to the practical
compressibility of block ciphers when no chaining is used between
blocks. Some performance results for practical code constructions used
to compress binary sources are presented.

With thanks as ever,
- alfonso

More information about the cryptography mailing list