# On the Response Entropy of APUFs

Vincent Dumoulin, Wenjing Rao, and Natasha Devroye
Department of Electrical and Computer Engineering
University of Illinois Chicago
E-mail: vdumou2, wenjing, devroye @uic.edu

###### Abstract

A Physically Unclonable Function (PUF) is a hardware security primitive used
for authentication and key generation. It takes an input bit-vector challenge
and produces a single-bit response, resulting in a challenge-response pair
(CRP). The truth table of all challenge-response pairs of each manufactured
PUF should look different due to inherent manufacturing randomness, forming a
digital fingerprint. A PUF’s entropy (the entropy of all the responses, taken
over the manufacturing randomness and uniformly selected challenges) has been
studied before and is a challenging problem. Here we explore a related notion
– the response entropy, which is the entropy of an arbitrary response given
knowledge of one (and later two) other responses. This allows us to explore
how knowledge of some CRP(s) impacts the ability to guess another response.

The Arbiter PUF (APUF) is a well-known PUF architecture based on accumulated
delay differences between two paths. In this paper, we obtain in closed form
the probability mass function of any arbitrary response given knowledge of one
or two other arbitrary CRPs for the APUF architecture. This allows us to
obtain the conditional response entropy and then to define and obtain the size
of the entropy bins (challenge sets with the same conditional response
entropy) given knowledge of one or two CRPs. All of these results depend on
the probability that two different challenge vectors yield the same response,
termed the response similarity of those challenges. We obtain an explicit
closed form expression for this. This probability depends on the statistical
correlations induced by the PUF architecture together with the specific known
and to-be-guessed challenges. As a by-product, we also obtain the optimal
(minimizing probability of error) predictor of an unknown challenge given
access to one (or two) challenges and the associated predictability.

###### Index Terms:

Arbiter PUF, CRP correlation, entropy bins, expected entropy, response
entropy.

##  I Introduction

Physically Unclonable Functions (PUFs) are circuits that can be integrated
into chip designs to provide a low-cost digital “fingerprint”. They show
promise as hardware security primitives for Internet of Things (IoT) devices
that need low-power cryptographic frameworks for authenticated communication.
PUF designs rely on randomness derived from many types of process variations,
such as gate/wiring delays, designed to be the same across all chips, but
inevitably differing due to random defects that occur during manufacturing
[1],[2]. This results in an uncontrollable, unique function for each device,
which is physically unclonable. With PUFs, the “fingerprint” of a device is
not some stored bit-stream, but rather extracted from its unique input /
output function, that may be “challenged” with an input vector ${\bf
c}\in\\{0,1\\}^{n}$, which interacts with the random elements of a PUF
instance to produce a “response”, $R_{\bf c}\in\\{\pm 1\\}$. The pair $({\bf
c},R_{\bf c})$ is called a challenge-response pair (CRP). A subset of CRPs,
usually randomly selected, can be used to uniquely identify or authenticate a
device. There are two classes of PUFs. In weak PUFs the size of the truth
table with respect to the number of random elements is small and hence must be
kept secret as it is easily obtained via exhaustive evaluation; they are
mostly used for key-generation in cryptography. Strong PUFs offer a huge
number of CRPs, usually exponential in the number of physical random elements,
and are primarily used in device authentication [1]. How good a PUF is is
often measured by their response bias, the uniqueness, and the entropy of the
PUFs, among other statistical metrics [3, 4, 5]. The arbiter PUF (APUF), a
well known strong PUF architecture, is the focus of this paper, which is
formally introduced in Section II.

A basic authentication framework for the APUF is as follows. During an
enrollment phase, which takes place in a secure environment, a large set of
random challenges are passed to the APUFs input and the outputs are recorded
to create CRPs. This large set of CRPs (or a model of the PUF obtained via
Machine Learning from this set) is then stored on the authentication server.
During the authentication phase the APUF is no longer guaranteed to be in a
secure environment. In order to authenticate a particular APUF according to
various protocols [6, 7, 8, 9], a small set of challenges are used to query
the APUF by the server, so as to verify the APUF’s identity.

CRP correlation: The PUF community has nearly always assumed the use of random
CRP sets either in protocols or analysis of PUF metrics, or to build multi-bit
responses. It has not deeply studied how challenges may be correlated, how
exposing one challenge (e.g. to an attacker) may impact how predictable
another challenge becomes.

We focus on presenting rigorous mathematical tools to understand how much
knowledge of one or two challenges reveals about the remaining challenges in
an arbiter PUF. We propose to measure this using the response entropy, and the
conditional response entropy, or entropy of a response to a challenge given
(in the conditional setting) knowledge of one or two other CRPs. This turns
out to be a function of how statistically correlated the CRPs of an APUF are.
We explicitly derive the response similarity $P[R_{\bf c^{\prime}}=R_{\bf
c}]$, which allows us to characterize the conditional response entropy and the
associated "entropy bins" which contain all the challenges who have the same
conditional entropy given knowledge of one (or two) CRPs.

Prior observations about the PUF CRP correlations: Our method is based on the
analytical derivation of the probability that the responses to different
challenges are the same. This probability has been observed experimentally and
numerically in previous work. In particular, for APUFs, figures such as [10,
Figure 6, simulated], [11, Figure 12], comments such as those in [12], and
partial analytical derivations (non-closed form integrals) as in [13] focus on
the how likely the responses to two challenges differing in one bit are to be
the same, and plot the probability that the response changes as a function of
the bit flip position (or two consecutive bit positions [13]). However, to the
best of our knowledge, this bit flip probability as an explicit closed-form
function of the challenges and responses has never been derived and is one of
the contributions here. We furthermore provide closed-form expressions for any
two arbitrarily correlated challenges ${\bf c}$ and ${\bf c^{\prime}}$ and not
only ones that change in one or two bit positions. We also propose explicit
algorithms enumerating all challenges with a desired response similarity to a
given one or two challenges.

Prior observations about the PUF entropy: In order for PUFs to be able to
uniquely identify many devices, one hopes that the entropy of the PUFs
manufactured in a particular architecture is large. This PUF entropy, or the
entropy of all the responses (to all challenges) or a particular architecture
has been studied before and is usually experimentally obtained, as it is
difficult to analytically characterize.

In [14] they asked the question of how to select challenges to maximize the
entropy (of the corresponding responses) of loop PUF outputs. They used an
analytical model for the loop PUF that assumes Gaussian delay elements as
justified in [15], and showed that $n$ bits of entropy (equated with the
randomness or hardness of predicting a response given no other responses) may
be obtained from $n$ challenges if and only if the challenges constitute a
Hadamard code. They do not touch on the probability that two challenges result
in the same response as a function of the challenges. Later work such as [16]
focuses on estimating the probability distribution of certain kinds of PUFs
composed of delay elements and finds the resulting Shannon entropy of the PUF
is close to the max-entropy, which is asymptotically quadratic in the number
of stages $n$. [17] presents a new approach for determining the min-entropy of
a PUF based on convolving histograms. [18] analyzes the entropy of FPGA Lookup
Table-based PUFs. None of these works focus on conditional response entropy
estimation given knowledge of some challenges, but rather on estimating the
overall PUF entropy. There is also work on the statistical analysis of PUFs
[19], and characterizing the entropy of “strong” PUFs [20, 19] but these have
been experimental and focus on the inherent qualities (bias, uniqueness and
reliability) of PUFs, and do not focus on how challenges correlate the PUF
responses.

Contributions: for APUF, we define and obtain:

$\bullet$ The _response similarity_ between any pair of challenges ${\bf c}$
and ${\bf c^{\prime}}$, $P[R_{{\bf c}^{\prime}}=R_{\bf c}]$, often denoted by
$p$. This response similarity is expressed as a function of the similarity
factor, a function of the two challenges, and denoted as $s$. To the best of
our knowledge, this is the first time that a closed form, analytical
characterization of the probability that two or three challenges will produce
the same response for an APUF. This underpins the Strict Avalanche Criterion
(SAC) property for APUFs and yields an alternative to the Monte Carlo
simulations often used in papers, e.g. [21] to simulate the probability that
the response flips if for example one challenge input bit flips. In fact, our
work provides a complete generalization of this single bit flip probability
(where only one bit is flipped with respect to a base or anchor challenge) to
the probability of flipping any number of bits with respect to an anchor
challenge.

$\bullet$ The _similarity bins_ of any anchor challenge ${\bf c}$,
$B_{s}(p,{\bf c})$: for any given challenge (anchor) and a given response
similarity $p$, we develop an efficient algorithm to find the set of all
challenges that have the same given response similarity with respect to the
anchor.

$\bullet$ The _response entropy_ and the conditional response entropy of a
challenge, conditioned on knowing one or two CRP(s). From this we are able to
compute the conditional minimum response entropy and the conditional Shannon
response entropy using the closed form expression for the probability that two
or three challenges will produce the same response.

$\bullet$ The _entropy bins_ of any anchor challenge or pair of challenges
${\bf c}$, $B_{H}(h,{\bf c})$: these are sets of challenges which all have the
same response conditional entropy given ${\bf c}$. We are able to calculate
the size of each entropy bin exactly. Such sets (entropy bins) can then be
used to compute the expected conditional entropy of a response.

$\bullet$ The _expected conditional entropy_ : knowing the size of each
entropy bin allows us to calculate the expected conditional response entropy
(not the conditional PUF entropy, which is more challenging [16]) when knowing
one or two challenges.

$\bullet$ Our results yield an immediate application: finding the optimal
predictor (minimizing the probability of error) of the response to one unknown
challenge ${\bf c^{\prime}}$ given the response to one (and later, extended to
two) known challenge(s).

##  II APUF architecture and notation

The APUF may be viewed as a Boolean function taking as input a challenge
vector ${\bf c}:=(c_{1},c_{2},\cdots c_{n})\in\\{0,1\\}^{n}$ and outputting a
response $R_{\bf c}\in\\{\pm 1\\}$. This response corresponds to the output of
a race resolution element, latch, or arbiter, which detects which of two
racing signals arrives first. The two signals traverse $n$ multiplexers in
series, and in the $i$-th stage, traverse the “parallel” paths ($t_{i},u_{i}$)
if the challenge bit $c_{i}=0$, else traverse the “crossed” paths
($r_{i},s_{i}$) if the challenge bit $c_{i}=1$. The response then is $-1$ if
the upper entrance to the arbiter arrives earlier than the lower, and is $+1$
otherwise - this is modeled by whether the final accumulated delay difference
$\Delta_{n}$ is positive or negative at the entrances of the arbiter.

In the interest of modeling this behavior analytically, in stage $i\in[1,n]$
of the APUF the delays of the four possible paths taken (parallel or crossed)
are modeled as four random delay elements, $t_{i},u_{i},r_{i}$ and $s_{i}$,
which are all i.i.d. normal random variables with mean $\mu$ and variance
$\sigma^{2}$, denoted as $\sim{\cal N}(\mu,\sigma^{2})$. they are always
selected in fixed pairs, and since the response depends only on which signal
arrives first, so on the relative delay difference between the two racing
paths. The assumption that all have the same mean corresponds to the fact that
the manufacturing process aims to produce identical MUXes, but due to process
variation, they end up similar but not identical, with a small spread around
the mean. Gaussians are good models for the inevitable manufacturing
randomness, as justified in [22, 15]. Truncated Gaussians may be more
suitable, but are less analytically tractable and not much better for the
small variance of the manufacturing delay.

The challenge bit $c_{i}\in\\{0,1\\}$ determines two factors: 1) which path
pair ($t_{i},u_{i}$ in parallel, or $r_{i},s_{i}$ crossing) at stage $i$ is
chosen, and 2) the sign of the accumulated delay difference from all the
previous stages before reaching $i$. The response $R_{\bf c}$ is expressed as
the sign of the accumulated delay difference at the final stage $\Delta_{n}$.
In general, the accumulated delay $\Delta_{i}$ is recursively defined
involving the challenge ${\bf c}$, the delay elements
$r_{i},s_{i},t_{i},u_{i}$ of the current stage, and the accumulated delay
difference at stage $i-1$, $\Delta_{i-1}$:

$\displaystyle R_{\bf c}=\text{sign}(\Delta_{n})\in\\{\pm 1\\},$ (1)

where $\Delta_{n}$ is computed recursively for $i\in[1,n]$, as

