Finite-key analysis for measurement-device-independent quantum key distribution

Abstract

Quantum key distribution promises unconditionally secure communications. However, as practical devices tend to deviate from their specifications, the security of some practical systems is no longer valid. In particular, an adversary can exploit imperfect detectors to learn a large part of the secret key, even though the security proof claims otherwise. Recently, a practical approach--measurement-device-independent quantum key distribution--has been proposed to solve this problem. However, so far its security has only been fully proven under the assumption that the legitimate users of the system have unlimited resources. Here we fill this gap and provide a rigorous security proof against general attacks in the finite-key regime. This is obtained by applying large deviation theory, specifically the Chernoff bound, to perform parameter estimation. For the first time we demonstrate the feasibility of long-distance implementations of measurement-device-independent quantum key distribution within a reasonable time frame of signal transmission.

ARTICLE

Received 4 Jul 2013 | Accepted 27 Mar 2014 | Published 29 Apr 2014

Quantum key distribution promises unconditionally secure communications. However, as practical devices tend to deviate from their specications, the security of some practical systems is no longer valid. In particular, an adversary can exploit imperfect detectors to learn a large part of the secret key, even though the security proof claims otherwise. Recently, a practical approachmeasurement-device-independent quantum key distributionhas been proposed to solve this problem. However, so far its security has only been fully proven under the assumption that the legitimate users of the system have unlimited resources. Here we ll this gap and provide a rigorous security proof against general attacks in the nite-key regime. This is obtained by applying large deviation theory, specically the Chernoff bound, to perform parameter estimation. For the rst time we demonstrate the feasibility of long-distance implementations of measurement-device-independent quantum key distribution within a reasonable time frame of signal transmission.

DOI: 10.1038/ncomms4732

Finite-key analysis for measurement-device-independent quantum key distribution

Marcos Curty1, Feihu Xu2, Wei Cui2, Charles Ci Wen Lim3, Kiyoshi Tamaki4 & Hoi-Kwong Lo2

1 EI Telecomunicacin, Department of Signal Theory and Communications, University of Vigo, Vigo E-36310, Spain. 2 Center for Quantum Information and Quantum Control, Department of Physics and Department of Electrical & Computer Engineering, University of Toronto, Toronto, Ontario, Canada M5S 3G4.

3 Group of Applied Physics, University of Geneva, Geneva CH-1211, Switzerland. 4 NTT Basic Research Laboratories, NTT Corporation, 3-1, Morinosato Wakamiya Atsugi-Shi, Kanagawa 243-0198, Japan. Correspondence and requests for materials should be addressed to M.C. (email: mailto:[email protected]

Web End [email protected] ).

NATURE COMMUNICATIONS | 5:3732 | DOI: 10.1038/ncomms4732 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications 1

& 2014 Macmillan Publishers Limited. All rights reserved.

ARTICLE NATURE COMMUNICATIONS | DOI: 10.1038/ncomms4732

It is unequivocal that quantum key distribution (QKD)1,2 needs to bridge the gap between theory and practice. In theory, QKD offers perfect security. In practice, however, it does not, as

most practical devices behave differently from the theoretical models assumed in the security proofs. As a result, we face implementation loopholes, or so-called side channels, which may be used by adversaries without being detected, as seen in recent attacks against certain commercial QKD systems311.

There are two potential ways to guarantee security in the realization of QKD. The rst is to develop mathematical models that perfectly match the behaviour of physical apparatuses, and then incorporate this information into a new security proof. While this is plausible in theory, unfortunately it is very hard to realize in practice, if not impossible. The second alternative is to design new protocols and develop security proof techniques that are compatible with a wide class of device imperfections. This allows us to omit an accurate characterization of real apparatuses. The most well-known example of such a solution is (full) device-independent QKD (diQKD)1216. Here the legitimate users of the system (typically called Alice and Bob) treat their devices as two quasi black boxesthat is, they need to know which elements their boxes contain, but not how they fully function17. The security of diQKD relies on the violation of a Bell inequality18,19, which certies the presence of quantum correlations. Despite its beauty, however, this approach is highly impractical because it requires a loophole-free Bell test that at the moment is still unavailable20. Also, its secret key rate at practical distances is very limited21,22.

Very recently, a novel approach has been introduced, which is fully practical and feasible to implement. This scheme is known as measurement-device-independent QKD (mdiQKD)23 and offers a clear avenue to bridge the gap between theory and practice. Its feasibility has been promptly demonstrated both in laboratories and via eld tests2427. It successfully removes all (existing and yet to be discovered) detector side channels3,5,6,911, which, arguably, is the most critical part of most QKD implementations. Importantly, in contrast to diQKD, this solution does not require that Alice and Bob perform a loophole-free Bell test; it is enough if they prove the presence of entanglement in a quantum state that is effectively distributed between them, just like in standard QKD schemes28. In addition, now Alice and Bob may treat the measurement apparatus as a true black box, which may be fully controlled by the adversary. A slight drawback is that Alice and Bob need to characterize the quantum states (for example, the polarization degrees of freedom of phase-randomized weak coherent pulses (WCPs)) that they send through the channel. However, as this process can be veried in a protected environment outside the inuence of the adversary, it is less likely to be a problem. For completeness, the readers can refer to ref. 29 where a characterization of the prepared states is no longer required.

Nevertheless, so far the security of mdiQKD has only been proven in the asymptotic regime23, which assumes that Alice and Bob have access to an unlimited amount of resources, or in the nite regime but only against particular types of attacks30,31. In summary, until now, a rigorous security proof of mdiQKD that takes full account of the nite size effects3234 has appeared to be missing and, for this reason, the feasibility of long-distance implementations of mdiQKD within a reasonable time frame of signal transmission has remained undemonstrated.

