Cryptology ePrint Archive: Report 2014/113

Secure Compression: Theory \& Practice

James Kelley and Roberto Tamassia

Abstract: 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.

Category / Keywords: secret-key cryptography / Compression, Encryption, Secure compression, Entropy, Provable security

Date: received 13 Feb 2014, last revised 25 Mar 2014

Contact author: jakelley at cs brown edu

Available format(s): PDF | BibTeX Citation

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.

Version: 20140325:182351 (All versions of this report)

Short URL: ia.cr/2014/113

Discussion forum: Show discussion | Start new discussion