Quantum Inf Process

DOI 10.1007/s11128-016-1316-x

Quantum cloning attacks against PUF-based quantum

authentication systems

Yao Yao1,2 · Ming Gao1,2 · Mo Li1,2 ·

Jian Zhang1,2

Received: 18 October 2015 / Accepted: 5 April 2016

© Springer Science+Business Media New York 2016

Abstract With the advent of physical unclonable functions (PUFs), PUF-based

quantum authentication systems have been proposed for security purposes, and
recently, proof-of-principle experiment has been demonstrated. As a further step
toward completing the security analysis, we investigate quantum cloning attacks
against PUF-based quantum authentication systems and prove that quantum cloning
attacks outperform the so-called challenge-estimation attacks. We present the analyt-
ical expression of the false-accept probability by use of the corresponding optimal
quantum cloning machines and extend the previous results in the literature. In light of
these findings, an explicit comparison is made between PUF-based quantum authen-
tication systems and quantum key distribution protocols in the context of cloning
attacks. Moreover, from an experimental perspective, a trade-off between the average
photon number and the detection efficiency is discussed in detail.

Keywords Quantum cloning attacks · Physical unclonable functions · Quantum

authentication · Quantum key distribution

B Yao Yao
yaoyao@mtrc.ac.cn
Mo Li
limo@mtrc.ac.cn

1 Microsystems and Terahertz Research Center, China Academy of Engineering Physics,

Chengdu 610200, Sichuan, China
2 Institute of Electronic Engineering, China Academy of Engineering Physics, Mianyang 621999,
Sichuan, China

123
 Y. Yao et al.

1 Introduction

Modern cryptographic applications, such as identification and authentication, rely

on mathematical one-way functions, which provide significant asymmetry between
a black-box inverter and a non-black-box extractor. However, they are confronted
with serious challenges from both practical and fundamental aspects. On one hand,
the enormous development has recently been made in the field of network parallel
computation and rapid reverse-engineering technology; on the other hand, a complete
proof of security is still missing, although the cryptographic primitives employed
nowadays are believed to be secure.
The concept of physical unclonable function (PUF) was introduced by R. Pappu
et al. to address all these security issues [1,2]. In contrast to mathematical one-way
functions, a PUF is a physical entity that is embodied in a specific physical structure
and is easy to evaluate but hard to characterize [3]. As its name suggests, an individual
PUF must be easy to be fabricated but practically infeasible to be duplicated, even
given the exact manufacturing process that produced it. In this sense, it is the physical
analog of a mathematical one-way function. Since the advent of the definition of PUF,
a great deal of PUF or PUF-like proposals and implementations has been raised as
cryptographic primitives for security purposes, such as optical PUFs [1,2], coating
PUFs [4], arbiter PUFs [5], ring oscillator PUFs [6], and SRAM PUFs [7]. For more
details, we refer the readers to Ref. [8].
Due to the desirable properties of PUF, such as unclonablity and unpredictability,
it naturally leads us to design authentication or anti-counterfeiting protocols based
on PUF devices. For instance, in the seminar paper by R. Pappu et al. [1,2], one of
the most significant demonstrations is to design authentication and anti-countering
protocol based on PUF made of a three-dimensional random scattering medium. It is
worth noting that the security of majority of PUF implementations is guaranteed by the
complex structure of the corresponding physical objects, e.g., the random distribution
of scatterers in optical medium [1,2]. Therefore, these classical PUF-based authenti-
cation protocols are theoretically breakable if infinite computing power is assumed. To
achieve a higher level of security, B. S̆korić proposed a new type of PUF, the quantum-
readout PUF, which combines the classical optical PUF with the quantum challenges
[9]. Recently, the first proof-of-principle experiment of PUF-based quantum-secure
authentication has been demonstrated by S. A. Goorden et al. [10], attracting a great
deal of attention from researchers [11].
However, the security analysis of PUF-based quantum-secure authentication pro-
tocols is still not more than mature or integrate due to its relative youth. To the best
our knowledge, only classical attacks, such as the challenge-estimation attacks, have
been considered [12,13]. As a further step toward completing the security analy-
sis, in this work we proposed the quantum cloning attacks, the first quantum attack
scenario against quantum-secure authentication systems, and investigated its effects
upon the false-accept probability. The outline of the reminder of this paper is as
follows: In Sect. 2, we provide a brief review of technical preliminaries of quantum-
readout PUFs and notations used throughout the paper. In the following Sect. 3, we
investigate quantum cloning attacks against PUF-based quantum authentication sys-
tems and prove that quantum cloning attacks outperform the challenge-estimation

