Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs \cite{DPW10} as an elegant generalization of the classical notions of error detection, where the corruption of a codeword is viewed as a tampering function acting on it. Informally, a non-malleable code with respect to a family of tampering functions $\mathcal{F}$ consists of a randomized encoding function $\Enc$ and a deterministic decoding function $\Dec$ such that for any $m$, $\Dec(\Enc(m))=m$. Further, for any tampering function $f \in \mathcal{F}$ and any message $m$, $\Dec(f(\Enc(m)))$ is either $m$ or is $\epsilon$-close to a distribution $D_f$ independent of $m$, where $\epsilon$ is called the error.

Of particular importance are non-malleable codes in the $C$-split-state model. In this model, the codeword is partitioned into $C$ equal sized blocks and the tampering function family consists of functions $(f_1,\ldots,f_C)$ such that $f_i$ acts on the $i^{th}$ block. For $C=1$ there cannot exist non-malleable codes. For $C=2$, the best known explicit construction is by Aggarwal, Dodis and Lovett \cite{ADL13} who achieve rate $= \Omega(n^{-6/7})$ and error $=2^{-\Omega(n^{-1/7})}$, where $n$ is the block length of the code.

In our main result, we construct efficient non-malleable codes in the $C$-split-state model for $C=10$ that achieve constant rate and error $=2^{-\Omega(n)}$. These are the first explicit codes of constant rate in the $C$-split-state model for any $C=o(n)$, that do not rely on any unproven assumptions. We also improve the error in the explicit non-malleable codes constructed in the bit tampering model by Cheraghchi and Guruswami \cite{CG14b}.

Our constructions use an elegant connection found between seedless non-malleable extractors and non-malleable codes by Cheraghchi and Guruswami \cite{CG14b}. We explicitly construct such seedless non-malleable extractors for $10$ independent sources and deduce our results on non-malleable codes based on this connection. Our constructions of extractors use encodings and a new variant of the sum-product theorem.