Non-Malleable Extractors and Codes, with their Many Tampered Extensions

Understand

Randomness extractors and error correcting codes are fundamental objects in computer science.

• Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography.
• These are seeded non-malleable extractors, introduced in [DW09]; seedless non-malleable extractors, introduced in [CG14b]; and non-malleable codes, introduced in [DPW10].
• However, explicit constructions of non-malleable extractors appear to be hard, and the known constructions are far behind their non-tampered counterparts.