Error-Correction capabilities of encryption?

Question

This is motivated by this question about the recovery of (corrupted) encrypted files, and in particular the statement (in the answer):

But If I know the algorithm and the key and I make a custom software to decrypt the contents of the file no matter what, I might get a decrypted JPEG that may be partially viewable/cluttered at some places.

In general, how things like full-disk encryption interact with randomly flipped bits is something I haven't thought about. There are two obvious solutions:

• Wrap the full-disk encryption in an error-correcting code
• Minimize the size of each "block" of data which is encrypted, and accept a full loss of data (to that single small block) if there is an error (although this wouldn't be full disk encryption I don't believe).

This question is asking about other potential solutions.

---

For a fixed key $k\in\mathcal{K}$ and encryption randomness $r\in\mathcal{R}$, one can view an encryption scheme $m\mapsto \mathsf{Enc}_k(m;r)$ as a code (in the sense of coding theory) with domain $\mathcal{M}$ and codomain $\mathcal{C}_{k, r}\subseteq \mathcal{X}$. The correctness of the encryption scheme states that the code is uniquely decodable, which one might write as the condition: $$\forall k\in\mathcal{K} : \mathsf{Dec}_k(\mathsf{Enc}_k(m; \mathcal{R})) = m$$ One could could define a code between $\mathcal{M}$ and $\mathcal{X}$ abstractly via the pair of maps $\mathsf{encode}$ and $\mathsf{decode}$. Then several coding-theoretic properties can be captured via conditions such as the above, like unique decodability: $$\forall m\in\mathcal{M} : \mathsf{decode}(\mathsf{encode}(m)) = m$$ A more interesting ability is that of being able to correct errors in some bounded set $\mathcal{E}$. This can often have a "geometric" flavor ($\mathcal{E}$ is a ball in some norm, so the errors are "small"), but I will not impose this requirement. The code $(\mathsf{encode}, \mathsf{decode}$) can correct $\mathcal{E}$ if: $$\forall m\in\mathcal{M} : \mathsf{decode}(\mathsf{encode}(m) + \mathcal{E}) = m$$

I'm curious about what can be said about the error-correction capabilities of IND-CPA encryption schemes. They clearly can have some, for the simple reason that if $(\mathsf{Enc}_k, \mathsf{Dec}_k)$ is IND-CPA, and $(\mathsf{encode}, \mathsf{decode})$ can correct $\mathcal{E}$ errors, then $(\mathsf{encode}\circ \mathsf{Enc}_k, \mathsf{Dec}_k\circ\mathsf{decode})$ is still IND-CPA (its ciphertexts are publicly computable from the initial scheme's ciphertexts), but can now correct $\mathcal{E}$ errors.

The question is therefore if any common schemes have any error-correction properties to speak of. Specifically, if I take some ciphertext $c$ and "flip" a single bit in it (or add any other potentially tiny error), can anything be said about the plaintext's relationship to the "true plaintext"? Do any IND-CPA secure schemes come with error-correction "baked in", or must they be explicitly combined with an error-correcting code as in the construction I mentioned above?

Note that I would be interested even if the schemes are no longer correct, but are "close to correct" in a certain sense. In particular, if $\forall k\in\mathcal{K}$: $$\mathsf{Dec}_k(\mathsf{Enc}_k(m;\mathcal{R}) + \mathcal{E}) \in m + \mathcal{E}'$$ Where $\mathcal{E}'$ is some set of allowable errors, and will hopefully be related to $\mathcal{E}$ (i.e. if the noise is promised to be small, the resulting errors are small as well).

Note that an obvious answer to the above (LWE encryption, which already has a natural coding-theoretic interpretation) appears to only partially work --- ciphertexts of the form $(a, b)$ are error-correcting "in the $b$ slot" naturally, but not "in the $a$ slot". One could then define the set of errors $\mathcal{E} = \{0\}^n\times \overline{\mathcal{E}}$ (where $a$ is $n$-dimensional), and $\overline{\mathcal{E}}$ is "small enough" in a precise sense. I find this slightly unsatisfying due to the "contrived" shape of the errors $\mathcal{E}$ (and that LWE-based encryption arguably requires choosing an error-correcting code already, so that it has error-correction properties "baked in" is unsurprising).

