Non-malleable Reductions and Applications

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs [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" F allowed to modify the original codeword is completely unrestricted, they are known to exist for many broad tampering families F. The family which received the most attention [DPW10, LL12, DKO13, ADL14, CG14a, CG14b] is the family of tampering functions in the so called (2-part) split-state model: here the message x is encoded into two shares L and R, and the attacker is allowed to 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 resolve this open problem.