Paper 2014/821

Non-malleable Reductions and Applications

Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana, and Maciej Obremski

Abstract

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs~\cite{DPW10}, provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely ``unrelated value''. Although such codes do not exist if the family of ``tampering functions'' \cF allowed to modify the original codeword is completely unrestricted, they are known to exist for many broad tampering families \cF. The family which received the most attention is the family of tampering functions in the so called (2-part) {\em split-state} model: here the message x is encoded into two shares L and R, and the attacker is allowed to {\em arbitrarily} tamper with each L and R individually. Despite this attention, the following problem remained open: 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.