IACR News item: 20 October 2014
Shashank Agrawal, Divya Gupta, Hemanta K. Maji, Omkant Pandey, Manoj Prabhakaran
ePrint ReportInformally, 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
{\\em explicit constructions} and to obtain {\\em 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.
Additional news items may be found on the IACR news page.