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 (82)

• Leftover Hashing Against Quantum Side Information
• Maximization of Extractable Randomness in a Quantum Random-Number Generator
• Differential Privacy: on the trade-off between Utility and Information Leakage
• Towards Formalizing the GDPR's Notion of Singling Out
• Key Generation in Wireless Sensor Networks Based on Frequency-selective Channels - Design, Implementation, and Analysis
• Securing Wireless Communications of the Internet of Things from the Physical Layer, An Overview
• A Cryptographic Treatment of the Wiretap Channel
• The Fuzzy Vault for fingerprints is Vulnerable to Brute Force Attack
• Strong experimental guarantees in ultrafast quantum random number generation
• Secure and Reliable Key Agreement with Physical Unclonable Functions
• Polynomial-Time, Semantically-Secure Encryption Achieving the Secrecy Capacity
• Security Vulnerabilities Against Fingerprint Biometric System
• On Error Correction for Physical Unclonable Functions
• Controllable Identifier Measurements for Private Authentication with Secret Keys
• THRIVE: Threshold Homomorphic encryption based secure and privacy preserving bIometric VErification system
• Theoretical framework for physical unclonable functions, including quantum readout
• Secure Communications using Nonlinear Silicon Photonic Keys
• Practical security analysis of a continuous-variable quantum random number generator with a noisy local oscillator
• Secret Key Agreement with Physical Unclonable Functions: An Optimality Summary
• A Modular End-to-End Framework for Secure Firmware Updates on Embedded Systems
• Building Scalable Decentralized Payment Systems
• Optimal Key Consensus in Presence of Noise
• Performance of the Fuzzy Vault for Multiple Fingerprints (Extended Version)
• Error Correction for Physical Unclonable Functions Using Generalized Concatenated Codes
• Capacity Upper Bounds for Deletion-Type Channels
• ShakeMe: Key Generation From Shared Motion
• PUF for the Commons: Enhancing Embedded Security on the OS Level
• Practical Rateless Set Reconciliation
• Actor-network procedures: Modeling multi-factor authentication, device pairing, social interactions
• Attacks and Countermeasures in Fingerprint Based Biometric Cryptosystems
• Security of the Improved Fuzzy Vault Scheme in the Presence of Record Multiplicity (Full Version)
• Secret Key Agreement: General Capacity and Second-Order Asymptotics
• Authentication Protocols for Internet of Things: A Comprehensive Survey
• On an almost-universal hash function family with applications to authentication and secrecy codes
• Application of single-electron effects to fingerprints of chips using image recognition algorithms
• Secret Sharing Schemes Based on Min-Entropies
• Randomized Nested Polar Subcode Constructions for Privacy, Secrecy, and Storage
• The Wiretap Channel for Capacitive PUF-Based Security Enclosures
• Key Generation for Internet of Things: A Contemporary Survey
• Secure authentication via Quantum Physical Unclonable Functions: a review
• Modulus Computational Entropy
• Modal frustration and periodicity breaking in artificial spin ice
• Converses for Secret Key Agreement and Secure Computing
• HoneyFaces: Increasing the Security and Privacy of Authentication Using Synthetic Facial Images
• Fuzzy Commitments Offer Insufficient Protection to Biometric Templates Produced by Deep Learning
• Efficiently decoding strings from their shingles
• Comparative Analysis of SRAM PUF Temperature Susceptibility on Embedded Systems
• A Near-Optimal Algorithm for L1-Difference
• Secure Biometric-based Remote Authentication Protocol using Chebyshev Polynomials and Fuzzy Extractor
• Non-Malleable Condensers for Arbitrary Min-Entropy, and Almost Optimal Protocols for Privacy Amplification
• Self-Controlled Jamming Resilient Design Using Physical Layer Secret Keys
• Entropies and their Asymptotic Theory in the discrete case
• Cancelable Indexing Based on Low-rank Approximation of Correlation-invariant Random Filtering for Fast and Secure Biometric Identification
• A New Biometric Template Protection using Random Orthonormal Projection and Fuzzy Commitment
• Identification with Encrypted Biometric Data
• Generation of Secret Key for Physical Layer to Evaluate Channel Characteristics in Wireless Communications
• IronMask: Modular Architecture for Protecting Deep Face Template
• Inaccessible Entropy I: Inaccessible Entropy Generators and Statistically Hiding Commitments from One-Way Functions
• Building Secure SRAM PUF Key Generators on Resource Constrained Devices
• Adversarial Wiretap Channel with Public Discussion
• A Capacity-achieving One-message Key Agreement With Finite Blocklength Analysis
• Information-theoretically Secret Key Generation for Fading Wireless Channels
• Code Constructions for Physical Unclonable Functions and Biometric Secrecy Systems
• On the Oblivious Transfer Capacity of Generalized Erasure Channels against Malicious Adversaries
• Leakage-resilient Cryptography with key derived from sensitive data
• Channel-Envelope Differencing Eliminates Secret Key Correlation: LoRa-Based Key Generation in Low Power Wide Area Networks
• An Improved Robust Fuzzy Extractor
• Minutia-pair spectral representations for fingerprint template protection
• Single-Component Privacy Guarantees in Helper Data Systems and Sparse Coding with Ambiguation
• Discrete Logarithmic Fuzzy Vault Scheme
• A Convex Analysis Approach to Computational Entropy
• Nearly-Linear Time Seeded Extractors with Short Seeds
• Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification
• Security and Privacy Enhanced Gait Authentication with Random Representation Learning and Digital Lockers
• Information-theoretic Key Encapsulation and its Applications
• Unique decodability of bigram counts by finite automata
• On fuzzy syndrome hashing with LDPC coding
• Space- and Computationally-Efficient Set Reconciliation via Parity Bitmap Sketch (PBS)
• Symbolic Execution + Model Counting + Entropy Maximization = Automatic Search Synthesis
• Privacy Amplification and Non-Malleable Extractors Via Character Sums
• Design and Analysis of a Secure Three Factor User Authentication Scheme Using Biometric and Smart Card
• Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols