Performing simple arithmetic operations on compressed, and both compressed and encrypted data

Question

We all know it is possible to perform addition and multiplication operations on encrypted data by means of homomorphic encryption methods. My questions are:

Is there any cryptosystem that is able to perform these operations on

1. compressed data

2. first-encrypted then-compressed data

3. first-compressed then-encrypted data

without any decryption or decompression?

Answer 1

Using generic homomorphic encryption the answer for all three is essentially yes. Although 3. in general is probably mainly of theoretical interest as it would be impractically slow.

1. For simply compressed data this is simple since compression should not do anything to hide the data. Just decompress, do the operation and possibly compress the result if needed.

2. For encrypted-then-compressed data this is also easy. Simply decompress and do the operation using the homomorphic encryption and compress the resulting ciphertext. However, you should note that ciphertexts rarely compress very well so it is not often you gain anything from doing this.

3. For compress-then-encrypt things get a little more difficult. However, in principle fully homomorphic encryption allows you to compute any function on a ciphertext. This includes decompression of your compression function. So what you could do is to run the decompression algorithm using the homomorphic encryption to get an encryption of the decompressed message, then apply any operation needed and finally apply the compress function using the homomorphic encryption to get an encryption of the compressed result. The problem here is that fully homomorphic encryption is really not practically efficient for anything but very simple computations. So doing compression and decompression would probably be completely impractical.

Answer 2

Answering just part (1), there do exist techniques to operate directly on compressed data without first decompressing it. Several specialized compression algorithms have been specifically designed to support directly operating on the compressed data.

For example: The RoaringBitmap, like several other compressed bitmap index algorithms, can implement intersection, union, and difference (AND, OR, and AND-NOT) directly on the compressed data without decompressing. (In many cases, the result is found faster than running the same operation on raw uncompressed bitmaps, which is of course faster than decompressing into a raw uncompressed bitmap and then running that same operation). (Some proposed applications of homomorphic encryption only require these 3 operators).

For example, several text compression schemes support searching compressed text for words and phrases; this is often faster than searching the raw uncompressed text directly.

A few kinds of processing can be performed directly on JPEG images, MPEG video, and MPEG audio, without completely decompressing the data (operating directly on the DCT transform coefficients). "A Survey of Compressed Domain Processing Techniques" seems to imply that includes simple arithmetic addition and multiplication operations.