Compression of Encrypted Data
Mark Johnson, Prakash Ishwar, Vinod Prabhakaran and Daniel Schonberg
(Professors David Wagner and Kannan Ramchandran)
National Science Foundation CCR-0208883, National Science Foundation
CCR-0219722, and Fannie and John Hertz Foundation
In order to transmit redundant data over an insecure and bandwidth-constrained
channel, the standard solution is to first compress the data to its entropy rate and then
encrypt the result. In this project [1,2], we investigate the possibility of
reversing the order of these steps, i.e., first encrypting and then compressing,
without compromising either the compression efficiency or the security. Although
counter-intuitive, this reversal of order is indeed possible in some settings of
interest through the use of source coding with side information constructions.
The data is first encrypted with a stream cipher. The encrypted data is then
compressed under the assumption that the encryption key will be available at the
decoder as side information.
In [1], we show that the reversed system
requires no more randomness in the encryption key than the standard system to
guarantee perfect secrecy. We also consider the achievable compression rates.
For the two special cases of (i) lossless coding, and (ii) lossy coding of a
Gaussian source with a mean-squared error fidelity criterion, we can compress
the encrypted source to the same rate as we could have compressed the original
source. We also consider the extension of our framework to more general
encryption schemes.
In [2], we consider the case where the key is not
truly random, but instead is generated by a pseudo-random generator (PRG). We
show that the computational security of such a system is a direct function of
the strength of the PRG.
Figure 1: The source is first encrypted
and then compressed. The compressor does not have access to the key used in the
encryption step. At the decoder, decompression and decryption are performed in a
single joint step.
Figure 2: An image (at left) is first
encrypted by adding a Bernoulli (0.5) bit-sequence to produce the second image.
The result is then compressed by a factor of two using a distributed source code
to produce the third compressed and encrypted bitstream. Finally, the compressed
bits are simultaneously decompressed and decrypted to obtain the last image. The
decoded image is identical to the original.
- [1]
- M. Johnson, P. Ishwar, V. Prabhakaran, D. Schonberg, and K. Ramchandran,
"On Compressing Encrypted Data," IEEE Trans. on Signal Processing,
Supplement on Secure Media I, vol. 52, no. 10, pp. 2992-3006, October 2004.
- [2]
- M. Johnson, D. Wagner, and K. Ramchandran, "On Compressing Encrypted Data
Without the Encryption Key," Proc. Theory of Cryptography Conference,
(Cambridge, MA), February 2004
Contact: Mark Johnson