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.
Category / Keywords: foundations / Non-malleable Codes, Explicit Construction, Information Theoretic, Rate 1. Original Publication (with minor differences): IACR-TCC-2015 Date: received 15 Oct 2014, last revised 15 Jan 2015 Contact author: hemanta maji at gmail com Available format(s): PDF | BibTeX Citation Note: Greatly expanded proof; cleaner notation. Version: 20150115:190124 (All versions of this report) Short URL: ia.cr/2014/842 Discussion forum: Show discussion | Start new discussion