Privacy Amplification and Non-Malleable Extractors Via Character Sums

Yevgeniy Dodis*, Xin Li, Trevor D. Wooley, David Zuckerman

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

17 Citations (Scopus)

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) not equal 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.

Original languageEnglish
Title of host publication2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011)
EditorsR Ostrovsky
Place of PublicationLOS ALAMITOS
PublisherIEEE Computer Society
Pages668-677
Number of pages10
DOIs
Publication statusPublished - 2011
Event52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) - Palm Springs, Canada
Duration: 22 Oct 201125 Oct 2011

Publication series

NameAnnual IEEE Symposium on Foundations of Computer Science
PublisherIEEE COMPUTER SOC
ISSN (Print)0272-5428

Conference

Conference52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)
CountryCanada
Period22/10/1125/10/11

Keywords

  • RANDOMNESS

Cite this

Dodis, Y., Li, X., Wooley, T. D., & Zuckerman, D. (2011). Privacy Amplification and Non-Malleable Extractors Via Character Sums. In R. Ostrovsky (Ed.), 2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011) (pp. 668-677). (Annual IEEE Symposium on Foundations of Computer Science). IEEE Computer Society. https://doi.org/10.1109/FOCS.2011.67