123
Quantum cloning attacks against PUF-based quantum…

attacks. In Sect. 4, we extend our consideration to other quantum cloning attacks in the
framework of quantum cryptography. Finally, Sect. 5 is devoted to the discussion and
conclusion.

2 The model of PUF-based quantum authentication systems

2.1 The challenge and response behavior of optical PUFs

In this subsection, we mainly focus on the modeling of optical PUFs [1,2]. Note that
the transport of light through a multiple-scattering medium can be described by means
of the scattering matrix or S-matrix [14]. Therefore, the key point is to view the PUF
as a black box. If the collisions between photons and scatterers are further assumed to
be completely elastic, the behavior of such a black box can be fully characterized by
a unitary transformation, which is represented by a unitary S-matrix (see Fig. 1).
To describe the functionality of quantum-readout PUFs [9,10], three types of quan-
tum states are involved: the challenge state, reflected state, and transmitted state [9,10].
All these states we are dealing with have two intertwined degree of freedoms: the
internal degree of freedom characterizes the optical properties (e.g., spin or polariza-
tion), but the external degree of freedom depicts the directivity of light (e.g., direction
of motion), which is mathematically denoted as a tensor product of Hilbert spaces
H = Hext ⊗ Hint . Thus, any quantum state |ψ ∈ H can be represented as
 
|ψ1 
|ψ = |outgoing ⊗ |ψ1  + |incoming ⊗ |ψ2  = , (1)
|ψ2 

where |incoming, |outgoing ∈ Hext , |ψ1 , |ψ2  ∈ Hint , and here incoming or outgo-
ing is with respect to the sender.
Equipped with these notations, the interaction between the quantum state and the
optical PUF can be expressed as (see Fig. 1)

Fig. 1 Sketch of PUF-based quantum authentication system. The PUF device can be characterized as
the scattering matrix S, which relates to the transmission and reflection matrices T and R, respectively,
according to Eq. (2). The spatial light modulator (SLM) is used for creating the desired challenge states by
modulating the phase of the initial laser beam

123
 Y. Yao et al.

      
|ψ1  |ψ1  T −R † |ψ1 
= S = , (2)
|ψ2  |ψ2  R T† |ψ2 

where the operators R and T denote the reflection and transmission submatrices,
respectively. Due to the unitarity of the S-matrix, we have the relation R R † +T T † = 1.

2.2 The authentication protocol

We only consider the authentication protocol based on the reflected states by assuming
T = 0, following the experimental implementation in [10]. Note that in this case, there
is no loss of generality since any transmitted state can always be re-routed to become
part of the reflected state [9]. The detailed protocol consists of two steps:
• Enrollment phase Alice assigns an identity code I to a specific quantum-readout
PUF, and the challenge–response state pairs are measured with as much light as
needed. This procedure also yields the reflection matrix R [9]. The challenge along
with the corresponding response is stored in a challenge–response database. Then,
this PUF is delivered to Bob.
• Verification phase At some time, Bob claims to have access to the quantum-readout
PUF with the identifier I . Alice looks up the identity code I in the database and
finds the corresponding matrix R. Then, she initializes two counters n 1 and n 2 to
zero and repeats the following procedure m times:

1. Alice randomly prepares a state |ψ with uniform distribution and sends it to Bob
as a challenge state.
2. Within a permitted amount of time, Alice will obtain two distinctive responses:
nothing or a reflected state |χ . If she receives a state, then
(1) The first counter n 1 is increased by one.
(2) Since the reflection matrix R is known, the valid reflected state should be |χψ  =
R|ψ. Alice performs the measurement defined by the projection operators {E 1 =
|χψ χψ |, E 0 = 1 − E 1 } onto the received state |χ , where the outcomes “1” and
“0” correspond to E 1 and E 0 , respectively. If the outcome is “1,” the second
counter n 2 is increased by one.

Finally, if the fraction n 1 /m of the responses is not consistent with the expected noise
level, the authentication is aborted; if n 2 ≥ (1 − ε)n 1 , then Alice is convinced that she
has probed the PUF with the identifier I . Here, ε is a robustness parameter denoting
the tolerable fraction of wrong responses.

3 Quantum cloning attacks

3.1 Universal quantum cloning machine and false-accept probability

In Ref. [9,12,13], the challenge-estimation attacks or so-called intercept-resend attacks

have been considered for security analysis of PUF-based quantum authentication sys-
tems, which are regarded as the strongest classical attacks (the reason for this claim

123
Quantum cloning attacks against PUF-based quantum…

will be clear below). Here, we propose the first quantum attack scenario resorting to
the optimal quantum cloning machines. Before presenting main results, two obser-
vations attract our attention: (i) From the experimental perspective, a weak coherent
laser source is usually employed instead of the fragile single-photon states, which
implies that multi-photon cases should be taken into account since every photon in
these pulses will be modulated by the spatial light modulator (SLM) with the same
configuration (see Fig. 1); (ii) the challenge state is chosen at random, which indicates
that no specific state is superior to others, and thus, the universal quantum cloning
machine is a more appropriate choice for our topic.
A N → M quantum cloning machine (QCM) is a completely positive map
L : B(H⊗N ) → B(H⊗M ), which maps input density operators of N identical pure
originals into output density operators of M clones. In general, the average fidelity of
the cloning process is
M 
 1    


FQCM (N , M) = ψ trk̄ L ψ ⊗N  ψ dψ, (3)
M
k=1 ψ

where L(ψ ⊗N ) = ρ1,2,...,M and trk̄ denotes the trace with respect to all the subsystems
but k. Note that for a d-dimensional Hilbert space H, the set of pure states is isomorphic
with the complex projective space CP d−1 . On this space, there exists a unique natural
measure dψ, induced by the uniform Haar measure dμ(U ) on the unitary group U (d)
[15,16]. If we restrict our consideration to the universal quantum cloning machine
(UQCM), then the M clones are all in the same states since the output of the cloning
machine is supported on the symmetric subspace [17]. Therefore, the reduced state
of one copy can be defined using the notation Ls = tr1̄ L = · · · = tr M̄ L. Now the
average fidelity can be expressed as
    

 
FUQCM (N , M) = ψ Ls ψ ⊗N  ψ dψ. (4)
ψ

Equipped with these notations, we investigate the following attack model: The
adversary first intercepts the incoming N -photon pulse |ψ⊗N and then applies the
universal N → M qudit cloner. Then, in the language of the experiment [10], the
collective unitary transformations R ⊗ · · · ⊗R = R ⊗M are automatically performed
⊗M ⊗N
 †⊗M
by the optical PUF, and the final state R L ψ R is sent back to Alice. Note
that here it is assumed that R is a public information or the adversary has had access
to the PUF temporarily in the past [9]. We are now in a position to state the main result
of this section (see “Appendix 1” for more details).
Theorem 1 Under the quantum cloning attack by N → M UQCM, the adversary’s
success probability or the authentication system’s false-accept probability for a single
copy is upper bounded by
M − N + N (M + d)
Paccept ≤ , (5)
M(N + d)

where d = dimH, which is determined by the SLM configuration.

123
 Y. Yao et al.

Proof Following the protocol described in Sect. 2.2, the projections of each quanta
(e.g., photon in [10]) are independent events in the detection process. Therefore, we
can trace out all other subsystems when considering the single-copy case. Mathemat-
ically, the adversary’s success probability or the authentication system’s false-accept
probability for a single copy is
  
  

   
Paccept|ψ = χψ RLs (ψ ⊗N )R †  χψ = ψ R † RLs (ψ ⊗N )R † R  ψ
  

 
= ψ Ls (ψ ⊗N ) ψ , (6)

where the relation R R † = 1 is applied here. Note that Paccept|ψ is conditioned on

a specific challenge state. To eliminate this dependence, we can average over the
challenge state space (e.g., the pure state space)
    

 
Paccept = Eψ Paccept|ψ = ψ Ls ψ ⊗N  ψ dψ = FUQCM (N , M). (7)
ψ

