International Association
for Cryptologic Research

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~\\cite{DPW10,LL12,DKO13,ADL14,CG14a,CG14b} is the family of tampering functions in the so called {\\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$ {\\em individually}.

Despite this attention, the following problem remained open:

\\begin{center}

{\\em Build efficient, information-theoretically secure non-malleable codes in the split-state model with constant encoding rate}: $|L|=|R|=O(|x|)$.

\\end{center}

In this work, we resolve this open problem. Our technique for getting our main result is of independent interest. We

\\begin{itemize}

\\item[(a)] develop a generalization of non-malleable codes, called {\\em non-malleable reductions};

\\item[(b)] show simple composition theorem for non-malleable reductions;

\\item[(c)] build a variety of such reductions connecting various (independently interesting) tampering families $\\cF$ to each other; and

\\item[(d)] construct our final, constant-rate, non-malleable code in the split-state model by applying the composition theorem to a series of easy to understand reductions.

\\end{itemize}