Non-malleable codes provide a useful and meaningful security 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'' $\cal{F}$ is completely unrestricted, they are known to exist for many broad tampering families $\cal{F}$. One such natural family is the family of tampering functions in the so called {\em split-state} model. Here the message $m$ is encoded into two shares $L$ and $R$, and the attacker is allowed to {\em arbitrarily} tamper with $L$ and $R$ {\em individually}. The split-state tampering arises in many realistic applications, such as the design of {\em non-malleable secret sharing schemes}, motivating the question of designing efficient non-malleable codes in this model.

Prior to this work, non-malleable codes in the split-state model received considerable attention in the literature, but were constructed either (1) in the random oracle model~\cite{DPW10}, or (2) relied on advanced cryptographic assumptions (such as non-interactive zero-knowledge proofs and leakage-resilient encryption)~\cite{LL12}, or (3) could only encode $1$-bit messages~\cite{DKO13}. As our main result, we build the first efficient, multi-bit, information-theoretically-secure non-malleable code in the split-state model.

The heart of our construction uses the following new property of the inner-product function $\langle L,R \rangle$ over the vector space $\mathbb{F}^n$ (for a prime $p$ and large enough dimension $n$): if $L$ and $R$ are uniformly random over $\mathbb{F}^n$, and $f,g:\mathbb{F}^n\rightarrow \mathbb{F}^n$ are two arbitrary functions on $L$ and $R$, then the joint distribution $(\langle L,R \rangle,\langle f(L),g(R) \rangle)$ is ``close'' to the convex combination of ``affine distributions'' $\{(U,aU+b)\mid a,b\in \mathbb{F}\}$, where $U$ is uniformly random in $\mathbb{F}$. In turn, the proof of this surprising property of the inner product function critically relies on some results from additive combinatorics, including the so called {\em Quasi-polynomial Freiman-Ruzsa Theorem} (which was recently established by Sanders \cite{San12} as a step towards resolving the Polynomial Freiman-Ruzsa conjecture~\cite{Gre05}).