# Quantum Lock: A Provable Quantum Communication Advantage

Kaushik Chakraborty<EMAIL_ADDRESS>School of Informatics,
University of Edinburgh, Edinburgh, UK  Mina Doosti<EMAIL_ADDRESS>School of Informatics, University of Edinburgh, Edinburgh, UK  Yao Ma
<EMAIL_ADDRESS>Laboratoire d’Informatique de Paris 6 (LIP6), Sorbonne
Université, Paris, France  Chirag Wadhwa<EMAIL_ADDRESS>Indian
Institute of Technology Roorkee, India  Myrto Arapinis<EMAIL_ADDRESS>School of Informatics, University of Edinburgh, Edinburgh, UK  Elham Kashefi
<EMAIL_ADDRESS>School of Informatics, University of Edinburgh,
Edinburgh, UK  Laboratoire d’Informatique de Paris 6 (LIP6), Sorbonne
Université, Paris, France

###### Abstract

Physical unclonable functions (PUFs) provide a unique fingerprint to a
physical entity by exploiting the inherent physical randomness. In the review
paper [Nature Electronics, 2020] on the PUF technology, Gao _et al._ discussed
the vulnerability of most current-day PUFs to sophisticated machine learning-
based attacks, highlighting the design of provably secure PUF as an important
open problem. By integrating classical PUFs, together with existing quantum
communication technology, we address this problem. Specifically, this paper
proposes a generic design of provably secure PUFs, called _hybrid locked PUFs_
(HLPUFs), providing a practical solution for securing classical PUFs. An HLPUF
uses a classical PUF (CPUF), and encodes the output into non-orthogonal
quantum states (namely BB84 states, which are widely used for quantum key
distribution) for hiding the outcomes of the underlying CPUF from any
adversary. Similar to the classical _lockdown_ technique [TMSCS, 2016], here
we introduce a _quantum lock_ , to protect the HLPUFs from any general
adversaries. The indistinguishability property of the non-orthogonal quantum
states, together with the quantum lockdown technique prevents the adversary
from accessing the outcome of the CPUFs. We show that, for quantum polynomial-
time adversaries, the ratio between the forging probabilities of the HLPUF,
and the underlying CPUF is upper bounded by the distinguishing probabilities
of those non-orthogonal states that decay exponentially in the number of
output bits of the CPUF. Moreover, we show that by exploiting non-classical
properties of quantum states, the HLPUF allows the server to reuse the
challenge-response pairs for further client authentication. This result
provides an efficient solution for running PUF-based client authentication for
an extended period while maintaining a small-sized challenge-response pairs
database on the server side. Later, we support our theoretical contributions
by instantiating the HLPUFs design using accessible real-world CPUFs, called
XOR-PUFs. We use the optimal classical machine-learning attacks to forge both
the CPUFs and HLPUFs, and we certify the security gap in our numerical
simulation for a construction which is ready for implementation.

Hardware Security and Physical Unclonable Functions and Quantum Cryptography

††preprint: APS/123-QED

##  I Introduction

The recent advances in the development of quantum internet and both short-
distance and long-distance quantum networks have enabled a broad range of
applications from simple secure communication to advanced functionalities such
as delegated quantum computation. Many of these applications are out of reach
for classical networks [9, 61, 22, 59, 42, 19, 21, 31, 12, 13, 58].
Nevertheless, the search for other useful and implementable applications of
quantum internet, and quantum communication in general, is a very active area
of research. A common essential security feature for most such applications is
the ability of secure authentication. In general, _authentication_ is captured
by different definitions and security levels, and plays a central role in
establishing secure communications over untrusted channels [2, 18, 10]. And in
particular, _entity authentication_ , also known as _device authentication_ or
_identification_ is a crucial, fundamental and yet a challenging and mostly
unsolved task [32, 27]. This sets authentication and identification as good
candidates for practical applications of quantum internet.

Among various approaches for authentication and identification, hardware
security provides a promising paradigm for solving such problems through
exploiting the underlying properties of hardware and physical devices. In this
context, Physically Unclonable Functions (PUFs) are a full of potential
technology that can establish trust in embedded systems without requiring any
_non-volatile memory_ (NVM) [24, 25, 36]. A PUF derives unique volatile secret
keys on the fly by exploiting the inherent random variations introduced by the
manufacturing processes of the _integrated circuits_ (ICs). Any slight (yet
unavoidable and uncontrollable) variation in the manufacturing process
produces a different PUF, rendering the fabrication of an identical physical
‘clone’ of a PUF [44] infeasible. Hence, PUFs provide copy-proof, cost-
efficient unique hardware fingerprints. Usually, one can generate such
fingerprints just by querying the PUF physically. In the literature, we refer
to the query and response pairs as _challenge-response pairs_ (CRPs). Due to
the uniqueness of these devices, different PUFs generate different CRPs.

The literature on classical PUFs (CPUFs) is rich, and there is a multitude of
constructions available based on different hardware technologies [25, 26, 33].
We refer to [45] for a detailed review of the available constructions of
classical PUFs. Although all of those constructions provide unique and
inexpensive hardware fingerprints, they all suffer from providing sufficient
randomness. As a result, most of the existing CPUF constructions are
vulnerable against machine learning modeling-based attacks [7, 6, 16, 48, 47].
In these types of attacks, the attacker first collects a sufficient number of
CRPs by adaptively querying the PUF and then uses that data to derive a
numerical model using the tools from machine learning. Here, the goal of the
model is to predict the response of the PUF to an arbitrary challenge. These
attacks open multiple new research directions on designing machine learning-
based attack resilient PUFs [41, 54]. In the classical domain, there are a few
proposals to prevent such sophisticated attacks, such as the _lockdown
technique_ [65], which prevents the adversary from adaptively querying the
CPUF. However, all of the previous works have a heuristic nature, and none of
the solutions provides _provable security_ for CPUFs or PUF-based
authentication protocols. On the other hand, in recent years, there has been a
line of research suggesting to exploit quantum mechanical features of certain
devices to design secure PUFs, known in the literature as quantum PUFs [1,
34]. Although these proposals provide provable security against quantum
machine learning attacks, they are challenging to realise with current-day
quantum technologies.

In this work, we introduce a new use-case of quantum communication, with
provable advantages in several aspects: A new PUF construction and a novel
quantum entity authentication protocol that exploits the combination of
hardware assumptions and quantum information to achieve secure authentication
with provable exponential security advantage compared to its classical
counterparts. We also formally prove that the protocol fulfils a specific
desired property, namely, _challenge reusability_ , which is impossible unless
using quantum communication, emphasizing the significance of quantum
communication technology and quantum network for a new quantum security era.
Moreover, we show that quantum communication makes our construction _cheat-
sensitive_ , i.e., our PUF-based authentication protocol can detect the
adversarial attempts (both passive and active) on intercepting the responses
of the PUF. We aim to keep our construction implementable using present-day
quantum communication technologies while exploiting the desirable security
promises that are provided due to the quantum nature of the challenges and
responses. Our PUF construction utilises classical PUFs, which are too weak to
be useful in a standalone manner, but present the advantage of being widely
accessible and easy to use, and enhances their security using commercially
available tools from quantum communication. Here for the first time, we show
that by encoding the output of classical PUFs into non-orthogonal qubits, one
can enhance the security of PUFs against weak (non-adaptive) adversaries. As
such, the first building block of our design is a construction we refer to as
_hybrid PUFs_ (HPUFs), which encompasses a classical PUF and produces quantum
responses for classical challenges. We prove that this construction provides
security against the mentioned adversary. With this gadget at hands we then
introduce a construction that is secure against more powerful adaptive quantum
adversaries (the general class of quantum polynomial-time (QPT) adversaries).
To this end, we borrow the idea of the classical lockdown technique and, by
redefining it in the quantum setting, we present our final construction,
namely _hybrid locked PUF_ (HLPUF). We show that classical PUFs combined with
quantum encoding and the new lockdown toolkit can considerably boost the
security of classical PUF without too much overhead. An important
technological improvement compared to previous quantum-enhanced proposals
where quantum memory was necessary is that for both HPUFs and HLPUFs, only a
classical database of challenge-response pairs needs to be stored on the
verifier’s side. We formally prove adversarial bounds on the unforgeability of
HLPUFs in comparison with the underlying classical PUFs, using rigorous proof
techniques from quantum information theory. We also formally prove the
security of our HLPUF-based device authentication protocol under realistic
assumptions.

In addition to our theoretical contributions, to better demonstrate the
applicability and strength of our results, we provide simulations for the
design of HPUF constructions with underlying silicon CPUFs instantiated by the
_pypuf_ python-based library [62]. Furthermore, we simulate machine-learning-
based modelling attacks on HLPUFs where an adversary acquires classical
challenges and quantum-encoded responses from an HLPUF. Our simulation results
assist in demonstrating our theoretical proofs by evidencing the security
enhancement from CPUFs to HLPUFs. Another significance of our simulation
results is that they certify the practicality, and security of our
construction, even beyond the scope of the proven theorems, in a real-world
scenario, as the CPUFs used in our simulations are commercially available and
not only theoretical models. We also bring forward practical proposals to
further improve the quality of such constructions.

Finally, through studying this construction, we will also address a long-
standing open problem in the field of PUF-based authentication, which is the
reusability of challenge-response pairs stored in the verifier database. One
significant drawback of PUF-based authentication protocols is that the
server/verifier cannot use the same challenge multiple times to authenticate a
client/prover due to man-in-the-middle attacks. Therefore, the server exhausts
all the challenges from the database after running several rounds of the
authentication protocol. This limitation is unavoidable in classical PUF-based
protocols. However, we show that due to the entropy uncertainty principle in
quantum information theory, with our proposed construction, the server can
reuse a challenge as long as they can successfully authenticate the client
using that challenge in the previous rounds. Our result overcomes this open
problem as we prove for the first time the challenge reusability of PUF-based
applications. The entropy uncertainty principle also allows the honest
server/client to detect any adversarial attempts on extracting information
from the response of the HPUFs, providing the cheat sensitivity of our
protocol.

##  II Our Results

We first present the construction of HLPUFs discussing our theoretical results
_w.r.t._ their security and showing a provable method of securing classical
PUFs, using quantum communication. This result, as mentioned, provides a novel
provable advantage that is only achievable using quantum communication. Then
we introduce our HLPUF-based authentication protocol. In addition to
discussing the security of the protocol, we also show a unique property of
such protocols, namely challenge-reusability, which cannot be realised purely
classically under similar assumptions. Lastly, we exhibit our theoretical
results in practice through simulations, while stepping even closer to
practice by using our construction to secure one of the most commercially
available and cheap existing PUFs.

###  II.1 Construction of Hybrid Locked PUF (HLPUF)

The core idea of our HLPUF construction is to hide the outcome of the
classical PUF inside quantum states and prevent the adversary from
implementing adaptive strategies or getting multiple copies of output quantum
states using the quantum lock. The underlying component of our construction is
a gadget which we name _Hybrid PUF_ (HPUF). HPUF is the part that protects the
output interface of the classical PUF by encoding the classical outcomes in
non-orthogonal states. Thus, an HPUF is a device with classical bit-string as
input and encoded quantum states as output.

####  II.1.1 Construction of the HPUFs

The construction uses a classical PUF
$f\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{2m}$
with $2m$ outcome bits. From the $2m$ output bits we construct $m$-pairs of
bits. One example of such construction is to take the ($2j-1$)-th, and the
$2j$-th (where $1\leq j\leq m$) output bits, and make a pair. Next, we define
a two-to-one mapping of the tuple $(y_{2j-1},y_{2j})$ (where $1\leq j\leq m$)
of $f$’s outcome to a qubit
$|\psi^{j}_{\mathrm{out}}\rangle\in\\{|0\rangle,|1\rangle,|+\rangle,|-\rangle\\}$.
Here, $|+\rangle=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, and
$|-\rangle=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Therefore, the HPUF
receives a classical query and produces a quantum state as a response. Figure
1 illustrates the HPUF construction. For a more formal description of the
construction, we refer to Construction 1 in the supplementary materials.

Figure 1: HPUF Construction with Conjugate Coding

Intuitively, to forge the HPUF, the adversary needs to extract the classical
outcome of each challenge from a series of quantum states produced by the
HPUF. The task reduces to extracting information on all the two-bit outcomes
of the classical PUF (say $(2j-1,2j)$-th bits) from each quantum state
$|\psi^{j}_{\mathrm{out}}\rangle$. Thus the adversary needs to distinguish
between four non-orthogonal states $\\{\ket{0},\ket{1},\ket{+},\ket{-}\\}$,
which is possible with a probability at most $p_{\text{guess}}$.
Distinguishing an unknown non-orthogonal quantum state from a pre-determined
set of the state is a well-known problem in quantum information which we
exploit here in a more general way to introduce extra randomness on the
adversary’s extracted database of the underlying classical PUF.

Thus, an adversary trying to break HPUF is forced to run its forgery algorithm
based on an imperfect training database. The adversarial model considered here
assumes that the adversary gets access to a random set of these classical
challenges and quantum responses, where there exist only one copy of each pair
in the adversary’s database. This model is usually referred to as _weak
adversary_. We later upgrade this adversary into a more powerful one, which is
our target most powerful quantum adversary of interest, when introducing the
locking mechanism of the construction.

Due to the probabilistic nature of this extraction process, the extra
randomness, captured by probability $p_{\text{guess}}$, enhances the security
of the HPUF against weak quantum adversaries as they require considerably more
challenge-response pairs to forge the HPUF. We refer to this specific forgery
attack as _measure-then-forge_ strategy. This attack is illustrated in Figure
4. Our first result in Lemma 2 (see supplementary materials) shows that
measure-then-forge is an optimal forging strategy for this problem.

Given a set of $q$ random classical challenge and quantum response pairs, the
adversary needs to extract _enough_ classical information to forge the HPUF
with the most optimal forging algorithm. We assume that for a successful
forgery, the adversary needs to extract the outcome of the CPUF from at least
$(1-\varepsilon)q$ responses, where $0\leq\varepsilon\leq 1$. The value of
$\varepsilon$ depends mainly on the quality of the CPUF and the noise
tolerance of the machine-learning algorithm. The calculation of the
$\varepsilon$ parameter is being discussed in Section III.

Figure 2: HLPUF Construction. HLPUF uses an HPUF, a single-qubit quantum
encoder device and a single-qubit measurement device, all inside a tamper-
proof environment which prevents any quantum adversary to adaptively query the
HPUF.

To derive one of our central results, i.e. the quantum advantage brought by
the HPUF construction, we prove an exponential gap between the success
probabilities of optimal forgery attack on CPUF and HPUF. Let
$P^{\text{classical}}_{\text{forge}}$ denote the probability of forging the
CPUF using $q$ challenge-response pairs from the CPUF. We derive the following
result, which is formally presented in Theorem 2 and Lemma 3.

Security Result 1: The forging probability of HPUF, denoted as
$p^{\text{quantum}}_{\text{forge}}$, is upper bounded by the following
quantity.

$p^{\text{quantum}}_{\text{forge}}\leq p_{\text{extract}}\times
P^{\text{classical}}_{\text{forge}}.$ (1)

where the $p_{\text{extract}}$ probability itself is bounded as:

$p_{\text{extract}}\leq\sum_{k=(1-\varepsilon)q}^{q}\binom{q}{k}(p_{\text{guess}})^{2mk}(1-(p_{\text{guess}})^{2m})^{q-k},$
(2)

Here, $p_{\text{guess}}$ is the probability of guessing a single bit outcome
of the CPUF from a single qubit outcome of the HPUF. As an important remark,
we note that the classical forging probability,
$P^{\text{classical}}_{\text{forge}}$, is not a small value, given that the
CPUF can be broken with a large enough number of queries. Therefore, the term
$p_{\text{extract}}$ is responsible for the exponential gap between the
security of HPUF and CPUF and consequently highlights the role of the quantum
encoding in deriving this quantum advantage result.

The $p_{\text{guess}}$ probability itself is upper bounded (calculated in
Lemma 1) as follows as a function of a parameter $0.5\leq p\leq 1$, which
quantifies the randomness of the underlying CPUF.

$p_{guess}\leq p(1+\sqrt{2}p),$ (3)

If $p_{\text{extract}}$ decays exponentially with the number of output bits of
the HPUF, i.e., $m$ then $p_{\text{forge}}^{\text{quantum}}$ would be
exponentially smaller than the success probability of CPUF forgery
$p_{\text{forge}}^{\text{classical}}$. One can observe that for a smaller
value of $\varepsilon$ (See Figure 10 in the supplementary materials),
$p_{\text{extract}}$ decays exponentially with $m$, showing an exponential
separation in the security between the HPUF, and the CPUF. To conclude, we
give concrete security bound for HPUF based on its underlying insecure CPUF.