Unitizing the results in [17,18], the false-accept probability is upper bounded by the
optimal single-copy fidelity of UQCM

opt M − N + N (M + d)
Paccept ≤ FUQCM (N , M) = . (8)
M(N + d)

This completes the proof. 

From Theorem 1, we can investigate the performances of the optimal cloning attacks
under various circumstances. In Fig. 2, we depict two extreme but practically relevant
cases: (i) When the single-photon light source is applied (i.e., N = 1), the false-accept
probability Paccept is gradually reduced with respect to the increase in the dimension d
for fixed M. In this case, Paccept becomes rather small when M and d are not quite large.
For instance, for M = 100 and d = 50, Paccept is already below 0.05; (ii) when the
number of copies M is considerably large (e.g., M = 2000), the quantum information
about |ψ contained in copies is greatly diluted during the copying process [19]. On
this condition, when N > 200 and d < 100, Paccept is always above 0.7, which
implies that the cloning attack is rather successful. However, if d is greatly increased
(e.g., d > 1000), the false-accept probability will be significantly suppressed. This
indicates that the dimension of quantum states is a critical resource for the security
of authentication protocol, especially when the d is not particularly large. However,
opt opt
when d is sufficiently large, PUQCM = FUQCM approaches N /M. In this case, it is
more appropriate to consider the number of copies as the resource.

3.2 The relation between quantum cloning and challenge-estimation attacks

In the previous literature, the challenge-estimation attacks have been evaluated by B.

S̆korić [12,13]. In fact, the strategy of this type of attacks is as follows: The adversary

123
Quantum cloning attacks against PUF-based quantum…

(a)

(b)

Fig. 2 a False-accept probability Paccept as a function of the number of copies M for different values of
the dimension d, when the single-photon light source is applied (i.e., N = 1); b Paccept as a function of
the photon number N of the incoming pulse for different values of d, when the number of copies is rather
large (M = 2000)

(Eve) first performs a coherent measurement M = {M j } of all N qudits. Depending

on the outcome r , a guess |ψ j  for the input state |ψ is made. The average fidelity of
the estimation process is defined as

Fest (N ) = tr(M j |ψψ|⊗N )|ψ j |ψ|2 dψ. (9)
j ψ

It is worth emphasizing that the core of the problem is to find the optimal measurement
and the corresponding strategy to reconstruct the guess state. Indeed, this universal
algorithm for optimal estimation of quantum states has already been established [20],
and optimal fidelity has been derived [21]. From these results and the equivalence
between the false-accept probability and the corresponding fidelity, B. S̆korić found
the false-accept probability (per quanta) for challenge-estimation attacks is upper
bounded by

123
 Y. Yao et al.

opt N +1
Pest ≤ Pest = , (10)
N +d

where the subscript “accept” is omitted henceforth for simplicity.

In comparison with quantum cloning attacks discussed above, two mathematical
observations catch our attention: (i) The upper bound of false-accept probability of
quantum cloning attacks is strictly larger than that of challenge-estimation attacks

opt M − N + N (M + d) opt N +1
PUQCM = > Pest = , (11)
M(N + d) N +d

opt opt
(ii) When M → ∞, PUQCM is reduced to Pest

opt opt N +1
lim PUQCM = Pest = . (12)
M→∞ N +d

In fact, there exists a strong relation between cloning the state of a quantum system
and acquiring knowledge about this state by taking measurements [22,23]. As for our
topic, these arguments in [22,23] can be summarized by the following two theorems:

Theorem 2 The optimal quantum cloning attack is superior to the optimal challenge-
estimation attack.

Theorem 3 Asymptotic quantum cloning attack is equivalent to the challenge-

estimation attack.

The proof of Theorem 2 is relatively simple since an M → ∞ cloner can be viewed as

a combination of the optimal state estimation process and a reconstruction procedure
of preparing infinite copies of the guessed state. However, this cloner is not necessary
an optimal one. Mathematically, this argument can be expressed as

opt opt
FQCM (N , M) ≥ Fest (N ). (13)

On the other hand, Theorem 3 is rather non-trivial. This argument was first proved to
be true for the UQCM case [22]. Bae and Acín extended this result to general cases
by using the monogamy of quantum correlations and the properties of entanglement
breaking channels [23]. Mathematically, this equivalence can be stated as

