  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. A strong extractor takes two inputs, a weakly-random x and a
uniformly random seed y, and outputs a string which appears uniform, even given
y. For a non-malleable extractor nmExt, the output nmExt(x,y) should appear
uniform given y as well as nmExt(x,A(y)), where A is an arbitrary function with
A(y) not equal to y.
  We show that an extractor introduced by Chor and Goldreich is non-malleable
when the entropy rate is above half. It outputs a linear number of bits when
the entropy rate is 1/2 + alpha, for any alpha>0. Previously, no nontrivial
parameters were known for any non-malleable extractor. 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. Our
analysis involves a character sum estimate, which may be of independent
interest.
  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 follows from a
result of Dodis and Wichs, and takes two rounds. When the secret has entropy
rate delta for any constant delta>0, our new 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.
