[DKO13] Non-malleable Codes from Two-Source Extractors

Authors: Stefan Dziembowski, Tomasz Kazana, Maciej Obremski | Venue: CRYPTO 2013 | Source

Abstract

We construct an efficient information-theoretically non-malleable 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 is non-malleable in the split-state model if any adversary, by manipulating independently and (where is an encoding of some message ), cannot obtain an encoding of a message that is not equal to but is “related” in some way. Until now it was unknown how to construct an information-theoretically secure code with such a property, even for . 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 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 .

BibTeX

@Inproceedings{C:DziKazObr13,
  author = {Stefan Dziembowski and Tomasz Kazana and Maciej Obremski},
  title = {Non-malleable Codes from Two-Source Extractors},
  pages = {239--257},
  editor = {Ran Canetti and Juan A. Garay},
  booktitle = {Advances in Cryptology -- {CRYPTO}~2013, Part~II},
  volume = {8043},
  series = {Lecture Notes in Computer Science},
  address = {Santa Barbara, CA, USA},
  month = {aug~18--22},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2013},
  doi = {10.1007/978-3-642-40084-1_14},
}