Cryptology ePrint Archive: Report 2014/938
Trapdoor Computational Fuzzy Extractors and Stateless Cryptographically-Secure Physical Unclonable Functions
Charles Herder and Ling Ren and Marten van Dijk and Meng-Day (Mandel) Yu and Srinivas Devadas
Abstract: We present a fuzzy extractor whose security can be reduced to the hardness of Learning Parity with Noise (LPN) and can efficiently correct a constant fraction of errors in a biometric source with a ``noise-avoiding trapdoor." Using this computational fuzzy extractor,
we present a stateless construction of a cryptographically-secure Physical Unclonable Function. Our construct requires no non-volatile (permanent) storage, secure or otherwise, and its computational security can be reduced to the hardness of an LPN variant under the random oracle model. The construction is ``stateless,'' because there is \emph{no} information stored between subsequent queries, which mitigates attacks against the PUF via tampering. Moreover, our stateless construction corresponds to a PUF whose outputs are free of noise because of internal error-correcting capability, which enables a host of applications beyond authentication. We describe the construction, provide a proof of computational security, analysis of the security parameter for system parameter choices, and present experimental evidence that the construction is practical and reliable under a wide environmental range.
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 8 May 2016
Contact author: devadas at mit edu
Available format(s): PDF | BibTeX Citation
Version: 20160509:002057 (All versions of this report)
Short URL: ia.cr/2014/938
[ Cryptology ePrint archive ]