The main contributions of this work are twofold. First, in contrast to existing heuristic results on mdiQKD, we provide, for the rst time, a security proof in the nite-key regime that is valid against general attacks and satises the composability denition35,36 of QKD. Second, we apply large deviation theory, specically a multiplicative form of the Chernoff bound37, to

perform the parameter estimation step. The latter is crucial to demonstrate that a long-distance implementation of mdiQKD (for example, 150 km of optical bre with 0.2 dB km 1) is feasible within a reasonable time frame. To obtain high secret key rates in this scenario, it is common to use decoy state techniques3840, both for standard QKD protocols and mdiQKD. Here a key challenge is to estimate the transmittance and the quantum bit error rate (QBER) of the single-photon component of the signal at the presence of high losses (for example, 30 dB). We show that such an estimation problem can be solved using the Chernoff bound, as it provides good bounds for the above parameters even in the high-loss regime. We highlight that our results can be applied to other QKD protocols (for example, the standard decoy state BB84 protocol3840) as well as to general experiments in quantum information.

ResultsSecurity denition. Before stating the protocol, let us quickly review the security framework35,36 that we are considering here. A general QKD protocol (executed by Alice and Bob) generates either a pair of bit strings SA and SB, or a symbol ? to indicate the

abort of the protocol. In general, the string of Alice, SA, can be quantum mechanically correlated with a quantum state that is held by the adversary. Mathematically, this situation is described by the classical quantum state

rAE

Xssj i sh j rsE;

where s

j i

f gs denotes an orthonormal basis for Alices system, and

the subscript E indicates the system of the adversary.

Ideally, we say that a QKD protocol is secure if it satises two conditions, namely the correctness and the secrecy. The correctness condition is met if SA SB, that is, Alices and

Bobs bit strings are identical. The secrecy condition is met if rAEUA rE, where UA

Ps1jSj sj i sh j is the uniform mixture of all possible values of the bit string SA. That is, the system of the adversary is completely decoupled from that of Alice.

Owing to the presence of errors, however, these two conditions can never be perfectly met. For example, in the nite-key regime it is impossible to guarantee SA SB with certainty. In practice,

this implies that we need to allow for some minuscule errors. That is, we say that a QKD scheme is Ecor-correct if Pr SA 6 SB

Ecor,

that is, the probability that Alices and Bobs bit strings are not identical is not greater than Ecor. Similarly, we say that a protocol is, Esec-secret if

1

2 rAB UA rE

k k1 Esec;

where

k k1 denotes the trace norm. That is, the state rAB is

Esec-close to the ideal situation described by UA rE. Thereby a

QKD protocol is said to be E-secure if it is both Ecor-correct and Esec-secret, with Ecor Esec E.

With this security denition we are able to guarantee that the security of the protocol holds even when combined with other protocols, that is, the protocol is secure in the so-called universally composable framework35,36.

Protocol denition. The set-up is illustrated in Fig. 1. Alice and Bob use a laser source to generate quantum signals that are diagonal in the Fock basis. Instances of such sources include attenuated laser diodes emitting phase-randomized WCPs, triggered spontaneous parametric downconversion sources and practical single-photon sources. Each pulse is prepared in a different BB84 state41, which is selected, for example, uniformly at random from two mutually unbiased bases, denoted as Z and X. The signals are then sent to an untrusted relay Charles,

2 NATURE COMMUNICATIONS | 5:3732 | DOI: 10.1038/ncomms4732 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications

& 2014 Macmillan Publishers Limited. All rights reserved.

NATURE COMMUNICATIONS | DOI: 10.1038/ncomms4732 ARTICLE

Pol-M

Pol-M

Box 1 | Protocol denition.

State preparation: Alice and Bob repeat the rst four steps of the protocol for i 1,y,N until the conditions in the Sifting step are met. For

each i, Alice chooses an intensity a 2 fas; ad ; . . . ; ad g, a basis

a 2 fZ; Xg, and a random bit r 2 f0; 1g with probability pa,a/2. Here

as ad

Laser

Laser

is the intensity of the signal (decoy) states. Next, she generates a quantum signal (for example, a phase-randomized WCP) of intensity a prepared in the basis state of a given by r. Likewise, Bob does the same.

Distribution: Alice and Bob send their states to Charles via the quantum channel.

Measurement: If Charles is honest, he measures the signals received with a Bell state measurement. In any case, he informs Alice and Bob (via a public channel) of whether or not his measurement was successful. If successful, he reveals the Bell state obtained.

Sifting: If Charles reports a successful result, Alice and Bob broadcast (via an authenticated channel) their intensity and basis settings. For each Bell state k, we dene two groups of sets: Za;bk and Xa;bk. The rst

(second) one identies signals where Charles declared the Bell state k and Alice and Bob selected the intensities a and b and the basis Z (X). The protocol repeats these steps until Za;bk

Na;bk and

Decoy-IM

Charles

Decoy-IM

Claims to do Bell state measurement

Figure 1 | A schematic diagram of mdiQKD. Alice and Bob prepare quantum signals in different BB84 polarization states41 with a polarization modulator (Pol-M). Also, they use an intensity modulator (Decoy-IM) to generate decoy states. The signals are sent to an untrusted relay Charles, who is supposed to perform a Bell state measurement that projects the incoming signals into a Bell state. See the main text for details.

AliceSecure laboratory

BobSecure laboratory

Xa;bk

who is supposed to perform a Bell state measurement that projects them into a Bell state. Also, Alice and Bob apply decoy state techniques3840 to estimate the gain (that is, the probability that the relay outputs a successful result) and the QBER for various input photon numbers.

