Paper 2013/498
NonMalleable Codes from TwoSource Extractors
Stefan Dziembowski, Tomasz Kazana, and Maciej Obremski
Abstract
We construct an efficient informationtheoretically nonmall\eable code in the splitstate model for onebit messages. Nonmalleable 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 nonmalleable in the splitstate 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 informationtheoretically secure code with such a property, even for $\cal M = \{0,1\}$. Our construction solves this problem. Additionally, it is leakageresilient, 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 innerproduct twosource extractor, but in general it can be instantiated by any twosource 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 nonmalleable codes for onebit 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$.
Metadata
 Available format(s)
 Publication info
 A major revision of an IACR publication in CRYPTO 2013
 Contact author(s)
 tkazana @ mimuw edu pl
 History
 20130815: received
 Short URL
 https://ia.cr/2013/498
 License

CC BY
BibTeX
@misc{cryptoeprint:2013/498, author = {Stefan Dziembowski and Tomasz Kazana and Maciej Obremski}, title = {NonMalleable Codes from TwoSource Extractors}, howpublished = {Cryptology ePrint Archive, Paper 2013/498}, year = {2013}, note = {\url{https://eprint.iacr.org/2013/498}}, url = {https://eprint.iacr.org/2013/498} }