Abstract
When it is desired to transmit redundant data over an insecure and bandwidth-constrained channel, it is customary to first compress the redundant data and then encrypt it for security reasons. In this paper, we investigate the novelty of reversing the order of these steps, i.e. first encrypting and then compressing. Although counter-intuitive, we show surprisingly that through the use of coding with side information principles, this reversal in order is indeed possible. In fact, for lossless compression, we show that the theoretical compression gain is unchanged by performing encryption before compression. We show that the cryptographic security of the reversed system is directly related to the strength of the key generator.
This research was supported by the Fannie and John Hertz Foundation and by NSF under grants CCR-0093337, CCR-0325311, and CCR-0208883.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Schneier, B.: Applied Cryptography. Wiley, New York (1996)
Slepian, D.K., Wolf, J.K.: Noiseless Coding of Correlated Information Sources. IEEE Transactions on Information Theory 19, 471–480 (1973)
Csiszar, I.: Linear Codes for Sources and Source Networks: Error Exponents, Universal Coding. IEEE Transactions on Information Theory 28, 585–592 (1982)
Cover, T.M., Thomas, J.A.: Elements of Information Theory. Wiley, New York (1991)
Pradhan, S.S., Ramchandran, K.: Distributed Source Coding Using Syndromes (DISCUS): Design and Construction. In: Proceedings of the Data Compression Conference (DCC), Snowbird, UT (March 1999)
Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A Concrete Security Treatment of Symmetric Encryption: Analysis of the DES Modes of Operation. In: 38th Symposium on Foundations of Computer Science, Miami Beach, FL (October 1997)
Wicker, S.: Error Control Systems for Digital Communication and Storage. Prentice Hall, Englewood Cliffs (1995)
Berrou, C., Glavieux, A., Thitimajshima, P.: Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes. In: IEEE International Conference on Communications, Geneva, Switzerland (May 1993)
Gallager, R.G.: Low Density Parity Check Codes. PhD thesis, MIT, Cambridge, MA (1963)
Sipser, M., Spielman, D.A.: Expander codes. IEEE Transactions on Information Theory 42, 1710–1722 (1996)
Schonberg, D., Ramchandran, K., Pradhan, S.S.: LDPC Codes Can Approach the Slepian Wolf Bound for General Binary Sources. In: 40th Annual Allerton Conference (October 2002)
Liveris, D., Xiong, Z., Georghiades, C.N.: Compression of Binary Sources with Side Information Using Low-Density Parity-Check Codes. IEEE Communication Letters (2002)
Garcia-Frias, J., Zhao, Y.: Compression of Correlated Binary Sources Using Turbo Codes. IEEE Communication Letters (October 2001)
Aaron, A., Girod, B.: Compression with Side Information Using Turbo Codes. In: IEEE Data Compression Conference (April 2002)
Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, New York (1997)
Witsenhausen, H., Wyner, A.D.: Interframe coder for video signals (1980) (United States Patent Number 4,191,970)
Gamal, E., Orlitsky, A.: Interactive data compression. In: Proceedings 25th IEEE Symposium on Foundations of Computer Science, October 1984, pp. 100–108 (1984)
Orlitsky, A.: Communication Issues in Distributed Computing. PhD thesis, Stanford University, Electrical Engineering Department (1986)
Feder, T., Kushilevitz, E., Naor, M., Nisan, N.: Amortized communication complexity. SIAM Journal on Computing 24(4), 736–750 (1995)
Orlitsky, A.: Interactive communication of balanced distributions and of correlated files. SIAM J. Discret. Math. 6, 548–564 (1993)
Cormode, G., Paterson, M., Sahinalp, S.C., Vishkin, U.: Communication complexity of document exchange. In: Proceedings of the 11th annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, pp. 197–206 (2000)
Capalbo, M., Reingold, O., Vadhan, S., Wigderson, A.: Randomness conductors and constant-degree lossless expanders. In: Proceedings of the 34th annual ACM symposium on Theory of computing, pp. 659–668. ACM Press, New York (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Johnson, M., Wagner, D., Ramchandran, K. (2004). On Compressing Encrypted Data without the Encryption Key. In: Naor, M. (eds) Theory of Cryptography. TCC 2004. Lecture Notes in Computer Science, vol 2951. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24638-1_27
Download citation
DOI: https://doi.org/10.1007/978-3-540-24638-1_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21000-9
Online ISBN: 978-3-540-24638-1
eBook Packages: Springer Book Archive