Non-malleable code

Uses your system voice; voice and rate in settings.

Snapshot

≈ 6 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

The notion of non-malleable codes was introduced in 2009 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.

The notion of non-malleable codes was introduced in 2009 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. A source message s is encoded via a (possibly randomized) procedure Enc , yielding a code-word c = Enc(s) . The code-word is modified under some tampering-function f\in F to an erroneous-code-word c^* = f(c) . 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 F of tampering functions. The following are several possibilities for the type of guarantees that we may hope for. 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^* = s . A weaker guarantee, called error-detection, requires that the tampering-experiment always results in either the correct value s^* = s or a special symbol s^* = \perp 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 s^* = s , or the decoded-message s^* is completely independent of and unrelated to the source-message s . 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 Tamper^f_s be a random variable for the value of the decoded-message, which results when we run the tampering experiment with source-message s and tampering-function f , over the randomness of the encoding procedure. Intuitively, we wish to say that the distribution of Tamper^f_s is independent of the encoded message s . Of course, we also want to allow for the case where the tampering experiment results in s^* = s (for example, if the tampering function is identity), which clearly depends on s . Thus, we require that for every tampering-function f\in F , there exists a distribution D_f which outputs either concrete values s^* or a special same * symbol, and faithfully models the distribution of Tamper^f_s for all s in the following sense: for every source message s , the distributions of Tamper^f_s and D_f are statistically close when the * symbol is interpreted as s . That is, D_f correctly simulates the "outcome" of the tampering-experiment with a function f\in F without knowing the source-messages s , 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 D_f depends on only f and not on s , shows that the outcome of Tamper^f_s is independent of s , exempting equality. With F_{BIT} we denote the family which contains all tampering functions that tamper every bit independently. Formally, this family contains all functions f_i: \left\{{0},{1}\right\}^n \to \left\{{0},{1}\right\}^n that are defined by n functions f_i: \left\{{0},{1}\right\} \to \left\{{0},{1}\right\} (for i=1...n) as f(c_1..c_n)=f_1(c_1)..f_n(c_n) . Note that there are only 4 possible choices for each f_i (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. Execute( x ): A user can provide the system with Execute(x) queries, for x\in \left\{{0},{1}\right\}^u , in which case the system computes (y,s^') \gets G(x,s) , updates the state of the system to s :=s^' and outputs y . Tamper( f ): We also consider tampering attacks against the system, modeled by Tamper( f ) commands, for functions f: \left\{{0},{1}\right\}^n \to \left\{{0},{1}\right\}^n . Upon receiving such command, the system state is set to s := f(s) . 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 F ) cannot provide the attacker with additional information. By using non-malleable code for this purpose we have the conclusion: Let (Enc,Dec) be any coding scheme which is non-malleable w.r.t F , then (Enc,Dec) can also be tamper-simulate w.r.t. F .

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1368011465 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

3 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.