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

Abstract

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

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. Proceedings of ICITS 2017
Contact author(s)
giacomelli @ cs au dk
History
2017-10-10: last of 2 revisions
2016-04-21: received
See all versions
Short URL
https://ia.cr/2016/397
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/397,
      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},
      url = {https://eprint.iacr.org/2016/397}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.