Title: Rate Optimizing Compiler for Non-malleable Codes

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

Speaker: Shashank Agrawal, UIUC

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. Our compiler uses a new technique for boot-strapping non-malleability by introducing errors, that may be of independent interest.