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 make progress towards obtaining this result. Specifically, we (a) develop a generalization of non-malleable codes, called {\em 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 $\cF$ 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.
In particular, we design an unconditionally secure non-malleable code with 5 parts where the size of each part is quadratic in the length of the message, and state a conjecture under which we obtain a constant rate 2 part non-malleable code in the split-state model.
Of independent interest, 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.
\paragraph{Note.} Some time after publishing the paper (it was presented at STOC 2015), Xin Li pointed out that one of the proofs in the paper had a mistake. In particular, we had incorrectly claimed a proof of Conjecture 26. We would like to emphasize that we still believe that Conjecture 26 is true but we do not have a proof.
Category / Keywords: applications / Non malleable codes, tampering-resilient cryptography Original Publication (with minor differences): STOC 2015 Date: received 10 Oct 2014, last revised 29 Jan 2019 Contact author: divesh aggarwal at gmail com Available format(s): PDF | BibTeX Citation Version: 20190130:052124 (All versions of this report) Short URL: ia.cr/2014/821