Cryptology ePrint Archive: Report 2018/1069

Non-Malleable Extractors and Codes for Composition of Tampering, Interleaved Tampering and More

Eshan Chattopadhyay and Xin Li

Abstract: Non-malleable codes were introduced by Dziembowski, Pietrzak, and Wichs (JACM 2018) as a generalization of standard error correcting codes to handle severe forms of tampering on codewords. This notion has attracted a lot of recent research, resulting in various explicit constructions, which have found applications in tamper-resilient cryptography and connections to other pseudorandom objects in theoretical computer science.

We continue the line of investigation on explicit constructions of non-malleable codes in the information theoretic setting, and give explicit constructions for several new classes of tampering functions. These classes strictly generalize several previously studied classes of tampering functions, and in particular extend the well studied split-state model which is a "compartmentalized" model in the sense that the codeword is partitioned a prior into disjoint intervals for tampering. Specifically, we give explicit non-malleable codes for the following classes of tampering functions.

(1) Interleaved split-state tampering: Here the codeword is partitioned in an unknown way by an adversary, and then tampered with by a split-state tampering function.

(2) Linear function composed with split-state tampering: In this model, the codeword is first tampered with by a split-state adversary, and then the whole tampered codeword is further tampered with by a linear function. In fact our results are stronger, and we can handle linear function composed with interleaved split-state tampering.

(3) Bounded communication split-state tampering: In this model, the two split-state tampering adversaries are allowed to participate in a communication protocol with a bounded communication budget. Our results are the first explicit constructions of non-malleable codes in any of these tampering models. We derive all these results from explicit constructions of seedless non-malleable extractors, which we believe are of independent interest. Using our techniques, we also give an improved seedless extractor for an unknown interleaving of two independent sources.

Category / Keywords: foundations / non-malleable codes, non-malleable extractors, explicit constructions

Date: received 2 Nov 2018

Contact author: eshanc at cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20181109:162934 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]