User:Lucyjuicy93/sandbox

The notion of Non-malleable codes was introduced 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 knowledge

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.

1. A source message s is encoded via a (possibly randomized) procedure $Enc$, yielding a code-word $c$ = $Enc(s)$.
2. The code-word is modified under some tampering-function f∈F to an erroneous-code-word $c^{*}$=$f(c)$.
3. 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 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= s.

Error Detection

A weaker guarantee, called error-detection, requires that the tampering-experiment always results in either the correct value = s 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 families 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. Letbe 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 is independent of the encoded message s. Of course, we also want to allow for the case where the tampering experiment results in = s (for example, if the tampering function is identity), which clearly depends on s. 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 s in the following sense: for every source message s, the distributions of and are statistically close when the same * symbol is interpreted as s. That is, correctly simulates the “outcome” of the tampering-experiment with a function 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 depends on only f and not on s, shows that the outcome of is independent of s, exempting equality.