opt opt
FQCM (N , M → ∞) = Fest (N ). (14)

Hence, the QCM can be regarded as a universal device transforming quantum infor-
mation into classical information [19]. The relevant information flow is illustrated in
Fig. 3.

123
Quantum cloning attacks against PUF-based quantum…

Fig. 3 Diagram of the information flow from quantum to classical

Table 1 Targets of Alice and

Identity Target N M d
Eve and their corresponding
manipulations Alice P N No control d
Eve P No control M No control

3.3 Experimental considerations

Obviously, the above theoretical findings are the guidance of experiment. However,
experimental considerations are actually more complicated. In this subsection, we
make several remarks on experimental setup.
Remark 1 To avoid being detected by the verifier via monitoring the photon number
 phase, the adversary (Eve) can trace out M − N copies of the
before the verification

output state L ψ ⊗N and resend the remaining N copies back to Alice.
Remark 2 In fact, the upper bound of the false-accept probability for a single copy
opt
PUQCM is a function of the triple {N , M, d}. A closer look at this function reveals that
opt
PUQCM is a monotone increasing function of N , but monotone decreasing with respect
to M and d. Therefore, Alice and Eve should take different operations according to
their targets (see Table 1).
In the protocol described in Sect. 2.2, a specific challenge state |ψ is usually
applied m times. Thus, the expected total number of photons is N mPUQCM . Due to
the photon loss and detection imperfections, actually if PUQCM ≥ 1 − ε, the attacker
will be accepted by the authentication protocol. Since the total detection precess can
be viewed as a sequence of N m independent yes/no experiments, the total false-accept
probability obeys the binomial distribution


Nm  
Nm
Ptotal = PUQCM
k
(1 − PUQCM ) N m−k = IP (n + 1, N m − n)
k
k=N m(1−ε)
(15)

123
 Y. Yao et al.

where n = N m(1−ε) and I x (a, b) is the so-called regularized incomplete beta func-
tion. We can prove that Ptotal is a monotone increasing function of PUQCM , and thus,
the results in Table 1 can also be adopted to improve the security of the authentication
protocol (see “Appendix 2” for more details).

Remark 3 It is important to note that some imperfect single-photon sources are uni-
tized in realistic experiments [10]. On this occasion, the number of photons in a single
pulse is not fixed and follows a certain probability distribution (e.g., Poisson distri-
bution for weak coherent states). Accordingly, the verification threshold should be
modified to Nav m(1 − ε), where Nav = E N [N ] denotes the average photon number.
Meanwhile, we should average the false-accept probability over such a distribution.
In this case, we have
M − N + N (M + d)
Pav ≤ E N
M(N + d)

d − 1 (d − 1)(M + d)
= EN 1 + −
M M(N + d)

d −1 (d − 1)(M + d)
=1+ − EN
M M(N + d)
d − 1 (d − 1)(M + d)
≤1+ −
M E N [M(N + d)]
M − Nav + Nav (M + d)
= , (16)
M(Nav + d)

where Jensen’s inequality and the convexity of 1/x are used. Note that the only dif-
ference is the substitution N ⇒ Nav .

Actually, when the detection efficiency η is close to 1, the ideal single-photon source
is indeed a better choice for the verifier since the false-accept probability Paccept is a
monotone increasing function of Nav . However, in the language of the experiment [10],
the decision of acceptance or rejection is totally determined by the difference in the
probability distribution of the number of photodetections. Therefore, if the detection
efficiency is rather low, the choice of Nav = 1 will have a consequence that we can
hardly distinguish between the true and random PUF since in this case the number
of photodetections is too low and thus it is difficult to discriminate the corresponding
probability distribution. This situation will result in a lower probability of detecting
an adversary who tries to pretend to have access to the PUF. Hence, the verifier can
appropriately adjust the average photon number to a moderate value (e.g., Nav = 230±
40 [10]), but note that on this condition, the false-accept probability Paccept is greatly
increased. Therefore, a trade-off relation between the average photon number and the
detection efficiency should be taken into considerations in a realistic experiment.

4 Comparison with QKD protocols and other cloning attacks

For QKD protocols, the relationship between the no-cloning theorem and the security
of quantum cryptography was already clarified in the first protocol, that is, the BB84

