Paper 2014/113

Secure Compression: Theory \& Practice

James Kelley and Roberto Tamassia


Encryption and compression are frequently used together in both network and storage systems, for example in TLS. Despite often being used together, there has not been a formal framework for analyzing these combined systems; moreover, the systems are usually just a simple chaining of compression followed by encryption. In this work, we present the first formal framework for proving security in combined compression-encryption schemes and relate it to the traditional notion of semantic security. We call this entropy-restricted semantic security. Additionally, we present a new, efficient cipher, called the squeeze cipher, that combines compression and encryption into a single primitive and provably achieves our entropy-restricted security.

Note: Revision: Added email addresses of the authors. Added two small lemmas that were omitted in the security proof. Small edits in the text to improve readability and formatting.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
CompressionEncryptionSecure compressionEntropyProvable security
Contact author(s)
jakelley @ cs brown edu
2014-03-25: last of 2 revisions
2014-02-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {James Kelley and Roberto Tamassia},
      title = {Secure Compression: Theory \& Practice},
      howpublished = {Cryptology ePrint Archive, Paper 2014/113},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.