Next, Charles announces whether or not his measurements are successful, including the Bell states obtained. Alice and Bob keep the data that correspond to these instances and discard the rest. Also, they post-select the events where they employ the same basis. Finally, either Alice or Bob ips part of her/his bits to correctly correlate them with those of the other. See Box 1 for a detailed description of the different steps of the protocol.

Since Charles measurement is basically used to post-select entanglement between Alice and Bob, the security of mdiQKD can be proven by using the idea of time reversal. Indeed, mdiQKD builds on the earlier proposals of time-reversed EPR protocols by Biham et al.42 and Inamori43, and combine them with the decoy state technique. The end result is the best of both worldshigh performance and high security. We note on passing that the idea of time reversal has also been previously used in other quantum information protocols including one-way quantum computation.

Security analysis. We now present one main result of our paper. It states that the protocol introduced above is both Ecor-correct and Esec-secret, given that the length of the secret key SA is selected appropriately for a given set of observed values. See Box 1 for the denition of the different parameters that we consider in this section.

The correctness of the protocol is guaranteed by its error correction step, where, for each possible Bell state k, Alice sends a hash of Zk to Bob, who compares it with the hash of ^

Zk. If both

Ma;bk 8a; b; k. Next, say Bob ips part of his bits to correctly

correlate them with those of Alice (see Table 1). Afterwards, they execute the last steps of the protocol for each k.

Parameter estimation: Alice and Bob use nk random bits from Za ;bk to

form the code bit strings Zk and Z0k, respectively. The remaining Rk bits from Za ;bk are used to compute the error rate Ea ;bk 1R

Pl rl r0l, where r0l are Bobs bits. If Ea ;bk 4Etol, Alice and Bob assign an empty string to Sk and abort steps 6 and 7 for this k. The protocol only aborts if

Ea ;bk 4Etol 8k. If Ea ;bk Etol, Alice and Bob use Za;bk and Xa;bk to

estimate nk,0, nk,1 and ek,1. The parameter nk,0, (nk,1) is a lower bound for the number of bits in Zk where Alice (Alice and Bob) sent a vacuum (single-photon) state. ek,1 is an upper bound for the single-photon phase error rate. If ek,14etol, an empty string is assigned to Sk and steps 6 and 7 are aborted for this k, and the protocol only aborts if ek;14etol 8k.

Error correction: For those k that passed the parameter estimation step, Bob obtains an estimate ^

Zk of Zk using an information reconciliation scheme. For this, Alice sends him leakEC,k bits of error

correction data. Next, Alice computes a hash of Zk of length log2 4=Ecor

using a random universal2 hash function, which she sends to Bob together with the hash35. If hash

^

Zk 6 hashZk, Alice

and Bob assign an empty string to Sk and abort step 7 for this k. The protocol only aborts if hash

^

Zk 6 hashZk 8k.

Privacy amplication: If k passed the error correction step, Alice and Bob apply a random universal2 hash function to Zk and ^

Zk to extract two shorter strings of length k (see ref. 35). Alice obtains Sk and Bob ^Sk.

The concatenation of Sk ^Sk

form the secret key SA (SB).

Table 1 | Post-processing of data in the sifting step.

Alice & Bob Bell state reported by Charles w

j i w

/

j i /

hash values are equal, the protocol gives Sk

Z basis Bit ip Bit ip X basis Bit ip Bit ip

To guarantee that their bit strings are correctly correlated, say Bob applies a bit ip to part of his data, depending on the Bell state reported by Charles and the basis setting selected.

^Sk except with error

probability Ecor/4. If hash

^

Zk 6 hashZk, its output is an empty

string (that is, the protocol is trivially correct). Moreover, if the protocol aborts, the result is ?, that is, it is also correct.

This guarantees that SA SB except with error probability rEcor.

Alternatively to this method, Alice and Bob may also guarantee the correctness of the protocol by exploiting properties of the error-correcting code employed44.

If the length k of each bit string Sk, which forms the secret key SA, satises

k nk;0 nk;1 1 h ek;1

leakEC;k

the protocol is Esec-secret, with Esec

Pk Ek;sec and Ek;sec 2e0k 2ek;e ^ek ek;b ek;0 ek;1 ek;PA. In equation (1),

hx x log2x 1 x log21 x is the binary Shannon

entropy, and the parameters ek,0, ek,1, and ek,e quantify, respectively, the probability that the estimation of the terms nk,0, nk,1 and ek,1 is incorrect. A sketch of the proof of equation (1)

can be found in the Methods section. Also explained there, is the meaning of all the epsilons contained in the term Ek;sec, which we

log2 8

Ecor

2log2 2 e0k^ek

2log2 1

2ek;PA ;

1

NATURE COMMUNICATIONS | 5:3732 | DOI: 10.1038/ncomms4732 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications 3

& 2014 Macmillan Publishers Limited. All rights reserved.

ARTICLE NATURE COMMUNICATIONS | DOI: 10.1038/ncomms4732

DiscussionIn this section, we analyse the behaviour of the secret key rate provided in equation (1). In our simulation, we consider that Alice and Bob encode their bits in the polarization degrees of freedom of phase-randomized WCPs. Also, we assume that Charles uses the linear optics quantum relay illustrated in Fig. 2, which is able to identify two of the four Bell states. With this setup, a successful Bell state measurement corresponds to the observation of precisely two detectors (associated to orthogonal polarizations) being triggered. Note, however, that the results presented in this paper can be applied to other types of coding schemes like, for instance, phase or time-bin coding1,2, and to any quantum operation that Charles may perform, as they solely depend on the measurement results that he announces.