####  II.1.2 Quantum Lock on the HPUFs

Next, in order to prove full quantum security of our construction, we need to
uplift the previously considered weak adversary into any general _adaptive_
quantum adversary. An adaptive quantum adversary is free to build their
database with any arbitrary query and in an adaptive manner, potentially
depending on the previous queries111Note that here we don’t allow
superposition queries to the underlying CPUF inside the HLPUF. However, we
allow the adversaries to run quantum algorithms on the challenge-response pair
database.. Particularly such adversaries can query HPUF multiple times with
the same challenge $x$, obtaining several copies of
$|\psi_{\mathrm{out}}\rangle$ and can easily extract the outcome $f(x)$ from
multiple copies. Consequently, a probability $p_{\text{guess}}\approx 1$ can
be achieved in theory, and a strong adversary can forge the HPUF efficiently.
Hence the construction of HPUFs on its own is not sufficient to achieve the
most compelling desired notion of quantum security.

To complete our construction, we equip it with a mechanism called _quantum
lock_ , which ensures security against general adaptive adversaries. The
quantum lock is a mechanism that allows both parties to partially authenticate
each other by having access to embedded small verification resources. As a
result, it restricts the adversary from adaptively querying the device and
reduces a powerful quantum polynomial time (QPT) adversary to a weak
adversary.

We start by subdividing the output of the HPUF
$\mathcal{E}_{f}\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow(\mathcal{H}^{2})^{\otimes
2m}$ corresponding to a classical PUF
$f\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{4m}$
into two different parts. The first part contains the first $m$ qubits, and
the second half contains the last $m$ qubits of the outcome of the HPUF
$\mathcal{E}_{f}$. Note that, the first $m$ qubits of the HPUF’s outcome comes
from the first $2m$ bits outcome of the underlying classical PUF $f$. For any
challenge $x\in\\{0,1\\}^{n}$ we can write the outcome of the classical PUF as
$f(x)=f_{1}(x)||f_{2}(x)$, where the mapping
$f_{1}\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{2m}$
denotes the first $2m$ bits of $f$ and
$f_{2}\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{2m}$
denotes the last $2m$ bits of $f$. Similarly, we can rewrite the HPUF
$\mathcal{E}_{f}$ as a tensor product of two mappings
$\mathcal{E}_{f_{1}}\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow(\mathcal{H}^{2})^{\otimes
m}$, and
$\mathcal{E}_{f_{2}}\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow(\mathcal{H}^{2})^{\otimes
m}$, where for any challenge $x\in\\{0,1\\}^{n}$, $\mathcal{E}_{f_{1}}(x)$
denotes the first $m$ qubits of $\mathcal{E}_{f}(x)$, and
$\mathcal{E}_{f_{2}}(x)$ denotes the last $m$ qubits of $\mathcal{E}_{f}(x)$.

The hybrid locked PUF, takes the classical input $x_{i}$ and a quantum state
$\tilde{\rho}_{1}$ and produces the second half of the response of the hybrid
PUF, $\ket{\psi_{f_{2}(x_{i})}}\bra{\psi_{f_{2}(x_{i})}}$, as an output if
$\tilde{\rho}_{1}$ is equal to the first half of the output of the hybrid PUF
$\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}}$. Figure 2 illustrates the
construction of HLPUF.

Figure 3: HLPUF-based authentication protocol. In each authentication round,
the verifier (server) uses a classical database and a quantum encoder to
create the required form of challenge for HLPUF which consists of two parts:
the classical challenge $x$, and the quantum state $\ket{\psi_{f_{1}(x)}}$,
constructed based of the first half of the classical response, stored in the
database. Then the verifier sends them through a public channel fully
controlled by a quantum adversary, as illustrated in the figure. The prover
(client) then inputs this two-part challenge into the HLPUF and either
receives the state $\ket{\psi_{f_{2}(x)}}$ or gets a reject outcome and aborts
the protocol, meaning the message did not come from the authentic verifier.
The prover then sends back the quantum state through the same public quantum
channel to the verifier, which will verify the client’s response by measuring
in $y_{3}$ according to the classical database. Recall that here,
$f_{2}(x)=y_{3}y_{4}$. Also, $\tilde{\rho}_{f_{1}(x)}$ and
$\tilde{\rho}_{f_{2}(x)}$ denote the real quantum state received by the prover
and verifier respectively, after the adversary’s interaction with the original
states.

Now we prove the promised security for this construction. Note that we assume
that the adversary does not have any direct access to the outcome of the
embedded classical PUF inside our construction. This assumption can be
satisfied by putting the HLPUF inside a tamper-proof box. Thus under the
assumption that the adaptive adversary has only access to the input/output
ports of the HLPUF, we prove the security of our HLPUF construction, presented
in the following informal theorem. (The formal result and its proof can be
found in Theorem 4 in the supplementary material, )

Security result 2 (Informal): Suppose there is a HLPUF $\mathcal{E}^{L}_{f}$
which is made out of an HPUF
$\mathcal{E}_{f}=\mathcal{E}_{f_{1}}\otimes\mathcal{E}_{f_{2}}$. If both
$\mathcal{E}_{f_{1}}$ and $\mathcal{E}_{f_{2}}$ are secure against $q$-query
weak adversaries then the HLPUF $\mathcal{E}^{L}_{f}$ is secure against any
$q$-query adaptive adversaries.

Intuitively, if an adversary tries to query the HLPUF with any arbitrary
challenge $x$, then they need to produce a correct quantum state
$|\psi_{f_{1}(x)}\rangle$, otherwise, the verification procedure inside the
HLPUF fails, and the HLPUF replies with a garbage output $\perp$. The
inability of the adversary to produce the outcome $|\psi_{f_{1}(x)}\rangle$ is
itself insured via the unforgeability of the HPUF construction, and the _no-
cloning_ principle of the quantum states.

The only remaining option for the adaptive adversary would be to intercept the
challenges sent by the server in the previous rounds and use them to query the
HLPUF. Therefore practically, with the same challenge $x$ they can query the
HLPUF only once. Given that, the server chooses the challenges uniformly at
random from its database, the adversary querying the HLPUF with those
challenges will reduce their power to a weak adversary. As we showed the
security of $\mathcal{E}_{f_{1}}$, and $\mathcal{E}_{f_{2}}$ against the
$q$-query weak adversaries, with the proposed construction, the HLPUF remains
secure against any $q$-query adaptive adversaries.

###  II.2 HLPUF-based Authentication Protocol

Putting our construction into practice, we propose an HLPUF-based
authentication protocol. Figure 3 gives an illustration of the protocol and
the formal description of the protocol is given in the supplementary
materials. In a nutshell, the verifier (server) sends a challenge that
consists of a classical part and a quantum state that will be verified on the
prover’s (client’s) end when queried to the HLPUF device. If the verifier is
successfully authenticated by the HLPUF, it produces the quantum response and
sends it back to the verifier which can use it to authenticate the prover.

Further, we formally prove the completeness and security of our protocol
against adaptive quantum adversaries in the supplementary materials.

Security Result 3: The HLPUF-based authentication protocol shown in Figure 3
is complete and secure (universally unforgeable) against any polynomial-time
adaptive quantum adversary, given that an HLPUF is used according to the
Construction 2, and all the assumptions for the construction are satisfied.

###  II.3 Challenge Reusability and Cheat-Sensitivity

In classical PUF-based authentication protocols, each challenge can be used
only in a single authentication round due to man-in-the-middle attacks. The
problem arises since the adversary can simply copy and record the challenges
and responses and have a perfect copy of the challenger’s database which later
they can use to falsely identify themselves. Therefore, the server needs to
store an enormous database for running the authentication protocol for a long
period. This is a fundamental limitation of classical PUFs [49, 30].

However, we show that HLPUFs provide an efficient and unique solution to this
issue by exploiting the unclonability of the quantum states and the existence
of uncertainty relations in quantum mechanics and quantum information. It
allows the use of the same challenge several times for authentication without
any security compromise. More precisely, each challenge-response pair can be
reused under the circumstance of previous successful authentication rounds.
This solution will resolve the important practical limitation of the
challenger storing a big database or renewing the database of challenge
responses frequently.

First, we clarify the condition under which the challenge can be reused. It is
a straightforward observation that the challenges for which the verification
test has failed should never be used again. A trivial attack, in this case,
would be that the adversary intercepts the communication and stores the
response state, and later when the same challenge has been queried again, will
re-send the stored correct response state to pass the verification. As a
result, all the challenges in the failed rounds should be discarded.

Nonetheless, one of our main results is to show that in the events of
successful authentication, the challenges can be reused. Here, by successful
identification, we mean that the received response state passes the
verification on the client and server-side and both of them are identified as
honest parties. Even though the events of false identification of an
adversary, is still possible (for example, if the challenge is the same as one
of the challenges that previously existed in the adversary’s local database),
our result, stated as follows, ensures that these events occur only with
negligible probability.

Security result 4 (Informal): If the HLPUF-based authentication protocol
(Figure 3) doesn’t abort for a specific challenge $x$, then the probability of
the adversary successfully extracting the classical outcome of the PUF is
upper bounded by $2^{-m}$. Therefore, the challenge $x$ can be reused.

This is an influential information-theoretic result that shows even in the
presence of a powerful quantum adversary, if the challenge-response pair of
HLPUF leads to successful authentication of the honest parties then the
adversary has almost no information about the response $f(x)$ of the
underlying CPUF $f$. We also show that using the same challenge for $k$ times,
if the authentication is passed for all of them, the probability that the
adversary successfully extracts the classical outcome of the PUF is upper
bounded by $k2^{-m}$, which quantifies further this reusability feature. The
results have been formally shown in Theorems 5 and 6 in the supplementary
materials. This feature is uniquely been enabled due to quantum communication
and the specific relation between the quantum states that we use for our
encoding. Our results have been proven using a sophisticated toolkit in
quantum information theory, namely entropic uncertainty relations [17, 11],
which have also been used for the full security proof of famous quantum
protocols such as QKD.

Another relevant feature that our quantum communication-based solution
provides is the cheat-sensitivity, meaning that due to the discussed quantum
properties of our CRPs, a passive adversary trying to intercept and hijack the
communication will be detected.

###  II.4 Our Theoretical Results in Practice: HLPUF’s Resiliency to the
Machine Learning-Based Attacks

We validate and showcase the practicality of our theoretical results for HLPUF
construction using numerical results and simulations. While introducing HPUF
and our security results earlier, we gave a theoretical upper bound on the
forging probability of HPUF. Our theoretical security analysis shows that
exponential security can be achieved for this construction, relying on certain
reasonable assumptions, including the existence of a classical PUF that is not
broken with probability $1$, nonetheless is breakable with non-negligible
probability given enough queries. Although such mid-level classical PUFs can
be theoretically found, especially in optical-based constructions, we focus on
putting our construction to into test using the cheapest and most widely
available CPUFs. We choose silicon CPUFs such as arbiter PUFs for this
purpose, which are known to be weak in security and breakable using machine-
learning attacks. We compare the performance of these CPUFs with an HPUF that
is constructed with the same underlying CPUF, performing measure-then-forge
attacks using classical machine-learning algorithms (see Figure 4 for the
illustration of the attack). The numerical simulation results assist in
demonstrating our theoretical proofs by exhibiting an exponential advantage of
success probability of HPUF forgery compared to its underlying CPUF with a
limited $q$-query.

Here, we instantiate the underlying silicon CPUFs by a python-based library
called _pypuf_ [62]. From the pypuf library, we only consider the XOR Arbiter
PUFs [49] which are timing-based CMOS PUFs of the form
$f\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}$. For
constructing the HPUFs, we need an underlying CPUF with at least two bits
outcome. Therefore, we use two such XOR arbiter PUFs (say $f_{1}$, and
$f_{2}$) for instantiating an HPUF. For the forgery, we use the measure-then-
forge strategy that we define in the HPUF section. As the best measurement
strategy for the measure-then-forge attack, we use the upper bound we derived
on the adversary’s guessing probability of extracting a single bit outcome of
the classical PUF from the outcome of the HPUF (see Lemma 1 in the
supplementary materials). After the measurement phase in the measure-then-
forge strategy, the adversary ends up with a classical database. We use the
classical _logistic regression_ (LR) algorithm for the forgery. Note that, for
the $k$-XOR PUFs, the LR attacks show the best performance. Therefore, we use
the same algorithm in our measure-then-forge strategy. For a more detailed
description of the forgery attack, we refer to Section G in the supplementary
materials. Our numerical results can be categorised into two main
contributions summarized as follows.

####  II.4.1 Advantage over CPUFs

First, our simulation results show a considerable advantage of our
construction over CPUFs, even when constructed from the on-the-counter low-
cost CPFs. We summarize our numerical results on the advantage of HLPUF over
the underlying CPUF in Figures 6 and 6. On each of the plots in these figures,
the $X$-axis denotes the number of CRPs we use for the forgery, and the
$Y$-axis denotes the accuracy of the forgery. The blue curves in each sub-
figure represent the forging accuracy of the underlying CPUF. The red curves
denote the forging accuracy of the HPUF against the general adaptive
adversary, and the green curves denote the forging accuracy of the HLPUFs
against general adaptive adversaries. From these plots, it is evident that
without the quantum lock, the HPUF provides a very small advantage over the
underlying CPUF. This implies that quantum communication alone is not
sufficient in providing a higher security boost. However, the gap between the
blue curve and the green curve in each of the plots of Figures 6 and 6, shows
the importance of the quantum lock for providing a much higher security boost.

The simulation results show that if the adversary has enough challenge-
response pairs from the HLPUF then eventually it can forge the HLPUF. However,
if the adversary tries to forge the HLPUF, then it needs to measure to extract
the classical information from the quantum state, i.e., the outcome of the
HLPUF. This measurement can disturb the quantum state, and if the measurement
is not successful then the authentication also fails. This is something
different from the classical scenario, where the adversary can remain
undetected and make the forgery. We refer to this property as the _cheat-
sensitivity_ of the HLPUFs. Due to this property, we can safely use the HLPUFs
in practice much more times than the prediction of Figures 6 and 6.

Figure 4: Illustration of the measure-then-forge attack. The quantum adversary
receives a sequence of BB84 quantum states as the output of the HPUF and
measures them with the optimal measurement strategy to obtain the underlying
classical information of the responses of CPUF. Due to the quantum nature of
the HPUF responses, even the best measurement strategy is still probabilistic,
which leaves the adversary with a noisy version of the classical database.
Then the adversary can run a machine learning attack on the noisy database (in
the optimal attack, this classical machine-learning algorithm is assumed to be
optimal as well) to extract the mathematical model of the PUF.

Figure 5: Evolution of LR attack performance of CPUF(in blue), HPUF(BB84, in
red for modeling a qubit), and HLPUF(BB84, in green for modeling a qubit) with
different CRPs as training set while the challenge size is 64/128 bits with
k=4 XORPUFs

Figure 6: Evolution of LR attack performance of CPUF(in blue), HPUF(BB84, in
red for modeling a qubit), and HLPUF(BB84, in green for modeling a qubit) with
different CRPs as training set while the challenge size is 64/128 bits with
k=5 XORPUFs Figure 7: Comparison of LR attack performance on HLPUFs with
different underlying CPUFs (left) and different encodings (right) strategies

####  II.4.2 Practical solutions for boosting the security: Better CPUF or
better quantum encoding

In Figure 7 (left), we observe that if we increase the value of $k$ in the
underlying $k$-XOR PUFs, then the adversary requires more challenge-response
pairs for a successful forgery. This observation suggests that one possible
way to enhance the security of the HLPUFs is to use more secure classical
PUFs. In Figure 7 (left), we elaborate the effect of different $k$-values on
the HLPUF forgery. Moreover, the red plot in this figure, also suggests that
one can improve the security of HLPUFs significantly just by increasing the
input size to the HLPUFs.

We also explore another possible way to improve the security of the HLPUFs.
The idea is to use a more sophisticated encoding than encoding two classical
bits into a quantum state $\ket{\psi}$ such that
$\ket{\psi}\in\\{\ket{0},\ket{1},\ket{+},\ket{-}\\}$. Here we use the concept
of Mutually Unbiased Bases (MUBs) [4] of dimension $d=4$ or $d=8$ for the
encoding. For the dimension $d=4$ ($d=8$), we encode four (six) classical bits
to a two (three) qubits quantum state. We describe the encoding procedure in
detail in the supplementary materials (see Section G.2). Intuitively, the
higher dimensional encoding helps to reduce substantially the value of
$p_{\text{guess}}$ in the measure-then-forge strategy significantly. For
example, in Section G.2, for the MUB encoding of dimension $8$, we calculate
the value of $p_{\text{guess}}\leq 0.62$.