$\displaystyle\Delta_{i}=\left\\{\begin{array}[]{ll}+\Delta_{i-1}+t_{i}-u_{i},&\text{when
}c_{i}=0\\\ -\Delta_{i-1}+s_{i}-r_{i},&\text{when
}c_{i}=1\end{array}\right.,\;\;\Delta_{0}=0.$ (4)

The recursive formula is not easy for modeling and analysis, thus APUFs are
frequently modeled by transforming the $n$-bit input vector ${\bf c}$ into
another $n+1$ bit vector $\Phi$, the $4n$ random variables into a vector ${\bf
w}$ of size $n+1$. The response is then expressed as a linear threshold
function of ${\bf\Phi},{\bf w}$, in a non-recursive fashion as shown in [23]:

$\displaystyle R_{\bf\Phi}=\text{sign}({\bf\Phi}\cdot{\bf
w})=\text{sign}\left(\sum_{i=1}^{n+1}\phi_{i}w_{i}\right)\in\\{\pm 1\\},$ (5)

where ${{\bf\Phi}}:=(\phi_{1},\phi_{2},\cdots\phi_{n+1})\in\\{\pm 1\\}^{n+1}$
is a vector depending solely on the challenge vector ${\bf c}$, and ${\bf
w}:=(w_{1},w_{2},\cdots w_{n+1})\in\mathbb{R}^{n+1}$ is a vector depending
only on the delay random variables, and $\cdot$ denotes the inner product:

$\displaystyle\phi_{i}=\left\\{\begin{array}[]{ll}(-1)^{\sum_{i}^{n}c_{k}},&1\leq
i\leq n,\\\ +1&i=n+1\end{array}\right.$ (8) $\displaystyle
w_{i}=\left\\{\begin{array}[]{ll}(t_{1}-u_{1})-(s_{1}-r_{1}),&i=1\\\ \\\
(t_{i-1}-u_{i-1})+(s_{i-1}-r_{i-1})\\\ +(t_{i}-u_{i})-(s_{i}-r_{i}),&2\leq
i\leq n,\\\ \\\ (t_{n}-u_{n})+(s_{n}-r_{n}),&i=n+1\\\ \end{array}\right.$ (15)

This representation eases the analysis as it separates the ${\bf\Phi}$
(dependent only on the challenge) from ${\bf w}$ (dependent only on the random
delay elements), and the output is now expressed as a linear threshold
function. ML attacks against APUFs often exploit this representation.

Figure 1: Illustration of the delay elements

This transformation renders the $w_{i}$’s Gaussian i.i.d., all with the same
variance except $w_{1}$ and $w_{n+1}$ (which have half the variance as the
others), as outlined in the following Lemma.

######  Lemma II.1.

For the arbiter PUF whose output is described by Eq. (5), and using the
transformation in Eq. (15), then

$\displaystyle w_{1}\sim{\cal N}(0,4\sigma^{2}),\;\;w_{i}\sim{\cal
N}(0,8\sigma^{2})$ (16) $\displaystyle\text{ for }2\leq i\leq
n,\;\;w_{n+1}\sim{\cal N}(0,4\sigma^{2}),$ (17)

and $w_{i},w_{j}$ are independent for $i\neq j$.

The transformation between the vectors ${\bf c}$ and ${\bf\Phi}$ is bijective.
For the rest of the paper we transform challenges ${\bf c},{\bf c^{\prime}}$
into ${\bf\Phi,\Phi^{\prime}}$, which turns the APUF response into a linear
threshold function, which is easier to deal with.

##  III Response similarity and entropy

Our technical contribution comes from the succinct derivation of the following
two notions, which are then (in the following subsection) used to calculate
the conditional response entropy given knowledge of another CRP.

The “response similarity” between ${\bf\Phi}$ and ${\bf\Phi^{\prime}}$,
$P[R_{{\bf\Phi}^{\prime}}=R_{\bf\Phi}]$, is the probability that they produce
the same response. The probability is taken over the random generation of the
delay elements, and NOT over the fixed challenges. The “similarity bins” of an
“anchor” challenge ${\bf\Phi}$ are sets of challenges with equal response
similarity to an anchor challenge.

The main theoretical results solve these two problems for an $n$-stage arbiter
PUF (with minor modifications to any other PUF that may be modeled as an
$n$-stage linear threshold function as long as the randomness in the stages
are independent and Gaussian distributed):

  * •

Problem 1: given challenge pair $({\bf\Phi},{\bf\Phi^{\prime}})$, derive their
response similarity $p=P[R_{\bf\Phi}=R_{\bf\Phi^{\prime}}]$.

  * •

Problem 2: given a CRP $({\bf\Phi},R_{{\bf\Phi}})$, optimally predict the
target response $R_{\bf\Phi^{\prime}}$ of another challenge
${\bf\Phi^{\prime}}$, and derive the prediction accuracy (i.e. find
$P[R_{\bf\Phi^{\prime}}|R_{\bf\Phi}]$)

  * •

Problem 3: given a challenge ${\bf\Phi}$ (an “anchor”), derive all the
challenges with the same response similarity $p$ to ${\bf\Phi}$,
$B_{s}(p,{\bf\Phi})$, or the same accuracy $B_{a}(p,{\bf\Phi})$ (and later,
the same entropy $B_{H}(p,{\bf\Phi})$).

Remark :  The predictor works for a particular PUF instance that is not
“abnormal” [24] i.e. there are no dominant or unusually large delay stages.

###  III-A Response similarity and accuracy

####  III-A1 Motivational example

Recall that
$R_{\bf\Phi}=\text{sign}\left(\sum_{i=1}^{n+1}\phi_{i}w_{i}\right)$ and
$R_{\bf\Phi^{\prime}}=\text{sign}\left(\sum_{i=1}^{n+1}\phi_{i}^{\prime}w_{i}\right)$,
where $\phi_{i}=(-1)^{\sum_{i}^{n}(c_{k})}$ and
$\phi_{i}^{\prime}=(-1)^{\sum_{i}^{n}(c_{k}^{\prime})}$, with
$\phi_{n+1}=\phi_{n+1}^{\prime}=1$ for all ${\bf c,c^{\prime}}$ from equations
(5) – (8). We now consider the following 3 challenges, among them the
likelihood of some pair resulting in the same response (over an “average”
PUF):

$\displaystyle{\bf c}=$ $\displaystyle\texttt{(00000)}\quad\leftrightarrow$
$\displaystyle\Phi=$ (+1,+1,+1,+1,+1,+1) $\displaystyle{\bf c^{\prime}}=$
$\displaystyle\texttt{(10000)}\quad\leftrightarrow$
$\displaystyle\Phi^{\prime}=$ (-1,+1,+1,+1,+1,+1) $\displaystyle{\bf
c^{\prime\prime}}=$ $\displaystyle\texttt{(00001)}\quad\leftrightarrow$
$\displaystyle\Phi^{\prime\prime\prime}=$ (-1,-1,-1,-1,-1,+1)

These challenges will lead to responses of the form (recalling that
$\phi_{n+1}=1$ always):

$\displaystyle R_{\bf\Phi}=$
$\displaystyle\text{sign}(+w_{1}+w_{2}+w_{3}+w_{4}+w_{5}+w_{6})$
$\displaystyle R_{\bf\Phi^{\prime}}=$
$\displaystyle\text{sign}(-w_{1}+w_{2}+w_{3}+w_{4}+w_{5}+w_{6})$
$\displaystyle R_{\bf\Phi^{\prime\prime}}=$
$\displaystyle\text{sign}(-w_{1}-w_{2}-w_{3}-w_{4}-w_{5}+w_{6})$

We can note the following: 1) ${\bf\Phi}$ and ${\bf\Phi^{\prime}}$ are most
likely to yield the same response because their corresponding $R_{\bf\Phi}$
and $R_{\bf\Phi^{\prime}}$ differ only in $w_{1}$; 2) ${\bf\Phi}$ and
${\bf\Phi^{\prime\prime}}$ are very likely to yield the opposite responses,
because they have all the $w_{i}$’s in opposite signs, except for $w_{6}$. All
of these observations can be confirmed by the following Theorem, where for the
pair $({\bf\Phi},{\bf\Phi^{\prime}})$ the similarity factor
$s=S({\bf\Phi},{\bf\Phi^{\prime}})$ is defined, and is a measure of how
similar ${\bf\Phi}$ and ${\bf\Phi^{\prime}}$ are.

####  III-A2 Main Theorem

This section’s main result is Theorem III.1, which shows the formal solution
to Problem 1.

All proofs of Lemmas may be found in the Appendix; the main Theorem proof is
shown in the text.

######  Theorem III.1 (Response similarity of APUFs.).

For an APUF with a pair of challenges ${\bf\Phi,\Phi^{\prime}}\in\\{\pm
1\\}^{n+1}$ their response similarity (i.e., the probability of
$R_{\bf\Phi}=R_{\bf\Phi^{\prime}}$) is

$\displaystyle
P[R_{\bf\Phi}=R_{{\bf\Phi^{\prime}}}]=\frac{1}{2}+\frac{1}{\pi}\left[\arcsin\left(\frac{2{S}({\bf\Phi,\Phi^{\prime}})}{n}-1\right)\right]$
(18)

where

$\displaystyle{S}({\bf\Phi,\Phi^{\prime}}):=\frac{1}{2}\mathbf{1}_{\phi_{1}=\phi_{1}^{\prime}}+\sum_{i=2}^{n}\mathbf{1}_{\phi_{i}=\phi^{\prime}_{i}}+\frac{1}{2}$
(19)

is the “similarity factor” between ${\bf\Phi}$ and ${\bf\Phi^{\prime}}$. This
takes on values $\in[0,n]$ by steps of $0.5$ depending on if
$\phi_{1}=\phi_{1}^{\prime}$. Sometimes we drop the arguments and call it $s$
(when evaluated, as a number) for brevity. It indicates how many bits are the
“same” in ${\bf\Phi}$ and ${\bf\Phi^{\prime}}$: with $\phi_{1}$ and
$\phi_{n+1}$ handled separately as they have half the weight as the other
$w_{i}$’s according to the APUF-specific transformation in (8).

Interpretation:  you can see the response similarity (i.e., the probability of
$R_{\bf\Phi}=R_{\bf\Phi^{\prime}}$) as the expected number of times (in %)
that the response to challenge ${\bf\Phi^{\prime}}$ will be the same as the
response to the anchor ${\bf\Phi}$ where the expectation is taken across
multiple PUF instances. This is equivalent to the probability (over the PUF
generation process) that for a given PUF, the two challenges will have the
same response.

As an example of how to use this Theorem, consider the previous example
challenges ${\bf\Phi,\Phi^{\prime},\Phi^{\prime\prime}}$ from Section III-A1.
For these, $S({\bf\Phi},{\bf\Phi^{\prime}})=4.5,P[R_{\bf c}=R_{\bf
c^{\prime}}]=\frac{1}{2}+\frac{1}{\pi}\left[\arcsin\left(\frac{9}{5}-1\right)\right]\sim
0.8$, and $S({\bf\Phi},{\bf\Phi^{\prime\prime}})=1/2,P[R_{\bf c}=R_{\bf
c^{\prime}"}]=\frac{1}{2}+\frac{1}{\pi}\left[\arcsin\left(\frac{1}{5}-1\right)\right]\sim
0.2$, aligning with the intuitive arguments before.

####  III-A3 Proof of Theorem III.1

We can write ${\bf\Phi_{1}}:=(\phi_{1,1},\phi_{1,2},\cdots,\phi_{1,n},1)$ and
${\bf\Phi_{2}}:=(\phi_{2,1},\phi_{2,2},\cdots,\phi_{2,n},1)$. Recall that
$R_{\bf\Phi_{1}}=\text{sign}\left(\sum_{i=1}^{n+1}\phi_{1,i}w_{i}\right)$ and
$R_{\bf\Phi_{2}}=\text{sign}\left(\sum_{i=1}^{n+1}\phi_{2,i}w_{i}\right)$.
Then, this proof follows using basics of probability and Lemma 28 below. We
see that

$\displaystyle P[R_{\bf\Phi_{1}}=R_{{\bf\Phi_{2}}}]$
$\displaystyle=2P[\Delta_{n}({\bf\Phi_{1}})>0,\Delta_{n}({\bf\Phi_{2}})>0]$
(20)
$\displaystyle\overset{(a)}{=}\frac{1}{2}+\frac{1}{\pi}\left[\arcsin\rho_{\Delta_{n}({\bf\Phi_{1}})\Delta_{n}({\bf\Phi_{2}})}\right]$
(21)

where $(a)$ follows by the multivariate Gaussian distribution orthant
probabilities (Lemma 28 below), and where $\rho_{AB}$ is the correlation
coefficient between random variables $A$ and $B$:

$\rho_{AB}:=\frac{E[AB]}{\sqrt{\text{Var}(A)}\sqrt{\text{Var}(B)}}.$ (23)

Let define the set $S_{ij}$ indicates the set of indices for which
${\bf\Phi_{i}}$ and ${\bf\Phi_{j}}$ are equal (excluding index $n+1$):

$S_{12}:=\\{i\in\\{1,2,\cdots n\\}:\phi_{1,i}=\phi_{2,i}\\}.$ (24)

In the same way, it is possible to define the set $D_{ij}$ of indices for
which ${\bf\Phi_{i}}$ and ${\bf\Phi_{j}}$ are not equal/different:

$D_{12}:=\\{i\in\\{1,2,\cdots n\\}:\phi_{1,i}\neq\phi_{2,i}\\}$ (25)

So $\rho_{12}:=\rho_{\Delta_{n}({\bf\Phi_{1}})\Delta_{n}({\bf\Phi_{2}})}$ may
be calculated as

$\displaystyle\rho_{12}$
$\displaystyle=\frac{E[\Delta_{n}({\bf\Phi_{1}})\Delta_{n}({\bf\Phi_{2}})]}{\sqrt{\text{Var}\Delta_{n}({\bf\Phi_{1}})}\sqrt{\text{Var}\Delta_{n}({\bf\Phi_{2}})}}$
$\displaystyle=\frac{E[\left(\sum_{i\in
S_{12}\cup(n+1)}\phi_{i}w_{i}\right)^{2}]-E[\left(\sum_{i\in
D_{12}}\phi_{i}w_{i}\right)^{2}]}{\sqrt{4n\sigma^{2}}\sqrt{4n\sigma^{2}}}$
$\displaystyle=\frac{\sum_{i\in S_{12}\cup(n+1)}E[|w_{i}|^{2}]-\sum_{i\in
D_{12}}E[|w_{i}|^{2}]}{\sqrt{4n\sigma^{2}}\sqrt{4n\sigma^{2}}}$

as
$\text{Var}(\Delta_{n}({\bf\Phi_{1}}))=\text{Var}(\Delta_{n}({\bf\Phi_{2}}))=4n\sigma^{2}$.
To further evaluate the expression in Eq. (III-A3) due to the $(\Phi,{\bf w})$
transformation/notation, we note that $E[|w_{i}|^{2}]=4\sigma^{2}$ for
$i\in\\{2,\cdots n\\}$ but that $E[|w_{i}|^{2}]=2\sigma^{2}$ for $i=1,n+1$, by
Lemma II.1. Since index $n+1$ is always in $S_{12}$, we need to determine
whether index 1 should be in $S_{12}$ or $D_{12}$.

If $\phi_{1,1}=\phi_{2,1}$ and hence index $1$ also lies in $S_{12}$, we have

$\displaystyle\rho_{12}$
$\displaystyle=\frac{4\sigma^{2}+4\sigma^{2}(|(S_{12}|-1)-|D_{12}|)}{4n\sigma^{2}}=\frac{|S_{12}|-|D_{12}|}{n}.$
(26)

If $\phi_{1,1}=-\phi_{2,1}$ and hence index $1$ is in $D_{12}$, we have

$\displaystyle\rho_{12}$
$\displaystyle=\frac{4\sigma^{2}+4\sigma^{2}(|S_{12}|-(|D_{12}|-1))}{4n\sigma^{2}}=\frac{1+|S_{12}|-|D_{12}|}{.}{n}$
(27)

Combining this with the “similarity factor” notation, we obtain a succinct
expression for $\rho_{12}$:

$\displaystyle\rho_{12}=\frac{2{S}({\bf\Phi_{1},\Phi_{2}})}{n}-1=\left\\{\begin{array}[]{ll}\frac{2|S_{12}|}{n}-1&\text{
if }\phi_{1,1}=\phi_{2,1}\\\ \frac{2|S_{12}|+1}{n}-1&\text{ if
}\phi_{1,1}\neq\phi_{2,1}\\\ \end{array}\right..$

######  Lemma III.2.

Let $X\sim{\cal N}(0,\sigma^{2})$, $Y\sim{\cal N}(0,\sigma^{2})$ with
correlation coefficient $E[XY]=\rho_{xy}$. Then,

$P[X>0,Y>0]=\frac{1}{4}+\frac{\arcsin\rho_{xy}}{2\pi}.$ (28)

####  III-A4 Application of Theorem III.1:

An “optimal predictor” $\widehat{R_{\bf\Phi_{2}}}(R_{\bf\Phi_{1}})$ to predict
$R_{\bf\Phi_{2}}$ based on the known $({\bf\Phi_{1}},R_{\bf\Phi_{1}})$

One immediate application of Theorem III.1 is to find the optimal predictor of
the response $R_{\bf\Phi_{2}}$ to challenge ${\bf\Phi_{2}}$ once we know the
response $R_{\bf\Phi_{1}}$ to challenge ${\bf\Phi_{1}}$. To find this, note
that the conditional probability mass function

$\displaystyle
P[R_{\bf\Phi_{2}}|R_{\bf\Phi_{1}}]=\frac{P[R_{\bf\Phi_{2}},R_{\bf\Phi_{1}}]}{P[R_{\bf\Phi_{1}}]}=\frac{P[R_{\bf\Phi_{2}},R_{\bf\Phi_{1}}]}{1/2}$
(29)
$\displaystyle=\left\\{\begin{array}[]{ll}2P[R_{\bf\Phi_{2}}=1,R_{\bf\Phi_{1}}=1]=P[R_{\bf\Phi_{1}}=R_{\bf\Phi_{2}}]\mbox{
if }R_{\bf\Phi_{2}}=R_{\bf\Phi_{1}}\\\
2P[R_{\bf\Phi_{2}}=1,R_{\bf\Phi_{1}}=-1]=1-P[R_{\bf\Phi_{1}}=R_{\bf\Phi_{2}}]\mbox{
O/W}\end{array}\right.$ (32)

may be derived immediately from Theorem III.1 and used to obtain the following
optimal predictor for $R_{\bf\Phi_{2}}$ based on $R_{\bf\Phi_{1}}$, written as
$\widehat{R_{\bf\Phi_{2}}}(R_{\bf\Phi_{1}})$:

######  Corollary III.2.1.

The optimal predictor for the response $R_{\bf\Phi_{2}}$ to an arbiter PUF
challenged with ${\bf\Phi_{2}}$ given knowledge of the CRP
$({\bf\Phi_{1}},R_{\bf\Phi_{1}})$ is,

$\displaystyle\widehat{R_{\bf\Phi_{2}}}(R_{\bf\Phi_{1}})=\arg\max_{R_{\bf\Phi_{2}}\in\\{\pm
1\\}}P[R_{\bf\Phi_{2}}|R_{\bf\Phi_{1}}]$ (33)
$\displaystyle=\left\\{\begin{array}[]{ll}R_{\bf\Phi_{1}}&\text{if
}P[R_{\bf\Phi_{1}}=R_{\bf\Phi_{2}}]>1-P[R_{\bf\Phi_{1}}=R_{\bf\Phi_{2}}]\\\
-{R_{\bf\Phi_{1}}}&\text{if
}P[R_{\bf\Phi_{1}}=R_{\bf\Phi_{2}}]<1-P[R_{\bf\Phi_{1}}=R_{\bf\Phi_{2}}]\\\
\end{array}\right.$ (36)

where ties (when the two are exactly equal) may be broken arbitrarily. The
prediction accuracy given by

$\displaystyle\max\\{P[R_{\bf\Phi_{1}}=R_{\bf\Phi_{2}}],1-P[R_{\bf\Phi_{1}}=R_{\bf\Phi_{2}}]\\}$

with

$\displaystyle P[R_{\bf\Phi_{1}}=R_{\bf\Phi_{2}}]$
$\displaystyle=\frac{1}{2}+\frac{1}{\pi}\left[\arcsin\left(\frac{2s}{n}-1\right)\right]$
$\displaystyle 1-P[R_{\bf\Phi_{1}}=R_{\bf\Phi_{2}}]$
$\displaystyle=\frac{1}{2}-\frac{1}{\pi}\left[\arcsin\left(\frac{2s}{n}-1\right)\right]$

where $s={S}({\bf\Phi_{1},\Phi_{2}})$.

As an example application of Corollary III.2.1, consider ${\bf c}=00000$ (as
this is what is physically input to the PUF we present it in this notation,
but all calculations are done by transforming ${\bf c}$ to ${\bf\Phi}$ first),
with $R_{\bf c}=+1$ and say we wish to predict $R_{\bf c^{\prime}}$, the
response to ${\bf c^{\prime}}=00110$. Since $P[R_{\bf c}=R_{\bf
c^{\prime}}]\sim 0.7>(1-0.7)$, we should guess that $R_{\bf c^{\prime}}$ is
also equal to $+1$ and this has a probability of 0.7 of being correct.

This predictor maximizes the probability of correctly guessing (in one guess)
the value of $R_{\bf\Phi^{\prime}}$ based on knowledge of $R_{\bf\Phi}$, hence
we term the predictor in (36) the optimal predictor in this sense. Here, if we
have one guess for $R_{\bf\Phi^{\prime}}$ based on knowledge of $R_{\bf\Phi}$
this corresponds to guessing the $\widehat{R_{\bf\Phi^{\prime}}}(R_{\bf\Phi})$
that maximizes $P[R_{\bf\Phi^{\prime}}|R_{\bf\Phi}]$ as in (36).

###  III-B Entropy

Recall the definitions of entropy of random variable (or vector) $X$ with
probability mass function $P_{X}(x)$ taking on values $x\in{\cal X}$ and
conditional entropy of random variable $X$ given random variable $Y$ (with
joint distribution $P_{X,Y}(x,y)$ taking on values $x,y\in{\cal X}\times{\cal
Y}$ [25]:

$\displaystyle H(X)$ $\displaystyle:=-\sum_{x\in{\cal
X}}p_{X}(x)\log(p_{X}(x))$ (37) $\displaystyle H(X|Y=y)$
$\displaystyle:=-\sum_{x\in{\cal X}}p_{X|Y}(x|y)\log(p_{X|Y}(x|y))$ (38)
$\displaystyle H(X|Y)$ $\displaystyle:=-\sum_{y\in{\cal Y}}p_{Y}(y)H(X|Y=y)$
(39) $\displaystyle=-\sum_{x\in{\cal X},y\in{\cal
Y}}p_{X,Y}(x,y)\log\left(\frac{p_{X,Y}(x,y)}{p_{Y}(y)}\right)$ (40)

We define the PUF entropy $H(\bigcup_{\bf\Phi}R_{\bf\Phi})$ as the entropy of
the vector of responses $\bigcup_{\bf\Phi}R_{\bf\Phi}$, recalling that each
response is a binary random value. Note that the joint distribution
$P(\bigcup_{\bf\Phi}R_{\bf\Phi})$ is hard to capture analytically as orthant
probabilities of Gaussian random vectors are generally unsolved for vectors of
dimensions greater than 3, necessitating estimates or bounds on this. The
conditional PUF entropy is the PUF entropy knowing one CRP:
$H(\bigcup_{\bf\Phi}R_{\bf\Phi}|R_{\bf\Phi_{1}})$, which is equally hard to
obtain given our inability to characterize the Gaussian orthant probabilities
beyond dimension 3.

We thus study what we call response entropy, i.e. the entropy of one response
$H(R_{\bf\Phi})$ and the conditional response entropy
$H(R_{\Phi_{2}}|R_{\Phi_{1}})$ given knowledge of one CRP
$({\bf\Phi},R_{\bf\Phi})$. Both the response entropy and the conditional
response entropy pertain to the entropy of one binary response and hence take
on values between $0$ and $1$. For the conditional response entropy
$H(R_{\Phi_{2}}|R_{\Phi_{1}})$, this value will depend on how correlated
$\Phi_{1}$ and $\Phi_{2}$ are, something we characterized precisely before
using the response similarity. We can use the chain rule to link all those
different entropies:

$\displaystyle
H\left(\bigcup_{\bf\Phi}R_{\bf\Phi}\right)=\sum_{i=1}^{n}H(R_{{\bf\Phi}_{i}}|R_{{\bf\Phi}_{1}},\cdots,R_{{\bf\Phi}_{i-1}})$
(41)
$\displaystyle=H(R_{{\bf\Phi}_{1}})+H(R_{{\bf\Phi}_{2}}|R_{{\bf\Phi}_{1}})+H(R_{{\bf\Phi}_{3}}|R_{{\bf\Phi}_{2}},R_{{\bf\Phi}_{1}})+\cdots$
(42)

This work calculates the first three terms (response entropies) exactly for
any choice of ${\bf\Phi_{1},\Phi_{2},\Phi_{3}}$. The left term is the overall
PUF entropy which is challenging to calculate.

All of the above definitions we presented the Shannon-entropy definition, but
these definitions can be equivalently modified for the min-entropy. The Min-
entropy of a probability mass function (or conditional probability mass
function) is defined as the log of the most likely outcome. When the response
$R_{\bf\Phi_{1}}=r_{\bf\Phi_{1}}$ is known, the most likely conditional
entropy will be given by the probability that you guess $R_{\bf\Phi_{2}}$ (for
a new, never before seen challenge ${\bf\Phi_{2}}$) correctly in one go. The
min entropy is simply defined as

$H_{\text{min}}(R_{\bf\Phi_{2}}|R_{\bf\Phi_{1}}=r_{\bf\Phi_{1}})=-\log\max\\{p_{s},1-p_{s}\\}.$
(43)

Min-entropy is often used when considering worst-case scenarios, ensuring that
even if the distribution is not uniform, the system remains secure. Shannon
entropy is more commonly used when analyzing average-case scenarios. In the
context of hardware security primitives, min-entropy may be preferred because
it helps assess the worst-case security of the PUF when one or two CRPs have
been revealed.

Without any CRP exposure, the response entropy
$P[R_{\Phi}=1]=P[R_{\Phi}=-1]=\frac{1}{2}$ so Min-response-entropy and Shannon
response entropy both equal $1$ bit. For arbitrary challenge bit vectors
${\bf\Phi_{1}},{\bf\Phi_{2}}$ the a conditional response entropy becomes:

$\displaystyle
H(R_{\bf\Phi_{2}}|R_{\bf\Phi_{1}}=r_{\bf\Phi_{1}})=-\sum_{r_{\bf\Phi_{2}}\in\\{\pm
1\\}}P[R_{\bf\Phi_{2}}=r_{\bf\Phi_{2}}|R_{\bf\Phi_{1}}=r_{\bf\Phi_{1}}]$ (44)
$\displaystyle\qquad\cdot\log_{2}(P[R_{\bf\Phi_{2}}=r_{\bf\Phi_{2}}|R_{\bf\Phi_{1}}=r_{\bf\Phi_{1}}])$
(45) $\displaystyle\overset{(a)}{=}-p_{s}\log p_{s}-(1-p_{s})\log(1-p_{s}),$
(46)

where $(a)$ follows when we define
$p_{s}=P[R_{\bf\Phi_{2}}=1|R_{\bf\Phi_{1}}=1]$ or
$p_{s}=P[R_{\bf\Phi_{2}}=-1|R_{\bf\Phi_{1}}=-1]$ (depending on what value
$r_{\bf\Phi_{1}}\in\\{\pm 1\\}$ takes on) and hence
$1-p_{s}=P[R_{\bf\Phi_{2}}=-1|R_{\bf\Phi_{1}}=1]$ or
$1-p_{s}=P[R_{\bf\Phi_{2}}=1|R_{\bf\Phi_{1}}=-1]$.

Figure 2 illustrates the similarity factors and their corresponding response
similarity $p_{s}=\frac{1}{2}+\frac{1}{\pi}\arcsin\left(\frac{2s}{n}-1\right)$
as a function of $s$ for a $32$-bit APUF. The x-axis shows the similarity
factor $s=S({\bf\Phi_{1},\Phi_{2}})$ between the known (say ${\bf\Phi_{1}}$)
and the unknown (say ${\bf\Phi_{2}}$) challenges. The green points $p_{s}$
shows the response similarity ranging from 0 to 1, corresponding to the y-axis
on the left. We plot also both the Shannon and min entropies of a challenge’s
response when we know 1 challenge as a function of $s$. As we can see, this
will depend on the correlation $\rho_{12}$ between the challenge whose
response we know, ${\bf\Phi_{1}}$, and the one whose response we wish to
guess, ${\bf\Phi_{2}}$. If they are uncorrelated, i.e. $\rho_{12}=0$ (or $s$
roughly equal to $n/2$), then the response entropy remains optimal at 1 bit;
the more correlated or anti-correlated they become, the more this drops, and
more dramatically so for the min entropy.

Figure 2: Accuracy, probability of same, Min-entropy and Shannon entropy of a
second challenge response ${\bf\Phi_{2}}$ when we know 1 challenge
${\bf\Phi_{1}}$’s response, as a function of the
${S}({\bf\Phi_{1},\Phi_{2}})$. Non-integer values of
$S({\bf\Phi_{1},\Phi_{2}})$ occur when $\phi_{1,1}\neq\phi_{2,1}$.

##  IV Similarity, accuracy and entropy Bins

Construction of Bins: Given an $n$-bit challenge ${\bf\Phi_{1}}$ (the
“anchor”), we now show how to construct various sets containing all the
challenges respecting a “semimetric” to the anchor. We can intuitively view a
bin B of challenges as a sphere of challenges of radius $r$ that all have the
same probability, a prediction accuracy or conditional entropy given the
anchor challenge. This radius can be

  * •

the response similarity: “similarity bins” written
$B(s,{\bf\Phi_{1}}):=\\{{\bf\Phi_{2}}|{S}({\bf\Phi_{1},\Phi_{2}})=s\\}$ or
equivalently
$B(p,{\bf\Phi_{1}}):=\\{{\bf\Phi_{2}}|P[R_{\bf\Phi_{1}}=R_{\bf\Phi_{2}}]=p\\}$
are the bins containing all the challenges that have the same response
similarity to the anchor. For sake of the convenience, we will use the first
definition $B(s,{\bf\Phi_{1}})$.

  * •

the prediction accuracy: “accuracy bins” written
$B_{a}(a,{\bf\Phi_{1}}):=\\{{\bf\Phi_{2}}|\max\\{P[R_{\bf\Phi_{1}}=R_{\bf\Phi_{2}}],1-P[R_{\bf\Phi_{1}}=R_{\bf\Phi_{2}}]\\}=a\\}$
have all the challenges which can be predicted with the same accuracy given
the anchor challenge.

  * •

the entropy (Shannon or min): “entropy bins” written
$B_{H}(h,{\bf\Phi_{1}}):=\\{{\bf\Phi_{2}}|H(R_{\bf\Phi_{2}}|R_{\bf\Phi_{1}}=r_{\bf\Phi_{1}})=h\\}$
all have the same conditional response entropy given the anchor challenge.

These bins $B$ can be derived using the probability
$P[R_{\bf\Phi_{1}}=R_{\bf\Phi_{2}}]$ which relies on the similarity factor.
From a specific value of your “semimetric” you can derive the similarity
factor(s) and then use algorithm 1 (Appendix Algorithms for bin creation).

According to Theorem III.1, there are only $2n$ distinct response similarities
thus for a given anchor challenge, all the challenges (including the anchor
itself) will be partitioned into a total of $2n$ disjoint similarity bins.
Intuitively, most of the challenges are in the “uncorrelated” bin of an
anchor, i.e., $B(p\approx 0.5,{\bf\Phi})$.

First, consider the trivial case $B(p=1,{\bf\Phi})=B(s=n,{\bf\Phi})$: among
all the $2^{n}$ challenges, the one with highest response similarity (100%) is
the anchor itself and itself only, thus $B(n,{\bf\Phi})=\\{{\bf\Phi}\\}$, and
its size is 1.

Next, consider the similarity bin with the highest $p<1$: this would be
$B(p,{\bf\Phi})=B(s=n-1/2,{\bf\Phi})$, where
$p=\frac{1}{2}+\frac{1}{\pi}\arcsin\left(\frac{2s}{n}-1\right)$. For a
challenge ${\bf\Phi^{\prime}}$ to be in this set, it needs to satisfy
$S({\bf\Phi^{\prime}},{\bf\Phi})=n-1/2$ according to Theorem III.1. This can
only be achieved by making $\phi^{\prime}_{1}=-\phi_{1}$, while keeping all
other $\phi^{\prime}_{i}=\phi_{i},i\in[2,n+1]$ – as $w_{1}$ contributes half
the weight as the other $w_{i},i\in[2,n]$, while $w_{n+1}$ always is positive
(as $\phi_{n+1}=+1$). Thus, this will constitute $B(s=n-1/2,{\bf\Phi})$, a set
with only one element.

Following the same argument, a challenge ${\bf\Phi^{\prime}}\in
B(s=n-1,{\bf\Phi})$ must satisfy $\phi^{\prime}_{1}=\phi_{1}$, with a single
$\phi^{\prime}_{i}=-\phi_{i}$ among $i\in[2,n]$. Thus the size of this bin
$|B(n-1,{\bf\Phi})|=n-1$. Similarly, a challenge ${\bf\Phi^{\prime}}\in
B(s=n-3/2,{\bf\Phi})$ can be derived by making $\phi^{\prime}_{1}=-\phi_{1}$,
and making sure only a single $\phi^{\prime}_{i}=-\phi_{i}$ among $i\in[2,n]$.
The size of the bin is again $n-1$.

Essentially, to obtain a challenge ${\bf\Phi^{\prime}}\in B(s,{\bf\Phi})$, one
needs to select $\lfloor s\rfloor$ among the anchor’s $\phi_{i},i\in[2,n]$ to
flip their signs to form the $\phi^{\prime}_{i}$’s. Whether
$\phi^{\prime}_{1}=\phi_{1}$ or $-\phi_{1}$ depends on whether $s$ is an
integer or not.

Size of Similarity Bins: Algorithm 1 summarizes the general method for
deriving the similarity bin $B(s,{\bf\Phi})$. The complexity is linear in the
size of the similarity bin to be derived. From Algorithm 1, we can derive the
size of a similarity bin as follows:

######  Corollary IV.0.1.

The size of the similarity bin $B(s,{\bf\Phi})$, for $s\in[1:n]$, for an APUF
of length $n$ is

$\displaystyle|B(s,{\bf\Phi})|$ $\displaystyle={n-1\choose s}$
$\displaystyle\text{if }\phi_{1}=\phi_{1}^{\prime}$ (47)
$\displaystyle={n-1\choose\lfloor s-1\rfloor}\ $ $\displaystyle\text{if
}\phi_{1}\neq\phi_{1}^{\prime}$ (48)

Figure 3: Similarity bin sizes (number of challenges) in function of
${S}({\bf\Phi_{1},\Phi_{2}})$. Not integer values of S means that
$\phi_{1,1}\neq\phi_{2,1}$.

Figure 3 shows the size of each similarity bin, $|B(s,{\bf\Phi})|$, obtained
from Corollary IV.0.1 on the right y-axis.

Expected conditional entropy: From Figures 2 and 3 we have all the information
needed to compute the expected conditional response entropy or accuracy of a
response given one CRP. We know the specific value of the response entropy for
each possible known challenge as well as the exact number of challenges in an
entropy bin, i.e the exact number of challenges such that
$H(R_{\bf\Phi^{\prime}}|R_{\bf\Phi}=r_{\bf\Phi})=h$ since $B(h,{\bf\Phi})$ is
the union of two disjoints $B(s,{\bf\Phi})$. Defining $h_{s,{\bf\Phi}}$ as
$h_{s,{\bf\Phi}}=H(R_{\bf\Phi^{\prime}}|R_{\bf\Phi}=r_{\bf\Phi})$ with
${\bf\Phi}^{\prime}\in B(s,{\bf\Phi})$, the expected response entropy becomes
the weighted average of the response entropies, weighted by the number of
challenges in each bin as below:

$\bar{H}(R_{\bf\Phi^{\prime}}|R_{\bf\Phi}=r_{\bf\Phi})=\frac{1}{2^{n}-1}\sum_{s\in\\{0,\frac{1}{2},1,\cdots,n-\frac{1}{2}\\}}h_{s,{\bf\Phi}}\cdot|B(s,{\bf\Phi})|$
(49)

The expected accuracy (of estimating a next challenge given knowledge of one
CRP) can be similarly calculated as a weighted sum. The expected conditional
min and Shannon entropies and the expected conditional accuracy are calculated
in Table I for different PUF lengths. Note that this does not depend on the
variance $\sigma^{2}$ of the delay element generation process.

| n=32 | n=64 | n=128
---|---|---|---
H-min | 0.8747 | 0.9112 | 0.9369
H-Shannon | 0.9900 | 0.9952 | 0.9977
Accuracy | 0.5465 | 0.5323 | 0.5226
TABLE I: Expected conditional entropy and expected accuracy of a challenge’s
response knowing one CRP for APUFs of different length (number of stages n).

##  V Scalability to more known CRPs

All conditional response entropy and optimal predictor results so far have
assumed a single anchor: i.e., one CRP $({\bf\Phi},R_{\bf\Phi})$ to be known.
The natural next question is how to obtain optimal predictors and conditional
response entropies with multiple anchors. This is based on finding the
conditional probability mass function, which, at its core, depends on the
availability of closed form expressions for the orthant probabilities of
jointly Gaussian random variables. While this is known for Gaussian vectors of
dimensions 2 (useful for one known, one target challenge) and 3 (useful for
two known, and one target challenge), it remains unknown for larger dimensions
[26], and hence there is little hope for closed form solutions for higher
dimensions, i.e. optimally predicting the response to a target challenge given
knowledge of 3 or more known CRPs. Numerical approximations are left for
future work.

###  V-A Optimal predictor

When $({\bf\Phi_{1}},R_{\bf\Phi_{1}})$ and $({\bf\Phi_{2}},R_{\bf\Phi_{2}})$
are known and we wish to predict the response $R_{\bf\Phi_{3}}$ to a third
challenge ${\bf\Phi_{3}}$, one naive approach may be to use our previous know-
one-predict-one predictor to predict $R_{\bf\Phi_{3}}$ based on the response
of the “most correlated” challenge to ${\bf\Phi_{3}}$, i.e. based on the
response predicted by either ${\bf\Phi_{1}}$ or ${\bf\Phi_{2}}$ We will show
that this is in fact provably optimal. This naive strategy can be extended to
knowing more than 2 CRPs to predict another, but we are unable to prove
optimality, which essentially stems from Gaussian orthant probabilities being
unknown for more than 3 dimensions.

For knowing two CRPs and predicting a third, the optimal predictor takes on
the following form [27]:

$\widehat{R_{\bf\Phi_{3}}}=\arg\max
P(R_{\bf\Phi_{3}}|R_{\bf\Phi_{1}},R_{\bf\Phi_{2}}).$ (50)

Hence, to obtain this optimal predictor, we need to obtain the conditional
probability mass functions
$P(R_{\bf\Phi_{3}}|R_{\bf\Phi_{1}},R_{\bf\Phi_{2}})$. This involves finding
the eight values

$P(R_{\bf\Phi_{3}}=r_{3}|R_{\bf\Phi_{1}}=r_{1},R_{\bf\Phi_{2}}=r_{2}),\;\;\;\;r_{i}\in\\{\pm
1\\}.$ (51)

We only need the four values
$P(R_{\bf\Phi_{3}}=-1|R_{\bf\Phi_{1}}=r_{1},R_{\bf\Phi_{2}}=r_{2})$ from which
we can find the others as
$P(R_{\bf\Phi_{3}}=1|R_{\bf\Phi_{1}}=r_{1},R_{\bf\Phi_{2}}=r_{2})=1-P(R_{\bf\Phi_{3}}=-1|R_{\bf\Phi_{1}}=r_{1},R_{\bf\Phi_{2}}=r_{2})$.
By definition, we have that

$\displaystyle
P(R_{\bf\Phi_{3}}=r_{3}|R_{\bf\Phi_{1}}=r_{1},R_{\bf\Phi_{2}}=r_{2})$ (52)
$\displaystyle=\frac{P(R_{\bf\Phi_{3}}=r_{3},R_{\bf\Phi_{1}}=r_{1},R_{\bf\Phi_{2}}=r_{2})}{P(R_{\bf\Phi_{1}}=r_{1},R_{\bf\Phi_{2}}=r_{2})}.$
(53)

Recall that $R_{\bf\Phi}=\text{sign}(\Delta_{n}({\bf\Phi}))$, and that
$\Delta_{n}$ is a Gaussian random variable, as it is the sum of Gaussian
random variables. To obtain (53) we thus need only calculate
$P(R_{\bf\Phi_{3}},R_{\bf\Phi_{1}},R_{\bf\Phi_{2}})$ and
$P(R_{\bf\Phi_{1}},R_{\bf\Phi_{2}})$. These may both be obtained by noting
that since $R_{\bf\Phi}=\text{sign}(\Delta_{n}({\bf\Phi}))$ are signs of zero
mean, equal variance Gaussian random variables, these probabilities amount to
the orthant probabilities of jointly Gaussian random variables, i.e.

$\displaystyle P(R_{\bf\Phi_{3}}=1|R_{\bf\Phi_{1}}=1,R_{\bf\Phi_{2}}=1)$ (54)
$\displaystyle=\frac{P(R_{\bf\Phi_{3}}=1,R_{\bf\Phi_{2}}=1,R_{\bf\Phi_{1}}=1)}{P(R_{\bf\Phi_{1}}=1,R_{\bf\Phi_{2}}=1)}$
(55)
$\displaystyle=\frac{P(\Delta_{n}({\bf\Phi_{3}})>0,\Delta_{n}({\bf\Phi_{2}})>0,\Delta_{n}({\bf\Phi_{1}})>0)}{P(\Delta_{n}({\bf\Phi_{1}})>0,\Delta_{n}({\bf\Phi_{2}})>0))}.$
(56)

If $X,Y,Z$ are zero mean Gaussian random variables, then

$\displaystyle P(X>0,Y>0,Z>0)$ (57)
$\displaystyle=\frac{1}{8}+\frac{1}{4\pi}\left[\arcsin\rho_{XY}+\arcsin\rho_{XZ}+\arcsin\rho_{XZ}\right]$
(58) $\displaystyle
P(X>0,Y>0)=\frac{1}{4}+\frac{1}{2\pi}\left[\arcsin\rho_{XY}\right]$ (59)
$\displaystyle P(X>0|Y>0,Z>0)$ (60)
$\displaystyle=\frac{1}{2}\left[1+\frac{\arcsin\rho_{XY}+\arcsin\rho_{XZ}}{\frac{\pi}{2}+\arcsin\rho_{YZ}}\right],$
(61)

Letting $\rho_{ij}$ be the correlation coefficient between
$\Delta_{n}({\bf\Phi_{i}})$ and $\Delta_{n}({\bf\Phi_{j}})$ (which we recall
are Gaussian random variables) we obtain the following:

######  Theorem V.1.

For $r_{1},r_{2}\in\\{\pm 1\\}$,

$\displaystyle
P(R_{\bf\Phi_{3}}=1|R_{\bf\Phi_{1}}=r_{1},R_{\bf\Phi_{2}}=r_{2})$ (62)
$\displaystyle=\frac{1}{2}\left[1+\frac{r_{1}\arcsin\rho_{13}+r_{2}\arcsin\rho_{23}}{\frac{\pi}{2}+r_{1}r_{2}\arcsin\rho_{12}}\right]$
(63)

and we can obtain
$P(R_{\bf\Phi_{3}}=-1|R_{\bf\Phi_{1}}=r_{1},R_{\bf\Phi_{2}}=r_{2})=1-P(R_{\bf\Phi_{3}}=1|R_{\bf\Phi_{1}}=r_{1},R_{\bf\Phi_{2}}=r_{2})$.

For clarity, we detail the quantities needed:

$\displaystyle|S_{ij}|$ $\displaystyle:=\\#\text{ indices }l\in\\{1,2,\cdots
n\\}\text{ for which }\phi_{i,l}=\phi_{j,l}$ (64) $\displaystyle\rho_{ij}$
$\displaystyle=\left\\{\begin{array}[]{ll}\frac{2|S_{ij}|}{n}-1&\text{ if
}\phi_{i,1}=\phi_{j,1}\\\ \frac{2|S_{ij}|+1}{n}-1&\text{ if
}\phi_{i,1}\neq\phi_{j,1}\\\ \end{array}\right..$ (67)

From the above equation (62) we notice a few things: 1) first, the prediction
accuracy depends on the actual response values $r_{1},r_{2}$ and how they
interact with the correlation coefficients. For example, for good prediction
accuracy, you want the second term inside the brackets to be close to $1$ or
$-1$ (and hence the overall prediction being close to either 1 or 0). Poor
accuracy corresponds to the second term being close to $0$ (and hence the
overall prediction being around $0.5$). For good accuracy you want
$r_{1}\arcsin\rho_{13}$ and $r_{2}\arcsin\rho_{23}$ to align or point in the
same direction, both adding to a positive $+1$ or a negative $-1$, then it
will be easy to predict the third $r_{3}$ as it will likely be in the same
direction as the others. If the two challenge responses and correlation
coefficients contradict each other, i.e. if
$r_{1}\arcsin\rho_{13}=-r_{2}\arcsin\rho_{23}$ then the accuracy will be poor.
The denominator also matters: if it becomes close to $0$, or if
$r_{1}r_{2}\arcsin\rho_{12}$ is close to $-\pi/2$ (could happen if
$r_{1}=r_{2}=+1$ but $\arcsin\rho_{12}=-\pi/2$ which means that $\rho_{12}=-1$
and the challenges are statistically anti-correlated yet produced the same
sign – virtually impossible), then the prediction accuracy is close to
$\frac{1}{2}$.

The optimal predictor of $R_{\bf\Phi_{3}}$ given knowledge of
$R_{\bf\Phi_{2}}$ and $R_{\bf\Phi_{1}}$ first calculates $\rho_{12},\rho_{13}$
and $\rho_{23}$. From this, and $R_{\bf\Phi_{2}}$ and $R_{\bf\Phi_{1}}$ we
select $R_{\bf\Phi_{3}}$ as:

$\widehat{R_{\bf\Phi_{3}}}=\arg\max_{R_{\bf\Phi_{3}}\in\\{\pm
1\\}}P(R_{\bf\Phi_{3}}|R_{\bf\Phi_{1}},R_{\bf\Phi_{2}}).$

The optimal prediction accuracy is then given by

$\displaystyle\text{Prediction
accuracy}=\max\bigl{\\{}P[R_{\bf\Phi_{3}}=1|R_{\bf\Phi_{1}}=r_{1},R_{\bf\Phi_{2}}=r_{2}],$
$\displaystyle\;\;\;\;\;\;P[R_{\bf\Phi_{3}}=-1|R_{\bf\Phi_{1}}=r_{1},R_{\bf\Phi_{2}}=r_{2}]\bigr{\\}}$
(68)

which may be re-written as a value $A$ as:

$\displaystyle A=\max\Bigl{\\{}$
$\displaystyle\frac{1}{2}\left[1+\frac{r_{1}\arcsin{\rho_{13}}+r_{2}\arcsin{\rho_{23}}}{\pi/2+r_{1}r_{2}\arcsin{\rho_{12}}}\right],$
(69) $\displaystyle
1-\frac{1}{2}\left[1+\frac{r_{1}\arcsin{\rho_{13}}+r_{2}\arcsin{\rho_{23}}}{\pi/2+r_{1}r_{2}\arcsin{\rho_{12}}}\right]\Bigr{\\}}.$
(70)

This shows that the optimal predictor may be obtained in closed form for the
arbiter PUF when two CRPs are known. In fact the optimal predictor has a
simple form: if you know 2 challenges and want to predict a third, simply
select the closest challenge to the anchor (the most correlated) and use the
know-one-predict-one predictor. In other words, the response of the third
challenge is the response of closest of the two challenges times the sign of
its correlation:

$\displaystyle
P(R_{\bf\Phi_{3}}=1|R_{\bf\Phi_{1}}=r_{1},R_{\bf\Phi_{2}}=r_{2})\gtrless 0.5$
$\displaystyle\Leftrightarrow\frac{1}{2}\left[1+\frac{r_{1}\arcsin\rho_{13}+r_{2}\arcsin\rho_{23}}{\frac{\pi}{2}+r_{1}r_{2}\arcsin\rho_{12}}\right]\gtrless
0.5$
$\displaystyle\Leftrightarrow\frac{r_{1}\arcsin\rho_{13}+r_{2}\arcsin\rho_{23}}{c}\gtrless
0$ $\displaystyle\Leftrightarrow
r_{1}\arcsin\rho_{13}+r_{2}\arcsin\rho_{23}\gtrless 0$
$\displaystyle\Leftrightarrow r_{1}\rho_{13}+r_{2}\rho_{23}\gtrless 0$
$\displaystyle\Leftrightarrow
R_{\bf\Phi_{3}}=r_{i}\cdot\text{sign}(\rho_{i3})\,\text{with
}i={\arg\max}{\\{|\rho_{13}|,|\rho_{23}|}\\}$

###  V-B Entropy

The conditional response entropy given two CRPs also depends only on the
conditional probability mass functions, this is easily obtained once we have
the conditional distributions, as:

$\displaystyle
H(R_{\bf\Phi_{3}}|R_{\bf\Phi_{1}}=r_{\bf\Phi_{1}},R_{\bf\Phi_{2}}=r_{\bf\Phi_{2}})$
$\displaystyle=-\sum_{r_{\bf\Phi_{3}}\in\\{0,1\\}}P(R_{\bf\Phi_{3}}=r_{\bf\Phi_{3}}|R_{\bf\Phi_{1}}=r_{\bf\Phi_{1}},R_{\bf\Phi_{2}}=r_{\bf\Phi_{2}})\cdot$
$\displaystyle\qquad\log_{2}(P(R_{\bf\Phi_{3}}=r_{\bf\Phi_{3}}|R_{\bf\Phi_{1}}=r_{\bf\Phi_{1}},R_{\bf\Phi_{2}}=r_{\bf\Phi_{2}})).$

Figure 4 shows the Min and Shannon entropy for different $\rho_{ij}$ values
for an arbiter PUF with $n=32$. Again, we see that the remaining APUF
entropies depend on the correlations between the two known challenges and the
other challenges. Once again, the min entropy is more dramatically reduced
than the Shannon entropy, as expected. This means that there is an increase in
the probability of guessing a third challenge correctly when two challenges
are known. On the diagonal (yellow) the two known challenges do not reveal any
information about the remaining challenges. While one CRP might give us some
information about the unknown challenge, the other CRP leads us on the
opposite direction, so we do not learn anything and the probability to guess
the unknown challenge response is still $0.5$, i.e. has entropy 1 bit.

(a) Min-Entropy : $r_{1}=r_{2}$ and $\rho_{12}=0$

(b) S-Entropy : $r_{1}=r_{2}$ and $\rho_{12}=0$

(c) Min-Entropy : $r_{1}=r_{2}$ and $\rho_{12}=0.5$

(d) S-Entropy : $r_{1}=r_{2}$ and $\rho_{12}=0.5$

Figure 4: Min-entropy and Shannon entropy when knowing 2 challenges

###  V-C Neighborhoods

We now ask how we may generalize the notion of similarity bins introduced
earlier, to predictability and entropy neighborhoods. The question is which
challenges ${\bf\Phi_{3}}$ lie within a certain "distance" / “semi-metric” $d$
to two anchor challenges rather than one. We would like an algorithm to
enumerate the challenges that lie within this predictability or entropy
neighborhood, denoted by $B(d,{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})$, and as a
by-product, its size. To this end, define

$\displaystyle
B(A,{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})=\bigl{\\{}{\bf\Phi_{3}}:$ (71)
$\displaystyle\;\;\;\max(P(R_{\bf\Phi_{3}}=1|R_{\bf\Phi_{1}}=r_{1},R_{\bf\Phi_{2}}=r_{2}),$
$\displaystyle\;\;\;1-P(R_{\bf\Phi_{3}}=1|R_{\bf\Phi_{1}}=r_{1},R_{\bf\Phi_{2}}=r_{2}))=A\bigr{\\}}$
$\displaystyle
B(H,{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})=\bigl{\\{}{\bf\Phi_{3}}:$ (72)
$\displaystyle\;\;\;H(R_{\bf\Phi_{3}}|R_{\bf\Phi_{1}}=r_{\bf\Phi_{1}},R_{\bf\Phi_{2}}=r_{\bf\Phi_{2}})=H\bigr{\\}}$

In this “know 2, predict a third” case, we will see that not all prediction
accuracies/entropies are possible. It depends on the relationship between the
challenges you know. If you know two challenges, they are fixed, and hence so
is their correlation $\rho_{12}$. We are thus interested in seeing how many
challenges lie at different correlations $\rho_{13},\rho_{23}$ to these
challenges.

In order to define the similarity neighborhoods and count them, we will need
to quantify which correlation triples $(\rho_{12},\rho_{13},\rho_{23})$ are
possible.

This is illustrated in Figure 5. To approach this, define

$\displaystyle K$ $\displaystyle:=\text{ number of indices in }S_{12}\text{
that we ``keep'' in }{\bf\Phi_{3}}$
$\displaystyle\overset{(a)}{=}\frac{|S_{13}|+|S_{23}|+|S_{12}|-n}{2}$ (73)

where (a) follows by setting $x:=|S_{13}|-K$ (the number of bits from $D_{12}$
that belongs to $|S_{13}|$), and $y:=|S_{23}|-K$ (the number of bits from
$D_{12}$ that belongs to $|S_{23}|$), from which, since $x$ and $y$ must cover
the whole $D_{12}$ set we see that $x+y=|D_{12}|=n-|S_{12}|$ and by replacing
$x$ and $y$, we obtain $K=\frac{|S_{13}|+|S_{23}|+|S_{12}|-n}{2}$.

####  V-C1 Neighborhood construction

How can we find one challenge in $B(d,{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})$? We
enumerate the steps below which takes known challenges
${\bf\Phi_{1},\Phi_{2}}$ with correlation coefficient $\rho_{12}$ and produces
a single output challenge ${\bf\Phi_{3}}$ at the desired distance $d$ in a
chosen “semi-metric” space (accuracy, Shannon or min entropies).

This distance $d$ depends on the challenge response values $r_{1}$ and
$r_{2}$, and how to pick $\rho_{13},\rho_{23}$ to satisfy this equation:

  1. 1.

Find $\rho_{13},\rho_{23}$ based on desired distance $d$ and the set of all
possible $(\rho_{12},\rho_{13},\rho_{23})$ tuples, given by Figure for the
given $\rho_{12}$. How this Figure is obtained is presented in the Question
below “Which correlations $\rho_{13}$ and $\rho_{23}$ are possible given
$\rho_{12}$”. This essentially boils down to picking $\rho_{13},\rho_{23}$ of
the desired accuracy (represented by color) in our numerical evaluations.

  2. 2.

The $\rho_{12},\rho_{13},\rho_{23}$ determine the sizes
$|S_{12}|,|S_{13}|,|S_{23}|$ of the sets $S_{12},S_{13},S_{23}$. From here we
can use Algorithm 3 in Appendix Algorithms for bin creation which gives the
following steps :

  3. 3.

From $|S_{12}|,|S_{13}|,|S_{23}|$ we find $K$ as in (73). Select any $K$
indices in $S_{12}$ to keep fixed in ${\bf\Phi_{3}}$. The remaining indices in
$S_{12}$ in ${\bf\Phi_{3}}$ must be flipped.

  4. 4.

For the remaining indices in $D_{12}$, pick $|S_{13}|-K$ of them the same as
${\bf\Phi_{1}}$ and flip the remaining ones with respect to ${\bf\Phi_{1}}$,
yielding the desired $\rho_{13}$ and $\rho_{23}$.

####  V-C2 Example: constructing a ${\bf\Phi_{3}}\in
B(d,{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})$

Given challenges ${\bf\Phi_{1}}$ and ${\bf\Phi_{2}}$, to create a third vector
with desired correlations (note that not all will be possible), the main idea
is to know how many bits we have to keep/fix from the first two challenges and
how many we have to flip. Consider $n=8$ and
${\bf\Phi_{1}}:=(+1,+1,+1,+1,+1,+1,+1,+1,+1)$,
${\bf\Phi_{2}}:=(+1,+1,+1,+1,-1,-1,-1,-1,+1)$, then $\rho_{12}=0$. Say we wish
to predict a third challenge ${\bf\Phi_{3}}$ with probability of accuracy
$A\approx 0.6$. We follow the steps of the algorithm:

  1. 1.

By generating the Figures from (81) – (84), we can see that $\rho_{23}=0$,
$\rho_{23}=1/3$ and $\Phi_{1,1}=\Phi_{2,1}=\Phi_{3,1}=1$ is one of the
multiple possible choices.

  2. 2.

This is equivalent to selecting $|S_{23}|=4$ and $|S_{13}|=6$.

  3. 3.

To create a challenge with these desired correlations to the two known
challenges, we need to decide how many indices in ${\bf\Phi_{3}}$ to keep from
$S_{12}$, let us call this set of indices $K$, and then how many to keep and
flip from the set $D_{12}$. Since $\Phi_{1,1}=\Phi_{2,1}=\Phi_{3,1}=1$ the
first bit belongs to the sets $S_{12},\,S_{13},\,S_{23}$ so we have to select
it in the ones we fix and
$K-1=(|S_{12}|+|S_{13}|+|S_{23}|-n)/2-1=(4+4+6-8)/2-1=2$ other bits to fix
from the $S_{12}$. Take for example ${\bf\Phi_{3}}:=(+1,*,+1,+1,*,*,*,*,+1)$
where the $*$ positions still need to be filled in.

  4. 4.

Finally, we can flip the other bits in $S_{12}$ to obtain
${\bf\Phi_{3}}:=(+1,-1,+1,+1,*,*,*,*,+1)$. Then we select $|S_{13}|-K=3$ bits
from $D_{12}$ to fix and flip the left ones as
${\bf\Phi_{3}}:=(+1,-1,+1,+1,+1,+1,+1,-1,+1)$. Equivalently, we could have
fixed $|S_{23}|-K=1$ bits from $D_{12}$ and flipped the left ones. Then, this
${\bf\Phi_{3}}$ can be predicted with accuracy
$P(R_{\bf\Phi_{3}}=1|R_{\bf\Phi_{1}}=1,R_{\bf\Phi_{2}}=1)=\frac{1}{2}\left[1+\frac{\arcsin{\frac{1}{3}}+\arcsin{0}}{\frac{\pi}{2}+\arcsin{0}}\right]\approx
0.61$.

The algorithm is given in Algorithm 3 in Appendix Algorithms for bin creation.

Figure 5: Illustration of the sizes of the difference index sets
$S_{12},S_{13},D_{12},S_{23}$ and integer $K$ representing the number of
indices in $S_{12}$ that we keep the same in ${\bf\Phi_{3}}$. In this example
we assume the first bit is the same in all three ${\bf\Phi_{1,2,3}}$.

####  V-C3 Neighborhood size

So far we have produced one challenge of a given desired distance to the
anchors. We now answer how many challenges exist with that ditance, and how
can they be efficiently enumerated? The answer to this is derived directly
from the way we created the single challenge – i.e. by looking at how many
arbitrary choices we had. For example, in the case
$\phi_{1,1}=\phi_{2,1}=\phi_{3,1}$: how many ways are there to choose $K-1$
bits from $S_{12}-1$ (since the first bit is fixed in this example) and
$|S_{13}|-K$ bits from $D_{12}$, with $|D_{12}|=n-|S_{12}|$. Now, there are
two possibilities, when $\phi_{1,1}=\phi_{2,1}$ and when
$\phi_{1,1}\neq\phi_{2,1}$ which must be treated differently as the 1st
position is special in the $\Phi$ notation.

  * •

If $\phi_{1,1}=\phi_{2,1}$ and $|S_{13}|+|S_{23}|+|S_{12}|-n\equiv 0\mod 2$,
then do not flip first bit:

$\displaystyle\\#\text{of challenges }$ $\displaystyle={|S_{12}|-1\choose
K-1}{n-|S_{12}|\choose|S_{13}|-K}$ (74) $\displaystyle={|S_{12}|-1\choose
K-1}{n-|S_{12}|\choose|S_{23}|-K}$ (75)

  * •

If $\phi_{1,1}=\phi_{2,1}$ and $|S_{13}|+|S_{23}|+|S_{12}|-n\equiv 1\mod 2$,
then flip the first bit:

$\displaystyle\\#\text{of challenges }$ $\displaystyle={|S_{12}|-1\choose
K}{n-|S_{12}|\choose|S_{13}|-K}$ (76) $\displaystyle={|S_{12}|-1\choose
K}{n-|S_{12}|\choose|S_{23}|-K}$ (77)

  * •

If $\phi_{1,1}\neq\phi_{2,1}$ we need $|S_{13}|+|S_{23}|+|S_{12}|-n\equiv
0\mod 2$ since we necessarily have $\phi_{3,1}\neq\phi_{2,1}$ or
$\phi_{3,1}\neq\phi_{1,1}$

$\displaystyle\\#\text{of challenges }$ (78) $\displaystyle={|S_{12}|\choose
K}{n-|S_{12}|\choose|S_{13}|-K-1}\text{ if ${S}({\bf\Phi_{1},\Phi_{3}})\equiv
0\mod 1$}$ (79) $\displaystyle={|S_{12}|\choose
K}{n-|S_{12}|\choose|S_{23}|-K-1}\text{ if ${S}({\bf\Phi_{2},\Phi_{3}})\equiv
0\mod 1$}$ (80)

Notice that, contrary to the accuracy, the number of challenges does not
depend on the challenge responses. To create similarity bins of size $m$ with
two anchors we can use Algorithm 2, which in turn calls Algorithms 4 and 5.

####  V-C4 Neighborhood landscape discussion

Now we provide some in-depth analysis on the details of a neighborhood’s
landscape with the following questions.

##### Which correlations $\rho_{13}$ and $\rho_{23}$ are possible given
$\rho_{12}$?

The answer depends on whether $\phi_{1,1},\phi_{2,1},\phi_{3,1}$ are the same
or different. This is because this first bit has a different variance than the
others, as per Lemma II.1. We present one case as an example; the others
follow similarly.

Assume $\phi_{1}^{1}=\phi_{2}^{1}=\phi_{3}^{1}$. Then equation (73) and (74)
imply two sufficient and necessary conditions on the correlation between the
three challenges to be able to create the third one. In particular, by
requiring $K\in\mathbb{N}$ in (73), and $\\#\text{of challenges
}={|S_{12}|-1\choose K-1}{n-|S_{12}|\choose|S_{13}|-K}={|S_{12}|-1\choose
K-1}{n-|S_{12}|\choose|S_{23}|-K}>0$ we obtain the following conditions:

$\displaystyle K\in\mathbb{N}\rightarrow|S_{13}|+|S_{23}|+|S_{12}|-n$
$\displaystyle\equiv 0\mod 2$ $\displaystyle{|S_{12}|-1\choose
K-1}{n-|S_{12}|\choose|S_{13}|-K}>0$ $\displaystyle\rightarrow|S_{12}|\geq K$
$\displaystyle\rightarrow n-|S_{12}|\geq|S_{13}|-K$
$\displaystyle{|S_{12}|-1\choose K-1}{n-|S_{12}|\choose|S_{23}|-K}>0$
$\displaystyle\rightarrow n-|S_{12}|\geq|S_{23}|-K$

Re-writing these using correlation coefficients (recall
$|S|=(\rho+1)\frac{n}{2}$) yields the inequalities relating the possible
correlations $\rho_{12},\rho_{13},\rho_{23}$ (which also must all lie in
$[-1,1]$):

$\displaystyle\rho_{13}\leq-\rho_{23}+1-\rho_{12}$ (81)
$\displaystyle\rho_{13}\geq\rho_{23}-1+\rho_{12}$ (82)
$\displaystyle\rho_{13}\leq\rho_{23}+1-\rho_{12}$ (83)
$\displaystyle\rho_{13}\geq-\rho_{23}-1+\rho_{12}$ (84)

One can visualize these equations easily, yielding rotated rectangles in the
$\rho_{13},\rho_{23}$ plane for each given $\rho_{12}$ (fixed by the two known
challenges ${\bf\Phi_{1}}$ and ${\bf\Phi_{2}}$. The shapes in Figures 6
indicate which triples are possible, as shown by the linear equations above.
The largest range of possible correlations occurs when $\rho_{12}=0$, i.e. the
first two challenges are uncorrelated. There are many such challenges, exactly
how many is given by for example Figure 6.

##### How many challenges lie at different possible $(\rho_{13},\rho_{23})$
from given challenges with correlation $\rho_{12}$?

To obtain this, we simply evaluate Equations (74) – (78) depending on what
case we are in for each possible $(\rho_{12},\rho_{13},\rho_{23})$ triple.
These yield the different colors in the yellow/blue plots of Figures 6. Notice
that the densities do not depend on the actual values $r_{1},r_{2}$ that the
challenges take on.

##### What prediction accuracies and entropies are possible with different
$(\rho_{12},\rho_{13},\rho_{23})$ triples?

Finally, given that we now know how many challenges there are at different
correlations to one another, the question is how many challenges there are at
different prediction accuracies or entropies. This is given by Theorem V.1 and
shown in the purplish plots of Figures 4 and 6.

##### Numerical evaluations and interpretations of plots

Algorithms 2–5 in Appendix Algorithms for bin creation allow us to create the
bins $B(d,{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})$ for all possible distance $d$
in the “semimetric” space defined by the accuracy or the entropies, and then
the Figures 4 and 6. We now present some numerical evaluations to provide an
understanding of the similarity bins when we know 2 challenges and wish to
understand how many challenges lie at different distances to these two. To do
so, we illustrate the following three questions:

  1. 1.

Which correlations $\rho_{13}$ and $\rho_{23}$ are possible given $\rho_{12}$?
This is given by the shape in Figures 6–LABEL:fig:all_fig2 which depict
equations (81) – (84).

  2. 2.

What prediction distances are possible with different
$(\rho_{12},\rho_{13},\rho_{23})$ triples? This is given by Theorem V.1 and is
given by the purplish plots of Figures 4,6 and LABEL:fig:all_fig2.. The
accuracy and entropies do depend on the actual values of the responses as well
as the correlations. This may be intuitively thought of as follows: if the two
challenges we know are well “aligned”, i.e. when $r_{1}\cdot
r_{2}\cdot\text{sign}(\rho_{12})=+1$ this means the challenges have the same
response and are highly correlated then they act more like one challenge with
respect to the third one. Otherwise the information provided by the two
challenges when $\rho_{12}$ negative, $r_{1}=r_{2}$ is somewhat contradictory,
then information is neutralized for $\rho_{13}=\rho_{23}$. The “blue line” on
the accuracy graphs shows where the information is neutralised: line $y=-x$ if
$r_{1}=r_{2}$, $y=x$ if $r_{1}\neq r_{2}$.

  3. 3.

How many challenges lie at different possible $(\rho_{13},\rho_{23})$ from
given challenges with correlation $\rho_{12}$? This is given by equations (74)
– (78) and is given by the blue/yellow plots of Figures 6.

##### Expected conditional entropy and accuracy of a challenge’s response

Knowing the values of the entropies and accuracy in each neighborhood as well
as the number of challenges in all of them. we can compute the expected
conditional entropy and accuracy of a challenge’s response. Calling $d_{i}$
the distance in $B(d_{i},{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})$ in the entropy
or accuracy space and $n^{2}$ the maximum number of different neighborhoods
knowing that if one is not possible then
$|B(d_{i},{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})|=0$. The expected semi-metric
$\bar{d}$ is then given as follows:

$\bar{d}=\frac{1}{\\#\text{possible
challenges}}\sum_{i=1}^{n^{2}}d_{i}|B(d_{i},{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})|.$
(85)

Table II shows the different expected conditional entropy and accuracy of a
challenge’s response in function of the correlation $\rho_{12}$ between the
two anchors and the number of stages of the PUF, $n$.

There is quite a bit of information packed into these Figures. Some things to
note include: highly predictable challenges have the yellow color in the left
(a) plots: they tend to be around the edges and there are relatively few of
them. Less predictable challenges are found along the dark blue/purplish lines
in the left (a) plots and there tend to be many of them. However, sometimes we
can see large clumps (density plots are greenish) that are also reasonably
well predicted (pinkish). Overall, the hope is that such plots will be useful
to PUF protocol design engineers to give them an idea of the landscape of
challenges: how many there are at different prediction accuracies or
conditional response entropies once one or two challenges are exposed.

(a) Accuracy : $r_{1}=r_{2}$ and $\rho_{12}=0$

(b) Density : $r_{1}=r_{2}$ and $\rho_{12}=0$

(c) Accuracy : $r_{1}=r_{2}$ and $\rho_{12}=0.5$

(d) Density : $r_{1}=r_{2}$ and $\rho_{12}=0.5$

(e) Accuracy : $r_{1}=r_{2}$ and $\rho_{12}=-0.5$

(f) Density : $r_{1}=r_{2}$ and $\rho_{12}=-0.5$

(g) Accuracy : $r_{1}\neq r_{2}$ and $\rho_{12}=-0.5$

(h) Accuracy : $r_{1}\neq r_{2}$ and $\rho_{12}=0.5$

Figure 6: Accuracy and density plot same and different responses.  | n=32 | n=64 | n=128
---|---|---|---
| $\rho_{12}=-0.5$ | $\rho_{12}=0$ | $\rho_{12}=0.5$ | $\rho_{12}=-0.5$ | $\rho_{12}=0$ | $\rho_{12}=0.5$ | $\rho_{12}=-0.5$ | $\rho_{12}=0$ | $\rho_{12}=0.5$
H-min | 0.8259 | 0.8329 | 0.8450 | 0.8728 | 0.8788 | 0.8879 | 0.9080 | 0.9127 | 0.9194
H-Shannon | 0.9798 | 0.9815 | 0.9842 | 0.9898 | 0.9908 | 0.9922 | 0.9948 | 0.9954 | 0.9961
Accuracy | 0.5663 | 0.5634 | 0.5584 | 0.5472 | 0.5448 | 0.5413 | 0.5335 | 0.5317 | 0.5292
TABLE II: Expected conditional entropies and accuracies of a challenge’s
response knowing two CRPs

##  VI Conclusion

We have presented two new tools for understanding and exploiting the CRP
correlations of APUF (and by almost immediate extension, compute then
entropy). The first is the response similarity, or the probability that two
challenges yield the same response, which is a function of the challenges
themselves. This may be used to optimally predict the response to one
challenge given the response to another challenge, and to obtain the
conditional response entropy, The second is the derivation of a simple
algorithm for enumerating the similarity bins, or entropy bins to a given
challenge, i.e. all challenges that have the same response similarity or
conditional response entropy to a given anchor challenge. In combination,
these form a powerful tool for understanding the CRP landscape: how CRPs are
correlated and may be used to obtain statistical properties of linear-
threshold-based PUFs.

## Declarations

  * •

Ethical Approval: This work is original and has not been published elsewhere,
nor is it currently under consideration for publication elsewhere.

  * •

Competing interests: The authors have no relevant financial or non-financial
interests to disclose.

  * •

Authors’ contributions: All authors contributed to the study conception and
design. Material preparation, simulations and analysis were performed by
Vincent Dumoulin, Natasha Devroye and Wenjing Rao. The first draft of the
manuscript was written by Vincent Dumoulin and Natasha Devroye then all
authors commented on previous versions of the manuscript. All authors read and
approved the final manuscript.

  * •

Funding: This work was supported by the National Science Foundation under
award 2217023 and 2244479.

  * •

Data: No exterior data set is used. All simulations and plots are derived
based on the statistical models, equations and pseudo algorithms presented in
the paper.

## References

  * [1] W. Che, F. Saqib, and J. Plusquellic, “Puf-based authentication,” in _2015 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)_ , Nov 2015, pp. 337–344.
  * [2] B. Gassend, D. Clarke, M. van Dijk, and S. Devadas, “Silicon physical random functions,” _9th ACM Conference on Computer and Communication Security_ , 2002.
  * [3] L. Feiten, M. Sauer, and B. Becker, “On metrics to quantify the inter-device uniqueness of PUFs,” Cryptology ePrint Archive, Paper 2016/320, 2016. [Online]. Available: https://eprint.iacr.org/2016/320
  * [4] Y. Hori, T. Yoshida, T. Katashita, and A. Satoh, “Quantitative and statistical performance evaluation of arbiter physical unclonable functions on fpgas,” _Int. Conf. on Reconfigurable Computing and FPGAs_ , pp. 298–303, 2010.
  * [5] Rukhin, A. et al., “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications,” 2010.
  * [6] M. Majzoobi, M. Rostami, F. Koushanfar, D. S. Wallach, and S. Devadas, “Slender puf protocol: A lightweight, robust, and secure authentication by substring matching,” in _Security and Privacy Workshops (SPW), 2012 IEEE Symposium on_. IEEE, 2012, pp. 33–44.
  * [7] M. Rostami, M. Majzoobi, F. Koushanfar, D. S. Wallach, and S. Devadas, “Robust and reverse-engineering resilient puf authentication and key-exchange by substring matching,” _IEEE Transactions on Emerging Topics in Computing_ , vol. 2, no. 1, pp. 37–49, 2014.
  * [8] Y. M.-D. et al., “A noise bifurcation architecture for linear additive physical functions,” in _2014 IEEE International Symposium on Hardware-Oriented Security and Trust (HOST)_. IEEE, 2014, pp. 124–129.
  * [9] J. Delvaux, R. Peeters, D. Gu, and I. Verbauwhede, “A survey on lightweight entity authentication with strong pufs,” _ACM Comput. Surv._ , vol. 48, no. 2, Oct. 2015. [Online]. Available: https://doi.org/10.1145/2818186
  * [10] M. Majzoobi, F. Koushanfar, and M. Potkonjak, “Lightweight secure pufs,” in _2008 IEEE/ACM International Conference on Computer-Aided Design_ , Nov 2008, pp. 670–673.
  * [11] ——, “Testing techniques for hardware security,” in _2008 IEEE International Test Conference_ , Oct 2008, pp. 1–10.
  * [12] J. Delvaux, “Machine-learning attacks on PolyPUFs, OB-PUFs, RPUFs, LHS-PUFs, and PUFÐFSMs,” _IEEE Transactions on Information Forensics and Security_ , pp. 1–1, 2019.
  * [13] P. H. Nguyen, D. P. Sahoo, R. S. Chakraborty, and D. Mukhopadhyay, “Security analysis of arbiter puf and its lightweight compositions under predictability test,” _ACM Trans. Des. Autom. Electron. Syst._ , vol. 22, no. 2, pp. 20:1–20:28, Dec. 2016. [Online]. Available: http://doi.acm.org/10.1145/2940326
  * [14] O. Rioul, P. Solé, S. Guilley, and J.-L. Danger, “On the entropy of physically unclonable functions,” in _ProcISIT_ , July 2016, pp. 2923–2932.
  * [15] M.-D. Yu, R. Sowell, A. Singh, D. M’Raïhi, and S. Devadas, “Performance metrics and empirical results of a puf cryptographic key generation asic,” in _HOST_. IEEE, 2012, pp. 108–115.
  * [16] A. Schaub, O. Rioul, and J. J. Boutros, “Entropy estimation of physically unclonable functions via chow parameters,” _2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pp. 698–704, 2019.
  * [17] Frisch, C., Wilde, F., Holzner, T. et al., “A practical approach to estimate the min-entropy in pufs,” _J Hardw Syst Secur_ , vol. 7, pp. 138–146, 2023.
  * [18] Jao, J., Wilcox, I., Thotakura, S. et al.., “An Analysis of FPGA LUT Bias and Entropy for Physical Unclonable Functions,” _J Hardw Syst Secur_ , vol. 7, p. 110–123, 2023.
  * [19] Y. Lao and K. K. Parhi, “Statistical analysis of mux-based physical unclonable functions,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 33, no. 5, pp. 649–662, May 2014.
  * [20] W. Che, V. K. Kajuluri, M. Martin, F. Saqib, and J. Plusquellic, “Analysis of entropy in a hardware-embedded delay puf,” in _Cryptography_ , Jun. 2017.
  * [21] W. Stefani, F. Kappelhoff, M. Gruber, Y.-N. Wang, S. Achour, D. Mukhopadhyay, and U. Rührmair, “Strong PUF security metrics: Sensitivity of responses to single challenge bit flips,” _Cryptology ePrint Archive, Paper 2024/378_ , 2024.
  * [22] D. Boning and S. Nassif, “Models of process variations in device and interconnect,” _Design of high performance microprocessor circuits_ , p. 6, 2000.
  * [23] J. Tobisch and G. T. Becker, “On the scaling of machine learning attacks on pufs with application to noise bifurcation,” in _Revised Selected Papers of the 11th International Workshop on Radio Frequency Identification - Volume 9440_ , ser. RFIDsec 2015. New York, NY, USA: Springer-Verlag New York, Inc., 2015, pp. 17–31.
  * [24] W. Yeqi, F. Tim, D. Vincent, R. Wenjing, and D. Natasha, “Apuf faults: Impact, testing, and diagnosis,” pp. 442–447, 2022.
  * [25] T. Cover and J. Thomas, _Elements of Information Theory_ , 2nd ed. New York:Wiley, 2006.
  * [26] M. C. Cheng, “The orthant probabilities of four gaussian variates,” _The Annals of Mathematical Statistics_ , vol. 40, no. 1, pp. 152–161, 1969. [Online]. Available: http://www.jstor.org/stable/2239206
  * [27] J. Massey, “Guessing and entropy,” in _ProcISIT_ , Jul 1995, p. 204.