We use experimental parameters from ref. 47. But, whereas ref. 47 considers a free-space channel, we assume a bre-based channel with a loss of 0.2 dB km 1. The detection efciency of the relay (that is, the transmittance of its optical components together with the efciency of its detectors) is 14.5% and the background count rate is 6.02 10 6. Moreover, we use a rather

generic channel model that includes an intrinsic error rate that simulates the misalignment and instability of the optical system. This is done by placing a unitary rotation in both input arms of the 50:50 beam splitter, and another unitary rotation in one of its output arms48. In addition, we x the security bound to E 10 10.

The results are shown in Figs 3 and 4 for the situation where Alice and Bob use two decoy states each. In this scenario, we obtain the parameters nk,0, nk,1 and ek,1 using the analytical estimation procedure introduced above (see Supplementary Note 1 for more details). The rst gure illustrates the secret key rate (per pulse) =N as a function of the distance between Alice and Bob for different values of the total number of signals N

omit here for simplicity. In the asymptotic limit of very large data blocks, the terms reducing the length of SA due to statistical uctuations may be neglected, and thus satises

Pk max nk;0 nk;1 1 hek;1

leakEC;k; 0

,

as previously obtained in ref. 23. That is, nk,0 and nk,1 provide a positive contribution to the secret key rate, while nk,1h(ek,1) and leakEC,k

reduce it. The term nk,1h(ek,1) corresponds to the information removed from Zk in the privacy amplication step of the protocol, while leakEC,k is the information revealed by Alice in the error correction step.

The second main contribution of this work is an estimation method to obtain the relevant parameters nk,0, nk,1 and ek,1 needed to evaluate the key rate formula above, when Alice and Bob send Charles a nite number, N, of signals and use a nite number of decoy states. We solve this problem using techniques in large deviation theory. More specically, we employ the Chernoff bound37. It is important to note that standard techniques such as Azumas inequality45 do not give very good bounds here. This is because this result does not consider the properties of the a priori distribution. Therefore, it is far from optimal for situations such as high loss or a highly bias coin ip, which are relevant in long-distance QKD. In contrast, the Chernoff bound takes advantage of the property of the distribution and provides good bounds even in a high-loss regime.

More precisely, we show that the estimation of nk,0, nk,1 and ek,1 can be formulated as a linear program, which can be solved efciently in polynomial time and gives the exact optimum even for large dimensions46. Importantly, this general method is valid for any nite number of decoy states used by Alice and Bob, and for any photon-number distribution of their signals. Also, for the typical scenario where Alice and Bob send phase-randomized WCPs together with two decoy states each, we solve analytically the linear program, and obtain analytical expressions for the parameters above, which can be used directly in an experiment. A sketch of the estimation technique is given in the Methods section. For a detailed analysis of both estimation techniques we refer to the Supplementary Notes 1 and 2.

104

Expected secret key rate (per pulse)

105

N=1014

N=1013.5

N=1013

N=1012.5

N=1012

106

107

Charles

D1H

D1V

PBS PBS

BS

D2H

D2V

108

109

10

10 0 50 100 150 200

Fibre link (km)

Figure 3 | Expected key rate as function of the distance. Secret key rate =N in logarithmic scale for the protocol introduced in the Results section with phase-randomized WCPs as a function of the distance. The solid lines correspond to different values for the total number of signals N sent by Alice and Bob. The overall misalignment in the channel is 1.5%, and the security bound E 10 10. For simulation purposes we consider the

following experimental parameters47: the loss coefcient of the channel is0.2 dB km 1, the detection efciency of the relay is 14.5% and the background count rate is 6.02 10 6. Our results show clearly that even

with a realistic nite size of data, say N 1012 to 1014, it is possible to

achieve secure mdiQKD at long distances. In comparison, the dotted line represents a lower bound on the secret key rate for the asymptotic case where Alice and Bob send Charles innite signals and use an innite number of decoy settings.

Alice

Bob

Figure 2 | A schematic diagram of Charles measurement device.

The signals from Alice and Bob interfere at a 50:50 beam splitter (BS), which has on each end a polarizing beam splitter (PBS) that projects the incoming photons into either horizontal (H) or vertical (V) polarization states. A click in the single-photon detectors D1H and D2V, or in D1V and D2H, indicates a projection into the Bell state j c i1

2

p j HVi jVHi

,

while a click in D1H and D1V, or in D2H and D2V, implies a projection into the Bell state j c i1

2

p j HVi j VHi

:

4 NATURE COMMUNICATIONS | 5:3732 | DOI: 10.1038/ncomms4732 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications

& 2014 Macmillan Publishers Limited. All rights reserved.

NATURE COMMUNICATIONS | DOI: 10.1038/ncomms4732 ARTICLE

Expected secret key rate (per pulse)

104

105

106

107

0.5%

1%1.5%

2%2.5%

108

1010 1011 1012 1013 1014

Total number of signals N sent by Alice and Bob

Figure 4 | Expected key rate as function of the block size. The plot shows the secret key rate =N in logarithmic scale as a function of the total number of signals N sent by Alice and Bob in the limit of zero distance. The security bound E 10 10. The solid lines correspond to different values

for the intrinsic error rate due to the misalignment and instability of the optical system. The horizontal dotted lines show the asymptotic rates. The experimental parameters are the ones described in the caption of Fig. 3. Our results show that, even for a nite size of signals sent by Alice and Bob, mdiQKD is robust to intrinsic errors due to basis misalignment and instability of the optical system.

sent. We x Ecor 10 15; this corresponds to a realistic hash tag

size in practice35. Also, we x the intensity of the weakest decoy states to ad2 bd2 5 10 4, since, in practice, it is difcult to

