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 share a long-term secret SK that they can use to generate a sequence of session keys R_j using multiple pairs (W_j, W'_j). 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.
(joint work with Yevgeniy Dodis, Jonathan Katz and Adam Smith)