## Algorithms for bin creation

Algorithm 1 builds a similarity bin. For a different “semimetric”, use the
theoretical results or the graph in Figure 2 to get the two ${\bf
s}=(s_{1},s_{2})$ factors that will give you the desired value/ create a
similarity bin for each $s_{i}$ (two similarity factors for entropy and
accuracy). Form the union of the two disjoint bins.

Input: anchor ${\bf\Phi},n$, similarity factor(s) ${\bf s}=(s_{1},s_{2})$
derived from a wanted “semimetric" (entropy, accuracy,probability).

Output: Bin $B({\bf s},{\bf\Phi})$.

// initialize

$B\leftarrow\emptyset$

// use $s$ and $\phi_{1}$ to determine $\phi^{\prime}_{1}$.

if  _$s$ mod $1!=0$_ then

$\phi^{\prime}_{1}=-\phi_{1}$ ;

// $s$ even

else

$\phi^{\prime}_{1}=\phi_{1}$ ;

// $s$ odd

/* use $s$ to decide how many of $\phi_{2},\cdots,\phi_{n}$, to flip to
construct $\phi^{\prime}_{2},\cdots,\phi^{\prime}_{n}$. */

$F\leftarrow\\{f|f\in\\{0,1\\}^{n-1},\sum{f_{i}}=\lfloor s\rfloor\\}$

