Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-070 | 13th April 2018 00:39

Non-Malleable Extractors and Codes in the Interleaved Split-State Model and More


Authors: Eshan Chattopadhyay, Xin Li
Publication: 15th April 2018 12:04
Downloads: 77


We present explicit constructions of non-malleable codes with respect to the following tampering classes. (i) Linear functions composed with split-state adversaries: In this model, the codeword is first tampered by a split-state adversary, and then the whole tampered codeword is further tampered by a linear function. (ii) Interleaved split-state adversary: Here the codeword is partitioned in an unknown (but fixed) way, and then tampered by a split-state adversary. (iii) Bounded communication split-state model: In this model, the split-state adversaries are allowed to participate in a communication protocol (with bounded communication budget) to tamper the codeword. Our results are the first explicit constructions of non-malleable codes in any of these tampering models.

We derive all our non-malleable codes from explicit constructions of seedless non-malleable extractors. We believe that our results on seedless non-malleable extractors and the techniques developed are of independent interest. Using our techniques, we also give an improved extractor for an unknown interleaving of two independent sources.

ISSN 1433-8092 | Imprint