Mfcttrf

We have two communication points in an information system, call them A(lice) and B(ackup).

B has to store encrypted data received from A. The storage of B is encrypted, but not compressed¹.

B should have no option to decrypt the data of A².

However, the data channel between A and B are too narrow, compared to the data volume, making the compression of the communication a requirement. However, encryption maximizes the entropy of the content, making it incompressible.

Another option would be to compress the data, and then encrypt it, but then B should be able to decrypt the data to decompress it.

My first idea was that these requirements are contradicting, as it seems with the practical tools known to me. But I am not sure, how does it look from a theoretical view?

Is an encryption possible, what does not worsens the compressibility of the data in it, despite that it is "enough" secure?

¹_{The reason is here data safety and the support of incremental backups, if it matters (I think, it doesn't).}

²_{It has obvious security reason - a backup storage having all data of a complex network becomes a security bottleneck.}

The decompression of compressed-then-encrypted data is not possible without the decryption key, at least for compression and encryption schemes independent of each other. We can make a theoretical argument for that: compression schemes compress only a small portion of possible plaintexts (that happen to be the ones where compression is used in practice), and slightly expand the others (e.g. random data). Encryption makes it impossible to distinguish if two ciphertexts of equal size correspond to plaintext that compression compressed, or not; thus prevents any meaningful decompression.

In the question's situation, the classical solution (described as "Another option" in the question) is to compress at A, then encrypt, then transfer the compressed+encrypted data to B. On retrieval, that same compressed+encrypted data is forwarded from B to A (or A'), decrypted, then decompressed. This reduce bandwidth for backup and retrieval, and storage requirements at B. B does not need to decompress the data at any point: the question's "but then B should be able to decrypt the data to decompress it" is true, but a non-issue.

What is an issue is direct access to a portion of a huge data set: for many common compression algorithms, that requires transfer of all the data before the point being accessed (sometime, all the data). This is solved by a split-then-compress-then-encrypt strategy, where the plaintext is split in segments that are compressed independently, then enciphered independently (or mostly so). But the splitting tends to reduces compression, especially for short segments.

Another issue is that the compression ratio leaks to an eavesdropper, and that reveals something about the data. This can be a serious issue: for voice, it has been shown to be enough to understand what's being said!

I think it is theoretically possible to have semantically secure encryption that supports decompression of encrypted data (both in lossy and lossless compression settings), but that it will be very inefficient in practice.

For a generic approach, one could compress the plaintext, encrypt it using a fully homomorphic encryption scheme, and then decompress the encrypted ciphertext server-side using an implementation of the decompression mechanism as a constant-size circuit that can be evaluated homomorphically. This requires only that the decompression mechanism be expressible as a fixed-size circuit, which is not too restrictive.

The argument made in a previous answer that the ability to decompress encrypted data will leak the compression ratio and therefore violate semantic security I believe to be wrong. It is possible that encrypted decompression blows up all ciphertexts equally, irrespective of the actual compression ratio on the plain data. Even when that is not the case, it is possible that the compression ratio is already apparent from the size of the compressed plaintext alone (e.g. in the case of compressed fixed-size images), so in that case the leakage is there but has nothing to do with the encryption scheme.

I am not an FHE expert, but I think this could be borderline practical in lossy compression settings nowadays. For instance, JPEG decompression is essentially application of an inverse discrete cosine transform on relatively small data blocks. I imagine it could be possible to actually implement this or some other lightweight lossy decompression scheme FHE-style without prohibitive work factors.

It would still be much more efficient in almost any imaginable sense to just store symmetrically encrypted compressed plaintext though. Specifically, I doubt that this can be made more efficient for the client than just decompressing client-side.