generate a vacuum state due to imperfect extinction. This value for ad2 and bd2 can be easily achieved with a standard intensity modulator. Moreover, for simplicity, we assume an error correction leakage that is a xed fraction of the sifted key length nk, that is, leakEC;knkzhEas;bsk, with z 1.16 and where

h( ) is again the binary Shannon entropy32. In a realistic

scenario, however, the value of z typically depends on the value of nk, and when nko105 the parameter z may be bigger than 1.16. For a given distance, we optimize numerically =N over all the free parameters of the protocol. This includes the intensities as; ad1; bs and bd1, the probability distributions pa;a and pb;b in the state preparation step, the parameters Na;bk and Ma;bk in the sifting step, the term nk in the parameter estimation step and the different epsilons contained in Esec. Our simulation result shows clearly that mdiQKD is feasible with current technology and does not require high-efciency detectors for its implementation. If Alice and Bob use laser diodes operating at 1 GHz repetition rate, and each of them sends N 1013 signals, we nd, for instance,

that they can distribute a 1-Mb secret key over a 75-km bre link in o3 h. This scenario corresponds to the red line shown in

Fig. 3. Notice that, at telecom wavelengths, standard InGaAs detectors have modest detection efciency of about 15%. Since mdiQKD requires twofold coincidence rather than single detection events, as is the case in the standard decoy state protocol, the key rate of mdiQKD is lower than that of the standard decoy state scheme. However, with high-efciency detectors such as silicon detectors49 in 800 nm or high-efciency superconducting nanowire single-photon detectors50, the key rate of mdiQKD can be made comparable to that of the standard decoy state protocol.

The second gure illustrates =N as a function of N for different values of the misalignment in the limit of zero distance. For comparison, this gure also includes the asymptotic secret key rate when Alice and Bob send an innite number of signals and use an innite number of decoy states23. Our results show

that signicant secret key rates are already possible with 1011 signals, given that the error rate is not too large.

In conclusion, we have proved the security of mdiQKD in the nite-key regime against general attacks. This is the only known fully practical QKD protocol that offers an avenue to bridge the gap between theory and practice in QKD implementations. Importantly, our results clearly demonstrate that even with practical signals (for example, phase-randomized WCPs) and a nite size of data (say 1012 to 1014 signals) it is possible to perform secure mdiQKD over long distances (up to about 150 km).

To achieve high secret key rates in such high-loss regime, it is typical for both standard QKD schemes and mdiQKD to use decoy state techniques. A main challenge in this scenario is to obtain tight bounds for the gain and QBER of the single-photon components sent by Alice and Bob. We have shown that this estimation problem can be successfully solved using techniques in large deviation theory, more precisely, the Chernoff bound. This result takes advantage of the property of the distribution, and thus provides good bounds for the relevant parameters even in the presence of high losses, as is the case in QKD realizations.

Using the Chernoff bound, we have rewritten the problem of estimating the gain and QBER of the single-photon signals as a linear program, which can be solved efciently in polynomial time. This general method is valid for any nite number of decoy states, and for any photon-number distribution of the signals. It can be used, for instance, with laser diodes emitting phase-randomized WCPs, triggered spontaneous parametric downconversion sources and practical single-photon sources. Also, for the common scenario where Alice and Bob send phase-randomized WCPs together with two decoy states each, we have obtained tight analytical bounds for the quantities above. These results apply to different types of coding schemes like, for example, polarization, phase or time-bin coding.

Methods

Secrecy. Here we briey discuss on the secrecy of the protocol described in Box 1. To begin with, note that Alice and Bob obtain the error rate Ea ;bk using a random sample of Za ;bk of size Rk. This means that when Ea ;bk satises the tolerated value

Etol, the error rate between the strings Zk and Z0k, which we denote as xa ;bk , satises the following inequality written as conditional probability51

Pr xa ;bk Ea ;bk wnk; Rk; ek j Opassh i

e2k; 2

where wx; y; z

p

. Here the parameter Opass

represents the event that all the tests performed during the realization of the protocol satisfy the tolerated values.

Let E0k denote the adversarys information about Zk up to the error correction step in Box 1. By using a privacy amplication scheme based on two-universal hashing35 we can generate an Ek-secret string Sk of length k, where ek40, and

Ek 8ek 2

H Z jE

y xy 1=xy 2

ln z 1

1: 3

The function H4emin Zk j E0k

denotes the smooth min-entropy35,52. It quanties the average probability that the adversary guesses Zk correctly using the optimal strategy with access to E0k.

The term E0k can be decomposed as E0kCkEk, where Ck is the information

revealed by Alice and Bob during the error correction step, and Ek is the adversarys information before that step. Using a chain rule for smooth entropies35, we obtain

H4emin Zk j E0k

H4emin Zk j Ek

jCk j; 4

with Ck

j j leakEC;k log2 8=Ecor

.

The bits of Zk can be distributed among three different strings: Z0k; Z1k and Zrestk. The rst contains bits where Alice sent a vacuum state, the second where both

Alice and Bob sent a single-photon state and Zrestk includes the rest of bits. Using the result from ref. 53, we have that

H4emin Zk j Ek

He 2e ^e 2^e ^e min Z0kZ1kZrestk j Ek

nk;0 Hemin Z1k j Z0kZrestkEk

2log2 2 e0k^ek

; 5

where 4eke0k 2e00k ^ek 2^e0k ^e00k

.

Here we have used the fact that

H^emin Zrestk j Z0kEk

0, and H^emin Z0k j Ek

H0min Z0k j Ek

H

min Z0k

n

k;0.

NATURE COMMUNICATIONS | 5:3732 | DOI: 10.1038/ncomms4732 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications 5

