pith. sign in

arxiv: 1907.05494 · v1 · pith:KUJFNJNPnew · submitted 2019-07-11 · 💻 cs.IT · math.IT

Entropy Estimation of Physically Unclonable Functions via Chow Parameters

Alexander Schaub , Olivier Rioul , Joseph , Joseph J. Boutros This is my paper

Pith reviewed 2026-05-24 22:32 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords physically unclonable functionsentropy estimationChow parametersBoolean threshold functionsRényi entropydelay elementsShannon entropy
0
0 comments X

The pith

Delay-based PUFs have Shannon entropy close to the maximum, which grows quadratically with the number of elements.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper estimates probability distributions for physically unclonable functions built from n delay elements, a task previously limited to n=7 because of exponential complexity. By connecting these PUFs to Boolean threshold functions and using their Chow parameter vectors, distributions become computable up to n=10. The resulting Shannon entropy stays close to the maximum possible entropy. This maximum itself scales quadratically in n, which directly informs how much randomness is available for cryptographic uses as the circuit grows.

Core claim

Linking PUF output distributions to the Chow parameter representation of Boolean threshold functions allows probability estimates for all 2^n challenges up to n=10. The computed Shannon entropy remains close to the max-entropy, which the paper shows is asymptotically quadratic in n.

What carries the argument

Chow parameter representation of Boolean threshold functions, used to estimate the probability distribution over PUF responses.

If this is right

  • Entropy assessment becomes feasible for PUFs with twice as many delay elements as before.
  • Rényi entropies of all orders can be tracked to confirm closeness to the maximum.
  • Security margins in authentication and key-generation protocols can be recalculated with the new scaling.
  • The quadratic growth rate gives a concrete rule for how much larger a PUF must be to gain a given amount of entropy.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same Chow-parameter technique could be tested on other PUF families whose challenge-response maps are close to threshold functions.
  • If the quadratic scaling holds, designers obtain a simple size-versus-entropy formula without needing full enumeration.
  • The reduction in computational cost from 2^{2^n} to a feasible regime for n=10 opens the door to Monte-Carlo validation on fabricated chips.

Load-bearing premise

The probability distribution of PUFs composed of n delay elements can be accurately estimated via the Chow parameter representation of the corresponding Boolean threshold functions.

What would settle it

Exact enumeration of all response probabilities for an n=8 delay PUF and direct comparison against the Chow-parameter estimate.

Figures

Figures reproduced from arXiv: 1907.05494 by Alexander Schaub, Joseph, Joseph J. Boutros, Olivier Rioul.

Figure 1
Figure 1. Figure 1: Entropy estimates for n ≤ 10. The upper bound of the min-entropy (dashed line) is taken from [25]. VI. CONCLUSIONS AND PERSPECTIVES While it had been previously shown [6] that the entropy of the loop-PUF of n elements could exceed n, the exact values were only known for very small values of n. Making the link with BTF theory using Chow parameters, we have extended these results to provide accurate approxim… view at source ↗
read the original abstract

A physically unclonable function (PUF) is an electronic circuit that produces an intrinsic identifier in response to a challenge. These identifiers depend on uncontrollable variations of the manufacturing process, which make them hard to predict or to replicate. Various security protocols leverage on such intrinsic randomness for authentification, cryptographic key generation, anti-counterfeiting, etc. Evaluating the entropy of PUFs (for all possible challenges) allows one to assess the security properties of such protocols. In this paper, we estimate the probability distribution of certain kinds of PUFs composed of $n$ delay elements. This is used to evaluate relevant R\'enyi entropies and determine how they increase with $n$. Such a problem was known to have extremely high complexity (in the order of $2^{2^n}$) and previous entropy estimations were carried out up to $n=7$. Making the link with the theory of Boolean threshold functions, we leverage on the representation by Chow parameters to estimate probability distributions up to $n=10$. The resulting Shannon entropy of the PUF is close to the max-entropy, which is asymptotically quadratic in $n$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims that modeling PUFs composed of n delay elements as Boolean threshold functions allows their response probability distributions to be estimated via Chow parameters, extending prior entropy calculations from n=7 to n=10. It reports that the resulting Shannon entropy is close to the maximum entropy, which grows asymptotically as a quadratic function of n.

Significance. If the modeling step is accurate, the work would meaningfully extend the feasible range for PUF entropy estimation, aiding security analysis of protocols that rely on PUF randomness. The connection to Chow parameters of threshold functions represents a potentially useful reduction of a 2^{2^n}-complexity problem.

major comments (2)
  1. [Abstract and modeling section] The central modeling step equating delay-element PUF response probabilities to the distribution over threshold functions (recoverable from Chow parameters) is load-bearing for all n>7 claims, yet the manuscript provides no explicit validation or error analysis against the known n=7 results referenced in the abstract.
  2. [Entropy results and asymptotic claim] The assertion that Shannon entropy remains close to max-entropy (and that the latter is asymptotically quadratic in n) rests on the Chow-parameter estimates for n=8–10; without reported bounds on how faithfully the Chow representation recovers the exact PUF probability measure, these numerical conclusions cannot be assessed for reliability.
