We construct the first reusable fuzzy extractor that makes no assumptions about how multiple readings of the source are correlated (the only prior construction assumed a very specific, unrealistic class of correlations). The extractor works for binary strings with Hamming noise; it achieves computational security under assumptions on the security of hash functions or in the random oracle model. It is simple and efficient and tolerates near-linear error rates.
Our reusable extractor is secure for source distributions of linear min-entropy rate. The construction is also secure for sources with much lower entropy rates--lower than those supported by prior (nonreusable) constructions--assuming that the distribution has some additional structure, namely, that random subsequences of the source have sufficient minentropy. We show that such structural assumptions are necessary to support low entropy rates.
We then explore further how different structural properties of a noisy source can be used to construct fuzzy extractors when the error rates are high, providing a computationally secure and an information-theoretically secure construction for large-alphabet sources.Category / Keywords: Fuzzy extractors, reusability, key derivation, error-correcting codes, computational entropy, digital lockers, point obfuscation Original Publication (with minor differences): IACR-EUROCRYPT-2016 Date: received 6 Apr 2014, last revised 25 Feb 2016 Contact author: bfuller at cs bu edu Available format(s): PDF | BibTeX Citation Note: This version has been significantly revised and the title has been changed. The previous versions of this work were titled "Reusable Fuzzy Extractors via Digital Lockers" and "Key Derivation From Noisy Sources With More Errors Than Entropy." This version also contains new analysis and discussion. Version: 20160226:022339 (All versions of this report) Short URL: ia.cr/2014/243 Discussion forum: Show discussion | Start new discussion