# Error-Correction capabilities of encryption?

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

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

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}$$ 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 avalanch properties, would be unlikely to have a set $$\cal E$$ which overlaps with a Hamming sphere centred at zero in any significant way.