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 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 and any message m , Dec ( f ( Enc ( m ))) is either m or is -close to a distribution D f independent of m , where 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 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 = ( n ? 6 7 ) and error = 2 ? ( 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 = 1 0 that achieve constant rate and error = 2 ? ( 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.
展开▼
