Robust fuzzy extractors and authenticated key agreement from close secrets

Yevgeniy Dodis, Jonathan Katz, Leonid Reyzin, Adam Smith

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 |W|/2. - 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - CRYPTO 2006 - 26th Annual International Cryptology Conference, Proceedings
PublisherSpringer Verlag
Pages232-250
Number of pages19
ISBN (Print)3540374329, 9783540374329
DOIs
StatePublished - 2006
Event26th Annual International Cryptology Conference, CRYPTO 2006 - Seattle, WA, United States
Duration: Aug 20 2006Aug 24 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4117 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other26th Annual International Cryptology Conference, CRYPTO 2006
CountryUnited States
CitySeattle, WA
Period8/20/068/24/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Robust fuzzy extractors and authenticated key agreement from close secrets'. Together they form a unique fingerprint.

  • Cite this

    Dodis, Y., Katz, J., Reyzin, L., & Smith, A. (2006). Robust fuzzy extractors and authenticated key agreement from close secrets. In Advances in Cryptology - CRYPTO 2006 - 26th Annual International Cryptology Conference, Proceedings (pp. 232-250). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4117 LNCS). Springer Verlag. https://doi.org/10.1007/11818175_14