In Figure 7 (right), we show the impact of this encoding on the forging
probability. Specifically, we show an interesting simulation result in Figure
8, where we only use $32$-bits input $5$-XOR PUF as an underlying CPUF. For
such CPUFs, the total number of possible challenges is $2^{32}\approx 10^{9}$.
In Figure 8, we observe that the underlying CPUF can be forged using only
$5000$ CRPs. On the other hand, for the forgery of the HLPUFs the adversary
requires almost $10^{6}$ queries. For the forgery of the HLPUF, the adversary
needs to use almost all the CRPs. We can enhance the security of the HLPUFs by
using higher-dimensional MUBs.

Figure 8: Evolution of LR attack performance of classical (in black) and
hybrid (MUB in 8-dimension encoding, in red for modeling 3-qubit)
constructions with different CRPs as training set while the challenge size is
32 bits with k=5 XORPUFs

##  III Discussion

In this paper, we proposed a new practical way to enhance the security of PUFs
using quantum communication technology and showed a new use case for quantum
communication, which benefits from both provability and practicality. We
classify the adversaries into adaptive and weak adversaries based on their
querying capabilities. This classification is not only useful in the proof
reductions but also provides a step-by-step path towards a provably secure PUF
against the strongest possible quantum adversaries. By harnessing the power of
quantum information theory, here we propose a construction of hybrid PUF with
classical challenge and quantum response. The main idea is to encode the
output of classical PUF into non-orthogonal quantum states. We show that for
the forgery of the HPUF, any $q$-query weak adversary first needs to extract
the classical string $f(x)$ from the outcome of the HPUF. The adversary tries
to forge the CPUF using that extracted data. Due to the indistinguishability
of the non-orthogonal quantum states, the adversary introduces extra
randomness at the outcome of the CPUF, which in turn complicates the forging
task for any QPT adversary. We have established the result under the
assumption that for a $q$ random outcomes of the HPUF, if the distance between
the outcomes of CPUF and the extracted outcomes from the HPUF is above a
threshold $\varepsilon$ then no QPT adversary can forge the HPUF. Under this
assumption, we show that the probability of forging the HPUF is exponentially
smaller than forging the CPUF. This is an exponential provable gap which is
only achievable via quantum communication.

We also instantiated our HPUF design using real-world CPUF, called XOR-PUFs.
In Figure 6 and Figure 6, we show the gap in the number of queries the
adversary needs to forge the HPUF compared to the underlying CPUF. As
displayed in those figures, the probability of the HPUFs being fully broken is
considerably small compared to their underlying CPUF. However, using an
enormous number of samples, the adversary eventually forges the HPUF,
certifying the assumption in our theoretical result. A more sophisticated
encoding can enhance this gap. Later in Figure 8, we show that the MUB of
dimension $8$ encoding of the outcome of the CPUFs can enhance this gap
substantially.

In PUF-based authentication protocols, one important issue (both for classical
and quantum PUFs) is that an adaptive adversary can query the PUF with
arbitrary input challenges. It permits such an adversary to learn efficiently
and emulate the input/output behaviour of the targeted PUF. We solve this
problem with our quantum locking mechanism, leading to our HLPUF construction
as discussed. In our proposed authentication protocol, we prove the security
against adaptive adversaries. The advantage is twofold: On one hand, the
probability of knowing information about a quantum state is upper-bounded
compared to a classical PUF due to the quantum information theory. On the
other hand, the implementation of hybrid PUFs is practical nowadays with the
existing quantum communication technology.

Another advantage of the hybrid locked construction is the reusability of the
challenge-response pairs, which was impossible prior to this work for similar
protocols. Therefore, with our solution, a server can perform secure client
authentication for an extended period without exhausting its CRP database.
This result overcomes the fundamental drawbacks of the existing classical PUF-
based authentication protocols while putting forward a novel and practical use
case for our HLPUF construction as well as a unique feature enabled solely by
quantum communication.

The no-cloning property of quantum states also prevents passive adversaries
from intercepting and storing the qubits for forgery without getting detected
by the server/client. Unlike the classical setting, quantum communication
forces all the adversaries to behave like active ones. In general, it is
impossible for adversaries to extract information about the outcome of the
underlying classical PUFs from the outcome of the HLPUFs without getting
detected. This makes our HLPUF protocol cheat sensitive, providing another
advantage over CPUF-based authentication protocols.

The quantum communication part of our HLPUF construction relies on the
conjugate coding, which is used in the quantum key distribution (QKD)
protocols. QKD technology is one of the most mature quantum technologies.
Long-distance QKD networks are already implemented and used in several
countries like the USA, UK, China, EU, Japan, [51, 53, 43, 60, 14] etc. Many
commercially available QKD infrastructures provide almost $300$kb/s secret key
rate over optical fibre links of length $120$km [23]. Moreover, the
availability of the mature QKD on-chip technology [50, 55, 8] makes all the
proposed constructions in this paper implementable using existing quantum
technology. Our results show that picking off-the-shelf classical PUF
technology and QKD technology, can solve all the shortcomings of the device
authentication problem in a quantum network.

In this work, we show that our HLPUF construction makes the current-day
insecure classical PUFs, secure with the help of quantum conjugate coding and
lockdown techniques, and against present and future powerful quantum
adversaries. However, all of our results are based on ideal implementations of
the protocol. The next research direction will be to explore the performance
of our HLPUF-based authentication protocol under channel noise and imperfect
single-photon sources. Yet another intriguing research direction will be the
design of robust variants of our protocol. Like some QKD protocols, our HLPUF
becomes vulnerable to photon number splitting attacks if the source suffers
from a multi-photon emission problem. Therefore, a further study of the
feasibility and practicality of hybrid PUF constructions is an important
future direction for bringing this technology from theory to practice.

## References

  * ADDK [21] Myrto Arapinis, Mahshid Delavar, Mina Doosti, and Elham Kashefi.  Quantum Physical Unclonable Functions: Possibilities and Impossibilities.  Quantum, 5:475, June 2021.
  * AM [17] Gorjan Alagic and Christian Majenz.  Quantum Non-malleability and Authentication.  In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology – CRYPTO 2017, Lecture Notes in Computer Science, pages 310–341, Cham, 2017. Springer International Publishing.
  * AMSY [16] Frederik Armknecht, Daisuke Moriyama, Ahmad-Reza Sadeghi, and Moti Yung.  Towards a Unified Security Model for Physically Unclonable Functions.  In Kazue Sako, editor, Topics in Cryptology - CT-RSA 2016, volume 9610, pages 271–287. Springer International Publishing, Cham, 2016\.
  * BBRV [02] Somshubhro Bandyopadhyay, P Oscar Boykin, Vwani Roychowdhury, and Farrokh Vatan.  A new proof for the existence of mutually unbiased bases.  Algorithmica, 34(4):512–528, 2002.
  * BCWdW [01] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf.  Quantum fingerprinting.  Physical Review Letters, 87(16):167902, September 2001.
  * Bec [14] Georg T. Becker.  On the Pitfalls of using Arbiter-PUFs as Building Blocks.  Technical Report 532, 2014.
  * Bec [15] Georg T. Becker.  The gap between promise and reality: On the insecurity of XOR arbiter PUFs.  pages 535–555, 2015.
  * BLL+ [18] Darius Bunandar, Anthony Lentine, Catherine Lee, Hong Cai, Christopher M Long, Nicholas Boynton, Nicholas Martinez, Christopher DeRose, Changchen Chen, Matthew Grein, et al.  Metropolitan quantum key distribution with silicon photonics.  Physical Review X, 8(2):021009, 2018.
  * BS [16] Anne Broadbent and Christian Schaffner.  Quantum cryptography beyond quantum key distribution.  Designs, Codes and Cryptography, 78(1):351–382, January 2016.
  * BZ [13] Dan Boneh and Mark Zhandry.  Quantum-Secure Message Authentication Codes.  In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology – EUROCRYPT 2013, Lecture Notes in Computer Science, pages 592–608, Berlin, Heidelberg, 2013. Springer.
  * CBTW [17] Patrick J Coles, Mario Berta, Marco Tomamichel, and Stephanie Wehner.  Entropic uncertainty relations and their applications.  Reviews of Modern Physics, 89(1):015002, 2017.
  * CCB [18] Marcello Caleffi, Angela Sara Cacciapuoti, and Giuseppe Bianchi.  Quantum internet: from communication to distributed computing!  In Proceedings of the 5th ACM International Conference on Nanoscale Computing and Communication, NANOCOM ’18, pages 1–4, New York, NY, USA, September 2018. Association for Computing Machinery.
  * CCT+ [20] Angela Sara Cacciapuoti, Marcello Caleffi, Francesco Tafuri, Francesco Saverio Cataliotti, Stefano Gherardini, and Giuseppe Bianchi.  Quantum Internet: Networking Challenges in Distributed Quantum Computing.  IEEE Network, 34(1):137–143, January 2020.
  * Cou [16] Rachel Courtland.  China’s 2,000-km quantum link is almost complete [news].  IEEE Spectrum, 53(11):11–12, 2016.
  * DDKA [21] Mina Doosti, Mahshid Delavar, Elham Kashefi, and Myrto Arapinis.  A unified framework for quantum unforgeability.  arXiv preprint arXiv:2103.13994, 2021.
  * Del [19] Jeroen Delvaux.  Machine-learning attacks on polypufs, ob-pufs, rpufs, lhs-pufs, and puf–fsms.  IEEE Transactions on Information Forensics and Security, 14(8):2043–2058, 2019.
  * Deu [83] David Deutsch.  Uncertainty in quantum measurements.  Physical Review Letters, 50(9):631, 1983.
  * DGJ+ [20] Yfke Dulek, Alex B. Grilo, Stacey Jeffery, Christian Majenz, and Christian Schaffner.  Secure Multi-party Quantum Computation with a Dishonest Majority.  In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, pages 729–758, Cham, 2020. Springer International Publishing.
  * Dia [19] Eleni Diamanti.  Demonstrating Quantum Advantage in Security and Efficiency with Practical Photonic Systems.  In 2019 21st International Conference on Transparent Optical Networks (ICTON), pages 1–2, July 2019.  ISSN: 2161-2064.
  * DLP [01] Giacomo D’Ariano and Paoloplacido Lo Presti.  Quantum tomography for measuring experimentally the matrix elements of an arbitrary quantum operation.  Physical review letters, 86:4195–8, 06 2001.
  * DWT+ [19] J. F. Dynes, A. Wonfor, W. W.-S. Tam, A. W. Sharpe, R. Takahashi, M. Lucamarini, A. Plews, Z. L. Yuan, A. R. Dixon, J. Cho, Y. Tanizawa, J.-P. Elbers, H. Greißer, I. H. White, R. V. Penty, and A. J. Shields.  Cambridge quantum network.  npj Quantum Information, 5(1):1–8, November 2019.
  * Fit [17] Joseph F. Fitzsimons.  Private quantum computation: an introduction to blind quantum computing and related protocols.  npj Quantum Information, 3(1):1–11, June 2017.
  * FLD+ [17] Bernd Fröhlich, Marco Lucamarini, James F Dynes, Lucian C Comandar, Winci W-S Tam, Alan Plews, Andrew W Sharpe, Zhiliang Yuan, and Andrew J Shields.  Long-distance quantum key distribution secure against coherent attacks.  Optica, 4(1):163–167, 2017.
  * [24] Blaise Gassend, Dwaine Clarke, Marten Van Dijk, and Srinivas Devadas.  Controlled physical random functions.  In 18th Annual Computer Security Applications Conference, 2002. Proceedings., pages 149–160. IEEE, 2002.
  * [25] Blaise Gassend, Dwaine Clarke, Marten Van Dijk, and Srinivas Devadas.  Silicon physical random functions.  In Proceedings of the 9th ACM Conference on Computer and Communications Security, pages 148–160, 2002.
  * GKST [07] Jorge Guajardo, Sandeep S Kumar, Geert-Jan Schrijen, and Pim Tuyls.  Fpga intrinsic pufs and their use for ip protection.  In International workshop on cryptographic hardware and embedded systems, pages 63–80. Springer, 2007.
  * Gol [96] D. Gollmann.  What do we mean by entity authentication?  In Proceedings 1996 IEEE Symposium on Security and Privacy, pages 46–54, May 1996.  ISSN: 1081-6011.
  * Hel [69] Carl W. Helstrom.  Quantum detection and estimation theory.  Journal of Statistical Physics, 1(2):231–252, June 1969.
  * Hol [73] A. S Holevo.  Statistical decision theory for quantum systems.  Journal of Multivariate Analysis, 3(4):337–394, December 1973.
  * HYKD [14] Charles Herder, Meng-Day Yu, Farinaz Koushanfar, and Srinivas Devadas.  Physical unclonable functions and applications: A tutorial.  Proceedings of the IEEE, 102(8):1126–1141, 2014.
  * KDW [20] Wojciech Kozlowski, Axel Dahlberg, and Stephanie Wehner.  Designing a quantum network protocol.  In Proceedings of the 16th International Conference on emerging Networking EXperiments and Technologies, pages 1–16. Association for Computing Machinery, New York, NY, USA, November 2020.
  * KHH+ [18] Min-Sung Kang, Jino Heo, Chang-Ho Hong, Hyung-Jin Yang, Sang-Wook Han, and Sung Moon.  Controlled mutual quantum entity authentication with an untrusted third party.  Quantum Information Processing, 17(7):159, May 2018.
  * KL [18] Younghyun Kim and Yongwoo Lee.  Campuf: physically unclonable function based on cmos image sensor fixed pattern noise.  In Proceedings of the 55th Annual Design Automation Conference, pages 1–6, 2018.
  * KMK [21] Niraj Kumar, Rawad Mezher, and Elham Kashefi.  Efficient construction of quantum physical unclonable functions with unitary t-designs.  arXiv preprint arXiv:2101.05692, 2021.
  * KRS [09] Robert Konig, Renato Renner, and Christian Schaffner.  The operational meaning of min-and max-entropy.  IEEE Transactions on Information theory, 55(9):4337–4347, 2009\.
  * LLG+ [04] Jae W Lee, Daihyun Lim, Blaise Gassend, G Edward Suh, Marten Van Dijk, and Srinivas Devadas.  A technique to build a secret key in integrated circuits for identification and authentication applications.  In 2004 Symposium on VLSI Circuits. Digest of Technical Papers (IEEE Cat. No. 04CH37525), pages 176–179. IEEE, 2004.
  * ML [16] Iman Marvian and Seth Lloyd.  Universal quantum emulator.  arXiv preprint arXiv:1606.02734, 2016.
  * MU [88] Hans Maassen and Jos BM Uffink.  Generalized entropic uncertainty relations.  Physical review letters, 60(12):1103, 1988.
  * MWCD [22] Yao Ma, Chirag Wadhwa, Kaushik Chakraborty, and Mina Doosti.  Hybrid Locked PUF Simulation, 2022.
  * NC [10] Michael A. Nielsen and Isaac L. Chuang.  Quantum computation and quantum information.  Cambridge University Press, Cambridge ; New York, 10th anniversary ed edition, 2010.
  * NSJ+ [19] Phuong Ha Nguyen, Durga Prasad Sahoo, Chenglu Jin, Kaleel Mahmood, Ulrich Rührmair, and Marten van Dijk.  The interpose puf: Secure puf design against state-of-the-art machine learning attacks.  IACR Transactions on Cryptographic Hardware and Embedded Systems, pages 243–290, 2019.
  * PPA+ [20] S. Pirandola, S. Pirandola, U. L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani, J. L. Pereira, M. Razavi, J. Shamsul Shaari, J. Shamsul Shaari, M. Tomamichel, M. Tomamichel, V. C. Usenko, G. Vallone, P. Villoresi, and P. Wallden.  Advances in quantum cryptography.  Advances in Optics and Photonics, 12(4):1012–1236, December 2020\.
  * PPM [08] Andreas Poppe, Momtchil Peev, and Oliver Maurhart.  Outline of the secoqc quantum-key-distribution network in vienna.  International Journal of Quantum Information, 6(02):209–218, 2008\.
  * RDK [12] Ulrich Rührmair, Srinivas Devadas, and Farinaz Koushanfar.  Security based on physical unclonability and disorder.  In Introduction to Hardware Security and Trust, pages 65–102. Springer, 2012.
  * Roe [12] MAES Roel.  Physically unclonable functions: Constructions, properties and applications.  Katholieke Universiteit Leuven, Belgium, 2012.
  * [46] Ulrich Rührmair, Frank Sehnke, Jan Sölter, Gideon Dror, Srinivas Devadas, and Jürgen Schmidhuber.  Modeling attacks on physical unclonable functions.  In Proceedings of the 17th ACM Conference on Computer and Communications Security, CCS ’10, page 237–249, New York, NY, USA, 2010. Association for Computing Machinery.
  * [47] Ulrich Rührmair, Frank Sehnke, and Jan Sölter.  Modeling attacks on physical unclonable functions.  page 13, 2010.
  * RSS+ [13] Ulrich Rührmair, Jan Sölter, Frank Sehnke, Xiaolin Xu, Ahmed Mahmoud, Vera Stoyanova, Gideon Dror, Jürgen Schmidhuber, Wayne Burleson, and Srinivas Devadas.  Puf modeling attacks on simulated and silicon data.  IEEE transactions on information forensics and security, 8(11):1876–1891, 2013.
  * SD [07] G. Edward Suh and Srinivas Devadas.  Physical unclonable functions for device authentication and secret key generation.  In 2007 44th ACM/IEEE Design Automation Conference, pages 9–14, 2007.
  * SEG+ [17] Philip Sibson, Chris Erven, Mark Godfrey, Shigehito Miki, Taro Yamashita, Mikio Fujiwara, Masahide Sasaki, Hirotaka Terai, Michael G Tanner, Chandra M Natarajan, et al.  Chip-based quantum key distribution.  Nature communications, 8(1):1–6, 2017.
  * SFI+ [11] Masahide Sasaki, Mikio Fujiwara, H Ishizuka, W Klaus, K Wakui, M Takeoka, S Miki, T Yamashita, Z Wang, A Tanaka, et al.  Field test of quantum key distribution in the tokyo qkd network.  Optics express, 19(11):10387–10409, 2011.
  * Ško [12] Boris Škorić.  Quantum readout of physical unclonable functions.  International Journal of Quantum Information, 10(01):1250001, 2012\.
  * SLB+ [11] Damien Stucki, Matthieu Legre, Francois Buntschu, B Clausen, Nadine Felber, Nicolas Gisin, Luca Henzen, Pascal Junod, Gérald Litzistorf, Patrick Monbaron, et al.  Long-term performance of the swissquantum quantum key distribution network in a field environment.  New Journal of Physics, 13(12):123001, 2011.
  * SMCN [17] Durga Prasad Sahoo, Debdeep Mukhopadhyay, Rajat Subhra Chakraborty, and Phuong Ha Nguyen.  A multiplexer-based arbiter puf composition with enhanced reliability and security.  IEEE Transactions on Computers, 67(3):403–417, 2017.
  * SSH+ [20] Henry Semenenko, Philip Sibson, Andy Hart, Mark G Thompson, John G Rarity, and Chris Erven.  Chip-based measurement-device-independent quantum key distribution.  Optica, 7(3):238–242, 2020.
  * TNO [09] Igor Tselniker, Moshe Nazarathy, and Meir Orenstein.  Mutually unbiased bases in 4, 8, and 16 dimensions generated by means of controlled-phase gates with application to entangled-photon qkd protocols.  IEEE Journal of Selected Topics in Quantum Electronics, 15(6):1713–1723, 2009.
  * TR [11] Marco Tomamichel and Renato Renner.  Uncertainty relation for smooth entropies.  Physical review letters, 106(11):110506, 2011.
  * Unr [13] Dominique Unruh.  Everlasting Multi-party Computation.  In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology – CRYPTO 2013, pages 380–397, Berlin, Heidelberg, 2013. Springer.
  * Ver [19] VeriQloud.  Quantum Protocol Zoo, 2019.
  * WCY+ [14] Shuang Wang, Wei Chen, Zhen-Qiang Yin, Hong-Wei Li, De-Yong He, Yu-Hu Li, Zheng Zhou, Xiao-Tian Song, Fang-Yi Li, Dong Wang, et al.  Field and long-term demonstration of a wide area quantum key distribution network.  Optics express, 22(18):21739–21756, 2014.
  * WEH [18] Stephanie Wehner, David Elkouss, and Ronald Hanson.  Quantum internet: A vision for the road ahead.  Science, 362(6412):eaam9288, October 2018.
  * WGM+ [21] Nils Wisiol, Christoph Gräbnitz, Christopher Mühl, Benjamin Zengin, Tudor Soroceanu, Niklas Pirnay, Khalid T. Mursi, and Adomas Baliuka.  pypuf: Cryptanalysis of Physically Unclonable Functions, 2021.
  * Wie [83] Stephen Wiesner.  Conjugate coding.  SIGACT News, 15(1):78–88, January 1983.
  * WZ [82] William K Wootters and Wojciech H Zurek.  A single quantum cannot be cloned.  Nature, 299(5886):802–803, 1982.
  * YHD+ [16] Meng-Day Yu, Matthias Hiller, Jeroen Delvaux, Richard Sowell, Srinivas Devadas, and Ingrid Verbauwhede.  A Lockdown Technique to Prevent Machine Learning on PUFs for Lightweight Authentication.  IEEE Transactions on Multi-Scale Computing Systems, 2(3):146–159, July 2016.

