Can Quantum Key Distribution Be Secure

Horace P. Yuen
Department of Electrical Engineering and Computer Science
Department of Physics and Astronomy
Northwestern University, Evanston Il. 60208
email: yuen@eecs.northwestern.edu
May 5, 2014
The importance of quantum key distribution as a cryptographic method depends upon its
purported strong security guarantee. The following gives reasons on why such strong security
guarantee has not been validly established and why good QKD security is dicult to obtain.
I. QKD KEY IS QUITE IMPERFECT
Three major problems in cryptography involve the establishment of a shared secret key be-
tween two users Adam and Babe and the use of this key to encrypt messages for privacy
and integrity, against possible attack from Eve who may want to eavesdrop or to alter the
messages. Quantum key distribution (QKD) protocols, specically of the BB84 variety [1],
This paper is the preliminary version of one to appear in Proc. IEEE.
1
a
r
X
i
v
:
1
4
0
5
.
0
4
5
7
v
1


[
q
u
a
n
t
-
p
h
]


2

M
a
y

2
0
1
4
purport to provide perfect security for the rst problem when Eve obtains information on
the generated key by interception, through the detection of quantum disturbance to ensure
such information is vanishingly small. The generated key could then be used for encryp-
tion with the perfectly secure one-time pad, or for message authentication. QKD is usually
compared with the public-key method currently widely employed for key distribution, the se-
curity of which depends on complexity consideration with unproved complexity assumption.
In contrast, QKD key has information theoretic security (ITS) that retains intrinsic uncer-
tainty to Eve, and so cannot be broken by increasing computational power as public-key
cryptosystems can be so broken.
The QKD generated key is widely claimed and perceived, in both the technical and popular
literature, to have perfect security, or is so except for a very small probability [1], or have
absolute security or unconditional security. In actuality, the QKD key is imperfect for
sure and its deviation from a perfect key is huge. Consider the prevalent claim that the
QKD generated key K is perfect except for a small probability upper bounded by a small
parameter , a conclusion drawn in the literature from bounding a trace distance security
criterion d, d . Being perfect here implies that the bit sequence K is the uniform
random variable U to Eve. Such conclusion was drawn and maintained to date from an
obvious error of reasoning, which was repeatedly pointed out [2-4] but never acknowledged.
Indeed, with d > 0 the key K is not perfect with probability 1, not with probability at most
, as will be discussed later on.
Equally signicantly, the security of a QKD protocol cannot be made arbitrarily close to
perfect at any xed key generation rate through a security parameter s in accordance with
2
the original denition of unconditional security. Such claim is based on purported proofs
that Eves maximum mutual information (called accessible information in the quantum
case) on K from any attack, I
E
(K), goes to zero as |K| = n gets large,
I
E
0 as n (1)
Thus, n is taken to be the security parameter s. Even if the proofs are valid, and they are
not, the claim (1) does not imply K is perfect asymptotically. Innity is not a number, and
it is the convergence rate of I
E
(K) that determines the asymptotic key rate and security
level. This can be seen as follows [2].
Information theoretic quantities like mutual information are theoretical constructs whose
operational meaning need to be spelled out. In the context of ordinary communications,
they are given through the Shannon coding theorems in terms of the empirical data rate
and error rate. In the context of cryptography, they have not been previously provided
except in the perfect case. Generally, it is Eves various success probabilities in getting
at K that are the relevant operational security criteria. From her attack Eve derives a
whole conditional distribution p(K|Y
E
) on the N = 2
n
possible values of the bit sequence
K given her measurement result Y
E
and knowledge from the users open exchange. This
a posteriori p(K|Y
E
) is derived from the cryptosystem transition probability p(Y
E
|K) and
Eves a priori distribution of K, through Bayes Rule. Any single number criterion such as
I
E
merely expresses a constraint on p(K|Y
E
). In particular, perfect security is expressed by
p(K|Y
E
) = U, the uniform random variable (with the same number of bits as K).
Let us drop the conditioning dependence and order the N dierent values of p(K|Y
E
) as
3
p
1
...... p
N
. Eves maximum probability p
1
of getting the whole K is clearly crucially
signicant, as it has to be suciently small for security. From Lemma 2 in [2], for l < n it
is possible that
I
E
n
2
l
, p
1
2
l
(2)
Since l is typically, in experiment and in theory, very much smaller than n with or without
privacy amplication (compressing the key to enhance security), the corresponding p
1
is very
much larger than that of a uniform K = U. Indeed, a very insecure K can satisfy (1), even
exponentially as in
I
E
= 2
(nlog n)
(3)
for a constant , in which it is possible p
1
2
n
for 1 as compared to 2
n
for a uniform
key. There is no unconditional security in QKD.
II. GUARANTEEDSECURITYLEVEL IS VERYLOW
AND NOT PROVED
The above p(K|Y
E
) describes only the security of K during the generation process. When
K is used, say in one-time pad encryption (OTP, K xored bit by bit into the data and
used only once) as is commonly suggested, parts of K may become known to Eve and the
correlation among dierent bits in K for an imperfect key may seriously compromise the rest
of K. In particular, in a known-plaintext attack (KPA) a segment of the encrypted data X,
Y = X K, may be known to Eve, a common situation in commercial applications though
4
perhaps not in many military ones. The ciphertext Y is always assumed openly known.
Thus, the portion of K corresponding to the known portion of X is known to Eve, which
she could use to get at the other portion of K through correlation among the bits of K,
and together with the corresponding portion of Y she may learn a lot about the unknown
portion of X. Eve can also use statistical information for such attacks, but we restrict to
exactly known data for clarity and simplicity. In conventional symmetric key cryptography,
it is always KPA that is the real concern. In fact, in an additive stream cipher Y = X K,
a uniform X to Eve would completely cover up K from Y and Eve could get at K only from
how it is generated.
It was only about ten years ago, long after many QKD security proofs were oered, that it
was found that the quantum accessible information criterion is not secure against KPA; in
fact its quantitative guarantee turns out so poor that it is not ruled out that Eve may break
the whole n-bit K with just log n bits of known data bits. This is a quantum cryptosystem
problem not present in conventional ITS cryptosystems. As a consequence, a quantum trace
distance criterion d is now widely (though not yet universally) employed as the security
criterion in lieu of accessible information [1]. The claim is that under the security condition
d , called -secure, K is secure with K being uniform to Eve with probability at least
1 , and K is furthermore decoupled totally from Eves probe set during her attack so
that K is universally composable. This interpretation of d is wrong and was pointed
out repeatedly, but the impression is maintained that such interpretation is correct, and
furthermore that the obtainable level of the theoretical and experimental QKD protocols
with d guarantee is adequate.
5
To understand the signicance of such QKD security guarantee and its correct operational
meaning, we briey review schematically the usual security analysis of QKD protocols as
depicted in Fig. 1.
Fig. 1: Schematic representation of a QKD system incorporating error correction and
privacy amplication with generated key K.
We omit the part before a so-called sifted key, K, is generated between Adam and Babe
upon which Eve has set her quantum probe
E
k
. The protocol goes forward with the checked
quantum bit error rate (QBER) below a set threshold so that the H
min
( log p
1
for
an average p
1
), the minimum entropy of Eve on K for any attack, can be bounded
from below. An error correcting code (ECC) is used to correct all the errors in K with
output key K

