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

Abstract

We provide formal definitions and efficient secure techniques for - turning noisy information into keys usable for any cryptographic application, and, in particular, - reliably and securely authenticating biometric data. 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.

47 pp., 3 figures. Prelim. version in Eurocrypt 2004, Springer LNCS 3027, pp. 523-540. Differences from version 3: minor edits for grammar, clarity, and typos

Cited by in corpus (22)

• Leftover Hashing Against Quantum Side Information
• Maximization of Extractable Randomness in a Quantum Random-Number Generator
• Securing Wireless Communications of the Internet of Things from the Physical Layer, An Overview
• The Fuzzy Vault for fingerprints is Vulnerable to Brute Force Attack
• Strong experimental guarantees in ultrafast quantum random number generation
• On Error Correction for Physical Unclonable Functions
• Error Correction for Physical Unclonable Functions Using Generalized Concatenated Codes
• Attacks and Countermeasures in Fingerprint Based Biometric Cryptosystems
• Authentication Protocols for Internet of Things: A Comprehensive Survey
• Converses for Secret Key Agreement and Secure Computing
• HoneyFaces: Increasing the Security and Privacy of Authentication Using Synthetic Facial Images
• Efficiently decoding strings from their shingles
• A Near-Optimal Algorithm for L1-Difference
• Non-Malleable Condensers for Arbitrary Min-Entropy, and Almost Optimal Protocols for Privacy Amplification
• Identification with Encrypted Biometric Data
• Information-theoretically Secret Key Generation for Fading Wireless Channels
• Adversarial Wiretap Channel with Public Discussion
• Discrete Logarithmic Fuzzy Vault Scheme
• On the Oblivious Transfer Capacity of Generalized Erasure Channels against Malicious Adversaries
• Minutia-pair spectral representations for fingerprint template protection
• Design and Analysis of a Secure Three Factor User Authentication Scheme Using Biometric and Smart Card
• An Improved Robust Fuzzy Extractor