{
  "id": "enwiki-001368011465",
  "slug": "non-malleable-code",
  "title": "Non-malleable code",
  "qid": "",
  "lead": "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.",
  "body": "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==",
  "categories": [
    "130042203",
    "20476448",
    "23603337",
    "26220375",
    "7692542"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1368011465",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1786019687.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001368011465",
    "type": "webpage",
    "title": "Non-malleable code",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/non-malleable-code",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001368011465",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1368011465",
    "note": "Immutable snapshot enwiki-001368011465"
  }
}