Consider the problem of deriving high-quality keys from noisy data in the presense of an active adversary: two parties (or the same party at two different times), holding correlated secret inputs W and W’, wish to agree on a uniformly distributed secret key R by sending a single message over an insecure channel. We study both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties longterm secret SK that they can use to generate a sequence of session keys Rj using multiple pairs (Wj, W0j). The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded storage model with errors.

Our results improve upon previous work in several respects:

– The best previous solution for the keyless case with no errors (i.e., W=W’) required the min-entropy of W to exceed 2n/3, where n is the bit-length of W. Our solution applies whenever min-entropy of W exceeds the minimal possible threshold n/2, and yields a longer key.

– Previous solutions for the keyless case in the presence of errors (i.e., W close, but not equal to, W’) required random oracles. We give the first constructions in the standard model.

– Previous solutions for the keyed case were stateful, thus requiring synchronization between the parties. We give the first stateless solution.