Stefan Dziembowski
A Lower Bound on the Key Length of Information-Theoretic Forward-Secure Storage Schemes
The 4th International Conference on Information Theoretic Security, 2009
Abstract We introduce the notion of “non-malleable codes” which relaxes the notion of error-correction and errordetection.
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, nonmalleability
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.
Available files: [PDF]
A Lower Bound on the Key Length of Information-Theoretic Forward-Secure Storage Schemes
The 4th International Conference on Information Theoretic Security, 2009
Abstract We introduce the notion of “non-malleable codes” which relaxes the notion of error-correction and errordetection.
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, nonmalleability
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.
Available files: [PDF]