International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Robust Fuzzy Extractors and Authenticated Key Agreement from Close Secrets

Yevgeniy Dodis
Jonathan Katz
Leonid Reyzin
Adam Smith
Search ePrint
Search Google
Abstract: Consider two parties holding samples from correlated distributions 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 {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., t=0) requires 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., 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.
  title={Robust Fuzzy Extractors and Authenticated Key Agreement from Close Secrets},
  booktitle={IACR Eprint archive},
  keywords={foundations / Information Reconciliation, Privacy Amplification, Fuzzy Extractors, Randomness Extractors, Error-Correcting Codes, Biometric Authentication},
  note={Corrected and revised version of the paper from Crypto 2006 14845 received 20 Aug 2010, last revised 24 Aug 2010},
  author={Yevgeniy Dodis and Jonathan Katz and Leonid Reyzin and Adam Smith},