Non-malleable code

Key takeaways

Non-malleable code belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Non-malleable code to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Non-malleable code from memory before moving on to harder problems.

Reference excerpt

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.

Background

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.

A source message s {\displaystyle s} is encoded via a (possibly randomized) procedure E n c {\displaystyle Enc} , yielding a code-word c {\displaystyle c} = E n c ( s ) {\displaystyle Enc(s)} . The code-word is modified under some tampering-function f ∈ F {\displaystyle f\in F} to an erroneous-code-word c ∗ {\displaystyle c^{*}} = f ( c ) {\displaystyle f(c)} . The erroneous-code-word c ∗ {\displaystyle c^{*}} is decoded using a procedure D e c {\displaystyle Dec} , resulting in a decoded-message s ∗ {\displaystyle s^{*}} = D e c ( c ∗ ) {\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 ( E n c , D e c ) {\displaystyle (Enc,Dec)} , which give us some meaningful guarantees about the results of the above tampering experiment, for large and interesting families F {\displaystyle F} 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 ∗ = s {\displaystyle s^{*}=s} .

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

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Non-malleable code

Start with the simplest possible case. Write down what Non-malleable code claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Non-malleable code before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Non-malleable code ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Non-malleable code

In research: Non-malleable code appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Non-malleable code in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Non-malleable code is common in secondary-school and first-year university syllabi. It links to neighbouring topics Algorithms, so understanding it makes those chapters shorter.
In everyday life: Look for Non-malleable code outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Non-malleable code in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Non-malleable code means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Non-malleable code out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Non-malleable code in simple terms?

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 unrelat…

Why does Non-malleable code matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Non-malleable code?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Non-malleable code.