IACR News item: 25 November 2014
Benjamin Fuller, Leonid Reyzin, Adam Smith
ePrint ReportHigh fuzzy min-entropy is necessary for the existence of a fuzzy extractor; moreover, there is evidence that it may be sufficient when only computational security is required. Nevertheless, information-theoretic fuzzy extractors are not known for many practically relevant sources of high fuzzy min-entropy. In this work, we ask: is fuzzy min-entropy sufficient to build information-theoretic fuzzy extractors?
We give a positive answer to this question when the fuzzy extractor knows the precise distribution of the physical source. On the other hand, because it is imprudent to assume precise knowledge of a complicated distribution, fuzzy extractors are typically designed to work for families of sources. We show that this uncertainty is an impediment to security by building a family of high fuzzy min-entropy sources for which no fuzzy extractor can exist.
We provide similar but stronger results for secure sketches, whose goal is not to derive a consistent key, but to recover a consistent reading of the secret.
Additional news items may be found on the IACR news page.