& 2014 Macmillan Publishers Limited. All rights reserved.

ARTICLE NATURE COMMUNICATIONS | DOI: 10.1038/ncomms4732

The latter arises because vacuum states contain no information about their bit values, which are uniformly distributed.

The next step is to obtain a lower bound for the term Hemin Z1k j Z0kZrestkEk

.

outcome of the random variable Xa;bk for a given trial. Then, if 2e 1a;b

exp 3= 4

2

p

2

and ^

e 1a;b

1=m

oexp 1=3

, with

ma;bk;L Za;bk

1=m

Taking that Alice and Bob do the state preparation scheme perfectly in the Z and X bases (that is, they prepare perfect BB84 states), we can re-write this quantity in terms of the smooth max-entropy between them, which is directly bounded by the strength of their correlations32. More precisely, the entropic uncertainty relation gives us

Hemin Z1k j Z0kZrestkEk

nk;1 Hemax X1k j X01k

s

Xa;bZa;bk

.2 ln 1=Ea;b

; 10

the Claim above implies that

Za;bk

nk;1 nk;1h ek;1

6

Combining equations (3)(6), we nd that a secret key of length k given by equation (1) gives an error of Ek 2 e0k 2e00k ^ek 2^e0k ^e00k

:

Xn;mpa;bjnm;ZSk;nm da;b; 11

except with error probability ga;bEa;b ea;b ^ea;b, where da;b 2 Da;b;

^

Da;b

ek;PA. Finally, after

composing the errors related with the estimation of nk,0, nk,1 and ek,1, selecting ^

e0k

and ^

e00k equal to zero, and also removing the conditioning on Opass, we obtain a security parameter Ek;sec given by

Ek;sec2 e0k 2ek;e ^ek

ek;b ek;0 ek;1 ek;PA; 7

where ek;b ek

Pr Opass

with Da;bg Za;bk

; e4a;b=16

and ^

.

h i

,

Da;bg Za;bk

;^

e3=2a;b

q

Using similar arguments, we nd that the parameter mk,0 can be written as

mk;0

Xmpa ;b j0 Sk;0m D0; 12

except with error probability e0, where D0 g

Pm pa;b j0 Sk;0 ; e0

.

, and ek,0, ek,1 and ek,e, denote, respectively, the error probability in the estimation of nk,0, nk,1 and ek,1.

Parameter estimation. To simplify the discussion, let us consider the estimation of the parameter nk,0. The method to obtain nk,1 and ek,1 follows similar arguments. The procedure can be divided into two steps. First, we calculate a lower bound for the number of indexes in Za ;bk where Alice sent a vacuum state. This quantity is

denoted as mk,0. Second, we compute nk,0 from mk,0 using the Sering inequality for random sampling without replacement51.

In the rst step we use a multiplicative form of the Chernoff bound37 for independent random variables, which does not require the prior knowledge on the population mean. More precisely, we use the following claim.

Claim: Let X1; X2; :::; Xn, be a set of independent Bernoulli random variables that satisfy Pr(Xi 1) pi, and let X

Now it is easy to nd a lower bound for mk,0. One only needs to minimize equation (12) given the linear constraints imposed by equation (11) for all a, b. This problem can be solved either by using numerical tools as linear programming46 or, for some particular cases, by using analytical techniques. See Supplementary Notes 1 and 2 for details.

The second step of the procedure is quite direct. Note that Alice forms her bit string Zk using nk random indexes from Za ;bk . Using ref. 51 we obtain

nk;0 max nk

mk;0

j Za ;bk j

( )

; 13

nkLj Za ;bk j; nk; e00k;0

$ %

; 0

Pni1 pi, where E[ ] denotes the mean value. Let x be the observed outcome of X for a given trial (that is, x 2 N ) and mLx

n=2 ln 1=E p

Pni1 Xi and mE X

except with error probability

ek;0

for certain E40. When 2e 1 1=m

exp 3= 4

p

2

and ^

2

e 1 1=m oexp 1=3

for a certain e;^e40, we have that

e0k;0 e00k;0; 14

where e0k;0 corresponds to the total error probability in the estimation of mk;0, and the function Lx; y; z is dened as Lx; y; z

x y 1lnz 1

p

=2xy

.

x satises

xm d; 8 except with the error probability gE e ^e, where the parameter d 2 D;

References

1. Gisin, N. et al. Quantum cryptography. Rev. Mod. Phys. 74, 145195 (2002).^ , 2. Scarani, V. et al. The security of practical quantum key distribution. Rev. Mod. Phys. 81, 13011350 (2009).

3. Qi, B. et al. Time-shift attack in practical quantum cryptosystems. Quantum Inf. Comput. 7, 7382 (2007).

4. Fung, C.-H. F. et al. Phase-remapping attack in practical quantum-key-distribution systems. Phys. Rev. A 75, 032314 (2007).

5. Lamas-Linares, A. & Kurtsiefer, C. Breaking a quantum key distribution system through a timing side channel. Opt. Express 15, 93889393 (2007).

6. Zhao, Y. et al. Quantum hacking: experimental demonstration of time-shift attack against practical quantum-key-distribution systems. Phys. Rev. A 78, 042333 (2008).

7. Nauerth, S. et al. Information leakage via side channels in freespace BB84 quantum cryptography. New J. Phys. 11, 065001 (2009).

8. Xu, F., Qi, B. & Lo, H.-K. Experimental demonstration of phase-remapping attack in a practical quantum key distribution system. New J. Phys. 12, 113026 (2010).

9. Lydersen, L. et al. Hacking commercial quantum cryptography systems by tailored bright illumination. Nat. Photon. 4, 686689 (2010).

