Abstract
Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs as an elegant generalization of the classical notion 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 F consists of a randomized encoding function Enc and a deterministic decoding function Dec with Dec(Enc(m))=m, such that for any tampering function f in F and any message m, either Dec(f(Enc(m))) equals m or is almost uncorrelated with m.
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,...,f_C) such that f_i acts on the ith block. 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.