Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
2006/02/28 by Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin +1 · 1,731 citations
Computer Science · Mathematics · #Algorithm #Biometric Identification and Security #Biometrics #Chaos-based Image/Signal Encryption #Closeness #Computer science #Computer security #Cryptographic primitive #Cryptographic protocol #Cryptography #Data mining #Hamming distance #Mathematics #Randomness #Sketch #Theoretical computer science #USable #User Authentication and Security Systems #cs.CR #cs.IT #math.IT
paper · pdf · doi:10.1137/060651380
published in SIAM Journal on Computing 38(1), 97-139 (Society for Industrial and Applied Mathematics) · 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
openalex publication_date 2008/01/01 · arxiv created 2008/04/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.
Citations
Cited by
- METTLE: Efficient Streaming Erasure Code with Peeling Decodability
- The Fuzzy Vault for fingerprints is Vulnerable to Brute Force Attack
- Ideal Attribution and Faithful Watermarks for Language Models
- ioPUF+: A PUF Based on I/O Pull-Up/Down Resistors for Secret Key Generation in IoT Nodes
- Channel-Envelope Differencing Eliminates Secret Key Correlation: LoRa-Based Key Generation in Low Power Wide Area Networks
- Leakage-resilient Cryptography with key derived from sensitive data
- ProxyPrints: From Database Breach to Spoof, A Plug-and-Play Defense for Biometric Systems
- Inaccessible Entropy I: Inaccessible Entropy Generators and Statistically Hiding Commitments from One-Way Functions
- HoneyFaces: Increasing the Security and Privacy of Authentication Using Synthetic Facial Images
- Rateless Bloom Filters: Set Reconciliation for Divergent Replicas with Variable-Sized Elements
- Model Inversion meets Cryptographic Fuzzy Extractors
- Space- and Computationally-Efficient Set Reconciliation via Parity Bitmap Sketch (PBS)
- Code Constructions for Physical Unclonable Functions and Biometric Secrecy Systems
- Secure Biometric-based Remote Authentication Protocol using Chebyshev Polynomials and Fuzzy Extractor
- ISO/IEC-Compliant Match-on-Card Face Verification with Short Binary Templates
- CommonSense: Efficient Set Intersection (SetX) Protocol Based on Compressed Sensing
- Practical Rateless Set Reconciliation
- Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds
- Unique decodability of bigram counts by finite automata
- Variational Secret Common Randomness Extraction
- Performance of the Fuzzy Vault for Multiple Fingerprints (Extended\n Version)
- On fuzzy syndrome hashing with LDPC coding
- A New Biometric Template Protection using Random Orthonormal Projection and Fuzzy Commitment
- Computational Monogamy of Entanglement and Non-Interactive Quantum Key Distribution
- Randomized Nested Polar Subcode Constructions for Privacy, Secrecy, and Storage
- Biometric Bound Credentials for Age Verification
- Wrangling Entropy: Next-Generation Multi-Factor Key Derivation, Credential Hashing, and Credential Generation Functions
- Lower Bounds for Linear Operators
- Tree algorithms for set reconciliation
- Secure authentication via Quantum Physical Unclonable Functions: a review
- IronMask: Modular Architecture for Protecting Deep Face Template
- Building Secure SRAM PUF Key Generators on Resource Constrained Devices
- Cancelable Indexing Based on Low-rank Approximation of Correlation-invariant Random Filtering for Fast and Secure Biometric Identification
- Authentication Protocols for Internet of Things: A Comprehensive Survey
- A Near-Optimal Algorithm for L1-Difference
- Information-theoretically Secret Key Generation for Fading Wireless Channels
- Adversarial Wiretap Channel with Public Discussion
- Entropies and their Asymptotic Theory in the discrete case
- Generalized and Unified Equivalences between Hardness and Pseudoentropy
- Self-Controlled Jamming Resilient Design Using Physical Layer Secret Keys
- An efficient fuzzy extractor for limited noise
- Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols
- Information-theoretic Key Encapsulation and its Applications
- Security of the Improved Fuzzy Vault Scheme in the Presence of Record Multiplicity (Full Version)
- Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification
- Actor-network procedures: Modeling multi-factor authentication, device pairing, social interactions
- Building Scalable Decentralized Payment Systems
- Noise-Driven AI Sensors: Secure Healthcare Monitoring with PUFs
- Security and Privacy Enhanced Gait Authentication with Random Representation Learning and Digital Lockers
- An Improved Robust Fuzzy Extractor
- Security Vulnerabilities Against Fingerprint Biometric System
- How to Verify that a Small Device is Quantum, Unconditionally
- Discrete Logarithmic Fuzzy Vault Scheme
- Identification with Encrypted Biometric Data
- Leakage-resilient Algebraic Manipulation Detection Codes with Optimal Parameters
- A Cryptographic Treatment of the Wiretap Channel
- Secret Key Agreement: General Capacity and Second-Order Asymptotics
- Optimal Key Consensus in Presence of Noise
- On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles
- A Modular End-to-End Framework for Secure Firmware Updates on Embedded\n Systems
- Single-Component Privacy Guarantees in Helper Data Systems and Sparse Coding with Ambiguation
- Error Correction for Physical Unclonable Functions Using Generalized Concatenated Codes
- Secure Long-Range Autonomous Valet Parking: A Reservation Scheme With Three-Factor Authentication and Key Agreement
- Crypto-ncRNA: a bio-inspired post-quantum cryptographic primitive exploiting RNA folding complexity
- Differential Privacy: On the Trade-Off between Utility and Information Leakage
- Property-Preserving Hashing for ℓ1-Distance Predicates: Applications to Countering Adversarial Input Attacks
- Universally Composable Commitments with Communicating Malicious Physically Uncloneable Functions
- CertainSync: Rateless Set Reconciliation with Certainty
- Securing Wireless Communications of the Internet of Things from the Physical Layer, An Overview
- Sharp lower bounds on the extractable randomness from non-uniform sources
Related