Paper 2010/456

Robust Fuzzy Extractors and Authenticated Key Agreement from Close Secrets

Yevgeniy Dodis, Bhavana Kanukurthi, Jonathan Katz, Leonid Reyzin, and Adam Smith

Abstract

Abstract: Consider two parties holding samples from correlated distributions W and W', respectively, where these samples are within distance t of each other in some metric space. The parties wish to agree on a close-to-uniformly distributed secret key R by sending a single message over an insecure channel controlled by an all-powerful adversary who may read and modify anything sent over the channel. 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_Ext 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. We show solutions that improve upon previous work in several respects: -- The best prior 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 the min-entropy of W exceeds the minimal 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.

Note: The version published in Crypto 2006 contains an incorrect claim (Corollary 2) about the existence of robust fuzzy extractors for the edit distance. The version posted here corrects this error and some other minor errors and adds many clarifications and proofs.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. This is an expanded and corrected version of papers published at CRYPTO 2006 and SCN 2008. It will appear in IEEE Transactions on Information Theory.
Keywords
Information ReconciliationPrivacy AmplificationFuzzy ExtractorsRandomness ExtractorsError-Correcting CodesBiometric Authentication
Contact author(s)
reyzin @ cs bu edu
History
2012-06-26: last of 2 revisions
2010-08-24: received
See all versions
Short URL
https://ia.cr/2010/456
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/456,
      author = {Yevgeniy Dodis and Bhavana Kanukurthi and Jonathan Katz and Leonid Reyzin and Adam Smith},
      title = {Robust Fuzzy Extractors and Authenticated Key Agreement from Close Secrets},
      howpublished = {Cryptology ePrint Archive, Paper 2010/456},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/456}},
      url = {https://eprint.iacr.org/2010/456}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.