*** Build efficient, information-theoretically secure non-malleable codes in the split-state model with constant encoding rate: |L|=|R|=O(|x|). ***
In this work, we resolve this open problem. Our technique for getting our main result is of independent interest. We (a) develop a generalization of non-malleable codes, called *non-malleable reductions*; (b) show simple composition theorem for non-malleable reductions; (c) build a variety of such reductions connecting various (independently interesting) tampering families F to each other; (d) construct several new non-malleable codes in the split-state model by applying the composition theorem to a series of easy to understand reductions.
Most importantly, we show several "independence amplification" reductions, showing how to reduce split-state tampering of very few parts to an easier question of split-state tampering with a much larger number of parts. In particular, our final, constant-rate, non-malleable code composes one of these reductions with the very recent, "9-split-state" code of Chattopadhyay and Zuckerman [CZ14].Category / Keywords: applications / Non malleable codes, tampering-resilient cryptography Date: received 10 Oct 2014, last revised 17 Sep 2015 Contact author: divesh aggarwal at gmail com Available format(s): PDF | BibTeX Citation Version: 20150918:055007 (All versions of this report) Short URL: ia.cr/2014/821 Discussion forum: Show discussion | Start new discussion