Delay‑Based Silicon Physical Unclonable Functions and Computational Fuzzy Extractors for Secure Key Generation

Introduction

The talk reviews 15 years of research on physical unclonable functions (PUFs) that generate device‑specific secrets from manufacturing variations. The goal is to replace costly, trusted‑key‑injection processes with secrets that are intrinsic to each integrated circuit.

Silicon PUFs and Process Variation

• No two chips are identical, even with the same layout, because of random variations during fabrication.
• These variations appear as differences in gate and wire delays, which can be measured and turned into a unique fingerprint – a silicon biometric.

Ring‑Oscillator (RO) PUFs

• The simplest delay‑based PUF uses pairs (or arrays) of ring oscillators.
• Each RO oscillates at a slightly different frequency; the frequency difference between two adjacent ROs encodes a bit.
• By comparing many pairs, a 128‑bit response can be generated per chip.
• Inter‑chip variation is close to the ideal 50 % Hamming distance, but intra‑chip noise (temperature, voltage) can flip up to ~16 bits on each regeneration.

The Need for Stable Keys

Because raw PUF responses are noisy, they cannot be used directly as cryptographic keys. A fuzzy extractor converts a noisy biometric source into a stable, uniformly random secret while publishing helper data that assists reconstruction.

Information‑Theoretic Fuzzy Extractors

• Consist of a Gen algorithm (produces helper data B from the noisy source E and a random secret S) and a Rep algorithm (reconstructs S from a new noisy measurement E' and B).
• Public helper data leaks information about E and S; the remaining entropy is |S| − |B|.
• As the error rate rises, the size of B must increase, reducing the usable secret length and creating a delicate trade‑off.

Computational Fuzzy Extractors via LPN

The speaker proposes a computational approach whose security relies on the hardness of the Learning Parity with Noise (LPN) problem.

• LPN formulation: given many equations b_i = a_i·s ⊕ e_i, where a_i are known n‑bit vectors, s is the secret, and e_i are random noise bits, recovering s is computationally hard.
• In the PUF context:
• e_i are the noisy comparison results from RO pairs.
• a_i can be hard‑coded on the chip.
• b_i become the public helper data.
• During Gen, a fresh random secret s is chosen, the chip computes b_i = a_i·s ⊕ e_i, and stores b_i as helper data.
• During Rep, the chip measures a new noisy vector e'_i. Because some e'_i differ from the original e_i, we cannot directly solve for s.

Selecting Stable Bits

• The magnitude of the RO frequency difference (the counter difference c_i) indicates stability: large c_i values are unlikely to flip under environmental changes.
• By sorting the c_i values and selecting the n largest ones, we obtain n equations whose noise bits are highly reliable (i.e., e'_i = e_i with high probability).
• With these reliable equations, the system becomes noise‑free and s can be recovered efficiently via Gaussian elimination.
• The parameter m = k·n (total equations) can be increased to tolerate higher error rates; k does not affect LPN security because the adversary never sees the noise bits.

Security Considerations

• The adversary knows the public helper data b_i and the matrix A, but not the noise bits e_i nor the stable subset chosen during reconstruction.
• Solving LPN without the noise bits remains computationally infeasible, providing a strong security foundation.
• The scheme avoids the entropy loss inherent in information‑theoretic fuzzy extractors.

Practical Deployments

• Variants of this computational fuzzy extractor have been implemented in SRAM‑PUFs, RO‑PUFs, and other silicon PUFs.
• They are used to derive secret keys in FPGAs, cryptographic processors, and other secure hardware products.

Summary of Advantages

• Eliminates the need for a trusted key‑injection authority.
• Generates device‑unique secrets from intrinsic manufacturing randomness.
• Provides stable keys despite environmental noise through selective equation use.
• Relies on well‑studied LPN hardness, offering strong computational security.

Silicon PUFs can turn unavoidable manufacturing variations into reliable, device‑specific cryptographic keys, and by leveraging computational fuzzy extractors based on the LPN problem, we obtain stable secrets without the entropy loss of traditional information‑theoretic methods, enabling practical, secure key generation for billions of devices.