minor comments (2)
  1. Notation for the specific Rényi entropies computed should be introduced earlier and used consistently when reporting numerical values.
  2. [Introduction] The abstract mentions an external link to Boolean threshold function theory; a self-contained one-sentence definition of Chow parameters in the introduction would improve accessibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed report and the opportunity to clarify the modeling assumptions and numerical claims in the manuscript. We respond to each major comment below.

read point-by-point responses

  1. Referee: [Abstract and modeling section] The central modeling step equating delay-element PUF response probabilities to the distribution over threshold functions (recoverable from Chow parameters) is load-bearing for all n>7 claims, yet the manuscript provides no explicit validation or error analysis against the known n=7 results referenced in the abstract.

    Authors: The referee correctly notes the absence of an explicit side-by-side validation. The equivalence between n-delay PUFs and threshold functions follows from the standard linear delay model used in the PUF literature; the Chow-parameter representation is then applied exactly to that model. Nevertheless, to strengthen the presentation we will add a dedicated subsection that recomputes the distributions for all n ≤ 7, compares the resulting Shannon and Rényi entropies against the values cited in the abstract, and reports the observed numerical discrepancy (if any) attributable to floating-point precision in the Chow-parameter recovery. revision: yes

  2. Referee: [Entropy results and asymptotic claim] The assertion that Shannon entropy remains close to max-entropy (and that the latter is asymptotically quadratic in n) rests on the Chow-parameter estimates for n=8–10; without reported bounds on how faithfully the Chow representation recovers the exact PUF probability measure, these numerical conclusions cannot be assessed for reliability.

    Authors: Within the threshold-function model the Chow parameters recover the exact Boolean function and therefore the exact probability measure (subject only to the finite-precision arithmetic used to solve the linear system). The quadratic growth of the max-entropy follows directly from the known asymptotic cardinality of the set of n-variable threshold functions. We will insert a short paragraph making this exactness-under-the-model explicit and will report the condition-number or residual norms obtained when solving for the Chow parameters at n = 8, 9, 10. If the referee is concerned with deviation between the idealized threshold model and fabricated silicon, that modeling gap is acknowledged as a standing limitation of the entire line of work and is outside the scope of the computational contribution. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external Boolean threshold function theory

full rationale

The paper's central step maps PUFs to Boolean threshold functions and applies Chow-parameter representation to estimate distributions up to n=10. This is presented as leveraging an established external theory rather than a self-citation chain, fitted parameter renamed as prediction, or self-definitional reduction. No equations or claims in the provided text reduce the entropy result to its own inputs by construction; the asymptotic quadratic claim follows from the estimated distributions without circular redefinition. The derivation remains self-contained against the cited mathematical framework.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the modeling assumption that Chow parameters of Boolean threshold functions capture the PUF output distribution; no free parameters or invented entities are mentioned.

axioms (1)
  • domain assumption The probability distribution of PUFs composed of n delay elements can be estimated via the Chow parameter representation of the corresponding Boolean threshold functions.
    The abstract states that the link with Boolean threshold functions is used to leverage the Chow parameter representation.

