Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification
Source: University of Warwick Library
The broad area of randomness extraction studies the problem of converting a weakly random source into a distribution that is close to the uniform distribution in statistical distance. Over the past decades extensive research has been conducted in this area. Besides its original motivation in computing with imperfect random sources, seeded extractors have found applications in coding theory, cryptography, complexity and many other areas. Now-a-days they have nearly optimal constructions of seeded extractors. Dodis and Wichs introduced the notion of a non-malleable extractor to study the problem of privacy amplification with an active adversary. A non-malleable extractor is a much stronger version of a strong extractor.