## Supplementary Materials

##  Appendix A Overview

In the supplementary materials, we provide all the formal definitions and
constructions, security proofs and other detailed technical results. The
structure is as follows: First, in Appendix B we introduce some of the basic
notions and tools from quantum information and PUF literature that we will use
later. In Appendix C we give a detailed description of an adaptive and weak
quantum adversary, in the most general case of the unforgeability game where
all the learning queries are density matrices. Then, we also give a more
detailed version of the quantum unforgeability game, with adaptive and weak
adversaries. In Appendix D and Appendix E we give the formal description of
HPUF and HLPUF constructions respectively and then in Appendix E.2, we present
the main results of the paper formally. Then in Appendix F, we discuss the
challenge reusability result in further detail and in I.6 we first give a
brief introduction of the entropic uncertainty relations that have been used
in the literature of quantum information for different purposes like security
proof of QKD protocols. Then, we establish a formal version of Theorem 5, in
terms of the described uncertainty quantities, and finally, we give a full
detailed proof of this theorem which we will use to establish the challenge
reusability property for our HLPUF-based protocol. In Appendix G we discuss
our simulation results more extensively, discussing also technical details
about the effect of different quantum encoding. In Appendix H we investigate
the lockdown technique on quantum PUFs and we establish a general no-go
result. Finally in Appendix I we give the full and detailed security proofs
for the theorem in Appendix E.2, including the proof of Theorem 1, Lemma 1,
Lemma 2, and Lemma 3.

##  Appendix B Preliminaries

In this section, we discuss some of the main concepts and definitions that we
rely upon in the paper.

###  B.1 Quantum information tools

Quantum states are denoted as unit vectors in a Hilbert space $\mathcal{H}$.
Any $d$-dimensional Hilbert space is equipped with a set of $d$ orthonormal
bases. We say a quantum state is pure if it deterministically describes a
vector in Hilbert space. On the other hand, a mixed quantum state is described
as a probability distribution over different pure quantum states, represented
as a density matrix $\rho\in\mathcal{H}^{d}$. If a quantum state can be
written as the tensor product of all its subsystems, we say that the state is
_separable_ , otherwise, it is referred to as _entangled state_.

If a quantum resource takes an input
$\rho_{\mathrm{in}}\in\mathcal{H}_{A}^{d_{\mathrm{in}}}$ and produces an
output $\rho_{\mathrm{out}}\in\mathcal{H}_{B}^{d_{\mathrm{out}}}$, we use a
completely positive and trace preserving (CPTP) map $\mathcal{E}$ to describe
the general quantum transformation
$\mathcal{E}\mathrel{\mathop{\ordinarycolon}}\mathcal{H}_{A}^{d_{\mathrm{in}}}\rightarrow\mathcal{H}_{B}^{d_{\mathrm{out}}}$.

The measurement of a quantum state is defined by a set of operators
$\\{M_{i}\\}$ satisfying $\sum_{i}M_{i}^{\dagger}M_{i}=I$ with its conjugate
transpose operator $M^{\dagger}$. The probability of getting measurement
result $i$ on quantum state $\ket{\psi}$ is:

$\displaystyle
P(i)=\bra{\psi}M_{i}^{\dagger}M_{i}\ket{\psi}=\bra{\psi}M_{i}\ket{\psi}.$

Furthermore, we define the set $\\{E_{i}\\}$ a _POVM_ (Positive Operator-
Valued Measure) with positive operators $E_{i}=M_{i}^{\dagger}M_{i}$, where
$\Sigma_{i}E_{i}=I$.

An important property of the quantum states is the impossibility of creating
perfect copies of general unknown quantum states, known as the _no-cloning
theorem_ [64]. This is an important limitation imposed by quantum mechanics
which is particularly relevant for cryptography. A variation of the same
feature makes it impossible to obtain the exact classical description of
quantum states by having a single or very few copies, therefore, there exists
a bound on how much classical information can be extracted from quantum
states, known as Holevo bound [29]. Moreover, distinguishing between two
unknown quantum states is also a probabilistic procedure known in the
literature of quantum information as _quantum state discrimination_. The
distinguishability of the quantum states depends on their distance. There
exist several distance measures for quantum states and quantum processes [40],
although, for the purpose of this paper, we introduce the fidelity, the trace
distance and the diamond norm. The trace distance between two quantum states
$\rho$ and $\sigma$ is defined as:

$\mathcal{D}_{tr}(\rho,\sigma)=\frac{1}{2}\|\rho-\sigma\|_{1}=\frac{1}{2}Tr[\sqrt{(\rho-\sigma)^{2}}]$
(4)

The fidelity of mixed states $\rho$ and $\sigma$ is defined by the Uhlmann
fidelity [40]:

$F(\rho,\sigma)=[Tr(\sqrt{{\sqrt{\rho}}\sigma{\sqrt{\rho}}})]^{2}$ (5)

which will become $|\bra{\psi}\phi\rangle|^{2}$ the following expression for
two pure quantum states $\ket{\psi}$ ($\rho=\ket{\psi}\bra{\psi}$) and
$\ket{\phi}$ ($\sigma=\ket{\phi}\bra{\phi}$). The fidelity is bounded between
0 and 1, $0\leq F(\rho,\sigma)\leq 1$. $F(\rho,\sigma)=0$ when two states
$\rho$ and $\sigma$ are orthogonal and $F(\rho,\sigma)=1$ when $\rho$ and
$\sigma$ are identical.

In this paper, we denote all the verification algorithms for checking equality
of two quantum states by distance as a CPTP map
$\texttt{Ver}\mathrel{\mathop{\ordinarycolon}}\mathcal{H}^{d}\otimes\mathcal{H}^{d}\rightarrow\\{0,1\\}$.
For any two states $\rho_{1},\rho_{2}\in\mathcal{H}^{d}$, this mapping is
defined below.

$\texttt{Ver}(\rho_{1},\rho_{2})\mathrel{\mathop{\ordinarycolon}}=\begin{cases}&1~{}~{}~{}~{}\text{if
}\mathinner{\\!\left\lVert\rho_{1}-\rho_{2}\right\rVert}_{1}\leq\epsilon,\\\
&0~{}~{}~{}~{}\text{otherwise.}\end{cases}$ (6)

This general verification also includes measurements of quantum states as
verification algorithms since it has been defined as a general CPTP map.
Finally, we mention the notion of _SWAP test_ [5] as a quantum circuit for
implementing the verification algorithm Ver(.) above. The swap test’s circuit
uses the controlled version of a swap gate, that swaps the order of two
quantum states if the control qubit is $\ket{1}$. The circuit outputs
$\ket{0}$ with probability $\frac{1}{2}+\frac{1}{2}F(\ket{\psi},\ket{\phi})$
and it outputs $\ket{1}$ with probability
$\frac{1}{2}-\frac{1}{2}F(\ket{\psi},\ket{\phi})$. As can be seen, the success
probability of this test depends on the fidelity of the states. This occurs
because of the quantum nature of these states and measurements in quantum
mechanics.

###  B.2 Models for PUF

A Physical Unclonable Function is a secure hardware cryptographic device that
is, by assumption, hard to clone or reproduce. Here we give the mathematical
model for the classical PUFs first, and then we also briefly mention the
quantum analogue of them known as quantum PUF (QPUF) as defined in [1]. As
classical PUFs are usually defined with probabilistic functions, due to their
inherent physical randomness, we first define the notion of probabilistic
functions as follows.

######  Definition 1 (Probabilistic Function).

A _probabilistic function_ is a mapping
$f\mathrel{\mathop{\ordinarycolon}}\mathcal{R}\times\mathcal{X}\rightarrow\mathcal{Y}$
with an input space $\mathcal{X}$, an _random coin_ space $\mathcal{R}$, and
an output space $\mathcal{Y}$.

For a fixed input $x\in\mathcal{X}$, and a random coin (or key)
$R\leftarrow\mathcal{R}$, we define the probability distribution of the output
random variable $f(x)\mathrel{\mathop{\ordinarycolon}}=f(R,x)$ over all
$y\in\mathcal{Y}$ as,

$p^{f}_{x}(y)\mathrel{\mathop{\ordinarycolon}}=\Pr[f(x)=y|x]=\sum_{r\mathrel{\mathop{\ordinarycolon}}f(r,x)=y}\Pr[R=r].$
(7)

A classical PUF can be modelled as a probabilistic function
$f\mathrel{\mathop{\ordinarycolon}}\mathcal{R}\times\mathcal{X}\rightarrow\mathcal{Y}$
where $\mathcal{X}$ is the input space, $\mathcal{Y}$ is the output space of
$f$ and $\mathcal{R}$ is the identifier. The creation of a classical PUF is
formally expressed by invoking a manufacturing process
$f\leftarrow\mathcal{MP}_{C}(\lambda)$, where $\lambda$ is the security
parameter.

To model classical PUF $f$ in terms of security primitives, Armknecht et al.
[3] define some requirements which are parameterized by some threshold
$\delta_{i}$ and a negligible function $\epsilon(\lambda)\leq\lambda^{-c}$,
where $c>0$ and $\lambda$ is large enough. Note that the requirements in our
paper corresponding to the requirements of intra and inter distances of PUF
$f$.

######  Definition 2.

The classical PUF
$f\mathrel{\mathop{\ordinarycolon}}\mathcal{R}\times\mathcal{X}\rightarrow\mathcal{Y}$
with $(\mathcal{MP}_{C},\delta_{1},\delta_{2},\delta_{3},\epsilon,\lambda)$
satisfies the requirements defined below:

######  Requirement 1 ($\delta_{1}$-Robustness).

Whenever a single classical PUF is repeatedly evaluated with a fixed input,
the maximum distance between any two outputs $y_{i}\leftarrow f(x)$ and
$y_{j}\leftarrow f(x)$ is at most $\delta_{1}$. That is for a created PUF $f$
and $x\in\mathcal{X}$, it holds that:

$\Pr\left[max({Dist(y_{i},y_{j})}_{i\neq
j})\leq\delta_{1}\right]=1-\epsilon(\lambda).$ (8)

######  Requirement 2 ($\delta_{2}$-Collision Resistance).

Whenever a single classical PUF is evaluated on different inputs, the minimum
distance between any two outputs $y_{i}\leftarrow f(x_{i})$ and
$y_{j}\leftarrow f(x_{j})$ is at least $\delta_{2}$. That is for a created PUF
$f$ and $x_{i},x_{j}\in\mathcal{X}$, it holds that:

$\Pr\left[min({Dist(y_{i},y_{j})}_{i\neq
j})\geq\delta_{2}\right]=1-\epsilon(\lambda).$ (9)

######  Requirement 3 ($\delta_{3}$-Uniqueness).

Whenever any two classical PUFs are evaluated on a single, fixed input, the
minimum distance between any two outputs $y_{i}\leftarrow f_{i}(x)$ and
$y_{j}\leftarrow f_{j}(x)$ is at least $\delta_{3}$. That is for a created PUF
$f$ and $x\in\mathcal{X}$, it holds that:

$\Pr\left[min({Dist(y_{i},y_{j})}_{i\neq
j})\geq\delta_{3}\right]=1-\epsilon(\lambda)$ (10)

where $Dist(.,.)$ is a general notion of distance between the responses.

We also introduce the notion of randomness for the classical PUF $f$. It says
the maximal probability of $p^{f}_{x}(y)$ with a input $x_{j}\in\mathcal{X}$
on PUF $f_{i}$ where $i\in\mathcal{R}$. conditioned on the residual output
space. A formal definition is as follows.