. A privacy amplication code (PAC) is used to compress K

into a much
shorter K for increased security level. The overall security of K is measured by a quantum
trace distance d involving
E
k
, which lower bounds any statistical distances between Eves
possible distribution {p
i
} on the N possible vales of K and the uniform U,
(P, U) =
1
2

i
|p
i
U
i
| (4)
The d performance of K obtained is an average over an openly known family of PAC. The
6
ECC information leak to Eve is given by the following formula, with h() the binary entropy
function,
leak
EC
= f n h(QBER) (5)
where f 2 is ad hoc correction factor for a nite n protocol with f = 1 taken to be the
asymptotic value. The net key length generated is taken to be
|K
g
| = n leak
EC
(6)
As in product manufacturing, quantitative cryptographic guarantee needs to be expressed
in terms of probability, not average. This is already done for information theoretic security
in practical conventional cryptography, such as OTP or message authentication, and the
statistical distance is not used whose correct probability signicance will be given in the
bound (7) below. Under the wrong probability interpretation of d or , the d guarantee
is still an average over PAC and needs to be converted to probabilistic individual PAC
guarantee through Markov inequality. For minimizing the failure probability of not getting
a guarantee, this yields an individual PAC guarantee at the level d
1
2
instead of d [4]. Note that
the specic PAC employed, which has to be openly announced due to its size, may introduce
serious security leak just by itself. The PAC is typically a binary matrix or Toeplitz matrix
that gives an n-bit output K from an m-bit input K

