A Rate-Optimizing Compiler for Non-malleable Codes Against Bit-wise Tampering and Permutations

Shashank Agrawal, Divya Gupta, Hemanta K. Maji, Omkant Pandey, and Manoj Prabhakaran

Abstract

A non-malleable code protects messages against a class of tampering functions. Informally, a code is non-malleable if the effect of applying any tampering function on an encoded message is to either retain the message or to replace it with an unrelated message. Two main challenges in this area -- apart from establishing the feasibility against different families of tampering -- are to obtain explicit constructions and to obtain high-rates for such constructions. In this work, we present a compiler to transform low-rate (in fact, zero rate) non-malleable codes against certain class of tampering into an optimal-rate -- i.e., rate 1 -- non-malleable codes against the same class. If the original code is explicit, so is the new one. When applied to the family of bit-wise tampering functions, this subsumes (and greatly simplifies) a recent result of Cheraghchi and Guruswami (TCC 2014). Further, our compiler can be applied to non-malleable codes against the class of bit-wise tampering and bit-level permutations. Combined with the rate-0 construction in a companion work, this yields the first explicit rate-1 non-malleable code for this family of tampering functions. Our compiler uses a new technique for boot-strapping non-malleability by introducing errors, that may be of independent interest.

Note: Greatly expanded proof; cleaner notation.

Available format(s)
Category
Foundations
Publication info
A minor revision of an IACR publication in TCC 2015
Keywords
Non-malleable CodesExplicit ConstructionInformation TheoreticRate 1.
Contact author(s)
hemanta maji @ gmail com
History
2015-01-15: last of 5 revisions
See all versions
Short URL
https://ia.cr/2014/842

CC BY

BibTeX

@misc{cryptoeprint:2014/842,
author = {Shashank Agrawal and Divya Gupta and Hemanta K.  Maji and Omkant Pandey and Manoj Prabhakaran},
title = {A Rate-Optimizing Compiler for Non-malleable Codes Against Bit-wise Tampering and Permutations},
howpublished = {Cryptology ePrint Archive, Paper 2014/842},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/842}},
url = {https://eprint.iacr.org/2014/842}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.