######  Definition 3 ($p$-Randomness).

We define the $p$-randomness of a classical PUF
$f\mathrel{\mathop{\ordinarycolon}}\mathcal{R}\times\mathcal{X}\rightarrow\mathcal{Y}$
as

$p\mathrel{\mathop{\ordinarycolon}}=\max_{\begin{subarray}{c}x\in\mathcal{X}\\\
y\in\mathcal{Y}\end{subarray}}p^{f}_{x}(y).$ (11)

For a correct valid modeling of PUF, $\delta_{1}<\delta_{2}$ and
$\delta_{1}<\delta_{3}$ are necessary conditions to allow for a clear
distinction between different input and different PUFs.

A quantum PUF, is again a hardware primitive that is unclonable by assumption
which also utilises the properties of quantum mechanics. Similar to a
classical PUF, a QPUF is assessed via challenge and response pairs (CPR).
However, in contrast to a classical PUF where the CRPs are classical states,
the QPUF CRPs are quantum states. Moreover, the evaluation algorithm of a QPUF
is modelled by a general quantum transformation that is a CPTP map that
produces an output in the form of a quantum state. A quantum transformation
needs to have few requirements such as robustness, collision resistance and
uniqueness to be considered a QPUF, similar to its classical counterpart. The
focus of this paper is not on full quantum PUFs, and only for the Section H,
where we discuss the feasibility of lockdown technique for general quantum
PUFs, we use the QPUF as defined in [1].

##  Appendix C Unforgeability against Adaptive and Weak Adversaries

###  C.1 Models for adaptive and weak adversaries

In this paper, we only consider the _network adversarial model_ , i.e., the
adversary has only access to the communication channel. Moreover, we assume
that the manufacturer of the PUF is honest. The network adversaries can get
the challenge-response pairs just by intercepting the messages that are
exchanged between the server and the clients. They can also pretend to be the
server and make queries to the PUF on the client side with a challenge and get
the response.

Any network adversary that tries to predict the response of a PUF
$\mathcal{E}\mathrel{\mathop{\ordinarycolon}}\mathcal{D}^{in}\rightarrow\mathcal{D}^{out}$,
can be modelled as an interactive algorithm. Here we consider Quantum
Polynomial-Time (QPT) adversaries that have $q$-query classical access to the
evaluation of the PUF, namely $\mathcal{E}$ where $q$ is polynomial in the
security parameter. An adaptive adversary can choose and issue any arbitrary
query (up to $q$-query) which could also depend on the previous responses
received from the PUF. On the other hand, a weak non-adaptive adversary,
cannot choose the queries and instead receives $q$ CRPs of $\mathcal{E}$. In
this case, the queries are being picked at random from a uniform distribution
by an honest party and sent to the adversary.

###  C.2 Unforgeability with game-based security

_Unforgeability_ is the main security property of PUFs. _Unforgeability_ means
that given a subset of challenge-response pairs of the target PUF, the
probability of correct estimation of a new challenge-response pair is
negligible in terms of the security parameter. The unforgeability for
Classical PUFs has been defined in [3], and for Quantum PUFs in [1] as a game-
based definition. Moreover, a general game-based framework for quantum
unforgeability has been defined in [15] for both quantum and classical
primitives in an abstract way. Following the previous works, here in this
paper, we present a game-based unforgeability definition for PUFs, emphasizing
the adversary’s capabilities in the learning phase, and capturing both
adaptive and weak adversaries as defined in the previous section. We define
the unforgeability of PUF as a formal game between two parties: a _challenger_
($\mathcal{C}$) and an _adversary_ ($\mathcal{A}$). The game is divided with 4
phases: _Setup_ , _Learning_ , _Challenge_ and _Guess_. A formal description
is given as follows:

######  Game 1 (Universal Unforgeability of PUF222We use the term _Universal
Unforgeability_ as defined in [15], to avoid confusion with a stronger
security model. Nevertheless, in the PUF literature, this level of security is
also called _Selective Unforgeability_ as also was used in [1].).

Let $\mathcal{MP}$ be the manufacturing process, Ver(.) be a verification
algorithm for checking the responses, and $\lambda$ the security parameter. We
define the following game $\mathcal{G}^{PUF}(\mathcal{A},\lambda)$ running
between an adversary $\mathcal{A}$ and a challenger $\mathcal{C}$:

  * •

Setup phase.

    * –

$\mathcal{C}$ selects a manufacturing process $\mathcal{MP}$ and security
parameter $\lambda$. Then $\mathcal{C}$ creates a PUF by
$\mathcal{E}\leftarrow\mathcal{MP}(\lambda)$, which is described by a CPTP
map. The challenge and response domain and range $\mathcal{D}^{in}$ and
$\mathcal{D}^{out}$ are shared between $\mathcal{C}$ and $\mathcal{A}$.

  * •

Learning phase.

    * –

If the adversary is adaptive, $\mathcal{A}=\mathcal{A}_{ad}$:

      * *

$\mathcal{A}_{ad}$ selects any desired challenge $c_{i}\in\mathcal{D}^{in}$,
and issues to $\mathcal{C}$ (up to $q$ queries).

      * *

$\mathcal{C}$ queries the PUF with each challenge $c_{i}$ and sends the
response $r_{i}=\mathcal{E}(c_{i})\in\mathcal{D}^{out}$ back to
$\mathcal{A}_{ad}$.

    * –

If the adversary is weak (non-adaptive), $\mathcal{A}=\mathcal{A}_{weak}$:

      * *

$\mathcal{C}$ selects a challenge $c_{i}\in\mathcal{D}^{in}$ uniformly at
random from $\mathcal{D}^{in}$ and independent of $i$.

      * *

$\mathcal{C}$ queries the PUF with $c_{i}$ and produces the response
$r_{i}=\mathcal{E}(c_{i})$.

      * *

$\mathcal{C}$ issues to $\mathcal{A}_{weak}$ the set of random challenges and
their respective responses $\\{(c_{i},r_{i})\\}^{q}_{i=1}$.

  * •

Challenge phase.

    * –

$\mathcal{C}$ chooses a challenge $\tilde{c}$ uniformly at random from
challenge domain $\mathcal{D}^{in}$.

    * –

$\mathcal{C}$ issues $\tilde{c}$ to $\mathcal{A}$.

  * •

Guess phase.

    * –

For the challenge $\tilde{c}$, $\mathcal{A}$ produces his forgery
$\sigma^{r}\leftarrow\mathcal{A}(1^{\lambda},\tilde{c},\\{(c_{i},r_{i})\\}^{q}_{i})$
and sends to $\mathcal{C}$.

    * –

$\mathcal{C}$ runs a verification algorithm
$b\leftarrow\texttt{Ver}(\sigma^{r},\tilde{r})$, where
$\tilde{r}=\mathcal{E}(\tilde{c})$ is the correct output and $b\in\\{0,1\\}$,
to check the fidelity or equality of the responses.

    * –

$\mathcal{C}$ outputs $b$. $\mathcal{A}$ wins if $b=1$.

The above game is the abstract version of the unforgeability game that can be
used for different classical or quantum PUFs and with different challenge
types. For instance, the learning phase challenges $c_{i}$ can be classical
bit-strings or quantum states and in that case, the domain $\mathcal{D}^{in}$
will be a Hilbert. Here we mostly focus on the notion of classical and Hybrid
PUFs. As a result, we do not need the full generalization to the quantum
setting. Nevertheless, for the sake of completeness, we also give a full
quantum version of this game-based definition in Appendix C.3.

Note that the adversary could not choose arbitrarily the challenges in the
challenge phase in this game. So it is so-called _universal unforgeability_.
Relatively, there are different notions of unforgeability e.g, _unconditional
unforgeability_ and _existential unforgeability_ [1]. Unconditional
unforgeability models the PUF against an unbounded adversary with unlimited
queries during the learning phase, which is the strongest notion of
unforgeability. The difference between existential unforgeability and
universal unforgeability is that the adversary could choose the challenges
during the challenge phase with existential unforgeability instead of choosing
the challenges by the challenger. Even though the universal unforgeability is
the weaker one compared with the rest of the two, it is sufficient for most
PUF-based applications.

Finally, we define game-based security in terms of universal unforgeability in
this setting:

######  Definition 4 (Universal Unforgeability against Adaptive Adversary).

A PUF with manufacturing process $\mathcal{MP}$ and verification algorithm
Ver(.) provides $(\epsilon,\lambda)$-universal unforgeability against adaptive
adversary if the success probability of any adaptive QPT adversary
$\mathcal{A}_{ad}$ in winning the game
$\mathcal{G}^{PUF}(\mathcal{A}_{ad},\lambda)$ is at most $\epsilon(\lambda)$.

$Pr[1\leftarrow\mathcal{G}^{PUF}(\mathcal{A}_{ad},\lambda)]\leq\epsilon(\lambda)$
(12)

######  Definition 5 (Universal Unforgeability against Weak Adversary).

A PUF with manufacturing process $\mathcal{MP}$ and verification algorithm
Ver(.) provides $(\epsilon,\lambda)$-universal unforgeability against weak
(non-adaptive) adversary if the success probability of any weak QPT adversary
$\mathcal{A}_{weak}$ in winning the game
$\mathcal{G}^{PUF}(\mathcal{A}_{weak},\lambda)$ is at most
$\epsilon(\lambda)$.

$Pr[1\leftarrow\mathcal{G}^{PUF}(\mathcal{A}_{weak},\lambda)]\leq\epsilon(\lambda)$
(13)

###  C.3 Unforgeability game for general quantum PUF against adaptive and weak
adversary

In this appendix, we introduce the full quantum unforgeability game against
adaptive and weak (non-adaptive) adversaries. Any adversary that tries to
predict the response of a PUF
$\mathcal{E}\mathrel{\mathop{\ordinarycolon}}\mathcal{H}^{d_{\mathrm{in}}}\rightarrow\mathcal{H}^{d_{\mathrm{out}}}$,
can be modelled as an interactive algorithm. Here we consider Quantum
Polynomial-Time (QPT) adversaries that have $q$-query access to the evaluation
of the PUF, namely $\mathcal{E}$ where $q$ is polynomial in the security
parameter. An adaptive adversary can choose and issue any arbitrary query
which could also depend on the previous responses received from the PUF. On
the other hand, a weak non-adaptive adversary, cannot choose the queries and
will instead receive $q$ input/output pairs states of $\mathcal{E}$. In the
case that all the queries are quantum, the post-learning phase database of a
weak adversary can be easily modelled by the definition. However, an adaptive
quantum adversary is likely to consume the quantum state of the response to be
able to pick the next query adaptively. Hence modeling the post-query database
of an adaptive quantum adversary is more challenging. In what follows we give
a $q$-query mathematical model for adaptive and weak adversaries.

######  Definition 6 (Adaptive and Weak Adversary).

Let $q$ be a positive integer, and
$\mathcal{E}\mathrel{\mathop{\ordinarycolon}}\mathcal{H}^{d_{\mathrm{in}}}\rightarrow\mathcal{H}^{d_{\mathrm{out}}}$
be a PUF. We model a probabilistic adversary as a CPTP map
$\mathcal{A}\mathrel{\mathop{\ordinarycolon}}\mathcal{R}\times(\mathcal{H}^{d_{\mathrm{in}}})^{\otimes
q}\otimes(\mathcal{H}^{d_{\mathrm{out}}})^{\otimes
q}\rightarrow(\mathcal{H}^{d_{\mathrm{in}}})$. Such an adversary is called an
adaptive adversary $\mathcal{A}_{ad}$ if for all random coin $r\in\mathcal{R}$
and for any
$\bigotimes_{i=1}^{q}\rho^{\mathrm{in}}_{i}\in(\mathcal{H}^{d_{\mathrm{in}}})^{\otimes
q}$ and for
$\bigotimes_{i=1}^{q}\rho^{\mathrm{out}}_{i}\in(\mathcal{H}^{d_{\mathrm{out}}})^{\otimes
q}$ (where
$\rho^{\mathrm{out}}_{i}\mathrel{\mathop{\ordinarycolon}}=\mathcal{E}(\rho^{\mathrm{in}}_{i})$),
the mapping
$\bigotimes_{i=1}^{q}(\rho^{\mathrm{in}}_{i}\otimes\rho^{\mathrm{out}}_{i})\rightarrow\mathcal{A}^{r}_{ad}(\bigotimes_{i=1}^{q}(\rho^{\mathrm{in}}_{i}\otimes\rho^{\mathrm{out}}_{i}))$
is dependent on the
$\rho^{\mathrm{in}}_{1}\otimes\rho^{\mathrm{out}}_{1},\ldots,\rho^{\mathrm{in}}_{q}\otimes\rho^{\mathrm{out}}_{q}$;
For a weak adversary $\mathcal{A}_{weak}$ the mapping
$\bigotimes_{i=1}^{q}(\rho^{\mathrm{in}}_{i}\otimes\rho^{\mathrm{out}}_{i})\rightarrow\mathcal{A}^{r}_{ad}(\bigotimes_{i=1}^{q}(\rho^{\mathrm{in}}_{i}\otimes\rho^{\mathrm{out}}_{i}))$
is independent of
$\bigotimes_{i=1}^{q}(\rho^{\mathrm{in}}_{i}\otimes\rho^{\mathrm{out}}_{i})$.
Moreover, the adversary has no choice over the query, i.e., all the queries
$\otimes_{i=1}^{q}\rho^{\mathrm{in}}_{i}$ are chosen following a distribution
$\mathcal{R}$, and a third party chooses the distribution.

Intuitively, an adaptive adversary
$\mathcal{A}\mathrel{\mathop{\ordinarycolon}}\mathcal{R}\times(\mathcal{H}^{d_{\mathrm{in}}})^{\otimes
q}\otimes(\mathcal{H}^{d_{\mathrm{out}}})^{\otimes
q}\rightarrow(\mathcal{H}^{d_{\mathrm{in}}})$ captures the strategy to choose
the query input $\rho^{\mathrm{in}}_{q+1}\in\mathcal{H}^{d_{\mathrm{in}}}$ to
the PUF $\mathcal{E}$. The adversary can use these query response pairs to
predict the output of the PUF. We call the pair
$(\bigotimes_{i=1}^{q}\rho^{\mathrm{in}}_{i},\bigotimes_{i=1}^{q}\rho^{\mathrm{out}}_{i})$
that is generated after the $q$-round of interaction between an adversary
$\mathcal{A}$ and a PUF $\mathcal{E}$, as a transcript. Note, that the
transcripts depend on the choice of the random coins of $\mathcal{A}$.

Similar to Game 1, We define the unforgeability of PUF as a formal game
between two parties: a _challenger_ ($\mathcal{C}$) and an _adversary_
($\mathcal{A}$). The difference here is that our adversaries are defined
according to Definition 6. A formal description is given as follows:

######  Game 2 (Universal Unforgeability of PUF).

Let $\mathcal{MP}$ be the manufacturing process, Ver(.) be a verification
algorithm for checking the responses, and $\lambda$ the security parameter. We
define the following game $\mathcal{G}^{PUF}(\mathcal{A},\lambda)$ running
between an adversary $\mathcal{A}$ and a challenger $\mathcal{C}$:

  * •

Setup phase.

    * –

$\mathcal{C}$ selects a manufacturing process $\mathcal{MP}$ and security
parameter $\lambda$. Then $\mathcal{C}$ creates a PUF by
$\mathcal{E}\leftarrow\mathcal{MP}(\lambda)$, which is described by a CPTP
map. The challenge and response domain $\mathcal{H}^{d_{\mathrm{in}}}$ and
$\mathcal{H}^{d_{\mathrm{out}}}$ are shared between $\mathcal{C}$ and
$\mathcal{A}$.

  * •

Learning phase.

    * –

If the adversary is adaptive, $\mathcal{A}=\mathcal{A}_{ad}$:

      * *

$\mathcal{A}_{ad}$ selects and prepares an initial state
$\rho^{\mathrm{in}}_{0}\in\mathcal{H}^{d_{\mathrm{in}}}$, while having full
access to the preparation algorithm.

      * *

$\mathcal{A}_{ad}$ issues to $\mathcal{C}$ the initial challenge state
$\rho^{\mathrm{in}}_{0}\otimes\rho_{anc}$ where $\rho_{anc}$ is an initially
blank state.

      * *

$\mathcal{C}$ queries the PUF with $\rho^{\mathrm{in}}_{0}$ and sends the
response
$(\mathcal{E}\otimes\mathcal{I})\rho^{\mathrm{in}}_{0}\otimes\rho_{anc}$ back
to $\mathcal{A}_{ad}$

      * *

