Yevgeniy Dodis
New York University

Robust Fuzzy Extractors and Authenticated Key Agreement from Close Secrets

Consider two parties holding correlated random variables W
and W., respectively, that are within distance t of each other in some
metric space. These parties wish to agree on a uniformly distributed
secret key R by sending a single message over an insecure channel controlled
by an all-powerful adversary. We consider 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 {Rj} using multiple pairs {(Wj ,Wj')}.
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.,
  t = 0) requires the min-entropy of W to exceed 2|W|/3. We show
  a solution when the min-entropy of W exceeds the minimal threshold
- Previous solutions for the keyless case in the presence of errors (i.e.,
  t > 0) required random oracles. We give the first constructions (for
  certain metrics) in the standard model.
- Previous solutions for the keyed case were stateful. We give the first
  stateless solution.

Joint work with:
Jonathan Katz, Leonid Reyzin and Adam Smith