, m > n. In order for the family to

be ASU for PAC to work [4], degenerate matrices (with linear dependence among the row
vectors) are included. These matrices would lead to strong correlation among some bits
in K and deterministic leak under KPA. It is mandatory for security that the degeneracy
probability be small, but general m by n result seems unavailable, while it is not known
whether the remaining family remains ASU if degenerate matrices are removed. Thus,
7
use of Markov inequality to obtain individual probabilistic guarantee is necessary for this
additional reason.
The best quantitative d security guarantee (with invalid proof) for single-photon BB84 is
given in [5] theoretically, with plots on the exchange between key rate and the PAC average
d. It obtains d 10
14
with vanishing key rate. If we use the erroneous interpretation of
d as security failure probability (failure can mean total breach of K), the individual PAC
guarantee allows a probability of 10
7
of totally breaking the system, from the last paragraph.
If a mere 100 such QKD rounds per second is carried out, there would already be 10
7
rounds per day and the security may be totally compromised with the whole K revealed to
Eve once every day on average. Recent experimental protocols claim average d to be 10
9
.
Clearly such guaranteed level is far from adequate, and surely far from the still prevalent
unconditionally secure claim.
Note that the MAC bit cost in a QKD protocol for defeating man-in-the-middle attack is not
yet accounted for in these results, and the MAC steps have not been integrated within the
protocol for security analysis although such integration is done in conventional cryptography.
The relatively large d level of QKD keys is very detrimental for its use in message authentica-
tion code (MAC), even according to the wrong interpretation, and moreover removes the tag
length security parameter |t| in MAC and leaves it with none [4]. A typical MAC with ITS
consists of a hash family with key K
h
and often another key K
t
for OTP the authentication
tag t. The security against impersonation and substitution attacks is guaranteed through
an -ASU hash family in which upper bounds Eves success probability and itself is lower
8
bounded by
1
|t|
for tag bit length |t|. When d
h
, Eves success probability may reach 1 for
some tags. Upon tag average an -ASU family becomes an ( +
h
)-ASU family. When K
t
with d
t
is used, it becomes an ( +m
t
)-ASU family when the hash function is used m times.
Thus, a lower limit on is now set by
h
or
t
however long the authentication tag t is. There
is no longer a security parameter for MAC since QKD itself has none. Furthermore, typical
tag lengths of 32-64 bits already require e
t
or e
h
to be at the eective d level of 10
10
to 10
20
with no averaging. This is not achievable with single-photon BB84, even for the
wrong interpretation as we indicated. With the correct one we now turn to, it is much more
unachievable.
The erroneous d interpretation springs from the error in interpreting the statistical distance
, and has been expounded in [2-4]. In particular, under (p, U) , p is generally not U
with probability 1 for > 0. The general probability guarantee [4] is, for K
*
2
any subset of
K
2
and K
1
known to Eve in a KPA,
p
1
(K
*
2
|K
1
) 2
|K
*
2
|
+ (7)
where average over K
1
and K
*
2
are included in p
1
. The above bound (7) can be achieved with
equality. It is the only available result for guaranteeing the essential KPA security for privacy
under d or . Since a random measurement result Y
E
is needed to get (7), there is
one more application of Markov inequality needed for conversion to individual probability
guarantee. In KPA the average over the known K
1
also needs to be so converted, while
K
2
does not because it is the distribution on K
2
that is involved in the statistical distance.
Thus, two or three applications of Markov inequality are needed for raw or KPA security
compared to just one for the wrong interpretation, resulting in an eective d level of d
1
3
or
9
d
1
4
for individual guarantee in the two cases compared to d
1
2
. In message authentication use
of K, there is one more average for the tag t that needs to be so converted. In the above
single-photon BB84 theory [5], the guaranteed level thus becomes d 10
3.5
for KPA, and
10
3.5
also for MAC application without KPA. For the experimental protocols they become
10
2.25
. Thus, it is not ruled out, even assuming the system model exactly describe reality
and the security analysis on deriving d is correct, that the cryptosystem may be totally
broken with a probability of one in several thousands in theory and several hundreds in
practice.
This gives a very bleak picture on obtainable quantitative QKD security. For both privacy
and MAC applications there is no security parameter s when QKD is used, in fact s is taken
away from MAC by QKD. The gap, between adequate protection and theoretical model
guarantee [5] in which many realistic system imperfections have still not been accounted for,
is enormous with many tens of orders of magnitude or more. The dierence from a perfect
uniform key is so gigantic, say between the p
1
of 10
10
(or 10
14
for vanishing |K|) from (7)
and the p
1
= 10
10000
for a 10
4
bits uniform K, that it is an understatement to just say K
is imperfect. It is very imperfect.
It has never been explained how (5) is to be validly derived so that (6) holds. The only hope
[4] for the approximate validity of such an approach is to use a linear ECC with information
bits given by K and parity check bits covered by a uniform secret key K
s
shared between
Adam and Babe. Under the wrong interpretation that K is uniform to Eve except for a
small probability, (6) is valid with a high probability. While such a step (5)-(6) is still
not rigorously valid [4], it may be approximately. When K is not U as is the actual case,
10
there is no reason for (5)-(6) to hold because an imperfect QKD key violates the premise
of OTP security necessary for the validity of (5)-(6). (Observe the above dramatic eect
of an imperfect key on MAC.) This fact alone already shows there is no valid complete
proof of QKD security, because the quantitative security level is not proved but obtained
heuristically.
Many QKD claims are just declared without any argument, ignoring many possible attacks
by Eve. This includes the recent measurement-device-independent QKD, which in any case
does not have security performance better than that of single photon BB84. Note that the
foundational criticisms above apply to all QKD protocols. In sum, regardless of ones view
on the quantitative security guarantee it is simply false to claim QKD security has been
proved.
III. COMPARISONWITHCONVENTIONAL CRYP-
TOGRAPHY
The above security issues concern the conceptual and information theoretic foundations of
QKD security. Since QKD relies on quantum and other physical eects for its security, it has
numerous other problems that are not present in conventional cryptography which is based
solely on mathematical relations whose physical embodiment is typically not problematic.
It is commonly claimed misleadingly that QKD security is based on the laws of quantum
physics, while it is based on that and a lot of other considerations in addition. In particular,
11
QKD is based on disturbance-information tradeo (the quantum cryptosystem KCQ [2] is
not so based) which implies very small signals, typical at the single photon level, need to be
used for detecting relatively sizable disturbance. Compare a single photon to the 10
7
photons
per pulse from a diode laser source in ber optic communication. Such weak signal leads
not only to system implementation problems, but they are also intrinsically sensitive (in
the sense of lacking robustness) to system imperfections and fundamentally inecient in the
sense of data rate. The corresponding cryptosystem is evidently incompatible with existing
infrastructures. Security or possible security appears to be the only possible QKD advantage.
At the same time, physical issues lead to a whole bundle of dierent dicult issues that have
not been addressed or adequately addressed in the literature. We cannot go into them
here, however, except noting that detector blinding attacks [6] led to a total compromise of
the QKD key in realistic demonstration. The underlying culprit is the use of microscopic
signals, that it is not clear what physical features of a concrete QKD implementation need
to be represented in the mathematical security analysis.
In the absence of KPA, conventional symmetric key expansion has better numerical security
guarantee than concrete QKD key [3]. The advantage of QKD lies in its information theoretic
security under known-plaintext attacks. Note that it is not the case that if asymmetric key
systems without ITS become vulnerable one would need QKD. Symmetric key distribution
is always available.
The key generated in QKD, as we see in section II, cannot be used to secure its own ECC
and MAC needed for protocol execution. There is no security parameter in QKD, it is always
a tradeo between key rate and security level determined by p
1
of K. Subsequent ECC
12
and PAC could only decrease the p
1
exponent (or H
min
, the -smooth generalization H

min
does not improve H
min
eectively) of K

