Cryptology ePrint Archive: Report 2014/243

Reusable Fuzzy Extractors for Low-Entropy Distributions

Ran Canetti and Benjamin Fuller and Omer Paneth and Leonid Reyzin and Adam Smith

Abstract: Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a secret into the same uniformly distributed key. To eliminate noise, they require an initial enrollment phase that takes the first noisy reading of the secret and produces a nonsecret helper string to be used in subsequent readings. Reusable fuzzy extractors (Boyen, CCS 2004) remain secure even when this initial enrollment phase is repeated multiple times with noisy versions of the same secret, producing multiple helper strings (for example, when a single person's biometric is enrolled with multiple unrelated organizations).

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:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]