We use a fuzzy commitment scheme so the extracted key is chosen by definition to have uniformly random bits. The biometric source is used as the noise term in the LPN problem. A key idea in our construction is to use additional `confidence' information produced by the source for polynomial-time key recovery even under high-noise settings, i.e., $\Theta(m)$ errors, where $m$ is the number of biometric bits. The confidence information is never exposed and is used as a noise-avoiding trapdoor to exponentially reduce key recovery complexity. Previous computational fuzzy extractors were unable to correct $\Theta(m)$ errors or would run in exponential time in $m$.
A second key result is that we relax the requirement on the noise in the LPN problem, which relaxes the requirement on the biometric source. Through a reduction argument, we show that in the LPN problem, correlation in the bits generated by the biometric source can be viewed as a bias on the bits, which affects the security parameter, but not the security of the overall construction.
Using a silicon Physical Unclonable Function (PUF) as a concrete example, we show how keys can be extracted securely and efficiently even under extreme environmental variation.
Category / Keywords: foundations / Physical Unclonable Function, PUF, ring oscillator, learning parity with noise, LPN, learning with errors, LWE Date: received 15 Nov 2014, last revised 15 Nov 2014 Contact author: devadas at mit edu Available format(s): PDF | BibTeX Citation Version: 20141118:190315 (All versions of this report) Short URL: ia.cr/2014/938 Discussion forum: Show discussion | Start new discussion