Paper 2019/399

Inception makes non-malleable codes shorter as well!

Divesh Aggarwal and Maciej Obremski

Abstract

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs in ICS 2010, have emerged in the last few years as a fundamental object at the intersection of cryptography and coding theory. Non-malleable codes provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely ``unrelated value''. Although such codes do not exist if the family of ``tampering functions'' {\mathcal F} allowed to modify the original codeword is completely unrestricted, they are known to exist for many broad tampering families {\mathcal F}. The family which received the most attention is the family of tampering functions in the so called (2-part) {\em split-state} model: here the message x is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with each L and R individually. Dodis, Kazana, and the authors in STOC 2015 developed a generalization of non-malleable codes called the concept of non-malleable reduction, where a non-malleable code for a tampering family {\mathcal F} can be seen as a non-malleable reduction from {\mathcal F} to a family NM of functions comprising the identity function and constant functions. They also gave a constant-rate reduction from a split-state tampering family to a tampering family {\mathcal G} containing so called $2$-lookahead functions, and forgetful functions. In this work, we give a constant rate non-malleable reduction from the family {\mathcal G} to NM, thereby giving the first {\em constant rate non-malleable code in the split-state model.} Central to our work is a technique called inception coding which was introduced by Aggarwal, Kazana and Obremski in TCC 2017, where a string that detects tampering on a part of the codeword is concatenated to the message that is being encoded.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
Non-malleable codesRandomness extraction
Contact author(s)
dcsdiva @ nus edu sg
History
2019-04-18: received
Short URL
https://ia.cr/2019/399
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/399,
      author = {Divesh Aggarwal and Maciej Obremski},
      title = {Inception makes non-malleable codes shorter as well!},
      howpublished = {Cryptology ePrint Archive, Paper 2019/399},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/399}},
      url = {https://eprint.iacr.org/2019/399}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.