10. Gerhardt, I. et al. Full-eld implementation of a perfect eavesdropper on a quantum cryptography system. Nat. Commun. 2, 349 (2011).

11. Weier, H. et al. Quantum eavesdropping without interception: an attack exploiting the dead time of single-photon detectors. New J. Phys. 13, 073024 (2011).

12. Mayers, D. & Yao, A. C.-C. in Proc. of the 39th Annual Symposium on Foundations of Computer Science (FOCS98) 503509 (IEEE Computer Society, 1998).

13. Acn, A. et al. Device-independent security of quantum cryptography against collective attacks. Phys. Rev. Lett. 98, 230501 (2007).

14. Pironio, S. et al. Device-independent quantum key distribution secure against collective attacks. New J. Phys. 11, 045021 (2009).

15. McKague, M. Device independent quantum key distribution secure against coherent attacks with memoryless measurement devices. New J. Phys. 11, 103037 (2009).

16. Masanes, L., Pironio, S. & Acn, A. Secure device-independent quantum key distribution with causally independent measurement devices. Nat. Commun. 2, 238 (2011).

17. Barrett, J., Colbeck, R. & Kent, A. Memory attacks on device-independent quantum cryptography. Phys. Rev. Lett. 110, 010503 (2013).

18. Bell, J. S. On the Einstein-Podolsky-Rosen paradox. Physics 1, 195200 (1964).

h i

with Dg x; e4=16

,

^

Dg x;^e3=2

and g x; y

.

2x ln y 1

p

. Here e ^e

denotes

the probability that xom D x4m

^

D

^

D) on the uctuation parameter d that appears in equation (8) do not depend on the mean value m. A proof of this claim can be found in the Supplementary Note 3. There we introduce as well a generalized version of the claim for the cases where 2e 1 1=m 4 exp 3=42

p

2

