### Trapdoor Computational Fuzzy Extractors and Stateless Cryptographically-Secure Physical Unclonable Functions

Charles Herder, Ling Ren, Marten van Dijk, 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.

Available format(s)
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Physical Unclonable FunctionPUFring oscillatorlearning parity with noiseLPNlearning with errorsLWE
Contact author(s)
History
2016-05-09: last of 2 revisions
See all versions
Short URL
https://ia.cr/2014/938

CC BY

BibTeX

@misc{cryptoeprint:2014/938,
author = {Charles Herder and Ling Ren and Marten van Dijk and Meng-Day (Mandel) Yu and Srinivas Devadas},
title = {Trapdoor Computational Fuzzy Extractors and Stateless Cryptographically-Secure Physical Unclonable Functions},
howpublished = {Cryptology ePrint Archive, Paper 2014/938},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/938}},
url = {https://eprint.iacr.org/2014/938}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.