We construct the first fuzzy extractors that work for a large class of distributions that have negative minimum usable entropy. Their security is computational. They correct Hamming errors over a large alphabet. In order to avoid the worst-case loss, they necessarily restrict distributions for which they work.
Our first construction requires high individual entropy of a constant fraction of symbols, but permits symbols to be dependent. Our second construction requires a constant fraction of symbols to have a constant amount of entropy conditioned on prior symbols. The constructions can be implemented efficiently based on number-theoretic assumptions or assumptions on cryptographic hash functions.Category / Keywords: foundations / fuzzy extractors, key derivation, error-correcting codes, computational entropy, point obfuscation Date: received 6 Apr 2014 Contact author: bfuller at cs bu edu Available format(s): PDF | BibTeX Citation Note: In submission. Version: 20140418:044857 (All versions of this report) Short URL: ia.cr/2014/243 Discussion forum: Show discussion | Start new discussion