/* $F$ contains all the strings of size $n-1$ with Hamming weight $\lfloor
s\rfloor$, and $f$ encodes where to flip $\phi_{2},\cdots,\phi_{n}$ for
$\phi^{\prime}_{i}$’s */

for  _$f\in F$ _ do

for  _i = 2 to n_ do

if  _$f_{i-1}==0$_ then

$\phi^{\prime}_{i}=\phi^{\prime}_{i}$

else

$\phi^{\prime}_{i}=-\phi^{\prime}_{i}$

${\bf\Phi^{\prime}}\leftarrow(\phi^{\prime}_{1},\phi^{\prime}_{2},\cdots,\phi^{\prime}_{n},+1)$

$B\leftarrow B\bigcup\\{{\bf\Phi^{\prime}}\\}$

return _$B$_ // This is $B({\bf s},{\bf\Phi})$

Algorithm 1 Bin construction for one anchor:

Input: Anchors ${\bf\Phi_{1},\Phi_{2}}$ and responses $r_{1}$ $r_{2}$

Output: Similarity bins of size $m$ for all possible distance $d$ :
$B(d,{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})$

// initialize: look for the bits to select

for  _$|S_{12}|=1$ to $n$ _ do

for  _$|S_{13}|=1$ to $n$_ do

for  _$|S_{23}|=1$ to $n$_ do

