Daniel Wichs

Non-Malleable Codes

AUTHORS: Stefan Dziembowski, Krzysztof Pietrzak and Daniel Wichs

We introduce the notion of “non-malleable codes” which relaxes the
notion of error correction and error detection. Informally, a code is
non-malleable if the message contained in a modified codeword is
either the original message, or a completely unrelated value. In
contrast to error-correction and error-detection, non malleability can
be achieved for very rich classes of modifications.

We construct an efficient code that is non-malleable with respect to
modifications that effect each bit of the codeword arbitrarily (i.e.
leave it untouched, flip it or set it to either 0 or 1), but
independently of the value of the other bits of the codeword. Using
the probabilistic method, we also show a very strong and general
statement: there exists a non-malleable code for every “small enough”
family F of functions via which codewords can be modified. Although
this probabilistic method argument does not directly yield efficient
constructions, it gives us efficient non-malleable codes in the
random-oracle model for very general classes of tampering
functions-e.g. functions where every bit in the tampered codeword can
depend arbitrarily on any 99% of the bits in the original codeword.

As an application of non-malleable codes, we show that they provide an
elegant algorithmic solution to the task of protecting functionalities
implemented in hardware (e.g. signature cards) against “tampering
attacks”. In such attacks, the secret state of a physical system is
tampered, in the hopes that future interaction with the modified
system will reveal some secret information. This problem, was
previously studied in the work of Gennaro et al. in 2004 under the
name “algorithmic tamper proof security” (ATP). We show that
non-malleable codes can be used to achieve important improvements over
the prior work. In particular, we show that any functionality can be
made secure against a large class of tampering attacks, simply by
encoding the secret-state with a non-malleable code while it is stored
in memory.