Paper 2013/498

Non-Malleable Codes from Two-Source Extractors

Stefan Dziembowski, Tomasz Kazana, and Maciej Obremski

Abstract

We construct an efficient information-theoretically non-mall\-eable code in the split-state model for one-bit messages. Non-malleable codes were introduced recently by Dziembowski, Pietrzak and Wichs (ICS 2010), as a general tool for storing messages securely on hardware that can be subject to tampering attacks. Informally, a code $(Enc : \cal M \rightarrow \cal L \times \cal R, Dec : \cal L \times \cal R \rightarrow \cal M)$ is {\em non-malleable in the split-state model} if any adversary, by manipulating {\em independently} $L$ and $R$ (where $(L,R)$ is an encoding of some message $M$), cannot obtain an encoding of a message $M'$ that is not equal to $M$ but is ``related'' $M$ in some way. Until now it was unknown how to construct an information-theoretically secure code with such a property, even for $\cal M = \{0,1\}$. Our construction solves this problem. Additionally, it is leakage-resilient, and the amount of leakage that we can tolerate can be an arbitrary fraction $\xi < {1}/{4}$ of the length of the codeword. Our code is based on the inner-product two-source extractor, but in general it can be instantiated by any two-source extractor that has large output and has the property of being {\em flexible}, which is a new notion that we define. We also show that the non-malleable codes for one-bit messages have an equivalent, perhaps simpler characterization, namely such codes can be defined as follows: if $M$ is chosen uniformly from $\{0,1\}$ then the probability (in the experiment described above) that the output message $M'$ is not equal to $M$ can be at most $1/2 + \epsilon$.