Paper 2016/397

Linear-Time Non-Malleable Codes in the Bit-Wise Independent Tampering Model

Ronald Cramer, Ivan Damgård, Nico Döttling, Irene Giacomelli, and Chaoping Xing


Non-malleable codes were introduced by Dziembowski et al. (ICS 2010) as coding schemes that protect a message against tampering attacks. Roughly speaking, a code is non-malleable if decoding an adversarially tampered encoding of a message m produces the original message m or a value m' (eventually abort) completely unrelated with m. It is known that non-malleability is possible only for restricted classes of tampering functions. Since their introduction, a long line of works has established feasibility results of non-malleable codes against different families of tampering functions. However, for many interesting families the challenge of finding "good" non-malleable codes remains open. In particular, we would like to have explicit constructions of non-malleable codes with high-rate and efficient encoding/decoding algorithms (i.e. low computational complexity). In this work we present two explicit constructions: the first one is a natural generalization of the work of Dziembowski et al. and gives rise to the first constant-rate non-malleable code with linear-time complexity (in a model including bit-wise indepen- dent tampering). The second construction is inspired by the recent works about non-malleable codes of Agrawal et al. (TCC 2015) and of Cher- aghchi and Guruswami (TCC 2014) and improves the previous result in the bit-wise tampering model: it builds the first non-malleable codes with linear-time complexity and optimal-rate (i.e. rate 1 - o(1)).

Note: Full version of the paper with the same title published in the proceeding of ICITS 2017

Available format(s)
Publication info
Published elsewhere. Minor revision. Proceedings of ICITS 2017
Contact author(s)
giacomelli @ cs au dk
2017-10-10: last of 2 revisions
2016-04-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ronald Cramer and Ivan Damgård and Nico Döttling and Irene Giacomelli and Chaoping Xing},
      title = {Linear-Time Non-Malleable Codes in the Bit-Wise Independent Tampering Model},
      howpublished = {Cryptology ePrint Archive, Paper 2016/397},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.