A Provably Secure Strong PUF Based on LWE: Construction and Implementation
Xiaodan Xi, Ge Li, Ye Wang, Michael Orshansky
Abstract
We construct a strong physical unclonable function (PUF) with provable security against machine learning (ML) attacks on both classical and quantum computers. The security is guaranteed by the cryptographic hardness of learning decryption functions of public-key cryptosystems, and the hardness of the learning-with-errors (LWE) problem defined on integer lattices. We call our construction the lattice PUF. We construct lattice PUF with a physically obfuscated key and an LWE decryption function block. To allow deployments in different scenarios, we demonstrate designs with different latency-area trade-offs. A compact design uses a highly serialized linear-feedback shift register (LFSR) and LWE decryption function, while a latency-optimized design uses an unrolled LFSR and a parallel datapath. We prototype lattice PUF designs with <inline-formula><tex-math notation="LaTeX">$2^{136}$</tex-math></inline-formula> challenge-response pairs (CRPs) on a spartan 6 field-programmable gate array (FPGA). In addition to theoretical security guarantee, we evaluate empirical resistance to the various leading ML techniques: the prediction error remains above <inline-formula><tex-math notation="LaTeX">$49.76\%$</tex-math></inline-formula> after 1 million training CRPs. The resource-efficient design requires only 45 slices for PUF logic proper, and 27 slices for reverse fuzzy extractor. The latency-optimized design achieves a <inline-formula><tex-math notation="LaTeX">$148X$</tex-math></inline-formula> reduction in latency, at a <inline-formula><tex-math notation="LaTeX">$10X$</tex-math></inline-formula> increase in PUF hardware utilization. The mean uniformity of PUF responses is <inline-formula><tex-math notation="LaTeX">$49.98\%$</tex-math></inline-formula> , the mean uniqueness is <inline-formula><tex-math notation="LaTeX">$50.00\%$</tex-math></inline-formula> , and the mean reliability is <inline-formula><tex-math notation="LaTeX">$1.26\%$</tex-math></inline-formula> .