Answer 1

There is no easy way of achieving what you want.

Let ${\cal M}=\{0,1\}^n,$ and ${\cal K}=\{0,1\}^k.$ Let the set $\cal E,$ have cardinality $2^{f},$ for simplicity (no Hamming sphere would have this value if you were only interested in stopping low weight errors, btw). You require that for every message $m\in {\cal M}$ and for every $e\in {\cal E}$ we have: $$ E^{-1}_k(E_k(m)+e)=m ,\quad \forall k\in {\cal K} $$ Let the block cipher being used obey an avalanche criterion. This can be statistical [a bit flip changes on average $n/2$ output bits] or deterministic [a bit flip changes at least $\theta n$ bits, with $\theta=1/2$ for concrete comparison.

In any case with high probability after your bit flip the altered ciphertext is going to be roughly at Hamming distance $n/2$ from the true ciphertext. This has two implications:

1. To correct $n/2$ errors requires a traditional error correction code with asymptotically zero rate. Since two Hamming spheres of radius $\lfloor n/2 \rfloor$ can only be disjoint when centred on a very small (logarithmic number of codewords). For example you could use the Hadamard (equivalently Reed Muller of order 1) code which has distance $n/2,$ but this only gives detection of $(n/2)-1$ or correction of $(n/4)-1$ errors. For $n=256$ you could correct $63$ errors and have $9$ information bits which is the dimension of this code. Hamming sphere of radius $n/2$ has roughly $2^{n-1}/\sqrt{n}$ volume (number of vectors). See the answer to this question herefor details.
2. There are codes which correct specified error patterns that are not Hamming spheres (i.e., the nearest vectors to a codeword up to a distance). See this paper by Tan, Welch and Scholtz hereThese codes are even less efficient, and the asymptotic properties will be even worse in terms of number of codewords.

This has efficiency implications since you are no longer really encrypting messages $m$ one to one but encrypting equivalence classes of messages, where the equivalence class of message $m$ is $$ [m]=\{m+e: e \in {\cal E}\}. $$ In particular, your effective message space is now ${\cal M}^\ast=\{[m]: m \in {\cal E}\}$ which has size $2^{n-f}.$ In fact this setup is reminiscent of Gilbert-Sloane's setup for (keyed) authentication codes (MACs) with no secrecy.

In terms of security parameters, I'd venture that if you wanted $N$ bit security you might want to choose $n=N+f,$ and $k=N,$ in case you like the keylength=blocklength regime, balancing dictionary and brute force attacks. Presumably AES-256 might be used this way.

A decently designed block cipher, however, having been designed with avalanche properties, would be unlikely to have a set $\cal E$ which overlaps with a Hamming sphere centred at zero or any other specified set of errors in any significant way.

Answer 2

There may be some specific use case where it would be desirable to combine the operations, but in general I don't see a benefit over encrypting and then encoding.

The main drawback is that if this scheme isn't equivalent to encryption followed by encoding - that is, the encoding really is a fundamental part of the encryption - then it follows that it's not possible to correct errors without performing the decryption with the key. That is, if this combined encryption and encoding can't be separated into independent steps $E_k(m) = Encode(Encrypt(m, k))$, then it must be that there isn't a key-independent error correction or detection algorithm. This would be a significant problem for long-term storage, where a device could otherwise monitor and correct "bit rot" on an on-going basis.

In general, the encoding parameters (i.e. the error correction capability) should be chosen based on the properties of the storage medium or transmission channel. A piece of encrypted data may move over or through several different channels, and it would be preferable to

1. correct any errors at each step (without decrypting) and
2. have the data encoded optimally for each one.

A scheme like this would require additional redundancy on top of what's built-in, which is just inefficient. Encryption and encoding are separate enough concerns that the algorithms and parameters should be selected independently.