TY - JOUR
T1 - Trapdoor Computational Fuzzy Extractors and Stateless Cryptographically-Secure Physical Unclonable Functions
AU - Herder, Charles
AU - Ren, Ling
AU - Van Dijk, Marten
AU - Yu, Meng Day
AU - Devadas, Srinivas
N1 - Funding Information:
This research was partially supported by the National Science Foundation. Marten van Dijk was supported in part by AFOSR MURI under award number FA9550-14-1-0351.
Publisher Copyright:
© 2016 IEEE.
PY - 2017/1/1
Y1 - 2017/1/1
N2 - 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 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.
AB - 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 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.
KW - Fuzzy extractor
KW - learning parity with noise
KW - physical unclonable function
KW - physically obfuscated keys
KW - ring oscillators
UR - http://www.scopus.com/inward/record.url?scp=85010280464&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85010280464&partnerID=8YFLogxK
U2 - 10.1109/TDSC.2016.2536609
DO - 10.1109/TDSC.2016.2536609
M3 - Article
AN - SCOPUS:85010280464
VL - 14
SP - 65
EP - 82
JO - IEEE Transactions on Dependable and Secure Computing
JF - IEEE Transactions on Dependable and Secure Computing
SN - 1545-5971
IS - 1
M1 - 7422776
ER -