### 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

Available format(s)
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
See all versions
Short URL
https://ia.cr/2016/397

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},
note = {\url{https://eprint.iacr.org/2016/397}},
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.