A bunch of silicon Physical Unclonable Functions (PUFs) designs rely on variations of the propagation delay (due to process variation) of signals in different path. In many cases, a challenge selects the paths (e.g. using a muxer) to be compared and the response bit(s) compare the two paths (e.g. which signal arrived first or the number of oscillations in ring oscillators).
For example, here is a conventional design using ring oscillators [1]:
Given $N$ oscillators, there are $N(N-1)/2$ distinct pairs of oscillators. The paper explains:
However, the entropy of this circuit, which corresponds to the number of independent bits that can begenerated from the circuit, is clearly less than $N(N−1)/2$ because the bits obtained from pair-wise comparisons are correlated. For example, if oscillator A is faster than oscillator B, the comparison will yield a 1. If B is in turn faster than C, the comparison will yield a 1. It is clear that when A is compared with C that the comparison will yield a 1—these bits are correlated. [1]
Since correlated answers are unwanted, the paper goes on:
Fortunately, it is possible to derive the maximum entropy of this circuit assuming pair-wise comparisons [...] There are $N!$ different orderings of ring oscillators based on their frequencies. If the orderings are equally likely, the entropy will be $log_2(N!)$ bits. For example, 35 oscillators can produce 133 bits.
However, some other designs use a different approach that splits oscillators into two sets/blocks/groups [2,3]:
[3] says this about the impact on correlations:
One very important goal of this system is separating the Transcient Effect Ring Oscillatoires (TERO) cells into two blocks because of security. Indeed, without this separation, first order dependencies appear inside generated signatures depending on which cells contribute to the response.
I understand that having two sets prevents direct correlations such as if $A_{freq} > B_{freq}$ and $B_{freq} > C_{freq}$ then $A_{freq} > C_{freq}$ (two elements of ${A, B, C}$ needs to be on the same set and thus cannot be compared). However, it looks like a bad solution as it does not prevent indirect correlations and it reduces the max entropy for $N$ oscillators.
What is the impact of using two sets on the correlations? Can we quantify it? I think it boils down to computing the entropy of the circuit with two sets of $N/2$ elements—which I don't know how to do.
