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 Date: received 6 Apr 2014, last revised 29 Oct 2015 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 version of this work was titled "Key Derivation From Noisy Sources With More Errors Than Entropy." This version also contains new analysis and discussion. Version: 20151029:205551 (All versions of this report) Short URL: ia.cr/2014/243 Discussion forum: Show discussion | Start new discussion