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.Category / Keywords: foundations / Information Reconciliation, Privacy Amplification, Fuzzy Extractors, Randomness Extractors, Error-Correcting Codes, Biometric Authentication Publication Info: 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. Date: received 20 Aug 2010, last revised 26 Jun 2012 Contact author: reyzin at cs bu edu Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation 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. Version: 20120626:165550 (All versions of this report) Discussion forum: Show discussion | Start new discussion