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


Too long for a comment:

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.