We study the question of information-theoretically secure authenticated key agreement from weak secrets. In this setting, Alice and Bob share a n-bit secret W, which might not be uniformly random but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Alice and Bob wish to use W to agree on a nearly uniform secret key R, over a public channel controlled by an active adversary Eve. We show that non-interactive (single-message) protocols do not work when k is less than n/2.

On the other hand, for arbitrary values of k, we design a communication efficient two-message  protocol extracting nearly k random bits. This dramatically improves the only previously known protocol of [Renner and Wolf 03], which required O(L) rounds where L is the security parameter. Our solution takes a new approach by studying and constructing "non-malleable" seeded randomness extractors} --- if an attacker sees a random seed X and comes up with an arbitrarily related seed X', then we bound the relationship between the randomness extracted from W using X and X' respectively.

We also extend our one-round key agreement protocol to the "fuzzy" setting, where Alice and Bob share "close" (but not equal) secrets W_A and W_B, and to the Bounded Retrieval Model (BRM) where the size of the secret W is huge.