${\bf K}\leftarrow(|S_{13}|+|S_{23}|+|S_{12}|-n)/2$;

if  _$\Phi_{1,1}=\Phi_{2,1}$_ then

CBSS$({\bf\Phi_{1},\Phi_{2}},\,r_{1},\,r_{2},\,|S_{12}|,\,|S_{13}|,\,|S_{23}|)$

if  _$\Phi_{1,1}\neq\Phi_{2,1}$_ then

CBDS$({\bf\Phi_{1},\Phi_{2}},\,r_{1},\,r_{2},\,|S_{12}|,\,|S_{13}|,\,|S_{23}|)$

else Ignore // Challenge does not exist

return _$B(d,{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})$ for all distances $d$_

Algorithm 2 Bin construction with two anchors

Algorithm 3 builds a third challenge at a distance $d$ in a the chosen
“semimetric” space (accuracy or entropy space). Algorithms 2-5 create the bins
using the previous algorithm.

Input: Anchors ${\bf\Phi_{1},\Phi_{2}}$, responses $r_{1}$ $r_{2}$,
$|S_{12}|,\,|S_{13}|,\,|S_{23}|,\,\Phi_{3,1}$

Output: a challenge ${\bf\Phi_{3}}$ with a desired distance d

// construct $\Phi_{3}$ from $\rho_{12},\,\rho_{13},\,\rho_{23}$ we know
$\Phi_{1,1}\stackrel{{\scriptstyle?}}{{=}}\Phi_{2,1}\stackrel{{\scriptstyle?}}{{=}}\Phi_{3,1}$

