Fuzzy Extractors are Practical

The Challenge with Biometric Authentication

Passwords present a significant security challenge; they are often hard for humans to remember but easy for computers to guess, and data breaches are common. Biometrics, such as iris scans, offer a compelling alternative as they are unique, universal, and convenient. However, they introduce a critical problem: noise. Repeated readings of the same biometric (e.g., two scans of the same iris) are never identical due to minor variations in lighting, angle, or physiological state.

This inherent noise means that traditional cryptographic tools like hash functions, which are fundamental to password security, are unusable. The avalanche effect of a hash function would produce completely different outputs for two very similar biometric readings. Furthermore, if a biometric template is leaked in a data breach, it is compromised forever—unlike a password, one cannot simply “get a new eyeball.”

Traditional Fuzzy Extractors and Their Limitations

The concept of Fuzzy Extractors, introduced nearly three decades ago, aimed to solve this by using error-correcting codes. The core idea is to:

1. Enroll (Gen): During an initial reading, generate a cryptographic key and a public “helper” value. The helper data contains redundancy information derived from an error-correcting code.
2. Authenticate (Rep): During a subsequent reading, use the helper data to correct the noise in the new reading, allowing for the consistent reproduction of the original key.

The critical flaw in this approach for real-world biometrics is the “more errors than entropy” problem. For biometrics like the iris, the amount of noise (error rate is 10-35%) is greater than the amount of unique, random information (entropy, estimated at ~249 bits for an iris). To correct this much error, traditional error-correcting codes require writing more redundancy information into the helper data than there is entropy in the biometric itself. This effectively leaks the entire biometric template, rendering the system insecure.

A Computationally Secure Approach: Sample then Lock

To overcome these limitations, the talk focuses on a computationally secure construction called Sample then Lock. This method abandons traditional error correction in favor of a “digital locker” approach:

1. Enrollment:

   • A random cryptographic key is generated.
   • The system creates hundreds of thousands of “lockers.”
   • For each locker, it randomly selects a small subset of bit positions from the initial biometric reading (e.g., positions 3, 5, and 9).
   • The bits at these positions are used as a combination to “lock” the key. In practice, this is implemented by hashing the subsampled bits and XORing the result with the key.
   • The helper data consists only of these locked values and the list of positions used for each locker. The actual biometric bits are not stored.

2. Authentication:

   • A new biometric reading is taken.
   • The user attempts to “unlock” each locker using the bits from their new reading at the corresponding positions.
   • If the new reading is close enough to the original, the bits at one of the sampled positions will match perfectly, successfully unlocking a locker and revealing the original key.
   • Check bits are appended to the key before locking to verify a successful unlock.

This approach is secure because the helper data does not contain enough information to reconstruct the biometric. An attacker would have to guess the correct combination for at least one locker, which is computationally infeasible if the subsets are large enough.

Innovations for Practical Application

The core contribution of the work is making the Sample then Lock scheme practical and highly effective through several key innovations:

1. Integrated ML Feature Extractor

Initial attempts to improve performance involved statistically analyzing which bit positions were most stable (“less error-prone”) for the same person and most random (“high-entropy”) between different people. However, this failed to account for complex correlations between bits.

The breakthrough was to build this logic directly into a machine learning feature extractor. Using a custom loss function, a model is trained to produce floating-point embeddings that, when converted to bits, naturally exhibit the desired properties:

• Low error for embeddings from the same person.
• High randomness for embeddings from different people.

This integrated approach effectively handles complex, non-pairwise correlations and significantly boosts performance, creating a gap between the intra-person (same iris) and inter-person (different irises) Hamming distance distributions.

2. Adopting a Stronger Security Metric

The research journey revealed that early security metrics were flawed. Initial work in the field (including previous versions of this work) used “average min-entropy,” which was found to be vulnerable to hill-climbing attacks where an adversary targets the weakest locker first and uses that information to guess the rest. The team adopted the much stronger and more pessimistic metric of minimum min-entropy, ensuring the system’s security is determined by its weakest possible link.

3. “Cutting the Tail” and Multiple Enrollments

Two final optimizations boost the system’s performance:

• Cutting the Tail: During setup, they generate a very large number of potential lockers and then discard a percentage of those with the lowest min-entropy. This increases the overall minimum security level at a small cost to the true accept rate (TAR).
• Multiple Readings: The TAR is significantly improved by enrolling multiple initial images and attempting to authenticate with multiple new images. Authentication succeeds if any enrollment/authentication pair matches. This is particularly effective at overcoming quality issues in academic datasets.

Results and Future Work

Combining these techniques, the system achieves unprecedented results for iris biometrics on a single thread of an M4 processor in under a second:

• 105 bits of entropy at a 92% True Accept Rate (TAR).
• 83 bits of entropy at a 98% TAR.

This work effectively closes the gap for iris biometrics. Future work aims to apply these principles to more challenging biometrics like fingerprints and faces, which currently yield lower entropy. This involves designing new fuzzy extractors and interactive protocols to bring practical, high-security key derivation to a wider range of biometric systems.

• Tags:
• Feature
• Machine Learning
• Cryptography
• Fuzzy Extractors
• Biometric Authentication
• Iris Recognition
• Key Derivation