Non-malleable code

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 ${\displaystyle s}$ is encoded via a (possibly randomized) procedure ${\displaystyle Enc}$, yielding a code-word ${\displaystyle c}$ = ${\displaystyle Enc(s)}$.
2. The code-word is modified under some tampering-function ${\displaystyle f\in F}$ to an erroneous-code-word ${\displaystyle c^{*}}$=${\displaystyle f(c)}$.
3. The erroneous-code-word ${\displaystyle c^{*}}$ is decoded using a procedure ${\displaystyle Dec}$, resulting in a decoded-message ${\displaystyle s^{*}}$= ${\displaystyle 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 ${\displaystyle (Enc,Dec)}$, which give us some meaningful guarantees about the results of the above tampering experiment, for large and interesting families ${\displaystyle F}$ of tampering functions. The following are several possibilities for the type of guarantees that we may hope for.[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 ${\displaystyle s^{*}=s}$.[3]

A weaker guarantee, called error-detection, requires that the tampering-experiment always results in either the correct value ${\displaystyle s^{*}=s}$ or a special symbol ${\displaystyle 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.

As one very concrete example, we study non-malleability with respect to the family of functions ${\displaystyle f}$ which specify, for each bit of the code-word ${\displaystyle c}$, whether to keep it as is, flip it, set it to 0, set it to 1. That is, each bit of the code-word is modified arbitrarily but independently of the value of the other bits of the code-word. We call this the “bit-wise independent tampering” family ${\displaystyle F_{BIT}}$. Note that this family contains constant functions ${\displaystyle F_{const}}$ and constant-error functions ${\displaystyle F_{err}}$ as subsets. Therefore, as we have mentioned, error-correction and error-detection cannot be achieved w.r.t. this family. Nevertheless, the following can show an efficient non-malleable code for this powerful family.

With ${\displaystyle F_{BIT}}$ we denote the family which contains all tampering functions that tamper every bit independently. Formally, this family contains all functions ${\displaystyle f_{i}:\left\{{0},{1}\right\}^{n}\to \left\{{0},{1}\right\}^{n}}$ that are defined by n functions${\displaystyle f_{i}:\left\{{0},{1}\right\}\to \left\{{0},{1}\right\}}$ (for i=1...n) as ${\displaystyle f(c_{1}..c_{n})=f_{1}(c_{1})..f_{n}(c_{n})}$. Note that there are only 4 possible choices for each ${\displaystyle 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.

• Probabilistic Method Approach

For any "small enough" function family ${\displaystyle F}$, there exists a (possibly inefficient) coding scheme which is non-malleable w.r.t. F. Moreover, for a fixed "small enough" function family ${\displaystyle F}$, a random coding scheme is likely to be non-malleable w.r.t. F with overwhelming probability. Unfortunately, random coding schemes cannot be efficiently represented, nor is the encoding/decoding function likely to be efficient. Therefore, this result should merely be thought of as showing "possibility" and providing a target that we should then strive to match constructively. Moreover, this result also highlights the difference between "error-correction/detection" and "non-malleability" since a result of this form could not be true for the former notions.

• Random Oracle Model Approach

It is not clear what the bound from the theorem[4] 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.

In this model, we consider two ways of interacting with the system:

Execute(${\displaystyle x}$): A user can provide the system with Execute(x) queries, for ${\displaystyle x\in \left\{{0},{1}\right\}^{u}}$, in which case the system computes ${\displaystyle (y,s^{'})\gets G(x,s)}$, updates the state of the system to ${\displaystyle s:=s^{'}}$ and outputs ${\displaystyle y}$.

Tamper(${\displaystyle f}$): We also consider tampering attacks against the system, modeled by Tamper(${\displaystyle f}$) commands, for functions ${\displaystyle f:\left\{{0},{1}\right\}^{n}\to \left\{{0},{1}\right\}^{n}}$. Upon receiving such command, the system state is set to ${\displaystyle 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 ${\displaystyle F}$) cannot provide the attacker with additional information. By using non-malleable code for this purpose we have the conclusion: Let ${\displaystyle (Enc,Dec)}$ be any coding scheme which is non-malleable w.r.t ${\displaystyle F}$, then ${\displaystyle (Enc,Dec)}$ can also be tamper-simulate w.r.t. ${\displaystyle F}$.