Compression Cryptosystem

Abstract A compression cryptosystem is a single coding process, the output of which is both reduced in space and secure against unauthorized decoding. Considering both Huffman and arithmetic coding, this paper proposes to apply repeatedly minor changes to the compression model, with negligible deterioration of its optimality. The cumulative impact of a large number of such changes leads to completely different ciphertexts, which can be decrypted only if a given secret key is known. The security of the system is based on the NP-completeness of a problem related to breaking the code. Several variants are suggested, and their results are tested in various settings, including for security against chosen plaintext attacks.