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

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review



  • Ronald Cramer
  • ,
  • Ivan Damgård
  • Nico Döttling, Friedrich-Alexander-University Erlangen-Nürnberg, Erlangen-Nurnberg, Germany
  • ,
  • Irene Giacomelli, University of Wisconsin-Madison
  • ,
  • Chaoping Xing, Nanyang Technological University, Singapore

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 (possibly ⊥) completely unrelated to 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 independent tampering). The second construction is inspired by the recent works about non-malleable codes of Agrawal et al. (TCC 2015) and of Cheraghchi and Guruswami (TCC 2014) and improves our previous result in the bit-wise independent tampering model: it builds the first non-malleable codes with linear-time complexity and optimal-rate (i.e. rate 1 - o(1)).

Original languageEnglish
Title of host publicationInformation Theoretic Security - 10th International Conference, ICITS 2017, Proceedings
EditorsJunji Shikata
Number of pages25
PublisherSpringer VS
Publication year2017
ISBN (print)9783319720883
Publication statusPublished - 2017
Event10th International Conference, ICITS 2017 - Hong Kong, China
Duration: 29 Nov 20172 Dec 2017
Conference number: 10


Conference10th International Conference, ICITS 2017
ByHong Kong
SeriesLecture Notes in Computer Science

    Research areas

  • Bit-wise independent tampering, Linear-time, Non-malleable codes, Secret-sharing

See relations at Aarhus University Citationformats

ID: 119399252