Privacy Amplification and Non-Malleable Extractors Via Character Sums

In studying how to communicate over a public channel with an active adversary, Dodis and Wichs introduced the notion of a non-malleable extractor. A non-malleable extractor dramatically strengthens the notion of a strong extractor in the sense that it requires the output to be close to uniform given the seed as well as the output of the extractor on an arbitrarily related different seed. We construct the first explicit non-malleable extractor. Our extractor works for sources with entropy rate above half. To achieve a polynomial running time when outputting many bits, we rely on a widely-believed conjecture about the distribution of prime numbers in arithmetic progressions. Using our non-malleable extractor, we obtain protocols for "privacy amplification": key agreement between two parties who share a weakly-random secret. Our protocols work in the presence of an active adversary with unlimited computational power, and have asymptotically optimal entropy loss. When the secret has entropy rate greater than 1/2, the protocol takes two rounds. When the secret has entropy rate delta for any constant delta0, our protocol takes a constant (polynomial in 1/delta) number of rounds. Our protocols run in polynomial time under the above well-known conjecture about primes. Joint work with Yevgeniy Dodis, Trevor D. Wooley and David Zuckerman.