123
Quantum cloning attacks against PUF-based quantum…

protocol [24]. In fact, various types of quantum cloning machines have been designed
to analyze the security of QKD protocols. Particularly, quantum cloning attacks are
proved to be the optimal incoherent attacks for BB84 protocol, six-state protocol,
and continuous-variable protocols [25,26]. Although there is no equivalence relation
between the optimal cloning and optimal eavesdropping, their relationship has been
shown to be strong and fruitful in the framework of quantum cryptography.
It is worth noting that the coding of BB84 and six-state protocols has been gen-
eralized to larger dimensional quantum systems [27–29]. Specifically, the spatial
degrees of freedom are exploited in high-dimensional QKD experiments [30,31].
Similarly, the high-spatial-dimension states of light are also employed in the PUF-
based quantum authentication experiment [10], where the number of controlled modes
d = 1100 ± 200. Remarkably, the SLM has played a critical role in creating the desir-
able challenge states. Intriguingly, in the context of quantum cryptography, the SLM
is also used to produce the d-dimensional states, which are of the form [31]

1
ld
| = eiφl |l, (17)
d
−ld

where ld = (d − 1)/2, |l forms the logical basis in the d-dimensional Hilbert space
of the transmitted photons, and φl are the phases introduced by the SLM [32].
Obviously, one possible scenario is that the adversary may acquire partial infor-
mation of the challenge states through the configuration of the SLM. For instance, the
adversary may know that a specific challenge state is of the form (17). In this case,
the phase-covariant quantum cloning machine (PQCM) for qudits can be employed to
launch an attack against the quantum authentication systems, which is more powerful
than the UQCM attacks [33]. For example, the optimal fidelity of 1 → 2 PQCM is
larger than that of UQCM [33]
opt 1 1  
FPQCM (1, 2) = + d − 2 + d 2 + 4d − 4
d 4d
opt d +3
> FUQCM (1, 2) = . (18)
2(d + 1)

Therefore, the leakage of the configuration information of the SLM will greatly com-
promise the security of the PUF-based quantum authentication systems. At the same
time, other quantum cloning machines such as PQCM can be exploited to attack the
authentication systems.

5 Conclusions

In this work, we systematically studied the quantum cloning attacks on the PUF-
based quantum authentication systems. First, we obtained the analytical formula of the
false-accept probability by use of the universal quantum cloning machines and proved
that optimal quantum cloning attack outperforms the so-called challenge-estimation
attacks. Remarkably, we have established the relationship between these two types of
attacks, and the information flow in the whole process is clarified. Moreover, from

123
 Y. Yao et al.

the experimental perspective, a trade-off between the average photon number and the
detection efficiency is discussed in detail. Finally, an explicit comparison is made
between QKD protocols and quantum authentication protocols, and other possible
cloning attacks are illustrated.
In view of these findings, a set of topics can be pursued as the future research
directions: (i) A detailed and integrated security analysis of the PUF-based quantum
authentication protocols is still missing. Other sorts of attacks may prove to be more
efficient, and the corresponding defending methods will be proposed. Such a positive
interaction between attacking and defending will enable us to gain deeper insight into
this subject. Interesting inspirations may come from the field of quantum cryptography.
(ii) Since QKD protocols can be viewed as some form of “quantum PUFs” [34],
the investigation of the security of quantum cryptography may be unified into the
framework of PUFs. This new direction seems promising, and the development of
secure “quantum PUFs” capable of tolerating realistic imperfections is of both practical
and fundamental importance.

Acknowledgments We are grateful to the Foundation of President of the China Academy of Engineering
Physics under Grant No. 2014-1-100.

Appendix 1: Attack models