and K. Privacy amplication does not amplify

privacy, only distills and concentrates it on a smaller number of bits. No approach has been
indicated on how one may increase the H
min
(K) level in [5]. Before this major impasse
in QKD is overcome theoretically, there is no basis to claim its cryptographic usefulness in
view of its very poor quantitative level even if the purported proofs are valid.
It is important to observe that in contrast to the vast majority of physics and engineering
problems, general security can only be established by rigorous mathematical proof from a
complete model that captures all the factors relevant to a security situation. One cant cover
all possible attack scenarios by experiments. In this paper we assume the model is correct
and complete, although that is a much more contentious issue in QKD as compared to
conventional cryptography. Ordinary cryptography, either symmetric key or asymmetric key
ones, have no general security proof (other than OTP and MAC with ITS). QKD appears to
ll a need with the prevalent widespread provable unconditional security claims. However,
as hopefully made clear in this paper, such claim is unfounded and is based on errors and
omissions. Since security is a serious business, it is important to critically assess QKD
security in detail, particularly given the history of cryptography in which many systems
thought to be secure turned out not.
In this connection, it should be pointed out that many assertions that would logically be
considered conjectures in mathematics or stated as assumptions in conventional cryptogra-
phy, are treated in the QKD literature as some sort of obvious truths that do not merit proof
or even mention. An example is (5)-(6) in this paper. Another example, when physics is
13
brought in, is that the inevitable optical loss would only aect the throughput but not the
security level of single-photon BB84.
Further technical details and a little history on some of the points raised in this paper can be
found in [4] and references cited therein. A treatment of certain physics issues is forthcoming
in a review paper, and a detailed exposition of all issues in a planned book-length treatise.
References
[1] V. Scarani, H. Bechmann-Pasuinucci, N. J. Cerf, M. Dusek, N. Lutkenhaus, and M.
Peev, Rev. Mod. Phys. 81, 1301 (2009).
[2] H. P. Yuen, IEEE J. Sel. Top. Quantum Electron. 15, 1630 (2009).
[3] H. P. Yuen, Phys. Rev. A 82, 062304 (2010).
[4] H. P. Yuen, arXiv:1310.0842v2 (2013). Also in Proceedings of the SPIE Conference on
Quantum Physics-Based Information Security held in Dresden, Germany, Sep 23-24,
2013.
[5] M. Tomamichel, C. Lin, N. Gisin, and R. Renner, Nat. Commun. 3, 634 (2012).
[6] I. Gerhardt, Q. Liu, A. Lamas-Linares, J. Skaar, C. Kursiefer, and V. Makarov, Nat.
Commun. 2, 349 (2011).
14