for the next challenges ($i\neq 0$), the adaptive adversary $\mathcal{A}_{ad}$
produces a new challenge for next query as
$\rho^{\mathrm{in}}_{i}=\mathcal{A}^{r_{i}}_{i}((\mathcal{E}\otimes\mathcal{I})\rho^{\mathrm{in}}_{i-1})$
and issues to $\mathcal{C}$.

      * *

$\mathcal{C}$ queries the PUF with $\rho^{\mathrm{in}}_{i}$ and sends the
response to $\mathcal{A}$. Recursively, $\mathcal{A}$ obtains the CPRs with
challenge $\rho^{\mathrm{in}}_{i}=\mathcal{A}_{i}^{r_{i}}(\mathcal{E}\otimes
I)\mathcal{A}_{i-1}^{r_{i-1}}(\mathcal{E}\otimes
I)\dots\mathcal{A}_{1}^{r^{1}}(\mathcal{E}\otimes I)(\rho^{\mathrm{in}}_{0})$
and corresponding response $\rho_{i}^{\mathrm{out}}=(\mathcal{E}\otimes
I)(\rho^{\mathrm{in}}_{i}\otimes\rho_{anc})$

    * –

If the adversary is (weak) non-adaptive, $\mathcal{A}=\mathcal{A}_{weak}$:

      * *

$\mathcal{C}$ selects a challenge $\rho^{\mathrm{in}}_{i}$ uniformly at random
from $\mathcal{H}^{d_{\mathrm{in}}}$ and independent of $i$, while being able
to prepare arbitrary copies of each challenge.

      * *

$\mathcal{C}$ queries the PUF with $\rho^{\mathrm{in}}_{i}$ and produces the
response $\mathcal{E}(\rho^{\mathrm{in}}_{0})$.

      * *

$\mathcal{C}$ issues to $\mathcal{A}_{weak}$ the set of random challenges
$\bigotimes_{i=1}^{q}\rho^{\mathrm{in}}_{i}$ and their respective responses
$\bigotimes_{i=1}^{q}\rho^{\mathrm{out}}_{i}$.

  * •

Challenge phase.

    * –

$\mathcal{C}$ chooses a challenge $\rho^{c}$ uniformly at random from
challenge domain $\mathcal{H}^{d_{\mathrm{in}}}$. $\mathcal{C}$ can produce
multiple copies of the challenge, and the respective response locally.

    * –

$\mathcal{C}$ issues $\rho^{c}$ to $\mathcal{A}$.

  * •

Guess phase.

    * –

For the challenge $\rho^{c}$, $\mathcal{A}$ produces his forgery
$\sigma^{r}\leftarrow\mathcal{A}(1^{\lambda},\rho^{c},\\{(\rho_{i}^{\mathrm{in}},\rho_{i}^{\mathrm{out}})\\})$
and sends to $\mathcal{C}$.

    * –

$\mathcal{C}$ runs a verification algorithm
$b\leftarrow\texttt{Ver}(\sigma^{r},\rho^{r},\rho_{\mathcal{C}})$, to check
the fidelity of the responses. Where $\rho^{r}=\mathcal{E}(\rho^{c})$ is the
correct output, $\rho_{\mathcal{C}}$ is the local register of the challenger
that can include extra copies of correct output if necessary for the
verification, and $b\in\\{0,1\\}$.

    * –

$\mathcal{C}$ outputs $b$. $\mathcal{A}$ wins if $b=1$.

Finally, the security definitions can be defined based on this game, similar
to definitions 4 and 5.

##  Appendix D Formal construction of HPUF

We have illustrated our HPUF construction in the main text. Here in
Construction 1, we give the formal description of our HPUF design which is
based on conjugate coding [63]. For our construction, we start with a
classical PUF (CPUF) that has a certain amount of randomness (also denoted as
min-entropy). To increase the min-entropy further, we encode the output of the
CPUF into non-orthogonal quantum states and send the qubits through the
communication channel. We refer to the entire system, i.e., CPUF together with
a quantum encoding as hybrid PUF (HPUF).

######  Construction 1 (Hybrid PUF).

Suppose
$f\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{4m}$ be
a classical PUF, that maps an $n$-bit string $x_{i}\in\\{0,1\\}^{n}$ to an
$4m$-bit string output $y_{i}\in\\{0,1\\}^{4m}$. We denote the $j$-th bit of
$y_{i}$ as $y_{i,j}\in\\{0,1\\}$. From the $4m$-bit string, we prepare the set
of $2m$-tuples $\\{(y_{i,(2j-1)},y_{i,2j})\\}_{1\leq j\leq 2m}$. The hybrid
PUF encodes each of the tuples $(y_{i,(2j-1)},y_{i,2j})$ into a single qubit
$|\psi^{i,j}\rangle$ (also known as _BB84 states_). The exact expression of
the encoding is defined in the following way,

$|\psi^{i,j}_{\mathrm{out}}\rangle\langle\psi^{i,j}_{\mathrm{out}}|\mathrel{\mathop{\ordinarycolon}}=\begin{cases}|0\rangle\langle
0|~{}&(y_{i,(2j-1)},y_{i,2j})=(0,0)\\\ |1\rangle\langle
1|~{}&(y_{i,(2j-1)},y_{i,2j})=(1,0)\\\
|+\rangle\langle+|~{}&(y_{i,(2j-1)},y_{i,2j})=(0,1)\\\
|-\rangle\langle-|~{}&(y_{i,(2j-1)},y_{i,2j})=(1,1)\end{cases}$ (14)

For any $x_{i}\in\\{0,1\\}^{n}$, the mapping of the HPUF
$\mathcal{E}_{f}\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow(\mathcal{H}^{2})^{\otimes
2m}$ is defined as follows.

$x_{i}\rightarrow|\psi^{i}_{\mathrm{out}}\rangle\langle\psi^{i}_{\mathrm{out}}|~{}~{}(\text{or}~{}|\psi_{f(x_{i})}\rangle\langle\psi_{f(x_{i})}|)$
(15)

where
$|\psi^{i}_{\mathrm{out}}\rangle\langle\psi^{i}_{\mathrm{out}}|=\bigotimes_{j=1}^{2m}|\psi^{i,j}_{\mathrm{out}}\rangle\langle\psi^{i,j}_{\mathrm{out}}|$.

##  Appendix E Hybrid Locked PUF

In this section, we give the first construction for lockdown mechanics in the
quantum setting. We use our proposed HPUF construction to increase the
security of the classical PUFs against quantum adversaries and then we combine
it with our quantum locking mechanism and construct a Hybrid Locked PUF
(HLPUF) that resits powerful quantum adaptive adversaries. We then give a PUF-
based authentication based on HLPUF and analyse its security.

###  E.1 Lockdown technique for Hybrid PUF

In construction 2 we show how to apply the lockdown technique on a hybrid PUF.
We refer to such HPUFs with the lockdown technique as the hybrid locked PUFs
(HLPUFs). We formalise the construction as follows:

######  Construction 2 (HLPUF).

Suppose we have a hybrid PUF $\mathcal{E}_{f}$ where
$f\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{4m}$ is
a CPUF. The mapping of the HLPUF
$\mathcal{E}^{L}_{f}\mathrel{\mathop{\ordinarycolon}}\mathcal{D}^{in}\times\mathcal{H}^{d_{\mathrm{out}_{1}}}\rightarrow\mathcal{H}^{d_{\mathrm{out}_{2}}}\otimes\mathcal{H}^{\perp}$
corresponding to a hybrid PUF $\mathcal{E}$ is defined as follows:

$(x_{i},\tilde{\rho}_{1})\rightarrow\begin{cases}&\ket{\psi_{f_{2}(x_{i})}}\bra{\psi_{f_{2}(x_{i})}}~{}\text{if
}\texttt{Ver}(\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}},\tilde{\rho}_{1})=1\\\
&\perp\hskip 56.9055pt\text{otherwise.}\end{cases}$ (16)

where $\texttt{Ver}(.,.)$ is verification algorithm that checks the equality
of the first half of the response based on the classical response $y^{1}_{i}$.
To be precise, $\texttt{Ver}(.,.)$ is specified by measuring each qubit of the
incoming quantum state with corresponding basis according to
$\\{y_{i,2j}\\}_{1\leq j\leq 2m}$ of response $y_{i}$ and check the equality
$\texttt{Equal}(y_{i,2j},\tilde{y}_{i,2j})_{1\leq j\leq 2m}$ in our
construction.

HPUF
$\mathcal{E}_{f}$$\texttt{Ver}(\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}},\tilde{\rho}_{1})$Output$x_{i}$$\ket{\psi_{f(x_{i})}}\bra{\psi_{f(x_{i})}}$$\tilde{\rho}_{1}$$\ket{\psi_{f_{2}(x_{i})}}\bra{\psi_{f_{2}(x_{i})}}$$/\perp$b
Figure 9: Hybrid Locked PUF (HLPUF) $\mathcal{E}^{L}_{f}$. The verification
algorithm $\texttt{Ver}(.,.)$ is specified by measurement as described in
Construction 2. Here,
$\ket{\psi_{f(x_{i})}}\bra{\psi_{f(x_{i})}}=\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}}\otimes\ket{\psi_{f_{2}(x_{i})}}\bra{\psi_{f_{2}(x_{i})}}$

###  E.2 Security Analysis

In this section, we give a comprehensive security analysis of the previously
proposed constructions. First, we show that using hybrid construction will
exponentially improve the security of classical PUFs. More precisely, it will
exponentially decrease the success probability of a quantum adversary in the
universal unforgeability game, compared to a classical PUF with the same
number of learning queries. Further, we show how much quantum communication
can improve the security of a weaker classical PUF and as a result propose an
efficient and secure construction that can be built using existing classical
PUFs. Finally, we analyse the completeness and security of the hybrid PUF-
based device authentication protocol and show that under the assumption that
the inherent classical PUF resist the weak quantum adversary, the HLPUF-based
protocol will be secure against an adaptive adversary.

####  E.2.1 Assumptions on the CPUFs

For the security analysis of our constructions we consider the following
assumptions of the CPUFs
$f\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{4m}$.

  1. 1.

For any input $x\in\\{0,1\\}^{n}$ the probability distributions of the $4m$
output bits $f(x)_{1},\ldots,f(x)_{4m}$ are independent and identically
distributed (i.i.d).

  2. 2.

The output distributions $\\{p^{f}_{x}(y)\\}_{y\in\\{0,1\\}^{4m}}$ for all the
inputs $x$ are independent and identically distributed (i.i.d).

####  E.2.2 Security of the HPUFs against the weak Adversaries

Intuitively the security of our HPUF comes from the indistinguishability
property of the non-orthogonal quantum states. In Theorem 1, we first show
that the HPUFs are at least as secure as the underlying CPUFs. Here we only
give the proof sketch, later in Appendix I.2 we give the detailed proof.

######  Theorem 1.

Let $f\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{2m}$
be a classical PUF. If there is no QPT weak adversary who can win the
universal unforgeability game for CPUF with more than a negligible probability
in the security parameter, then the HPUF constructed from $f$ according to
construction 2, is also universally unforgeable.

###### Proof Sketch..

Here we prove the theorem using a contrapositive argument, i.e., we show that
if any QPT weak adversary can forge the HPUF, then it can also forge the
underlying CPUF efficiently. If any QPT weak adversary can forge the HPUF,
i.e., win the universal unforgeability game with a non-negligible probability,
then for a random challenge $x^{*}\in_{R}\\{0,1\\}^{n}$ it can produce the
correct output state $|\psi_{f(x^{*})}\rangle$. Note that, the adversary can
produce multiple copies of the output state $|\psi_{f(x^{*})}\rangle$ by
fixing all the internal parameters of the attack algorithm to the same values.
The forged quantum state $|\psi_{f(x^{*})}\rangle$ is a product state of $m$
qubit states, where each qubit belongs to the set
$\\{|0\rangle,|1\rangle,|+\rangle,|-\rangle\\}$. If the adversary has multiple
copies of each qubit, then it can perform full state tomography just by
measuring them in the $\\{|0\rangle,|1\rangle\\}$-basis, and
$\\{|+\rangle,|-\rangle\\}$-basis. Thus, it can learn $f(x^{*})$ from
$|\psi_{f(x^{*})}\rangle$ with probability arbitrarily close to one.
Therefore, it can forge the CPUF with a non-negligible probability. This
concludes the proof sketch. The full proof is given in Appendix I.2. ∎

The above theorem is an intuitive result that shows HPUF is stronger or at
least as strong as the underlying CPUF. Although we want to prove a more
powerful and explicit statement regarding HPUFs by quantifying how much the
hybrid construction will boost security. In fact, we want to show that one can
construct a secure unforgeable HPUF against a quantum adversary even if the
underlying CPUF is breakable (with a certain probability) against the
classical forger. To this end, we compare the success probability of a QPT
adversary in breaking the HPUF in the universal unforgeability game, with the
success probability of the adversary who breaks the CPUF with a certain non-
negligible probability in a fixed query setting. This will allow us to show
that some of the weak and considerably broken CPUFs can still be used to
construct an asymptotically secure HPUF against stronger quantum adversaries
since the quantum encoding drastically decreases the success probability.

In Lemma 1, first we give an upper bound on the adversaries guessing
probability of the response $f(x_{i})$ corresponding to a challenge $x_{i}$
and a single copy of the quantum response state $|\psi_{f(x_{i})}\rangle$. The
complete proof can be found in Section I.1.

######  Lemma 1.

Suppose
$f\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{4m}$ be
a CPUF with the following property,

$\forall~{}~{}x_{i}\in\\{0,1\\}^{n},\forall~{}~{}1\leq j\leq
4m,~{}~{}p^{f}_{x_{i}}(y_{i,j}=0)=\frac{1}{2}+\delta_{r},$ (17)

with a biased distribution $p=\frac{1}{2}+\delta_{r}$ where
$0\leq\delta_{r}\leq\frac{1}{2}$, and $\mathcal{E}_{f}$ be a HPUF
corresponding to $f$ that we construct using Construction 1. Let a quantum
adversary $\mathcal{A}^{i,j}_{guess}$ extract the value $y_{i,(2j-1)}$ out of
$(y_{i,(2j-1)},y_{i,2j})$ from quantum state
$|\psi^{i,j}_{\mathrm{out}}\rangle\langle\psi^{i,j}_{\mathrm{out}}|$
corresponding to a random challenge $x_{i}$. If all the output bits of the
CPUF are independent and identically distributed, then for any quantum
adversary $\mathcal{A}^{i,j}_{guess}$, and $\forall~{}x_{i}\in\\{0,1\\}^{n}$,

$\displaystyle p_{\text{guess}}$
$\displaystyle\mathrel{\mathop{\ordinarycolon}}=\Pr[\mathcal{A}^{i,j}_{guess}(x_{i},|\psi^{i,j}_{\mathrm{out}}\rangle\langle\psi^{i,j}_{\mathrm{out}}|)=y_{i,(2j-1)}]$
$\displaystyle\leq p(1+\sqrt{p^{2}+(1-p)^{2}})$ $\displaystyle\leq
p(1+\sqrt{2}p)$ (18)

Lemma 2 shows that the adversary needs to extract the classical information
$f(x)$ that is encoded in the quantum state $|\psi_{f(x)}\rangle$ for the
forgery of the HPUFs. Here we only state the lemma, and for the complete proof
we refer to Appendix I.3.

######  Lemma 2.

Suppose
$|D_{q}\rangle=\bigotimes_{i=1}^{q}\left(|x_{i}\rangle_{C}\otimes|\psi_{f(x_{i})}\rangle_{R}\right)$
denotes the adversary’s database of $q$ random CRPs that are generated from a
HPUF
$\mathcal{E}_{f}\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow(\mathcal{H}^{2})^{\otimes
m}$. If $E(D_{q})$ denotes the measurement strategy for forging the HPUF with
probability $p_{\text{forge}}$ using the database $D_{q}$, then using the
following measure-then-forge strategy that can forge the HPUF with the same
probability $p_{\text{forge}}$.

  * •

Adversary extracts the classical encoding $\\{f(x_{i})\\}_{1\leq i\leq q}$
from $|D_{q}\rangle$. Let $\\{\tilde{f}(x_{i})\\}_{1\leq i\leq q}$ denotes the
extracted classical string.

  * •

The QPT adversary applies a forging strategy using the extracted data set
$\\{\tilde{f}(x_{i})\\}_{1\leq i\leq q}$.

