**Non-Malleable Codes from Two-Source Extractors**

*Stefan Dziembowski and 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$.

**Category / Keywords: **

**Original Publication**** (with major differences): **IACR-CRYPTO-2013

**Date: **received 14 Aug 2013

**Contact author: **tkazana at mimuw edu pl

**Available format(s): **PDF | BibTeX Citation

**Version: **20130815:072621 (All versions of this report)

**Short URL: **ia.cr/2013/498

[ Cryptology ePrint archive ]