Paper 2015/1013

Inception Makes Non-malleable Codes Stronger

Divesh Aggarwal, Tomasz Kazana, and Maciej Obremski


Non-malleable codes (NMCs), introduced by Dziembowski, Pietrzak and Wichs~\cite{DPW10}, 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. NMCs have emerged as a fundamental object at the intersection of coding theory and cryptography. A large body of the recent work has focused on various constructions of non-malleable codes in the split-state model. Many variants of NMCs have been introduced in the literature i.e. strong NMCs, super strong NMCs and continuous NMCs. Perhaps the most useful notion among these is that of continuous non-malleable codes, that allows for continuous tampering by the adversary. In this paper we give the first efficient, information-theoretic secure construction of continuous non-malleable codes in $2$-split-state model. Enroute to our main result, we obtain constructions for almost all possible notion of non-malleable codes that have been considered in the split-state model, and for which such a construction is possible. Our result is obtained by a series of black-box reductions starting from the non-malleable codes from~\cite{ADL14}. One of the main technical ingredient of our result is a new concept that we call \emph{inception coding}. We believe it may be of independent interest.

Note: fixed citation error

Available format(s)
Publication info
Published by the IACR in TCC 2017
Non-malleable codescontinuous non-malleable codesstrong non-malleable codesinception coding
Contact author(s)
tkazana @ mimuw edu pl
obremski math @ gmail com
2019-04-08: last of 3 revisions
2015-10-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Divesh Aggarwal and Tomasz Kazana and Maciej Obremski},
      title = {Inception Makes Non-malleable Codes Stronger},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1013},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.