Lemma 2 suggests that the optimal adversary first needs to extract the
classical information from the database state $|D_{q}\rangle$, and then
perform the modeling attack to guess $|\psi_{f(x^{*})}\rangle$. In general, if
the extracted classical information $\\{\tilde{f}(x_{i})\\}_{1\leq i\leq q}$
from the database state $|D_{q}\rangle$ is very far from the original encoded
string $\\{f(x_{i})\\}_{1\leq i\leq q}$ then it would be difficult for the
adversary to forge the HPUF, based on that noisy data set. Here, we define the
distance between $\tilde{D}^{x}_{q}=\\{\tilde{f}(x_{i})\\}_{1\leq i\leq q}$,
and $D^{x}_{q}=\\{f(x_{i})\\}_{1\leq i\leq q}$ as follows.

$\text{dist}(\tilde{D}^{x}_{q},D^{x}_{q})\mathrel{\mathop{\ordinarycolon}}=\frac{\sum_{i=1}^{q}\text{Mis-
match}(\tilde{f}(x_{i}),f(x_{i}))}{q},$ (19)

where we define $\text{Mis-match}(\tilde{f}(x_{i}),f(x_{i}))$ as follows.

$\text{Mis-
match}(\tilde{f}(x_{i}),f(x_{i}))\mathrel{\mathop{\ordinarycolon}}=\begin{cases}&1~{}~{}~{}~{}~{}\text{If
}(\tilde{f}(x_{i})\neq f(x_{i}))\\\
&0~{}~{}~{}~{}~{}\text{Otherwise.}\end{cases}$ (20)

It is reasonable to assume that, no forging strategy can forge the HPUF with a
non-negligible probability that run on the noisy database set
$\tilde{D}^{x}_{q}$ such that
$\text{dist}(\tilde{D}^{x}_{q},D^{x}_{q})>\varepsilon$, where
$0\leq\varepsilon\leq 1$ is a parameter that quantifies the error threshold.
In the next lemma we give an upper bound on extracting $\tilde{D}^{x}_{q}$
from $|D_{q}\rangle$ such that
$\text{dist}(\tilde{D}^{x}_{q},D^{x}_{q})\leq\varepsilon$. Intuitively, a
robust HPUF is with low $\varepsilon$ such that an adversary can not forge it
with a noisy data set which is very far away from the original data set.
Otherwise, the $\varepsilon$ should be high with a bad HPUF.

######  Lemma 3.

Suppose
$|D_{q}\rangle=\bigotimes_{i=1}^{q}\left(|x_{i}\rangle_{C}\otimes|\psi_{f(x_{i})}\rangle_{R}\right)$
denotes the adversary’s database of $q$ random CRPs that are generated from a
HPUF
$\mathcal{E}_{f}\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow(\mathcal{H}^{2})^{\otimes
m}$. If $\tilde{D}_{q}$ denotes the noisy classical response set that is
extracted from $|D_{q}\rangle$ such that
$\text{dist}(D_{q},\tilde{D}_{q})\leq\varepsilon$ with probability
$p_{\text{extract}}$, then

$p_{\text{extract}}\leq\sum_{k=(1-\varepsilon)q}^{q}\binom{q}{k}(p_{\text{guess}})^{2mk}(1-(p_{\text{guess}})^{2m})^{q-k},$
(21)

where $p_{\text{guess}}\leq p(1+\sqrt{2}p)$, defined in Lemma 1.

###### Proof Sketch..

A $q$-query weak adversary gets a $q$ random outputs from the HPUF
$\mathcal{E}_{f}\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow(\mathcal{H}^{2})^{\otimes
m}$ along with $q$ bit random strings $X_{i}\in_{R}\\{0,1\\}^{n}$. Here each
output state is $m$-qubit product state, where each qubit belongs to
$\\{|0\rangle,|1\rangle,|+\rangle,|-\rangle\\}$, depending on the value of the
random variable $f(X_{i})$. In Lemma 1, we show that the probability of
guessing a single output bit is $p_{\text{guess}}$. Due to the i.i.d
assumption on the different output bits of a single outcome of the CPUF, the
probability of guessing all the $2m$ output bits from the state
$|\psi_{f(X_{i})}\rangle$ is upper bounded by $(p_{\text{guess}})^{2m}$.

Here, we would like to compute the probability of successfully guessing
$f(X_{i})$’s for at least $(1-\varepsilon)q$ random samples. e denote this
probability as $p_{\text{extract}}$. Due to the i.i.d assumption on the
outcomes $f(X_{i})$’s of the CPUF, the probability of guessing exactly $k$
responses out of $q$ responses is given by
$\binom{q}{k}(p_{\text{guess}})^{2m}(1-(p_{\text{guess}})^{2m})^{q-k}$.
Therefore, we get the following upper bound on the $p_{\text{extract}}$.

$p_{\text{extract}}\leq\sum_{k=(1-\varepsilon)q}^{q}\binom{q}{k}(p_{\text{guess}})^{2mk}(1-(p_{\text{guess}})^{2m})^{q-k}.$
(22)

This concludes the proof. ∎

To provide a better intuition of the expression of $p_{\text{extract}}$ to
show the exponential gap, we give in Figure 10 the evolution of
$p_{\text{extract}}$ for different values of $\varepsilon$. It means that with
a bad HPUF with high $\varepsilon$, the $p_{\text{extract}}$ converges to
$1-negl(\lambda)$ as $q$, the number of queries of the QPT weak adversary,
increases. Otherwise, for smaller error threshold, corresponding to a better
HPUF, it decreases exponentially with $q$. Later, we show in Section G the
$\varepsilon$ of HPUF depends on its underlying CPUFs, and the machine-
learning algorithm we use to forge the HPUF.

Figure 10: Evolution of $p_{\text{extract}}$ with different values of
$\varepsilon$

In the next theorem, we give a upper bound of the success probability of
forging a HPUF by a QPT weak adversary.

######  Theorem 2.

Let $f\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{4m}$
be a classical PUF with $p$-randomness, where $p=(\frac{1}{2}+\delta_{r})$
with the following two properties.

  1. 1.

Let any $q$-query weak adversary win the universal unforgeability game for the
CPUF $f$ with probability at most
$p_{\text{forge}}^{\text{classical}}(m,p,q)\geq nonnegl(\lambda)$.

  2. 2.

There is no QPT adversary that can win the universal unforgeability game for
the CPUF using a noisy database $\tilde{D}_{q}$ such that
$\text{dist}(D_{q},\tilde{D}_{q})>\varepsilon$.

If we construct a HPUF $\mathcal{E}_{f}$ from such a CPUF $f$, then the
$q$-query weak quantum adversary can win the universal unforgeability game for
the HPUF $\mathcal{E}_{f}$ with probability
$p_{\text{forge}}^{quantum}(x^{*},p,|Q_{q}\rangle)$, such that,

$p_{\text{forge}}^{\text{quantum}}(x^{*},p,|Q_{q}\rangle)\leq
p_{\text{extract}}\times p_{\text{forge}}^{\text{classical}}(m,p,q),$ (23)

where

$p_{\text{extract}}\leq\sum_{k=(1-\varepsilon)q}^{q}\binom{q}{k}(p_{\text{guess}})^{2mk}(1-(p_{\text{guess}})^{2m})^{q-k}.$

###### Proof.

From Lemma 2, we get that the optimal adversary’s strategy is measure-then-
forge. Let $\tilde{D}_{q}$ denotes the set of extracted database response.
From the assumption $2$, we get that the adversary can forge the HPUF with a
non-negligible probability if and only if
$\text{dist}(\tilde{D}_{q},D_{q})\leq\varepsilon$. Suppose
$p_{\text{extract}}$ denotes the optimal success probability of extracting
$\tilde{D}_{q}$ from $|D_{q}\rangle$ such that
$\text{dist}(D_{q},\tilde{D}_{q})\leq\varepsilon$. If
$p^{\text{classical}}_{\text{forge}}(\tilde{D}_{q},X^{*},p)$ denotes the
optimal forging probability using the database $\tilde{D}_{q}$, then the total
forging probability is given by the following equation.

$p_{\text{forge}}^{\text{quantum}}(X^{*},p,|D_{q}\rangle)=p_{\text{extract}}\times
p_{\text{forge}}^{\text{classical}}(\tilde{D}_{q},X^{*},p).$ (24)

Note that, the adversary’s optimal forging probability with database $D_{q}$
is always higher than the optimal forging probability with the database
$\tilde{D}_{q}$, i.e.,

$p_{\text{forge}}^{\text{classical}}(m,p,q)\geq
p_{\text{forge}}^{\text{classical}}(\tilde{D}_{q},X^{*},p).$ (25)

Substituting the relation in Equation (25) in Equation (24) we get the
following expression of
$p_{\text{forge}}^{\text{quantum}}(X^{*},p,|D_{q}\rangle)$.

$p^{\text{quantum}}_{\text{forge}}(X^{*},p,|D_{q}\rangle)\leq
p_{\text{extract}}\times p_{\text{forge}}^{\text{classical}}(m,p,q).$ (26)

From Lemma 3 we get that
$p_{\text{extract}}\leq\sum_{k=(1-\varepsilon)q}^{q}\binom{q}{k}(p_{\text{guess}})^{2mk}(1-(p_{\text{guess}})^{2m})^{q-k}$.
By substituting the expression of $p_{\text{success}}$ in Equation (26), we
get the desired upper bound on the
$p^{\text{quantum}}_{\text{forge}}(X^{*},p,|D_{q}\rangle)$. This concludes the
proof. ∎

The above result is a general statement for any fixed number of queries and
compares the success probability of a weak adversary in breaking the
unforgeability of CPUF and HPUF. Given this theorem, we can also easily state
the following corollary that ensures the universal unforgeability of an HPUF
constructed from a CPUF that does not provide suitable security, yet is not
totally broken with overwhelming probability.

######  Corollary 1.

Let the success probability of any QPT weak-adversary in the universal
unforgeability game with a CPUF
$f\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{4m}$
with $p$-randomness, be at most $p^{\text{classic}}_{\text{forge}}$, where
$0\leq p^{\text{classic}}_{\text{forge}}\leq 1-\text{non-negl}(2m)$. Then,
there always exist an error threshold $0<\varepsilon\leq 1$ for which the
success probability of any QPT adversary in the universal unforgeability game
for the HPUF $\mathcal{E}_{f}$, is at most $\epsilon(2m)$, which is a
negligible function in the security parameter. Hence such HPUFs are
universally unforgeable.

This directly follows from Theorem 2 where
$p^{\text{classic}}_{\text{forge}}=p_{\text{forge}}^{\text{classical}}(m,p,q)$
for any $q=poly(m)$ is a value between $0$ and $1$, and not negligibly close
to $1$. As shown in the proof of Theorem 2 in the Appendix, for a large family
of $\varepsilon$ the first part of the probability, namely
$p_{\text{extract}}$ becomes negligibly small (in $2m$) and hence the overall
probability becomes a negligible function $\epsilon(2m)$.

####  E.2.3 Security of the HLPUFs against general adaptive adversaries

In the last two theorems, we analyse the security of the HPUFs against only
weak adversaries. In Theorem 3 we show that if the HPUFs are secure against
the weak adversaries then with the lockdown technique we can make the HLPUFs
secure against the adaptive adversaries.

######  Theorem 3.

Let
$\mathcal{E}_{f}\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow(\mathcal{H}^{2})^{\otimes
m}\otimes(\mathcal{H}^{2})^{\otimes m}$ be a hybrid PUF that we construct from
a classical PUF
$f\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{2m}\times\\{0,1\\}^{2m}$
and let
$\mathcal{E}^{L}_{f}\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\times(\mathcal{H}^{2})^{\otimes
m}\rightarrow(\mathcal{H}^{2})^{\otimes m}$ denotes the HLPUF that we
construct from $\mathcal{E}_{f}$ using the Construction 2. If
$\mathcal{E}_{f}=\mathcal{E}_{f_{1}}\otimes\mathcal{E}_{f_{2}}$ and if each of
the mappings $\mathcal{E}_{f_{1}},\mathcal{E}_{f_{2}}$ has
$(\epsilon,m)$-universal unforgeability against the $q$-query weak
adversaries, then the corresponding HLPUF $\mathcal{E}^{L}_{f}$ is
$(\epsilon,m)$-secure against the $q$-query adaptive adversaries.

###### Proof Sketch..

According to the Construction 2, if the adaptive adversary tries to query the
HLPUF with any arbitrary challenge $x\in\\{0,1\\}^{n}$, then it also needs to
send a quantum state $\rho_{f_{1}(x)}$. The adversary successfully gets
$|\psi_{f_{1}(x)}\rangle$ as a reply if and only if
$\texttt{Ver}(\rho_{f_{1}(x)},|\psi_{f_{1}(x)}\rangle\langle\psi_{f_{1}(x)})=1$.
Note that the adversary doesn’t have any access to the underlying classical
PUF $f_{1}$, therefore it cannot produce such a $\rho_{f_{1}(x)}$ for an
arbitrary $x$. The only possible option is to use some of the previous
intercepted queries $x,|\psi_{f_{1}(x)}\rangle$ that were sent by the server.
As the server chooses its queries uniformly at random, the adaptive
adversaries need to depend on those random queries to make an adaptive query
to the HLPUF. Moreover, for the adaptive queries to the HLPUF, first the
adversary needs to forge the mapping $\mathcal{E}_{f_{1}}$ using the $q$
random challenge-response pairs
$\\{x_{i},|\psi_{f_{1}(x_{i})}\rangle\\}_{1\leq i\leq q}$. Here, we assume
that the mapping $\mathcal{E}_{f_{1}}$ is secure against $q$-query weak
adversaries, therefore the adaptive adversary cannot forge
$\mathcal{E}_{f_{1}}$. Hence, the $q$-query adaptive adversary can only get
the responses from the mapping $\mathcal{E}_{f_{2}}$ for at most $q$ random
queries. According to the assumption, the mapping $\mathcal{E}_{f_{2}}$ is
also secure against $q$-query weak adversaries. Therefore, from $q$ random
challenge-response pairs the adaptive adversary couldn’t forge
$\mathcal{E}_{f_{2}}$. Hence, the HLPUF remains secure against the $q$-query
adaptive adversaries. This concludes the proof sketch. ∎

####  E.2.4 Security of the HLPUF-based Authentication Protocol:

In this section, we firstly give a full formal description of the HLPUF-based
authentication protocol, then we define the completeness and security property
of Protocol E.2.4. Later, in Theorem 4 we prove its completeness and security.

[!h] Hybrid PUF-based Authentication Protocol with Lockdown Technique

  1. 1.

Setup:

    1. (a)

The Prover $\mathcal{P}$ equips a Hybrid Locked PUF: $\mathcal{E}_{f}^{L}$
with HPUF
$\mathcal{E}_{f}\mathrel{\mathop{\ordinarycolon}}\\{0,1\\}^{n}\rightarrow(\mathcal{H}^{2})^{\otimes
2m}$ constructed upon a classical PUF
$f\mathrel{\mathop{\ordinarycolon}}\mathcal{X}\rightarrow\mathcal{Y}$. Here,
the classical PUF $f$ maps an $n$-bit string $x_{i}\in\\{0,1\\}^{n}$ to an
$4m$-bit string output $y_{i}\in\\{0,1\\}^{4m}$.

    2. (b)

The Verifier $\mathcal{V}$ has a classical database
$D\mathrel{\mathop{\ordinarycolon}}=\\{(x_{i},y_{i})\\}_{i=1}^{d}$ with all
$d$ CRPs of $f$, as well as the necessary quantum devices for preparing and
measuring quantum states.

  2. 2.

Authentication:

    1. (a)

$\mathcal{V}$ randomly chooses a CRP $(x_{i},y_{i})$ and splits the response
equally into two partitions
$y_{i}=f_{1}(x_{i})||f_{2}(x_{i})=y_{i}^{1}||y_{i}^{2}$ with length $2m$.

    2. (b)

$\mathcal{V}$ then encodes the first partition of response into
$\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}}\mathrel{\mathop{\ordinarycolon}}=\bigotimes_{j=1}^{m}|\psi^{i,j}_{f_{1}(x_{i})}\rangle\langle\psi^{i,j}_{f_{1}(x_{i})}|$
and issues the joint state
$(x_{i},\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}})$ to the client.

    3. (c)

$\mathcal{P}$ receives the joint state $(x_{i},\tilde{\rho}_{1})$ and queries
Hybrid Locked PUF $\mathcal{E}_{f}^{L}$. If the verification algorithm
$\texttt{Ver}(\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}},\tilde{\rho}_{1})\geq
1-\epsilon(\lambda)$ with negligible $\epsilon(\lambda)$, $\mathcal{P}$
obtains
$\ket{\psi_{f_{2}(x_{i})}}\bra{\psi_{f_{2}(x_{i})}}\mathrel{\mathop{\ordinarycolon}}=\bigotimes_{j=1}^{m}|\psi^{i,j}_{f_{2}(x_{i})}\rangle\langle\psi^{i,j}_{f_{2}(x_{i})}|$
from $\mathcal{E}_{f}^{L}$ and sends back to $\mathcal{V}$. Otherwise, the
authentication aborts.

    4. (d)