Importantly, the bounds ( D and

and/or ^

e 1 1=m exp 1=3

.

To apply this statement and be able to obtain the parameter mk,0, we rephrase the protocol described in Box 1. For each signal, we consider that Alice (Bob) rst chooses a photon-number n(m) and sends the signal to Charles, who declares whether his measurement is successful or not. After Alice decides the intensity setting a, Bob does the same. This virtual protocol is equivalent to the original one because the essence of decoy state QKD is precisely that Alice and Bob could have postponed the choice of which states are signals or decoys after Charles declaration of the successful events. This is possible because Alices and Bobs observables commute with those of Charles. Note that for each specic combination of values n and m, the observables that Alice and Bob use to determine whether a state is a signal or a decoy act on entirely different physical systems from those of Charles. This implies that Alice and Bob are free to postpone their measurement and thus their choice of signals and decoys. Also, this result shows that for each combination n and m, the signal and decoy states provide a random sample of the population of all signals containing n and m photons, respectively. Therefore, one can apply random sampling theory in classical statistics to the quantum problem.

Let Sk;nm denote the set that identies those signals sent by Alice and Bob with

n and m photons, respectively, when they select the Z basis and Charles announces the Bell state k. And, let Sk;nm

Sk;nm, and pa;b nm;Zj be the conditional probability

that Alice and Bob have selected the intensity settings a and b, given that their signals contain, respectively, n and m photons prepared in the Z basis. Then, if we apply the above equivalence, independently of each other and for each signal Alice and Bob assign to each element in Sk;nm the intensity setting a, b, with probability

pa;b nm;Z

j .

Let Xa;bi k;nmj be 1 if the ith element of Sk;nm is assigned to the intensity setting

combination a, b, and otherwise 0. And, let

Xa;bk

Xn;m

S

i1

Xa;bi k;nmj; 9

with ma;bk E Xa;bkh i P

n;m pa;bjnm;ZSk;nm. Let xa;bk Za;bk

denote the observed

6 NATURE COMMUNICATIONS | 5:3732 | DOI: 10.1038/ncomms4732 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications

& 2014 Macmillan Publishers Limited. All rights reserved.

NATURE COMMUNICATIONS | DOI: 10.1038/ncomms4732 ARTICLE

19. Clauser, J. F. et al. Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23, 880884 (1969).

20. Pearle, P. Hidden-variable example based upon data rejection. Phys. Rev. D 2, 14181425 (1970).

21. Gisin, N., Pironio, S. & Sangouard, N. Proposal for implementing device-independent quantum key distribution based on a heralded qubit amplier. Phys. Rev. Lett. 105, 070501 (2010).

22. Curty, M. & Moroder, T. Heralded-qubit ampliers for practical device-independent quantum key distribution. Phys. Rev. A 84, 010304(R) (2011).

23. Lo, H.-K., Curty, M. & Qi, B. Measurement-device-independent quantum key distribution. Phys. Rev. Lett. 108, 130503 (2012).

24. Rubenok, A. et al. Real-world two-photon interference and proof-of-principle quantum key distribution immune to detector attacks. Phys. Rev. Lett. 111, 130501 (2013).

25. Ferreira da Silva, T. et al. Proof-of-principle demonstration of measurement device independent QKD using polarization qubits. Phys. Rev. A 88, 052303 (2013).

26. Liu, Y. et al. Experimental measurement-device-independent quantum key distribution. Phys. Rev. Lett. 111, 130502 (2013).

27. Tang, Z. et al. Experimental demonstration of polarization encoding measurement-device-independent quantum key distribution. Preprint at (http://arxiv.org/abs/1306.6134

Web End =http://arxiv.org/abs/1306.6134) (2013).

28. Curty, M., Lewenstein, M. & Ltkenhaus, N. Entanglement as a precondition for secure quantum key distribution. Phys. Rev. Lett. 92, 217903 (2004).

29. Lim, C. C. W. et al. Device-Independent quantum key distribution with local Bell test. Phys. Rev. X 3, 031006 (2013).

30. Song, T.-T. et al. Finite-key analysis for measurement-device-independent quantum key distribution. Phys. Rev. A 86, 022332 (2012).

31. Ma, X., Fung, C.-H. F. & Razavi, M. Statistical uctuation analysis for measurement-device-independent quantum key distribution. Phys. Rev. A 86, 052305 (2012).

32. Tomamichel, M., Lim, C. C. W., Gisin, N. & Renner, R. Tight nite-key analysis for quantum cryptography. Nat. Commun. 3, 634 (2012).

33. Bacco, D., Canale, M., Laurenti, N., Vallone, G. & Villoresi, P. Experimental quantum key distribution with nite-key security analysis for noisy channels. Nat. Commun. 4, 2363 (2013).

34. Lim, C. C. W., Curty, M., Walenta, N., Xu, F. & Zbinden, H. Concise security bounds for practical decoy-state quantum key distribution. Phys. Rev. A 89, 022307 (2014).

35. Renner, R. Security of Quantum Key Distribution. PhD thesis, ETH Zurich (2005).

36. Mller-Quade, J. & Renner, R. Composability in quantum cryptography. New J. Phys. 11, 085006 (2009).

37. Chernoff, H. A measure of asymptotic efciency for tests of ahypothesis based on the sum of observations. Ann. Math. Stat. 23, 493507 (1952).

38. Hwang, W.-Y. Quantum key distribution with high loss: toward global secure communication. Phys. Rev. Lett. 91, 057901 (2003).

39. Lo, H.-K., Ma, X. & Chen, K. Decoy state quantum key distribution. Phys. Rev. Lett. 94, 230504 (2005).

40. Wang, X.-B. Beating the photon-number-splitting attack in practical quantum cryptography. Phys. Rev. Lett. 94, 230503 (2005).

41. Bennett, C. H. & Brassard, G. in Proc. IEEE Int. Conf. on Comp. Sys. and Signal Processing 175179 (Bangalore, India, 1984).

42. Biham, E., Huttner, B. & Mor, T. Quantum cryptographic network based on quantum memories. Phys. Rev. A 54, 26512658 (1996).

43. Inamori, H. Security of practical time-reversed EPR quantum key distribution. Algorithmica 34, 340365 (2002).

44. Ltkenhaus, N. Estimates for practical quantum cryptography. Phys. Rev. A 59, 33013319 (1999).

45. Azuma, K. Weighted sums of certain dependent random variables. Thoku Math. J. 19, 357367 (1967).

46. Vanderbei, R. J. (ed.) Linear Programming: Foundations and Extensions. International Series in Operations Research and Management Science, 3rd edn (Springer, 2008).

47. Ursin, R. et al. Entanglement-based quantum communication over 144 km. Nat. Phys. 3, 481486 (2007).

48. Xu, F. et al. Practical aspects of measurement-device-independent quantum key distribution. New J. Phys. 15, 113007 (2013).

49. Hadeld, R. H. Single-photon detectors for optical quantum information applications. Nat. Photon. 3, 696705 (2009).

50. Marsili, F. et al. Detecting single infrared photons with 93% system efciency. Nat. Photon. 7, 210214 (2013).

51. Sering, R. J. Probability inequalities for the sum in sampling without replacement. Ann. Statist. 2, 3948 (1974).

52. Tomamichel, M., Colbeck, R. & Renner, R. Duality between smooth min- and max-entropies. IEEE Trans. Inf. Theory 54, 46744681 (2010).

53. Vitanov, A., Dupuis, F., Tomamichel, M. & Renner, R. Chain rules for smooth min- and max-entropies. IEEE Trans. Inf. Theory 59, 26032612 (2013).

Acknowledgements

We thank Xiongfeng Ma and Johan Lfberg for valuable comments and stimulating discussions, and Lina M. Eriksson for comments on the writing and presentation of the paper. F.X. thanks the Paul Biringer Graduate Scholarship for nancial support. We acknowledge support from the European Regional Development Fund (ERDF), the Galician Regional Government (projects CN2012/279 and CN 2012/260, Consolidation of Research Units: AtlantTIC), NSERC, the CRC program, the National Centre of Competence in Research QSIT, the Swiss NanoTera project QCRYPT, the FP7 Marie-Curie IAAP QCERT project and CHIST-ERA project DIQIP. K.T. acknowledges support from the project Secure photonic network technology as part of The project UQCC by the National Institute of Information and Communications Technology (NICT) of Japan, and from the Japan Society for the Promotion of Science (JSPS) through its Funding Program for World-Leading Innovative R&D on Science and Technology (FIRST Program).

Author contributions

All authors contributed extensively to the work presented in this paper.

Additional information

Supplementary Information accompanies this paper at http://www.nature.com/naturecommunications

Web End =http://www.nature.com/ http://www.nature.com/naturecommunications

Web End =naturecommunications

Competing nancial interests: The authors declare no competing nancial interests.

Reprints and permission information is available online at http://npg.nature.com/reprintsandpermissions/

Web End =http://npg.nature.com/ http://npg.nature.com/reprintsandpermissions/

Web End =reprintsandpermissions/

How to cite this article: Curty, M. et al. Finite-key analysis for measurement-device-independent quantum key distribution. Nat. Commun. 5:3732 doi: 10.1038/ncomms4732 (2014).

NATURE COMMUNICATIONS | 5:3732 | DOI: 10.1038/ncomms4732 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications 7

& 2014 Macmillan Publishers Limited. All rights reserved.