Welcome to the resource topic for 2013/498
Title:
Non-Malleable Codes from Two-Source Extractors
Authors: Stefan Dziembowski, Tomasz Kazana, 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.
ePrint: https://eprint.iacr.org/2013/498
Talk: https://www.youtube.com/watch?v=zh2wKSh3XNM
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .