Fuzzy Extractors:
How to Generate Strong Keys from Biometrics and Other Noisy Data

by Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin and Adam Smith
 
Abstract

We provide formal definitions and efficient secure techniques for

Our techniques apply not just to biometric information, but to any keying material that, unlike traditional cryptographic keys, is (1) not reproducible precisely and (2) not distributed uniformly. We propose two primitives: a fuzzy extractor reliably extracts nearly uniform randomness R from its input; the extraction is error-tolerant in the sense that R will be the same even if the input changes, as long as it remains reasonably close to the original. Thus, R can be used as a key in a cryptographic application. A secure sketch produces public information about its input w that does not reveal w, and yet allows exact recovery of w given another value that is close to w. Thus, it can be used to reliably reproduce error-prone biometric inputs without incurring the security risk inherent in storing them.

We define the primitives to be both formally secure and versatile, generalizing much prior work. In addition, we provide nearly optimal constructions of both primitives for various measures of "closeness" of input data, such as Hamming distance, edit distance, and set difference.

Note: an implemenation of some of the algorithms in this paper is available. You may also want to see the related survey.

A preliminary version of this work appears in Advances in Cryptology -- Eurocrypt 2004, Cachin and Camenisch, editors, Lecture Notes in Computer Science 3027, pages 523-540, Springer-Verlag, 2004. This version appears in SIAM Journal on Computing 38(1):97-139, 2008. Copyright by the authors.

Revision history: Jan 20 2008: minor typos and grammar corrections. Sept 20 2007: Clarified discussion of average min-entropy and explicitly addressed average-case extractors. Corrected many minor bugs, typos and inconsistencies. Feb 5 2006: New version includes one new author. Substantial revisions to most sections of the paper, plus a corrected BCH decoding algorithm. Apr 28 2006: The differences from the previous version are only in Appendix E: (a) a minor mistake in the description of Euclidean-algorithm-based BCH decoding is corrected and (b) the description of the decoding process is clarified.