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.

Silicon physical unclonable functions (PUFs) produce a sequence of response bits from chip-unique manufacturing variations. Since the response bits are physically derived, there is noise present. To generate bit-exact cryptographic keys, error correction algorithms are used. The error correction is typically split into small processing blocks to reduce implementation complexity. The reliability of PUF responses varies from bit to bit, but there has been very little work so far that mathematically analyzes the effect of the block size on the reliability of PUF response sequences. We use the information theoretical concept of typicality to show that the probability of drawing an unreliable sequence decreases exponentially with the block size. We present differential sequence coding that scales efficiently across larger block sizes without having the super-linear increase in decoding complexity of prior approaches. It scans the entire PUF response sequentially and then only operates on one single, maximally reliable, block to generate the cryptographic key. Our sample FPGA implementation with a convolutional code is designed for a popular SRAM PUF scenario. It generates a 128-bit key for an average input bit error probability of 15% with an output bit error probability of 6.14 · 10-9and only uses 974 PUF bits and 1, 108 helper data bits. There are 36% less PUF bits and 71% less helper data bits than the best previous individual results in both criteria without increasing the implementation size of the key generation module noticeably.

Physical Unclonable Functions (PUFs) derive unique secrets from internal manufacturing variations in integrated circuits. This work shows that key generation with PUFs is a practical application of the generic information theoretic problem of secret key agreement with a compound source.

This paper describes the use of physical unclonable functions (PUFs) in low-cost authentication and key generation applications. First, it motivates the use of PUFs versus conventional secure nonvolatile memories and defines the two primary PUF types: “strong PUFs” and “weak PUFs.” It describes strong PUF implementations and their use for low-cost authentication. After this description, the paper covers both attacks and protocols to address errors. Next, the paper covers weak PUF implementations and their use in key generation applications. It covers error-correction schemes such as pattern matching and index-based coding. Finally, this paper reviews several emerging concepts in PUF technologies such as public model PUFs and new PUF implementation technologies.