Computer Science/Discrete Mathematics Seminar II

Seeded and seedless non-malleable extractors are non-trivial generalizations of the more commonly studied seeded and seedless extractors. The original motivation for constructing such non-malleable extractors are from applications to cryptography (privacy amplification and tamper-resilient cryptography). Interestingly, explicitly constructing non-malleable extractors have led to many new connections and progress in pseudoranomness as well. In this talk, I will present explicit constructions of (seedless) non-malleable extractors against small depth circuits (AC0 and NC0) and affine functions. No such construction was known prior to this work, even for full entropy. Using this, we derive the first construction of non-malleable codes (a well studied relaxation of error correcting codes that have applications in cryptography) that can handle tampering functions that are small depth circuits or affine functions. Based on joint work with Xin Li.