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. To know the operation schema of non-malleable code, we have to have a knowledge of the basic experiment it based on.
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.
, which give us some meaningful guarantees about the results of the above tampering experiment, for large and interesting families
[2] 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
[3] A weaker guarantee, called error-detection, requires that the tampering-experiment always results in either the correct value
This notion of error-detection is a weaker guarantee than error-correction, and achievable for larger F of tampering functions.
A non-malleable code ensures that either the tampering experiment results in a correct decoded-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.
be a random variable for the value of the decoded-message, which results when we run the tampering experiment with source-message
(for example, if the tampering function is identity), which clearly depends on
correctly simulates the "outcome" of the tampering-experiment with a function
symbol to indicate that the decoded-message should be the same as the source-message, without specifying what the exact value is.
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
, 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
[1] As one very concrete example, we study non-malleability with respect to the family of functions
We call this the “bit-wise independent tampering” family
Note that this family contains constant functions
Nevertheless, the following can show an efficient non-malleable code for this powerful family.
, there exists a (possibly inefficient) coding scheme which is non-malleable w.r.t.
Therefore, this result should merely be thought of as showing "possibility" and providing a target that we should then strive to match constructively.
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.
): A user can provide the system with Execute(x) queries, for
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