Secure sketch ⇒ Fuzzy extractor
Statement
Let be an -secure sketch for a metric space whose elements are represented as -bit strings, and let be a universal hash family with . Then , which samples and outputs and , with , is an -fuzzy extractor for , by the leftover hash lemma for average min-entropy; in particular the key can have length — DORS08.
Sketch
is correct because whenever . For security, , so the leftover hash lemma with side information bounds the statistical distance between and by — DORS08.
Notes
- The same construction works with any average-case -strong extractor in place of the hash family, that is, one with -close to for every with ; a worst-case -strong extractor gives an -fuzzy extractor — DORS08.
- If the sketch is average-case, with for every with , then so is the fuzzy extractor: is -close to for every such — DORS08.
- A sketch whose output takes at most values has entropy loss at most , so the construction gives an -fuzzy extractor for every — DORS08.