${\bf K}\leftarrow(|S_{13}|+|S_{23}|+|S_{12}|-n)/2$

if  _$\Phi_{1,1}=\Phi_{2,1}=\Phi_{3,1}$_ then

if  _${\bf K}\in\mathbb{N}$_ then

Fix: the first bit and ${\bf K}-1$ other bits in $S_{12}$

Flip: all other bits in $S_{12}$

Fix: any $|S_{13}|-K$ bits in $D_{12}$

Flip: all other bits in $D_{12}$

// equivalently fix $|S_{23}|-K$ bits in $D_{12}$, and flip the rest

else

return False

// # of bits to fix is not an integer

else if  _$\Phi_{1,1}=\Phi_{2,1}\neq\Phi_{3,1}$_ then

if  _${\bf K}=x.5$_ then

Fix: any $\lfloor{\bf K}\rfloor$ bits except the 1st bit in $S_{12}$

Flip: all other in $S_{12}$ (including the 1st bit)

Fix: any $|S_{13}|-K$ bits in $D_{12}$

Flip: all other bits in $D_{12}$

// equivalently fix $|S_{23}|-K$ bits in $D_{12}$, and flip the rest

else

return False

else if  _$\Phi_{1,1}\neq\Phi_{2,1}=\Phi_{3,1}$_ then