First, we would like to emphasize that not only in our attack model but also in [9,12,13]
the target of the attacks is only the challenge state. In particular, in the context of the
experiment [10], the false PUF key is actually imitated by sending random challenges
to the true key (see caption of Fig. 3 in [10]). In fact, in the language of [10], the
verification phase goes as follows: (i) The challenge state is determined by the config-
uration of SLM1; (ii) the PUF automatically performs the unitary transformation R;
(iii) the SLM2 functions as the projection measurement (R|ψ)† = ψ|R † . As shown
in Fig. 4, it is evident that the difference in the two attack models is that:
Challenge-estimation attacks: Quantum measurement strategy + State preparation
Quantum cloning attacks: Implantations of quantum cloning machines
Since the attack model described in [9,12,13] adopts the so-called “measurement
and prepare” strategy, this attack model is classified to the (strongest) type of clas-
sical attacks. However, in our attack model, no measurement is involved except for
the projection of SLM2. More precisely, we preform the quantum attack against the
challenge state by employing quantum cloning machines. Actually, the justification
of our statement and [10] relies on the following equivalence relationship:

Correct challenge state + Random PUF key


Random challenge state + True PUF key

since an unclonable physical key (PUF) can be viewed as a unitary transformation.

Note that the only key difference lies in that the “measure and prepare” strategy is
replaced by “quantum cloning” scenarios in our model.

123
Quantum cloning attacks against PUF-based quantum…

Controlled
by SLM1

Challenge Quantum State

State measurement preparation

PUF
Reflected
(a) Challege-estimation SLM2 state
attacks

Controlled
by SLM1

Challenge Quantum
State Cloner

PUF
Reflected
(b) Quantum cloning SLM2
state
attacks

Fig. 4 Comparison of the attack models of challenge estimation and quantum cloning

Appendix 2: The cumulative binomial probability function

In general, if the random variable X follows the binomial distribution with N trials
and success probability p for each trial, the cumulative distribution function can be
expressed as
n  
 N
F(n; N , p) = P(X ≤ n) = p k (1 − p) N −k
k
k=0
= I1− p (N − n, n + 1)
   1− p
N
= (N − n) t N −n−1 (1 − t)n dt (19)
n 0

123
 Y. Yao et al.

where I x (a, b) is the regularized incomplete beta function

B(x; a, b)
I x (a, b) = , (20)
B(a, b)

B(a, b) is the beta function, and B(x; a, b) is the incomplete beta function. In our
context, the probability of obtaining more successes than n observed in a binomial
distribution is

P(X > n) = 1 − F(n; N , p) = I p (n + 1, N − n), (21)

where we have used the relation I x (a, b) + I1−x (b, a) = 1. Note that the partial
derivative of B(x; a, b) with respect to x is

∂ B(x; a, b)
= (1 − x)b−1 x a−1 . (22)
∂x

Therefore, we have

∂ I p (n + 1, N − n) (1 − p) N −n−1 p n
= > 0, (23)
∂p B(N − n, n + 1)

which implies that I p (n + 1, N − n) is a monotone increasing function of p.

References
1. Pappu, R.: Physical one-way functions. PhD thesis, MIT (2001)
2. Pappu, R., Recht, B., Taylor, J., Gershenfeld, N.: Physical one-way functions. Science 297, 2026 (2002)
3. Gassend, B.: Physical Random Functions. MSc Thesis, MIT (2003)
4. Tuyls, P., Schrijen, G.-J., S̆korić, B., van Geloven, J., Verhaegh, N., Wolters, R.: Read-proof hardware
from protective coatings. In: Cryptographic Hardware and Embedded Systems—CHES 2006, volume
4249 of Lecture Notes in Computer Science, pp. 369–383. Springer (2006)
5. Lim, D.: Extracting Secret Keys from Integrated Circuits. MSc thesis, MIT (2004)
6. Suh, G.E., Devadas, S.: Physical unclonable functions for device authentication and secret key gener-
ation. In: Proceedings of the 44th Design Automation Conference, pp. 9–14. ACM, New York (2007)
7. Guajardo, J., Kumar, S.S., Schrijen, G.J., Tuyls, P.: FPGA intrinsic PUFs and their use for IP protection.
In: Proceedings of the 9th International Workshop on Cryptographic Hardware and Embedded Systems.
LNCS, vol. 4727, pp. 63–80 (2007)
8. Maes, R.: Physically Unclonable Functions: Constructions, Properties and Applications. PhD. disser-
tation, KU Leuven (2012)
9. S̆korić, B.: Quantum readout of physical unclonable functions. Int. J. Quantum. Inf. 10, 1250001 (2012)
10. Goorden, S.A., Horstmann, M., Mosk, A.P., S̆korić, B., Pinkse, P.W.H.: Quantum-secure authentication
with a classical key. Optica 1, 421 (2014)
11. Miller, D.A.B.: Sorting out light. Science 347, 1423 (2015)
12. S̆korić, B., Mosk, A.P., Pinkse, P.W.H.: Security of quantum-readout PUFs against quadrature-based
challenge-estimation attacks. Int. J. Quantum. Inf. 11, 1350041 (2013)
13. S̆korić, B.: Security analysis of quantum-readout PUFs in the case of challenge-estimation attacks.
http://eprint.iacr.org/2013/479 (2013)
14. Beenakker, C.W.J.: Random-matrix theory of quantum transport. Rev. Mod. Phys. 69, 731 (1997)
15. Życzkowski, K., Sommers, H.-J.: Induced measures in the space of mixed quantum states. J. Phys. A:
Math. Gen. 34, 7111 (2001)

