Non-malleable code
The notion of non-malleable codes was introduced in 2010 by Dziembowski, Pietrzak, and Wichs, 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

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.
 A source message  is encoded via a (possibly randomized) procedure , yielding a code-word  = .
 The code-word is modified under some tampering-function  to an erroneous-code-word =.
 The erroneous-code-word  is decoded using a procedure , resulting in a decoded-message  = .

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

Error detection 
A weaker guarantee, called error-detection, requires that the tampering-experiment always results in either the correct value  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 F of tampering functions.

Algorithm description
A non-malleable code ensures that either the tampering experiment results in a correct decoded-message  , or the decoded-message  is completely independent of and unrelated to the source-message . In other word, the notion of non-malleability for codes is similar, in spirit, to notions of non-malleability for cryptographic primitives (such as encryption2, commitments and zero-knowledge proofs), introduced by the seminal work of Dolev, Dwork and Naor.

Compared to error correction or error detection, the "right" formalization of non-malleable codes is somewhat harder to define. Let  be a random variable for the value of the decoded-message, which results when we run the tampering experiment with source-message  and tampering-function , over the randomness of the encoding procedure. Intuitively, we wish to say that the distribution of  is independent of the encoded message . Of course, we also want to allow for the case where the tampering experiment results in  (for example, if the tampering function is identity), which clearly depends on .

Thus, we require that for every tampering-function , there exists a distribution  which outputs either concrete values  or a special same  symbol, and faithfully models the distribution of  for all  in the following sense: for every source message , the distributions of  and  are statistically close when the  symbol is interpreted as . That is,  correctly simulates the "outcome" of the tampering-experiment with a function  without knowing the source-messages , but it is allowed some ambiguity by outputting a same  symbol to indicate that the decoded-message should be the same as the source-message, without specifying what the exact value is. The fact that  depends on only  and not on , shows that the outcome of  is independent of , exempting equality.

Relation to error correction/detection 
Notice that non-malleability is a weaker guarantee than error correction/detection; the latter ensure that any change in the code-word can be corrected or at least detected by the decoding procedure, whereas the former does allow the message to be modified, but only to an unrelated value. However, when studying error correction/detection we usually restrict ourselves to limited forms of tampering which preserve some notion of distance (e.g., usually hamming distance) between the original and tampered code-word. 
For example, it is already impossible to achieve error correction/detection for the simple family of functions  which, for every constant , includes a "constant" function  that maps all inputs to . There is always some function in  that maps everything to a valid code-word . In contrast, it is trivial to construct codes that are non-malleable w.r.t , as the output of a constant function is clearly independent of its input. The prior works on non-malleable codes show that one can construct non-malleable codes for highly complex tampering function families  for which error correction/detection can not be achievable.

Application over tampering functions

Bit-wise independent tampering 
As one very concrete example, we study non-malleability with respect to the family of functions  which specify, for each bit of the code-word , whether to keep it as is, flip it, set it to 0, set it to 1. That is, each bit of the code-word is modified arbitrarily but independently of the value of the other bits of the code-word. We call this the “bit-wise independent tampering” family . Note that this family contains constant functions  and constant-error functions  as subsets. Therefore, as we have mentioned, error-correction and error-detection cannot be achieved w.r.t. this family. Nevertheless, the following can show an efficient non-malleable code for this powerful family.

With  we denote the family which contains all tampering functions that tamper every bit independently. Formally, this family contains all functions   that are defined by n functions (for i=1...n) as . Note that there are only 4 possible choices for each  (i.e. how to modify a particular bit) and we name these “set to 0”, “set to 1”, “flip”, “keep” where the meanings should be intuitive. We call the above family the bit-wise independent tampering family.

All families of bounded size 
 Probabilistic Method Approach 
For any "small enough" function family , there exists a (possibly inefficient) coding scheme which is non-malleable w.r.t. F. Moreover, for a fixed "small enough" function family , a random coding scheme is likely to be non-malleable w.r.t. F with overwhelming probability. Unfortunately, random coding schemes cannot be efficiently represented, nor is the encoding/decoding function likely to be efficient. Therefore, this result should merely be thought of as showing "possibility" and providing a target that we should then strive to match constructively. Moreover, this result also highlights the difference between "error-correction/detection" and "non-malleability" since a result of this form could not be true for the former notions.
 
 Random Oracle Model Approach
It is not clear what the bound from the theorem of this type actually implies. For example, it does tell us that non-malleable codes exist with respect to all efficient functions, but this is misleading as we know that efficient non-malleable codes (and ultimately we are only interested in such) cannot be non-malleable w.r.t. this class. Nevertheless, the result by the probabilistic method does give us codes which are non-malleable w.r.t. very general classes of functions in the random oracle model.

Model of tamper-resilient security 
In this model, we consider two ways of interacting with the system:

Execute(): A user can provide the system with Execute(x) queries, for , in which case the system computes , updates the state of the system to  and outputs .

Tamper(): We also consider tampering attacks against the system, modeled by Tamper() commands, for functions . Upon receiving such command, the system state is set to .

An attacker that can also interact with the system via Tamper queries can potentially learn significantly more about the secret state, even recover it entirely. Therefore, we would like to have a general method for securing systems against tampering attacks, so that the ability to issue Tamper queries (at least for functions f in some large family ) cannot provide the attacker with additional information. By using non-malleable code for this purpose we have the conclusion: Let  be any coding scheme which is non-malleable w.r.t , then  can also be tamper-simulate w.r.t. .

Capacity of non-malleable codes 
 For every family  with , there exist non-malleable codes against  with rate arbitrarily close to 1 −  (this is achieved w.h.p. by a randomized construction).
 For families of size  against which there is no non-malleable code of rate 1 −  (in fact this is the case w.h.p for a random family of this size).
 1 −  is the best achievable rate for the family of functions which are only allowed to tamper the first  bits of the code-word, which is of special interest.

References

Algorithms