## 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 language | English |
---|---|

Title of host publication | 2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011) |

Editors | R Ostrovsky |

Place of Publication | LOS ALAMITOS |

Publisher | IEEE Computer Society |

Pages | 668-677 |

Number of pages | 10 |

DOIs | |

Publication status | Published - 2011 |

Event | 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) - Palm Springs, Canada Duration: 22 Oct 2011 → 25 Oct 2011 |

### Publication series

Name | Annual IEEE Symposium on Foundations of Computer Science |
---|---|

Publisher | IEEE COMPUTER SOC |

ISSN (Print) | 0272-5428 |

### Conference

Conference | 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) |
---|---|

Country/Territory | Canada |

Period | 22/10/11 → 25/10/11 |

## Keywords

- RANDOMNESS