Paper 2014/243
Key Derivation From Noisy Sources With More Errors Than Entropy
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 high-entropy 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. This helper string reduces the entropy of the original secret—in the worst case, by as much as the logarithm of the number of tolerated error patterns. For many practical sources of secrets, reliability demands that the number of tolerated error patterns is large, making this loss greater than the original entropy of the secret. We say that such sources have more errors than entropy. Most known approaches for building fuzzy extractors cannot be used for such sources. 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.
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.
Metadata
- Available format(s)
- Publication info
- Preprint. MINOR revision.
- Keywords
- Fuzzy extractorsreusabilitykey derivationerror-correcting codescomputational entropypoint obfuscation
- Contact author(s)
- bfuller @ cs bu edu
- History
- 2020-08-26: last of 5 revisions
- 2014-04-18: received
- See all versions
- Short URL
- https://ia.cr/2014/243
- License
-
CC BY