if  _${\bf K}\in\mathbb{N}$_ then

Use: the first bit of $\Phi_{2,1}$

Fix: any ${\bf K}$ bits in $S_{12}$

Flip: all other bits in $S_{12}$

Fix: any $|S_{23}|-K-1$ bits in $D_{12}$

Flip: all other bits in $D_{12}$

else

return False

// Number of bits to fix is not integer

else if  _$\Phi_{1,1}=\Phi_{3,1}\neq\Phi_{2,1}$_ then

if  _${\bf K}\in\mathbb{N}$_ then

Use: the first bit of $\Phi_{3,1}$

Fix: any ${\bf K}$ bits in $S_{12}$

Flip: all other bits in $S_{12}$

Fix: any $|S_{13}|-K-1$ bits in $D_{12}$

Flip: all other bits in $D_{12}$

else

return False

// Number of bits to fix is not integer

return _$\Phi_{3}$_ // Challenge $\Phi_{3}$ has desired distance

Algorithm 3 CC: Create a 3rd Challenge ${\bf\Phi_{3}}$

Input: Anchors ${\bf\Phi_{1},\Phi_{2}}$, responses $r_{1}$ $r_{2}$,
$|S_{12}|,\,|S_{13}|,\,|S_{23}|$ under $\Phi_{1,1}=\Phi_{2,1}$

