Paper 2013/416

Computational Fuzzy Extractors

Benjamin Fuller, Xianrui Meng, and Leonid Reyzin


Fuzzy extractors derive strong keys from noisy sources. Their security is usually defined information- theoretically, with gaps between known negative results, existential constructions, and polynomial-time constructions. We ask whether using computational security can close these gaps. We show the following: -Negative Result: Noise tolerance in fuzzy extractors is usually achieved using an information reconciliation component called a secure sketch. We show that secure sketches are subject to upper bounds from coding theory even when the information-theoretic security requirement is relaxed. Specifically, we define computational secure sketches using conditional HILL pseudoentropy (Hastad et al., SIAM J. Computing 1999). We show that a computational secure sketch implies an error-correcting code. Thus, HILL pseudoentropy is bounded by the size of the best error-correcting code. Similar bounds apply to information-theoretic secure sketches. -Positive Result: We show that our negative result can be avoided by constructing and analyzing a computational fuzzy extractor directly. We modify the code-offset construction (Juels and Wattenberg, CCS 1999) to use random linear codes. Security is based on the Learning with Errors (LWE) problem and holds when the noisy source is uniform or symbol-fixing (that is, each dimension is either uniform or fixed). As part of the proof, we reduce symbol-fixing security to uniform error security.

Note: Full version of paper that will appear at Information and Computation. Previous version of paper appeared at Asiacrypt 2013.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.Conference version in Asiacrypt 2013. Journal version to appear in Information and Computation
fuzzy extractorssecure sketcheskey derivationlearning with errorserror-correcting codescomputational entropyrandomness extractors
Contact author(s)
benjamin fuller @ uconn edu
2020-06-23: last of 2 revisions
2013-06-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benjamin Fuller and Xianrui Meng and Leonid Reyzin},
      title = {Computational Fuzzy Extractors},
      howpublished = {Cryptology ePrint Archive, Paper 2013/416},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.