  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 2^136 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
2^128 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.
