# A Provably Secure Strong PUF based on LWE: Construction and Implementation

arXiv: https://arxiv.org/abs/2303.02802 · HTML: https://mlsanity.com/paper/2303.02802/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 45 references that are in the map.
- First posted on arXiv 5 Mar 2023.

## Builds on (most cited first, 3 of 3)

- [Classical Hardness of Learning with Errors](https://mlsanity.com/paper/1306.0281/) (2013)
- [Lattice PUF: A Strong Physical Unclonable Function Provably Secure against Machine Learning Attacks](https://mlsanity.com/paper/1909.13441/) (2019)
- [Going Deep: Using deep learning techniques with simplified mathematical models against XOR BR and TBR PUFs (Attacks and Countermeasures)](https://mlsanity.com/paper/2009.04063/) (2020)

## Abstract (arXiv)

We construct a strong PUF with provable security against 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 LFSR and LWE decryption function, while a latency-optimized design uses an unrolled LFSR and a parallel datapath. We prototype lattice PUF designs with 2136 challenge-response pairs (CRPs) on a Spartan 6 FPGA. In addition to theoretical security guarantee, we evaluate empirical resistance to the various leading ML techniques: the prediction error remains above 49.76% after 1 million training CRPs. The resource-efficient design requires only 45 slices for the PUF logic proper, and 351 slices for a fuzzy extractor. The latency-optimized design achieves a 148X reduction in latency, at a 10X increase in PUF hardware utilization. The mean uniformity of PUF responses is 49.98%, the mean uniqueness is 50.00%, and the mean reliability is 1.26%.