$\mathcal{V}$ receives the quantum state $\tilde{\rho}_{2}$ and performs the
the verification algorithm $\texttt{Ver}(.,.)$ as described in Construction 2.
If
$\texttt{Ver}(\ket{\psi_{f_{2}(x_{i})}}\bra{\psi_{f_{2}(x_{i})}},\tilde{\rho}_{2})\geq
1-\epsilon(\lambda)$ with negligible $\epsilon(\lambda)$, the authentication
passes. Otherwise it aborts.

######  Definition 7 (Completeness of HLPUF-based Authentication Protocol
E.2.4).

We say the HLPUF-based authentication protocol E.2.4 satisfies completeness if
in the absence of any adversary, an honest client and server generating
$|\psi_{f_{1}(x_{i})}\rangle\langle\psi_{f_{1}(x_{i})}|$ and
$|\psi_{f_{2}(x_{i})}\rangle\langle\psi_{f_{2}(x_{i})}|$ with a valid HLPUF
for any selected challenge $x_{i}$, can pass the verification algorithms with
overwhelming probability:

$\displaystyle\text{Pr}[\texttt{Ver}$
$\displaystyle(|\psi_{f_{1}(x_{i})}\rangle\langle\psi_{f_{1}(x_{i})}|,\tilde{\rho}_{1})$
$\displaystyle=\texttt{Ver}(|\psi_{f_{2}(x_{i})}\rangle\langle\psi_{f_{2}(x_{i})}|,\tilde{\rho}_{2})=1]\geq
1-\epsilon(\lambda)$ (27)

Now, we also define the security of our HLPUF-based authentication protocol,
in relation with the universal unforgeability game as follows:

######  Definition 8 (Security of the HLPUF-based Authentication Protocol
E.2.4).

We say the HLPUF-based authentication protocol E.2.4 is secure if the success
probability of any QPT adaptive adversary $\mathcal{A}_{ad}$ in winning the
universal unforgeability game to forge an output of HLPUF according to
Construction 2, for any randomly selected challenge of the form
$\tilde{c}=(x,|\psi_{f_{1}(x)}\rangle\langle\psi_{f_{1}(x)}|)$ is at most
negligible in the security parameter:

$Pr[1\leftarrow\mathcal{G}^{HLPUF}(\mathcal{A}_{ad},\lambda)]\leq\epsilon(\lambda)$
(28)

where the verification algorithm of the universal unforgeability game checks
the adversary’s output $\sigma_{2}$, with the output of the HLPUF,
$\ket{\psi_{f_{2}(x)}}\bra{\psi_{f_{2}(x)}}$.

######  Theorem 4.

If the HLPUF $\mathcal{E}^{L}_{f}$ is constructed from a hybrid PUF
$\mathcal{E}_{f}$ using the Construction 2 then the locked PUF-based
authentication Protocol E.2.4 satisfies both the completeness and security
conditions.

###### Proof.

In Protocol E.2.4 with hybrid PUF
$\mathcal{E}_{f}=\mathcal{E}_{f_{1}}\otimes\mathcal{E}_{f_{2}}$, the server
chooses the classical input $x_{i}\in\mathcal{X}$, encodes the quantum state
corresponding to $2m$ bits of $f_{1}(x_{i})$ and issues the joint state to the
client. If there is no adversary, the client receives the joint state and
queries $\mathcal{E}_{f}$ with $x_{i}$ and $\tilde{\rho}_{1}$, where
$\tilde{\rho}_{1}=\mathcal{E}_{f_{1}}(x_{i})=\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}}$
for the first $m$ qubits of $\mathcal{E}_{f}(x_{i})$. Hence we have:

$Pr\left[\texttt{Ver}(|\psi_{f_{1}(x_{i})}\rangle\langle\psi_{f_{1}(x_{i})}|,\tilde{\rho}_{1})=1\right]=1$
(29)

On the client side, since the verification algorithm of HLPUF
$\mathcal{E}_{f}^{L}$ always passes with
$\texttt{Ver}(|\psi_{f_{1}(x_{i})}\rangle\langle\psi_{f_{1}(x_{i})}|,\tilde{\rho}_{1})=1$,
he returns the quantum state
$\mathcal{E}_{f_{2}}(x_{i})=|\psi_{f_{2}(x_{i})}\rangle\langle\psi_{f_{2}(x_{i})}|$
corresponding to $2m$ bits of $f_{2}(x_{i})$ to the server. Without the
presence of adversary, the server always receives the state with
$\tilde{\rho}_{2}=|\psi_{f_{2}(x_{i})}\rangle\langle\psi_{f_{2}(x_{i})}|$, and
we obtain the equation similarly to Equation (29). Therefore, we can say the
locked PUF-based authentication protocol satisfies the completeness condition
with

$\displaystyle\text{Pr}[\texttt{Ver}$
$\displaystyle(|\psi_{f_{1}(x_{i})}\rangle\langle\psi_{f_{1}(x_{i})}|,\tilde{\rho}_{1})$
$\displaystyle=\texttt{Ver}(|\psi_{f_{2}(x_{i})}\rangle\langle\psi_{f_{2}(x_{i})}|,\tilde{\rho}_{2})=1]=1$
(30)

On the other hand for the security, we rely on Theorem 3 that the HLPUF
$\mathcal{E}_{f}^{L}$ is $(\epsilon,m)$-secure against any QPT adaptive
adversary (a $q$-query adaptive adversary for any $q$ polynomial in the
security parameter). For both $\mathcal{E}_{f_{1}}$ and $\mathcal{E}_{f_{2}}$
of HPUF $\mathcal{E}_{f}$, we show that the power of adaptive adversary can be
reduced to the power of a weak adversary, due to the lockdown technique. Also
since $\mathcal{E}_{f_{1}}$ has the universal unforgeability against weak
adversary by definition, for any adaptive query of the form
$(x_{i},\sigma_{1})$ that an adaptive adversary issues to the HLPUF, the
following applies:

$\text{Pr}\left[\texttt{Ver}(|\psi_{f_{1}(x_{i})}\rangle\langle\psi_{f_{1}(x_{i})}|,\sigma_{1})=1\right]\leq\epsilon(m)$
(31)

Where $|\psi_{f_{1}(x_{i})}\rangle\langle\psi_{f_{1}(x_{i})}|$ is the correct
response constructed from CPUF according to HPUF construction. Thus the power
of the adaptive adversary reduces to the power of weak adversary and we have:

$Pr[1\leftarrow\mathcal{G}^{HLPUF}(\mathcal{A}_{ad},m)]\approx
Pr[1\leftarrow\mathcal{G}^{HLPUF}(\mathcal{A}_{weak},m)]$ (32)

Now given the fact that the adaptive adversary cannot boost from the weak-
learning phase to the HPUF, producing a forgery $\sigma_{2}$ for the HLPUF
that passes the verification
$\texttt{Ver}(|\psi_{f_{2}(x_{i})}\rangle\langle\psi_{f_{2}(x_{i})}|,\sigma_{2})$,
reduces to forging the HPUF $\mathcal{E}_{f_{2}}$. Again by assumption,
$\mathcal{E}_{f_{2}}$ has the universal unforgeability against weak adversary,
hence we have:

$\displaystyle Pr[1\leftarrow\mathcal{G}^{HLPUF}(\mathcal{A}_{ad},m)]$
$\displaystyle=Pr[1\leftarrow\mathcal{G}^{HPUF}(\mathcal{A}_{weak},m)]$
$\displaystyle\leq\epsilon(m)$ (33)

This concludes the proof. ∎

##  Appendix F Challenge Reusability

We have discussed in the main paper about the issue of challenge-reusability
in classical PUF-based protocols and discussed how our construction brings
forward unique and new solution for this problem. In this section we dive
deeper into this issue and we formally prove why our proposal satisfies the
important property of challenge reusability.

We are thus interested in the eavesdropping attacks by the adversary on the
first and second half of the response states that are of the form
$\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}}=\bigotimes_{j=1}^{m}|\psi^{i,j}_{f_{1}(x_{i})}\rangle\langle\psi^{i,j}_{f_{1}(x_{i})}|$
and
$\ket{\psi_{f_{2}(x_{i})}}\bra{\psi_{f_{2}(x_{i})}}=\bigotimes_{j=1}^{m}|\psi^{i,j}_{f_{2}(x_{i})}\rangle\langle\psi^{i,j}_{f_{2}(x_{i})}|$.
Note that eavesdropping on the states that encode the first part of the
response will lead to breaking the locking mechanism while eavesdropping on
the second half will lead to an attack on the identification. Without loss of
generality, we only consider one of the cases where the adversary wants to
eavesdrop on the first (or second) half to break the protocol in the upcoming
rounds where the challenge is reused. The arguments will hold equivalently for
both cases since the states and verification are symmetric.

Given all these considerations, the challenge reusability problem will reduce
to the optimal probability of the eavesdropping attack on
$\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}}=\bigotimes_{j=1}^{m}|\psi^{i,j}_{f_{1}(x_{i})}\rangle\langle\psi^{i,j}_{f_{1}(x_{i})}|$
which is in fact $m$ qubit states encoded in conjugate basis same as BB84
states. In the most general case, the adversary can perform any arbitrary
quantum operation on the state
$\bigotimes_{j=1}^{m}|\psi^{i,j}_{f_{1}(x_{i})}\rangle\langle\psi^{i,j}_{f_{1}(x_{i})}|$
or separately on each qubit state $\ket{\psi^{i,j}_{f_{1}(x_{i})}}$, together
with a local ancillary system and sends a partial state of this larger state
to the verifier to pass the verification test, and keep the local state to
extract the encoded response bits. Let $\rho_{SEC}$ be the joint state of the
server, the eavesdropper and the client. Since the states used in the protocol
are from Mutually Unbiased Basis (MUB) states i.e. from either
$Z=\\{\ket{0},\ket{1}\\}$ or $X=\\{\ket{+},\ket{-}\\}$, in order to show the
optimal attack, we can rely on the entropy uncertainty relations that have
been used for the security proof of QKD. The measurements for verification are
also performed in the $\\{Z,X\\}$ bases accordingly. We use the entropy
uncertainty relations from [11] where the security criteria for QKD have been
given in terms of the conditional entropy for MUBs measurements. Using these
results we show that the entropy of Eve in guessing the correct classical bits
for the response is very high if the state sent to the verification algorithm
passes the verification with a high probability. Intuitively this is due to
the uncertainty that exists related to the commutation relation between $X$
and $Z$ operators in quantum mechanics. Hence we conclude that the success
probability of Eve in extracting information from the encoded halves of the
response is relatively low. Also, we show that this uncertainty increases
linearly with $m$ similar to the number of rounds for QKD. This argument
results in the following theorem which we will formally describe and prove in
Appendix I.6 where we also introduce the uncertainty relations.

######  Theorem 5 (informal).

In Protocol E.2.4, if the client (or server for the second half of the state)
verification does not abort for a challenge $x$, then Eve’s uncertainty on
respective response of the CPUF, denoted by $H_{min}^{Eve}$ is greater than
$m-\epsilon(m)$.

Now, we first define the reusability in relation with the unforgeability game
and then using Theorem 5, we prove the challenge reusability of the HLPUF-
based Protocol E.2.4.

######  Definition 9 (Challenge ($k$-)reusability in the universal
unforgeability game).

Let $\mathcal{G}_{re}(\lambda,\mathcal{A},x_{k+1})$ be a special instance of
the universal unforgeability game, where a challenge $x$, picked uniformly at
random by the challenger, has been previously used $k$ times. We are
interested in the events where the same challenge is used in the $(k+1)$-th
round, which we denote by $x_{k+1}$. We say the challenge $x$ is ($k$-)re-
usable if the success probability of any QPT adversary in winning
$\mathcal{G}_{re}(\lambda,\mathcal{A},x_{k+1})$, i.e, in forging message
$x_{k+1}$, is negligible in the security parameter:

$Pr_{forge}(\mathcal{A},x_{k+1})=Pr[1\leftarrow\mathcal{G}_{re}(\lambda,\mathcal{A},x_{k+1})]\leq\epsilon(\lambda)$
(34)

######  Theorem 6 (Challenge reusability of HLPUF-based Authentication
Protocol E.2.4).

A challenge $x$ can be reused $k$ times during the Protocol E.2.4 as long as
the received respective response $\sigma$ for each round passes the (client’s
or server’s) verification with overwhelming probability. In other words, under
the successful verification, the success probability of the adversary in
passing the $(k+1)$-th round with the same challenge $x$ is bounded as
follows:

$Pr_{forge}(\mathcal{A},x_{k+1})\leq k2^{-m}\approx\epsilon(m).$ (35)

###### Proof.

To prove this theorem, we use the Theorem 5 directly. First, we assume that
$x$ has been used one time before in a previous round. Given the assumption
that the verification is passed with probability $1-\epsilon(m)$, and this
theorem, we conclude that the uncertainty of the adversary in guessing the
encoded response of the HLPUF is larger than $m-\epsilon(m)$. In our case, the
joint quantum state between the server and the adversary is a classical-
quantum state (server has the classical description of $f(x)$, and the
adversary has the quantum state $|\psi_{f(x)}\rangle$). For such states, Eve’s
uncertainty, $H_{min}^{Eve}$ is same as $-\log P_{guess}^{Eve}$, where
$P_{guess}^{Eve}$ is Eve’s guessing probability of the classical information
encoded in the quantum state [35]. Therefore,

$\begin{split}P_{guess}^{Eve}&=2^{-H_{min}^{Eve}}\\\ &\leq
2^{-m+\epsilon(m)}\end{split}$ (36)

This probability is negligible in the security parameter, which means that
after performing any arbitrary quantum operations, the adversary’s local state
includes at most, a negligible amount of information on the response of $x$,
each round that the state $x$ is reused. Now, we can use the union bound to
show that this success probability only linearly scales with $k$:

$P_{guess}^{Eve,k}=P(\bigcup^{k}_{i=1}E_{guess}^{i})\leq\sum^{k}_{i=1}P(E_{guess}^{i})\approx
k2^{-m}$ (37)

where $E_{guess}^{i}$ are the events where Eve correctly guesses the response
and $P(E_{guess}^{i})=(P_{guess}^{Eve})^{i}$ is the success probability of Eve
in guessing in the $i$-th round. Finally, let the success probability of an
adversary in the universal unforgeability game for the HLPUF be upper-bounded
by $\epsilon_{1}(m)$ which is a negligible function in the security parameter
since we assume that the HLPUF satisfies the universal unforgeability. This is
the same as the success probability of the adversary in passing the
verification for a new challenge, chosen at random from the database. Now in
the $(k+1)$-th round, where the same $x$ is reused, the success probability is
at most boosted by the guessing probability over the previous $k$-th rounds,
hence we will have:

$Pr_{forge}(\mathcal{A},x_{k+1})\leq\epsilon_{1}(m)+k2^{-m}=\epsilon(m)$ (38)

As long as $k$ is polynomial in the security parameter, the second term is
also a negligible function and since the sum of two negligible probabilities
will be also negligible. This concludes the proof. ∎

##  Appendix G Simulation for HPUF/HLPUF

In this section, we simulate the design of HPUF/HLPUF constructions with
underlying silicon CPUFs instantiated by _pypuf_ [62]. _pypuf_ is a python-
based emulator that features different existing CPUFs. Furthermore, we
simulate the situation where a adversary acquires classical challenges and
quantum-encoded responses from HPUF/HLPUF and converts the response into
classical bit string by measuring the output quantum state. The adversary then
attempts to perform machine learning-based attacks with the obtained CRPs to
reproduce a model that predicts accurately enough the behaviour of the
underlying CPUF. As a result, we say such an adversary wins the unforgeability
game successfully in the end. According to the simulation result, we show the
performance of hybrid construction in boosting the security of CPUF, quantify
the existing advantage of hybrid construction and discuss potential
improvements to obtain greater security.

XOR Arbiter PUFs [49] with $n$-bit challenge to a one-bit response is one of
the CPUFs provided by pypuf. Its security is studied widely by Ulrich Rührmair
et al. [46]. In that paper, the performance of different machine learning
attacks like _Logistic Regression_ (LR), _Support Vector Machines_ (SVMs), and