Non-malleable code

The notion of Non-malleable codes was introduced for relaxing the notion of error-correction and error-detection. Informally, a code is non-malleable if the message contained in a modified code-word is either the original message, or a completely unrelated value. Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction and error-detection is impossible; for example, when the attacker can completely overwrite the encoded message. Although such codes do not exist if the family of “tampering functions” F is completely unrestricted, they are known to exist for many broad tampering families F.

Background knowledge

Tampering Experiment

To know the operation schema of Non-malleable code, we have to have a knowledge of the basic experiment it based on. The following is the three step method of tampering experiment.

1. A source message s is encoded via a (possibly randomized) procedure $Enc$, yielding a code-word $c$ = $Enc(s)$.
2. The code-word is modified under some tampering-function f∈F to an erroneous-code-word $c^{*}$=$f(c)$.
3. The erroneous-code-word $c^{*}$ is decoded using a procedure $Dec$, resulting in a decoded-message $s^{*}$= $Dec(c^{*})$.

The tampering experiment can be used to model several interesting real-world settings, such as data transmitted over a noisy channel, or adversarial tampering of data stored in the memory of a physical device. Having this experimental base, we would like to build special encoding/decoding procedures (Enc; Dec), which give us some meaningful guarantees about the results of the above tampering experiment, for large and interesting families of tampering functions. The following are several possibilities for the type of guarantees that we may hope for.

Error Correction

One very natural guarantee, called error correction, would be to require that for any tampering function and any source-message s, the tampering experiment always produces the correct decoded message= s.

Error Detection

A weaker guarantee, called error-detection, requires that the tampering-experiment always results in either the correct value = s or a special symbol = indicating that tampering has been detected. This notion of error-detection is a weaker guarantee than error-correction, and achievable for larger families F of tampering functions.