123
Quantum cloning attacks against PUF-based quantum…

16. Bengtsson, I., Życzkowski, K.: Geometry of Quantum States: An Introduction to Quantum Entangle-
ment. Cambridge University Press, Cambridge (2008)
17. Werner, R.F.: Optimal cloning of pure states. Phys. Rev. A 58, 1827 (1998)
18. Keyl, M., Werner, R.F.: Optimal cloning of pure states, testing single clones. J. Math. Phys. 40, 3283
(1999)
19. Gisin, N., Massar, S.: Optimal quantum cloning machines. Phys. Rev. Lett. 79, 2153 (1997)
20. Derka, R., Buz̆ek, V., Ekert, A.K.: Universal algorithm for optimal estimation of quantum states from
finite ensembles via realizable generalized measurement. Phys. Rev. Lett. 80, 1571 (1998)
21. Bruß, D., Macchiavello, C.: Optimal state estimation for d-dimensional quantum systems. Phys. Lett.
A 253, 249 (1999)
22. Bruß, D., Ekert, A., Macchiavello, C.: Optimal universal quantum cloning and state estimation. Phys.
Rev. Lett. 81, 2598 (1998)
23. Bae, J., Acín, A.: Asymptotic quantum cloning is state estimation. Phys. Rev. Lett. 97, 030402 (2006)
24. Bennett, C.H., Brassard, G.: Quantum cryptography: public key distribution and coin tossing. In Pro-
ceedings of IEEE International Conference on Computers, Systems, and Signal Processing, India IEEE,
New York, Bangalore, p. 175 (1984)
25. Scarani, V., Iblisdir, S., Gisin, N., Acín, A.: Quantum cloning. Rev. Mod. Phys. 77, 1225 (2005)
26. Fan, H., et al.: Quantum cloning machines and the applications. Phys. Rep. 544, 241 (2014)
27. Bechmann-Pasquinucci, H., Tittel, W.: Quantum cryptography using larger alphabets. Phys. Rev. A
61, 062308 (2000)
28. Bechmann-Pasquinucci, H., Peres, A.: Quantum cryptography with 3-state systems. Phys. Rev. Lett.
85, 3313 (2000)
29. Cerf, N.J., Bourennane, M., Karlsson, A., Gisin, N.: Security of quantum key distribution using d-level
systems. Phys. Rev. Lett. 88, 127902 (2002)
30. Walborn, S.P., Lemelle, D.S., Almeida, M.P., Ribeiro, P.H.S.: Quantum key distribution with higher-
order alphabets using spatially encoded qudits. Phys. Rev. Lett. 96, 090501 (2006)
31. Etcheverry, S., et al.: Quantum key distribution session with 16-dimensional photonic states. Sci. Rep.
3, 2316 (2013)
32. Neves, L., et al.: Generation of entangled states of qudits using twin photons. Phys. Rev. Lett. 94,
100501 (2005)
33. Fan, H., Imai, H., Matsumoto, K., Wang, X.B.: Phase-covariant quantum cloning of qudits. Phys. Rev.
A 67, 022317 (2003)
34. Plaga, R., Koob, F.: A formal definition and a new security mechanism of physical unclonable functions.
In: Measurement, Modelling, and Evaluation of Computing Systems and Dependability and Fault
Tolerance, ser. Lecture Notes in Computer Science, Springer, Berlin. 7201, pp. 288–301 (2012)

123