pith-pipeline@v0.9.0 · 5734 in / 1185 out tokens · 31177 ms · 2026-05-24T22:32:48.971266+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Power-up SRAM state as an identifying fingerprint and source of true random numbers,

    D. E. Holcomb, W. P. Burleson, and K. Fu, “Power-up SRAM state as an identifying fingerprint and source of true random numbers,” IEEE Transactions on Computers, vol. 58, no. 9, pp. 1198–1210, 2009

    work page 2009

  2. [2]

    Physical unclonable functions for device authentication and secret key generation,

    G. E. Suh and S. Devadas, “Physical unclonable functions for device authentication and secret key generation,” in 44th ACM/IEEE Design Automation Conference, 2007, pp. 9–14

    work page 2007

  3. [3]

    An easy-to-design PUF based on a single oscillator: The Loop PUF,

    Z. Cherif, J.-L. Danger, S. Guilley, and L. Bossuet, “An easy-to-design PUF based on a single oscillator: The Loop PUF,” in 15th Euromicro Conference on Digital System Design (DSD) . IEEE, 2012, pp. 156– 162

    work page 2012

  4. [4]

    Recombination of physical unclonable functions,

    M.-D. M. Yu and S. Devadas, “Recombination of physical unclonable functions,” in 35th Annual GOMACTech Conference , 2010

    work page 2010

  5. [5]

    Delay-based circuit authentication and applications,

    B. Gassend, D. Clarke, M. Van Dijk, and S. Devadas, “Delay-based circuit authentication and applications,” in Proceedings of the 2003 ACM Symposium on Applied Computing . ACM, 2003, pp. 294–301

    work page 2003

  6. [6]

    On the entropy of physically unclonable functions,

    O. Rioul, P. Sol ´e, S. Guilley, and J.-L. Danger, “On the entropy of physically unclonable functions,” in IEEE International Symposium on Information Theory (ISIT) , July 2016, pp. 2928–2932

    work page 2016

  7. [7]

    Statistical timing analysis considering spatial correlations using a single PERT-like traversal,

    H. Chang and S. S. Sapatnekar, “Statistical timing analysis considering spatial correlations using a single PERT-like traversal,” in Proceedings of the 2003 IEEE/ACM International Conference on Computer-Aided Design. IEEE Computer Society, 2003, p. 621

    work page 2003

  8. [8]

    On measures of entropy and information,

    A. R ´enyi, “On measures of entropy and information,” in Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability. Berkeley: University of California Press, 1961

    work page 1961

  9. [9]

    Machine learning resistant strong PUF: Possible or a pipe dream?

    A. Vijayakumar, V . C. Patil, C. B. Prado, and S. Kundu, “Machine learning resistant strong PUF: Possible or a pipe dream?” in IEEE International Hardware Oriented Security and Trust , 2016, pp. 19–24

    work page 2016

  10. [10]

    Some theorems useful in threshold logic for enumerating boolean functions

    E. Goto and H. Takahasi, “Some theorems useful in threshold logic for enumerating boolean functions.” in IFIP Congress, 1962, pp. 747–752

    work page 1962

  11. [11]

    Single stage threshold logic,

    R. O. Winder, “Single stage threshold logic,” in Symposium on Switching Circuit Theory and Logical Design . IEEE, 1961, pp. 321–332

    work page 1961

  12. [12]

    Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition,

    T. M. Cover, “Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition,”IEEE Transactions on Electronic Computers , no. 3, pp. 326–334, 1965

    work page 1965

  13. [13]

    On the characterization of threshold functions,

    C.-K. Chow, “On the characterization of threshold functions,” in Symposium on Switching Circuit Theory and Logical Design , 1961, pp. 34–38

    work page 1961

  14. [14]

    Hu, Threshold Logic

    S.-T. Hu, Threshold Logic. Univ of California Press, 1965

    work page 1965

  15. [15]

    Bounds on the number of threshold functions,

    D. R. Smith, “Bounds on the number of threshold functions,” IEEE Transactions on Electronic Computers , no. 3, pp. 368–369, June 1966

    work page 1966

  16. [16]

    A lower bound of the number of threshold functions,

    S. Yajima and T. Ibaraki, “A lower bound of the number of threshold functions,” IEEE Transactions on Electronic Computers , vol. EC-14, no. 6, pp. 926–929, Dec 1965

    work page 1965

  17. [17]

    Methods of geometry and probabilistic combinatorics in threshold logic,

    Y . A. Zuev, “Methods of geometry and probabilistic combinatorics in threshold logic,” Discrete Mathematics and Applications , vol. 2, no. 4, pp. 427–438, 1992

    work page 1992

  18. [18]

    Linear separability of the vertices of an n-dimensional hypercube,

    N. Gruzling, “Linear separability of the vertices of an n-dimensional hypercube,” Master’s thesis, University of Northern British Columbia, 2008

    work page 2008

  19. [19]

    T. W. Hungerford, Algebra, ser. Graduate Texts in Mathematics. New York: Springer-Verlag, 1980, vol. 73

    work page 1980

  20. [20]

    Challenge codes for physically unclonable functions with Gaussian delays: A maximum entropy problem,

    A. Schaub, O. Rioul, J. J. Boutros, J.-L. Danger, and S. Guilley, “Challenge codes for physically unclonable functions with Gaussian delays: A maximum entropy problem,” Latin American Week on Coding and Information, UNICAMP-Campinas, Brazil , pp. 22–27, 2018

    work page 2018

  21. [21]

    The probable error of a mean,

    Student, “The probable error of a mean,” Biometrika, pp. 1–25, 1908

    work page 1908

  22. [22]

    Estimation of entropy and mutual information,

    L. Paninski, “Estimation of entropy and mutual information,” Neural computation, vol. 15, no. 6, pp. 1191–1253, 2003

    work page 2003

  23. [23]

    Entropy and inference, revisited,

    I. Nemenman, F. Shafee, and W. Bialek, “Entropy and inference, revisited,” in Advances in Neural Information Processing Systems , 2002, pp. 471–478

    work page 2002

  24. [24]

    The complexity of estimating R ´enyi entropy,

    J. Acharya, A. Orlitsky, A. T. Suresh, and H. Tyagi, “The complexity of estimating R ´enyi entropy,” in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms . SIAM, 2014, pp. 1855–1869

    work page 2014

  25. [25]

    Upper bounds on the min- entropy of RO sum, arbiter, feed-forward arbiter, and S-ArbRO PUFs,

    J. Delvaux, D. Gu, and I. Verbauwhede, “Upper bounds on the min- entropy of RO sum, arbiter, feed-forward arbiter, and S-ArbRO PUFs,” in Hardware-Oriented Security and Trust (AsianHOST), IEEE Asian . IEEE, 2016, pp. 1–6

    work page 2016

  26. [26]

    Probable inference, the law of succession, and statistical inference,

    E. B. Wilson, “Probable inference, the law of succession, and statistical inference,” Journal of the American Statistical Association , vol. 22, no. 158, pp. 209–212, 1927

    work page 1927