Paper 2014/938

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
Physical Unclonable FunctionPUFring oscillatorlearning parity with noiseLPNlearning with errorsLWE
Contact author(s)
devadas @ mit edu
History
2016-05-09: last of 2 revisions
2014-11-18: received
See all versions
Short URL
https://ia.cr/2014/938
License
Creative Commons Attribution
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.