Is the decompression of compressed and encrypted data without decryption also theoretically impossible?

Question

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.}

Answer 1

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 or decrypt 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. B does not need the key, and (thus) can't decrypt.

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!

Answer 2

You say you want to decompress the data coming from A so B can do incremental backups and recovery. Were A's data not encrypted this would make perfect sense. But A's data is encrypted and that changes everything. Let's think this through.

Let's say A compresses its data and then encrypts it. And let's say B could somehow decompress the data from A without decrypting it; it can't, but let's suppose. B now has A's decompressed, but encrypted, data. It has, effectively, random bits.

In order to do incremental backups the latest versions of files from A must have something in common with their older versions. But even the smallest change to the unencrypted data will completely change the encrypted data. There are no increments. Each encrypted version of a file from A has nothing in common with the previous version, else you'd be able to extract information. B can't do incremental backups on encrypted data whether the original was compressed or not.

Similarly to do data recovery B must have some sort of pattern to look for. Encrypted data is effectively random. B cannot do data recovery on encrypted data, there's no pattern to look for.

So, from B's perspective, compressed and encrypted data from A is the same as encrypted data from A. It's just smaller.

The integrity of your backup can be handled by conventional means: multiple redundant backups, RAID, off-site backups, and so on. As for incremental backups, I don't think it's possible here. Fortunately that's just about saving disk space. Consider off-loading older versions to cheaper, slower storage.

---

UPDATE As Barmar mentioned in the comment, A could have to slice up its data into files in such a way so that small logical changes only touched a corresponding number of small files. Then B would dutifully backup the new versions of just those files.

For example, if you had a database of resources rather than having them in one big file A could split them up into one resource per file. The resource reference would be obfuscated as a checksum. The checksum would either be calculated or stored in an index. For example, data for thing 123 might be stored as c27b4225f9ed9b196e307b97f07f04e869d954b9.

stuff/
  objects/
    00/9df0b6c69370f17f4abb0eccf335048497dac3
    97/d5b7466a5eb62e8309d8df06e76d0a7496ed26
    af/d5a4ca06ef2f3c8550a3d2ff923a73dd07b17a
    c2/7b4225f9ed9b196e307b97f07f04e869d954b9

You might recognize this as being very similar to a Git repository.

If A makes a change to a single resource it only changes one (hopefully small) file. B only has to store a new version of a single file.

This does mean B can see what resources are changing, how often, and with what other resources. Even with the obfuscated filenames, this can provide some clues to what's in them. I believe this is a necessary information leak if you want incremental backups; there has to be some boundries to the encrypted data for B to use.

Answer 3

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.

Answer 4

The general concept you're thinking of is homomorphic encryption, which is an umbrella term for encryption schemes which allow for some type of internally consistent computation to be performed on the cipher-text (the encrypted data) to produce an encrypted result. For example, you might have two encrypted integers (same key) and you can add them to get a result which would decrypt to the sum with the same key.

The encryption scheme has to be intentionally designed to allow the desired computations and it's a nontrivial problem. I'd say it's certainly possible to design an encryption and compression scheme such that the encryption is homomorphic over the compression, but I don't know of any in practice and I expect it would be very, very difficult.

This is an active area of research. You can read more about it on wikipedia.

Answer 5

An alternative approach to accomplishing your goal: the way incremental backups are typically accomplished on compressed and encrypted data is with convergent encryption.

Note that in this case the backup client is required to maintain an encrypted index of files or file chunks and send that to the server as well. The server is pretty dumb and just stores encrypted blobs and perhaps reference counts. But critically the server need only store each unique encrypted and compressed blob once.

You can use a keyed HMAC instead of a simple hash function to derive the per-file/per-chunk encryption keys if you want to ensure each “tenant” of the system is not vulnerable to confirmation-of-existence attacks.

Variants of convergent encryption are used in many deduplicating backup systems as of 2019. These approaches save on both storage and more significantly network bandwidth.

Answer 6

I agree that these 2 requirements seem contradictory: fast incremental backups, and secure (host-proof) off-site backups.

However, the rsyncrypto documentation specifically points out those specific contradictory requirements:

Sometimes it is necessary to store files on a remote server. This is typically needed for backup purposes. When that is done, there are two concerns that need to be addressed:

1. How to keep the privacy of the files stored?

i.e., "Backup should not be able to decrypt the files."

2. How to keep bandwidth usage to a minimum?

i.e., "the data channel between A and B are too narrow, compared to the data volume."

Both problems have rather simple solutions:

1. Encrypt the files prior to sending them. Keep the key locally.
2. Use rsync to only transfer the changes.

There is just one problem - the two solutions contradict. Plain mode encryption of files hide the specific changes to the file, making rsync useless at detecting in-file changes. This is where rsyncrypto comes to the rescue.

-- https://rsyncrypto.lingnu.com/ ( source code )

Rsyncrypto was designed as part of [a] backup service ... [with] two basic needs:

1. Transfer incremental data over poor upload bandwidths
2. Encrypt the data in a way that does not allow the server to decrypt it

Rsyncrypto solves this problem

-- https://rsyncrypto.lingnu.com/index.php?title=Algorithm

Since rsyncrypto seems to more-or-less solve the stated problem (with small compromises on both sides -- slightly more bandwidth than completely unencrypted plaintext, and slightly less theoretical security than unmodified CBC), I'm going to say that yes, it is theoretically possible.