Cryptology ePrint Archive: Report 2013/416

Computational Fuzzy Extractors

Benjamin Fuller and Xianrui Meng and Leonid Reyzin

Abstract: 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.

Category / Keywords: cryptographic protocols / fuzzy extractors, secure sketches, key derivation, learning with errors, error-correcting codes, computational entropy, randomness extractors

Original Publication (with major differences): Conference version in Asiacrypt 2013. Journal version to appear in Information and Computation

Date: received 24 Jun 2013, last revised 23 Jun 2020

Contact author: benjamin fuller at uconn edu

Available format(s): PDF | BibTeX Citation

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

Version: 20200623:144014 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]