Output: $B(d,{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})$ of size $m$

$\rho_{12}=(2|S_{12}|)/n-1$

begin

$\Phi_{3,1}=\Phi_{1,1}$

$\rho_{13}=(2|S_{13}|)/n-1$

$\rho_{23}=(2|S_{23}|)/n-1$

$\\#\text{of challenges }={|S_{12}|-1\choose
K-1}{n-|S_{12}|\choose|S_{13}|-K}$

if  _${\bf K}\in\mathbb{N}\quad\ &\quad\\#\text{of challenges }\geq 0$_ then

$p\leftarrow\frac{1}{2}\left[1+\frac{r_{1}\arcsin{\rho_{13}}+r_{2}\arcsin{\rho_{23}}}{\pi/2+r_{1}r_{2}\arcsin{\rho_{12}}}\right]$

$d_{1}=$ Accuracy(p) or entropy(p)

for  _$i=1$ to $m$_ do

$\Phi_{3}\leftarrow$
CC$({\bf\Phi_{1},\Phi_{2}},\,r_{1},\,r_{2},\,|S_{12}|,\,|S_{13}|,\,|S_{23}|,\,\Phi_{3,1})$

$B(d_{1},{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})\leftarrow
B(d_{1},{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})\bigcup\\{\Phi_{3}\\}$

else Ignore // Challenge does not exist

begin

$\Phi_{3,1}=-\Phi_{1,1}$

$\rho_{13}=(2|S_{13}|+1)/n-1$

$\rho_{23}=(2|S_{23}|+1)/n-1$

$\\#\text{of challenges }={|S_{12}|-1\choose K}{n-|S_{12}|\choose|S_{13}|-K}$

if  _${\bf K}\in\mathbb{N}\quad\ &\quad\\#\text{of challenges }\geq 0$_ then

$p\leftarrow\frac{1}{2}\left[1+\frac{r_{1}\arcsin{\rho_{13}}+r_{2}\arcsin{\rho_{23}}}{\pi/2+r_{1}r_{2}\arcsin{\rho_{12}}}\right]$

$d_{2}=$ Accuracy(p) or entropy(p)

for  _$i=1$ to $m$_ do

$\Phi_{3}\leftarrow$
CC$({\bf\Phi_{1},\Phi_{2}},\,r_{1},\,r_{2},\,|S_{12}|,\,|S_{13}|,\,|S_{23}|,\,\Phi_{3,1})$

$B(d_{2},{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})\leftarrow
B(d_{2},{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})\bigcup\\{\Phi_{3}\\}$

else Ignore // Challenge does not exist

return _$B(d_{1},{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})$ ,
$B(d_{2},{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})$_

Algorithm 4 CBSS: Create Bin first bit Same Sign: $\Phi_{1,1}=\Phi_{2,1}$

Input: Anchors ${\bf\Phi_{1},\Phi_{2}}$, responses $r_{1}$ $r_{2}$,
$|S_{12}|,\,|S_{13}|,\,|S_{23}|$ under $\Phi_{1,1}\neq\Phi_{2,1}$

Output: $B(d,{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})$ of size $m$

$\rho_{12}=(2|S_{12}|+1)/n-1$

begin

$\Phi_{3,1}=\Phi_{1,1}$

$\rho_{13}=(2|S_{13}|)/n-1$

$\rho_{23}=(2|S_{23}|+1)/n-1$

$\\#\text{of challenges }={|S_{12}|\choose K}{n-|S_{12}|\choose|S_{13}|-K-1}$

if  _${\bf K}\in\mathbb{N}\quad\ &\quad\\#\text{of challenges }\geq 0$_ then

$p\leftarrow\frac{1}{2}\left[1+\frac{r_{1}\arcsin{\rho_{13}}+r_{2}\arcsin{\rho_{23}}}{\pi/2+r_{1}r_{2}\arcsin{\rho_{12}}}\right]$

$d_{1}=$ Accuracy(p) or entropy(p)

for  _$i=1$ to $m$_ do

$\Phi_{3}\leftarrow$
CC$({\bf\Phi_{1},\Phi_{2}},\,r_{1},\,r_{2},\,|S_{12}|,\,|S_{13}|,\,|S_{23}|,\,\Phi_{3,1})$

$B(d_{1},{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})\leftarrow
B(d_{1},{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})\bigcup\\{\Phi_{3}\\}$

else Ignore // Challenge does not exist

begin

$\Phi_{3,1}=\Phi_{2,1}$

$\rho_{13}=(2|S_{13}|+1)/n-1$

$\rho_{23}=(2|S_{23}|)/n-1$

$\\#\text{of challenges }={|S_{12}|\choose K}{n-|S_{12}|\choose|S_{23}|-K-1}$

if  _${\bf K}\in\mathbb{N}\quad\ &\quad\\#\text{of challenges }\geq 0$_ then

$p\leftarrow\frac{1}{2}\left[1+\frac{r_{1}\arcsin{\rho_{13}}+r_{2}\arcsin{\rho_{23}}}{\pi/2+r_{1}r_{2}\arcsin{\rho_{12}}}\right]$

$d_{2}=$ Accuracy(p) or entropy(p)

for  _$i=1$ to $m$_ do

$\Phi_{3}\leftarrow$
CC$({\bf\Phi_{1},\Phi_{2}},\,r_{1},\,r_{2},\,|S_{12}|,\,|S_{13}|,\,|S_{23}|,\,\Phi_{3,1})$

$B(d_{2},{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})\leftarrow
B(d_{2},{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})\bigcup\\{\Phi_{3}\\}$

else Ignore // Challenge does not exist

return _$B(d_{1},{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})$ ,
$B(d_{2},{\bf\Phi_{1},\Phi_{2}},r_{1},r_{2})$_

Algorithm 5 CBDS: Create Bin first bit Different Sign:
$\Phi_{1,1}\neq\Phi_{2,1}$