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.

A Compression Cryptosystem is a single coding process, the output of which is both reduced in space and secure against unauthorized decoding. Considering Huffman coding, this pa-per 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 decoded 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.

Unlike the uniform treatment of symbols in different locations of an input file, a new approach is taken in the weighted dynamic compression method suggested in [1], which assigns higher priority to closer to be encoded symbols by means of an increasing weight function. The weighted method is especially suited for the encoding of files with locally skewed distributions. Empirical results have shown that weighted techniques can improve beyond the lower bound given by the entropy for static encoding.

Dynamic compression methods continuously update the model of the underlying text file to be compressed according to the already processed part of the file, assuming that such a model accurately predicts the distribution in the remaining part. Since this premise is not necessarily true, we suggest to update the model only selectively. We give empirical evidence that this hardly affects the compression efficiency, while it obviously may save processing time and allow the use of the compression scheme for cryptographic applications.