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.
Contents
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
s is encoded via a (possibly randomized) procedureE n c , yielding a code-wordc =E n c ( s ) . - The code-word is modified under some tampering-function
f ∈ F to an erroneous-code-wordc ∗ f ( c ) . - The erroneous-code-word
c ∗ D e c , resulting in a decoded-messages ∗ D e c ( 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
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
Algorithm description
A non-malleable code ensures that either the tampering experiment results in a correct decoded-message
Compared to error correction or error detection, the "right" formalization of non-malleable codes is somewhat harder to define. Let
Thus, we require that for every tampering-function
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
Bit-Wise independent tampering
As one very concrete example, we study non-malleability with respect to the family of functions
With
All families of bounded size
For any "small enough" function family
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(
Tamper(
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
Capacity of non-malleable codes
- For every family
F with| F | ≤ 2 2 α n F with rate arbitrarily close to 1 −α (this is achieved w.h.p. by a randomized construction). - For families of size
e x p ( n O ( 1 ) 2 α n ) 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α n bits of the code-word, which is of special interest.