We provide constructions of fuzzy extractors for large classes of sources with more errors than entropy. Our constructions exploit the structural properties of a source in addition to its entropy guarantees. Some are made possible by relaxing the security requirement from information-theoretic to computational.
Reusable fuzzy extractors (Boyen, CCS 2004) remain secure even when the initial enrollment phase is repeated multiple times with the same or correlated secrets, producing multiple helper strings. By relying on computational security, we construct the first reusable fuzzy extractors that make no assumption about how multiple readings of the source are correlated.Category / Keywords: Fuzzy extractors, reusability, key derivation, error-correcting codes, computational entropy, point obfuscation Date: received 6 Apr 2014, last revised 1 Dec 2014 Contact author: bfuller at cs bu edu Available format(s): PDF | BibTeX Citation Note: This version contains significant new results. The work now contains information-theoretic and computational constructions. The parameters of sample-then-extract are significantly improved and it is shown to be a reusable fuzzy extractor. Minor modifications and new acknowledgements. Version: 20141201:131554 (All versions of this report) Discussion forum: Show discussion | Start new discussion