On Compressing Encrypted Data

TLDR

When transmitting redundant data over insecure, bandwidth‑constrained channels, it is customary to compress first and then encrypt. This paper investigates whether reversing that order—encrypting first and then compressing—can be done without sacrificing compression efficiency or information‑theoretic security. The authors prove the theoretical feasibility of this reversal and present a system that compresses encrypted data. They show that, using coding with side information, the reversed scheme achieves optimal compression and perfect secrecy while requiring no more key randomness than the conventional approach in certain settings.

Abstract

When it is desired to transmit redundant data over an insecure and bandwidth-constrained channel, it is customary to first compress the data and then encrypt it. In this paper, we investigate the novelty of reversing the order of these steps, i.e., first encrypting and then compressing, without compromising either the compression efficiency or the information-theoretic security. Although counter-intuitive, we show surprisingly that, through the use of coding with side information principles, this reversal of order is indeed possible in some settings of interest without loss of either optimal coding efficiency or perfect secrecy. We show that in certain scenarios our scheme requires no more randomness in the encryption key than the conventional system where compression precedes encryption. In addition to proving the theoretical feasibility of this reversal of operations, we also describe a system which implements compression of encrypted data.