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:\mathcal{M}\to \mathcal{L}\times \mathcal{R}\mathcal{,}\mathcal{D}\mathcal{e}\mathcal{c}\mathcal{:}\mathcal{L}\times \mathcal{R}\to \mathcal{M}\mathcal{)}$ 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^{\prime }$ 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 $\mathcal{M}\mathcal{=}\{\mathcal{0}\mathcal{,}\mathcal{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 $$ 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 $$ is chosen uniformly from $$ then the probability (in the experiment described above) that the output message $$ is not equal to $$ can be at most $$.