Lattice PUF: A Strong Physical Unclonable Function Provably Secure against Machine Learning Attacks

We propose a strong physical unclonable function (PUF) provably secure against machine learning (ML) attacks with both classical and quantum computers. Its security is derived from cryptographic hardness of learning decryption functions of public-key cryptosystems. Our design compactly realizes the decryption function of the learning-with-errors (LWE) cryptosystem. Due to the fundamental connection of LWE to lattice problems, we call the construction the lattice PUF. Lattice PUF is constructed using a physically obfuscated key (POK), an LWE decryption function block, and a linear-feedback shift register (LFSR) as a pseudo-random number generator. The POK provides the secret key of the LWE decryption function; its stability is ensured by a fuzzy extractor (FE). To reduce the challenge size, we exploit distributional relaxations of space-efficient LWEs. That allows only a small challenge-seed to be transmitted with the full-length challenge generated by the LFSR, resulting in a 100X reduction of communication cost. To prevent an active challenge-manipulation attack, a self-incrementing counter is embedded into the challenge seed. We prototyped the lattice PUF with 2136 challenge-response pairs (CRPs) on a Spartan 6 FPGA, which required 45 slices for the PUF logic proper and 233 slices for the FE. Simulation-based evaluation shows the mean (std) of uniformity to be 49.98% (1.58%), of uniqueness to be 50.00% (1.58%), and of reliability to be 1.26% (2.88%). The LWE concrete hardness estimator guarantees that a successful ML attack of the lattice PUF will require the infeasible 2128 CPU operations. Several classes of empirical ML attacks, including support vector machine, logistic regression, and deep neural networks, are used: in all attacks, the prediction error remains above 49.76% after 1 million training CRPs.