Abstract
Physically Unclonable Functions (PUFs) are critical for hardware security, yet they often suffer from reliability issues due to environmental noise and predictability concerns. This paper introduces Multiply Constant-Weight Codes (MCWCs) to address these challenges in Loop PUFs. By ensuring control words have a constant weight across multiple blocks, MCWCs balance baseline delays and maximize Hamming distance between challenges. We provide theoretical bounds, construction methods, and asymptotic analyses, demonstrating that the structural constraints of MCWCs do not significantly degrade information rates compared to standard constant-weight codes.
Introduction
Physically Unclonable Functions (PUFs) exploit microscopic manufacturing variations in silicon to create unique, unclonable cryptographic signatures for devices such as RFIDs and smart cards. A common implementation is the "Loop PUF," which operates by measuring the delay differences in oscillating circuits controlled by binary challenge words.
Despite their utility, Loop PUFs face two major challenges:
- Unpredictability: If an attacker knows the control words, they might predict the delay if the words activate an unbalanced number of delay elements.
- Reliability: Physical delay differences are minute. Environmental noise, such as temperature or voltage fluctuations, can flip the measured response, leading to authentication failure.
To mitigate these issues, engineers require a specific set of control words—a code—where every word activates the exact same number of delay elements per circuit cluster. This ensures the baseline delay is identical, leaving only the manufacturing variations to dictate the response.
Methodology: Multiply Constant-Weight Codes
The authors formalize this requirement through Multiply Constant-Weight Codes (MCWCs). An MCWC is a binary code of length $mn$ partitioned into $m$ equal blocks of length $n$, where each block has a constant Hamming weight $w$. This structure generalizes standard constant-weight codes ($m=1$) and doubly constant-weight codes ($m=2$).
The physical layout of FPGAs, which group logic into clusters, maps directly to the mathematical structure of MCWCs. As shown in Figure 2, the delay chains are organized into $n$ clusters, each containing $m$ delay elements.
By maintaining a constant weight per cluster, predictable routing delays are canceled out, ensuring that only the unclonable manufacturing variations determine the PUF's response. Furthermore, maximizing the Hamming distance between code words directly correlates to increased physical delay differences, which enhances the signal-to-noise ratio and overall reliability.
Theoretical Framework and Bounds
To understand the theoretical limits of MCWCs, the authors developed several analytical tools:
- Lower Bounds (Constructions): Valid MCWCs were constructed using concatenation (combining an outer $q$-ary code with an inner constant-weight code), pseudo-product codes, and generalizations of Zinoviev’s method.
- Upper Bounds: The authors extended classical Johnson bounds to the multiply constant-weight domain using recursive formulas.
- Asymptotic Analysis: Using graph-theoretic methods, they studied code rates as parameters scale to infinity.
Key Results
The research yielded several significant findings:
- Tightness of Bounds: The generalized Johnson bounds for MCWCs were proven to be asymptotically tight up to a constant factor for fixed $m$, $w$, and distance $d$.
- Rate Equivalency: A surprising result is that the asymptotic rate of an MCWC (with $m$ blocks of length $n$ and weight $w$) is identical to the asymptotic rate of a standard constant-weight code of length $mn$ and weight $mw$. The strict structural requirements of MCWCs do not asymptotically degrade the code's information rate.
- Explicit Lower Bounds: For the specific case where the weight is half the block length ($w = n/2$), explicit lower bounds for the asymptotic rate were derived using geometric Goppa codes and Varshamov-Gilbert bounds.
Conclusion
MCWCs provide a robust theoretical and practical framework for enhancing the security and reliability of Loop PUFs. While the exact value of the general asymptotic rate remains an open question in coding theory, this work establishes that MCWCs are a viable and efficient solution for hardware authentication. Future work includes tabulating exact estimates for real-world parameter values and exploring applications in other fields, such as power line communications.
Summary updated