### DIMACS Theoretical Computer Science Seminar

Title: Privacy Amplification and Non-Malleable Extractors Via Character Sums

Speaker: **David Zuckerman**, Institute for Advanced Study

Date: Wednesday, October 5, 2011 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

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) \neq 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 + a, for any a>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 character sum estimates, 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.

Joint work with Yevgeniy Dodis, Xin Li, and Trevor Wooley.

See: http://paul.rutgers.edu/~yixinxu/theory-fall11.html