I miss Adrian Colyer’s “The Morning Paper” where he discussed one research paper per day – it was a great read and I learned a lot. I’ll probably never be able to match his quality and throughput, but I actually do read papers (or, more lazily, watch their presentations) and wanted to keep up Adrian’s tradition, at a less ambitious cadence. The inaugural piece in “OPAW: one paper a week” is Alexander Russel’s presentation at Microsoft Research “Fuzzy Extractors are Practical“.
A fuzzy extractor is a cryptographic tool designed to solve a specific problem: getting a stable, secret key from “noisy” data that is slightly different every time it’s measured (like a fingerprint or iris scan); similar enough between scans to identify, not close enough to work as a hash key. Alexander Russell explains how to derive cryptographic keys from iris scans.
The core problem: passwords vs. biometrics
Passwords: If leaked, they can be changed. They are stored as hashes to prevent theft.
Biometrics: Permanent and irreplaceable. If a biometric database is leaked, that “key” is compromised forever.
The Technical Hurdle: Traditional hashes have an avalanche effect—a 1% difference in an image results in a 100% different hash. Error-correcting codes often require “helpers” that are so large they accidentally leak the entire biometric.
The solution: “sample, then lock”
How “Gen” (enrolment) works:
1. Take an initial iris scan.
2. Pick several random combinations of bit positions (eg. bits at positions 1, 2, and 9).
3. Create multiple lockers. In each locker, place the same secret cryptographic key.
4. Lock each locker using the bits from those specific positions.
How “Rep” (authentication) works:
1. Take a new scan of the iris.
2. Because of noise, some bits will be wrong, and most lockers won’t open.
3. As long as at least one locker uses a set of positions that weren’t affected by noise, that locker opens and reveals the secret key.
“Zeta, then lock”: optimising the selection
Not all bits in an iris scan are equal. “Zeta, then Lock”, uses ML and global statistics to select the “best” bits:
- Low noise: Bits that rarely change for the same person.
- High entropy: Bits that vary wildly between different people.
- Weighted Sampling: Instead of picking positions purely at random, the system favours positions that are statistically more reliable and unique.
The method compares favourably to others: the accept rate (“accuracy”) is > 90% and speed is very fast.
Challenges
An issue with previous methods was “more errors than entropy”, where the high noise in biometric scans requires so much error-correction data that it may accidentally leak the secret. The new method uses “min-entropy” (a method to rate cryptographic systems), while simultaneously fighting the natural correlation of iris bits. ML identifies “high-quality” bits that are both uniquely random and statistically stable which are used to build “lockers” that are secure enough to resist hackers, but flexible enough to open reliably for the rightful owner despite minor scanning noise.
George's Techblog 