## Abstract

Quantum key distribution is widely thought to offer unconditional security in communication between two users. Unfortunately, a widely accepted proof of its security in the presence of source, device, and channel noises has been missing. This long-standing problem is solved here by showing that, given fault-tolerant quantum computers, quantum key distribution over an arbitrarily long distance of a realistic noisy channel can be made unconditionally secure. The proof is reduced from a noisy quantum scheme to a noiseless quantum scheme and then from a noiseless quantum scheme to a noiseless classical scheme, which can then be tackled by classical probability theory.

The art of secure communication—cryptography—has a long history. Before two parties can communicate securely, they often must share a secret random string of numbers (a key) for encryption and decryption. The secrecy of the message depends on the secrecy of the key. A problem in conventional cryptography is the key distribution problem: In classical physics, there is nothing to prevent an eavesdropper from monitoring the key distribution channel passively, without being caught by the legitimate users.

Quantum key distribution (QKD) (1–5) has been proposed as a solution to the problem. The quantum no-cloning theorem states that it is impossible to make an exact copy of an unknown quantum state (6). Thus, it is generally thought that eavesdropping on a quantum channel will almost surely produce detectable disturbances. The two users can, therefore, use part of their quantum signals to test for eavesdropping. Only when the error rates are acceptable will they use the quantum signals to generate a key. Thus, the two users (commonly called Alice and Bob) have the confidence that if an eavesdropper (commonly called Eve) has a nonnegligible amount of information on the final key, she will almost surely be caught, even if she has infinite computing power and access to a quantum computer. Incidentally, several recent experiments have demonstrated the feasibility of QKD over tens of kilometers (7).

“The most important question in quantum cryptography is to determine how secure it really is” (8, p. 16). QKD is widely claimed to provide perfect security. However, this viewpoint has been under renewed scrutiny for two reasons. First, contrary to well-known claims of unconditional security (9), a class of other quantum cryptographic schemes, including so-called quantum bit commitment and quantum one-out-of-two oblivious transfer, has recently been shown to be insecure (10). Cheaters can defeat these schemes by a subtle application of the well-known Einstein-Podolsky-Rosen (EPR) paradox (11) and by delaying their measurements. These “no-go” theorems not only shattered the long-standing belief in the security of those schemes, but they also undermined the confidence in QKD itself. Second, a convincing and rigorous proof of the security of QKD has been missing despite extensive investigations (12–15). Thus, the foundation of quantum cryptography has been shaky. Here, we solve this long-standing problem by proving that, given quantum computers, QKD can be made unconditionally secure over arbitrarily long distances.

A rigorous proof of the security of a QKD scheme requires the explicit construction of a procedure such that, whenever Eve's strategy has a nonnegligible probability of passing the verification test by Alice and Bob, her information on the final key will be exponentially small (16–17). This procedure must be secure and efficient, even when Alice and Bob use imperfect sources and devices and share a noisy quantum channel.

Most analyses of the security of QKD have dealt with single-particle eavesdropping strategies (12), with immediate or delayed measurements, as well as the so-called collective attacks (13), in which Eve brings each signal particle into interaction with a separate probe system but then, after hearing the public discussion between Alice and Bob, measures all probes together. Security against the most general type of attack, the so-called joint attack, has been investigated by Deutsch *et al*. and also by Mayers. The discussion by Deutsch *et al*. was restricted to the special case of perfect devices (14). It introduced the concept of quantum privacy amplification, based on a process called entanglement purification, which was studied by Bennett, DiVincenzo, Smolin, and Wootters (BDSW) (18). Earlier versions of Mayers's proof (15) have not been accepted as definitive. His most recent version of the proof is more detailed and complex (19). He proposes a proof of security of the Bennett and Brassard (BB84) (2) scheme against joint attacks in the presence of detector and channel noise but with an ideal trusted single-photon source. Our current work and work by Mayers (19) are contemporaneous and independent. They differ greatly in their premises, methods, and consequences. (i) Mayers's work deals with the standard BB84 QKD protocol (2) for preparation, transmission, and measurements of nonorthogonal states. His approach does not require Alice and Bob to have a quantum computer, although Eve may have one. In contrast, our proof applies to a new QKD protocol, involving fault-tolerant sharing and purification of so-called EPR pairs, and requires that Alice and Bob have quantum computers. (ii) Mayers's work (19) assumes an ideal single-photon or EPR-pair source, thus disallowing a beam-splitter attack. [A testing procedure for an allegedly ideal EPR-pair source from an untrusted vendor has recently been suggested by Mayers and Yao (20).] In contrast, our work allows the reception of untrusted imperfect quantum signals from the channel (21). (iii) Our proof and protocol allow QKD to be securely extended over arbitrarily large distances through a chain of insecure relay stations. A similar extension of BB84 in Mayers's proposed proof would require secure relay stations, to which Eve does not have access. (iv) Our proof is conceptually simpler. (v) Our techniques have widespread applications outside QKD.

Why is a proof of security of QKD so difficult? In a joint attack, Eve treats the whole sequence of quantum signals as a single entity. She couples this entity with her probe and then unitarily evolves the combined system. She forwards a subsystem to Bob and keeps the remaining subsystem for eavesdropping purposes. Eve can use any unitary transformation she likes, and yet, a secure QKD scheme must defeat all of them. Moreover, Eve may attempt to mask her presence by attributing the errors caused by her eavesdropping attack to normal transmission noise. Furthermore, because the particles are now generally entangled with each other, a naı̈ve application of classical probability theory may lead to fallacies [see the EPR paradox (11)].

Despite these apparent difficulties, we show that it is possible to distinguish a malicious Eve from noise. Moreover, it is possible to use classical probability theory to establish the security of QKD.

Techniques and importance of results.

Assuming that users have access to quantum computers, we show the security of QKD by a reduction in two steps. The central theme of the first step is to reduce the noisy quantum scheme (imperfect devices, noisy channels, storage errors, and so forth) to a noiseless quantum scheme. We do this by combining the ideas of “quantum repeaters” (22, 23) and fault-tolerant quantum computation (FTQC) (24, 25). Although these are existing ideas in the field, we make the nontrivial observation that they can be combined and applied to QKD to distinguish noise from a malicious Eve. In particular, we note that knowing the error syndrome does not help an eavesdropper. Therefore, we can give an eavesdropper full control of the quantum repeater stations without compromising security.

Even in a noiseless quantum scheme, Alice and Bob are required to verify that the particles are untampered by Eve. Things will be easy if one can apply classical arguments to solve this quantum problem at hand. However, as illustrated by the EPR paradox, naı̈ve classical arguments often lead to fallacies. The most important technical contribution of this paper is our second theme—reducing the noiseless quantum verification scheme to a classical one. Finally, we establish the security of the classical verification scheme by classical probability theory. The security of the quantum scheme then follows.

The use of classical arguments in our quantum problem allows us to simplify our discussion greatly. We emphasize that the validity of this usage is highly paradoxical. Classical arguments work in our quantum problem because all of the observables *O _{i}
*'s under consideration are diagonal with respect to a single basis ℬ. In more detail, let us consider the observable

*M*, which represents a complete von Neumann measurement along the same basis ℬ. Because all of the

*O*'s under consideration are diagonal with respect to ℬ,

_{i}*M*commutes with all the observables

*O*'s. Therefore, the measurement

_{i}*M*along basis ℬ will in no way change the outcome of the subsequent

*O*'s. Without any loss of generality, one can imagine that such a complete von Neumann measurement

_{i}*M*is always performed before the measurement of subsequent

*O*'s. In other words, the initial state of the quantum system is simply a classical mixture of eigenstates of

_{i}*M*, and hence, classical arguments carry over to the quantum case. We remark that the

*O*'s that we consider are coarse-grained observables (observables with degenerate eigenvalues) rather than fine-grained observables (observables with nondegenerate eigenvalues).

_{i}Quantum-computational protocols.

The execution of our secure QKD scheme requires large-scale quantum computers for both error correction and verification. Building such computers is a technological feat that is far beyond our current technology. However, all existing QKD security analyses require some idealization also. In an actual experimental implementation of polarization-coding BB84 (a standard “prepare-and-measure” P/M scheme) over a substantial distance (say 40 km) of a lossy quantum channel using coherent states, Eve may, in principle, break the system completely by a generalized beam-splitting attack (26). This is so even when the bit error rate of the quantum signals is strictly zero.

Quantum-computational protocols like ours are worthy of analysis for several reasons. First, unlike the usual P/M schemes, they extend the range of secure QKD to arbitrarily long distances even with insecure quantum repeaters. Second, when implemented over a noisy channel without repeaters, it is conceivable that they can tolerate a higher noise level than a standard P/M scheme. Third, a proof of security and the trade-off between noise and key rate are much easier than those for P/M schemes. Indeed, our scheme provides a conceptually simple and rigorous proof of the security of QKD without the full complexity of a P/M scheme.

#### EPR pairs.

Before we report our QKD scheme in detail, let us first recapitulate the usefulness of an EPR pair, that is, a singlet state (1/
*) in QKD. If two members of an EPR pair are measured along any common axis, each member will give a random outcome, and yet, the outcomes of the two members will always be antiparallel. This spooky action at a distance defies any simple classical explanation and is at the core of EPR paradox (*11*).*

Now, suppose two distant users share R *EPR pairs. Then, the random outcome of measurement along a common axis generates an *R*-bit key between them. The laws of quantum physics assure that the key is truly random and that Eve cannot have any information on its value. Indeed, the two lemmas in supplementary material (available at www.sciencemag.org/feature/data/984035.shl) show that, to generate an almost perfectly secure *R*-bit key, Alice and Bob only need to share *R* EPR pairs of almost perfect fidelity (*28*). Therefore, all we need for secure QKD is a way for Alice and Bob to share EPR pairs and to verify that, indeed, they are EPR pairs. We focus on these EPR distribution and verification problems. There are two issues that Alice and Bob have to address: noise and Eve.*

#### Reduction to a noiseless scheme.

One can classify errors in an EPR-pair distribution process into four types. First, the quantum communication channel between Alice and Bob is generally noisy. Second, the EPR source may be imperfect in itself. Third, errors may occur during the storage of quantum information. Fourth, errors may also occur during computation; because elementary gates and measuring devices for quantum computation are generally imperfect, gate errors and measurement errors may arise.

The last three types of errors can be fixed by recently developed quantum error correction (29*) and fault-tolerant quantum computation (FTQC) (*24, 25*) techniques. In particular, there is a “threshold result” in FTQC: Assuming an independent noise model and that the error rates for each primitive computational gate and for each time step of storage are smaller than some positive threshold values, one can perform arbitrarily long quantum computations with an arbitrarily high fidelity (*25*). The essence of FTQC is to defeat errors by encoding quantum states in quantum error-correcting codes (QECC) and then performing quantum computation on the encoded states.*

#### Quantum repeaters.

We must consider the first type of noise—channel noise. If the quantum communication channel is very noisy (for example, it is very long), we cannot apply the threshold result in FTQC to combat quantum communication errors. Fortunately, the idea of quantum repeaters has been proposed as a much more efficient way of correcting quantum communication errors (23*). This idea is summarized as follows.*

Given impure EPR pairs shared between two distant observers, they can apply local operations and classical communication to distill a smaller number of higher fidelity EPR pairs in a procedure known as entanglement purification (18*). However, for distances much longer than the coherence length of a noisy quantum communication channel, the probability that a quantum state will remain error-free is exponentially small. Therefore, the fidelity of transmission is so low that standard purification methods are not applicable.*

Quantum repeaters are essentially simple quantum computers installed throughout a quantum communication channel. They are used to divide the channel into shorter segments, which are then purified separately, before they are connected. The number and locations of quantum repeaters are chosen so that it is possible to create EPR pairs with sufficiently high fidelity between the two ends of each segment. After creating EPR pairs that are shared between the two ends, one applies entanglement purificaton by using quantum repeaters. This will, at the cost of discarding some pairs, increase the fidelity of the remaining pairs. Afterwards, EPR pairs shared between various segments are connected together by “quantum teleportation” (30*). Indeed, a highly efficient procedure involving a sequence of entanglement purification and teleportation has been devised that allows the reliable sharing of EPR pairs between two arbitrarily distant locations (*23*).*

Three important remarks are in order. First, with two-way classical communication, quantum repeaters can greatly improve the yield of distillation (18, 23*) over the standard fault-tolerant circuits. Second, even highly imperfect quantum repeaters can do the job very well: It has been argued (*23*) that an error rate in the percent level is readily tolerable. Third, a strength of our approach is that, assuming perfectly reliable local quantum operations by Alice and Bob, one can actually calculate the threshold value for tolerable noise between two adjacent quantum repeaters. For example, in the case of a depolarizing channel, it is known that a fidelity of 1/2 is the threshold value (*18*).*

With quantum repeaters and FTQC, the usual threshold result can be extended to distributed quantum computation over a realistic noisy quantum channel (31*). In other words, any distributed quantum algorithm, including the EPR-pairs distribution process, that works in the noiseless case can always be extended to the noisy case.*

Error syndrome contains no useful information for an eavesdropper.

We make the most generous assumption that Eve completely controls the quantum repeaters and the quantum communication channel. Alice and Bob need only trust their own quantum computers and authenticated classical messages from each other. There is a subtlety for us to address. If Eve follows the correct procedure, she will not be caught. However, she does learn about the error syndrome (that is, the pattern of measurement results) generated during a FTQC, which allows the error-correction apparatus to correct a corrupted state to a former value. So, the question is Can the error syndrome tell her anything useful about the state? The answer is “no” because of the following. Mathematically, each of Alice and Bob's state can be written as a tensor product of the logical qubits (which actually contain the quantum information) and the ancillary qubits (which contain the error syndromes) (32); that is, the wave function |Ψ〉 can be written as Σ_{i,j}
*c _{ij}|a_{i}〉_{L} ⊗ |e_{j}〉_{A}
*, where subscripts

*L, A, i*, and

*j*represent the logical qubits, the ancillary qubits, the logical state (in some orthonormal basis), and the error syndrome, respectively, and

*c*

_{ij}'s are some complex coefficients. (In reality, Alice and Bob's system is generally entangled with Eve's probe. However, this does not change the essential point of our argument.) Because of FTQC, although the state of the ancillary qubits evolves unpredictably over time, the state of the logical qubits will, with a very high fidelity [1 −

*O*(

*e*

^{−ℓ}) for some arbitrarily chosen ℓ > 0 (33)], follow the desired computation and remain unaffected by the errors. As long as the gate error rate and storage error rate are sufficiently small, the subsequent verification and key generation steps can be thought of as being performed solely on the logical qubits. In other words, the ancillary qubits decouple from the verification step. Accordingly, we shall ignore the ancillary qubits and focus only on the logical qubits.

If there is no appreciable eavesdropping, the logical qubits will represent the desired state. Of course, an honest Eve can learn as much as she likes about the error syndrome. The general theory of QECC tells us that the error syndrome contains absolutely no information about the encoded quantum state (*29).*

In summary, we have reduced the proof of security of our noisy QKD (or EPR delivery) scheme to that of a noiseless one. Now, we focus on the noiseless scheme.

The goal of verification.

To make sure that there is no substantial eavesdropping, Alice and Bob must verify that the state of the logical qubits is, indeed, that of *N*EPR pairs. Without any loss of generality, we can allow Eve to not merely act on the *N* EPR pairs while they are being shared but to actually prepare them in an arbitrary state of her choosing and then give them to Alice and Bob (14). She claims that they are perfect EPR pairs. Alice and Bob will be happy to sacrifice a small number *m* of those pairs to verify Eve's claim. If any one of the *m* tested pairs fails the test, then all the *N* pairs are discarded. However, if all the*m* pairs pass the test, the remaining *N − m* pairs will be accepted as singlets and used to generate the key. The goal of the verification is for Alice and Bob to make sure that Eve has a very small probability of cheating successfully. By cheating successfully, we mean that the *m* tested pairs pass the verification test and yet the remaining *N − m* pairs, if given a yes or no test of being *N − m *singlets, will give “no” as an answer (34).

The security of our quantum verification scheme will automatically guarantee the security of the corresponding QKD scheme [refer to (28) for an explicit bound on Eve's information]. We will now consider the security of our quantum verification scheme.

Essentially, what Alice and Bob are trying to do is to distinguish singlets from triplets. Although there is no way for Alice and Bob to do so with certainty using only local operations and classical communication, they can do so with a very high probability.

The goal of a quantum verification scheme is to verify that the state of the *N *pairs is, in fact, *N* singlet. A direct testing of a random subset of EPR pairs requires an exponential amount of resources in terms of the security parameter *k*, where the probability for Eve to cheat successfully is, at most,*e ^{−k}
*. Direct testing of a random subset is, therefore, not an efficient verification scheme. To understand this point, suppose Eve cheats by inserting a single nonsinglet among the

*N*pairs and only

*m*random pairs are tested by Alice and Bob. There is a probability (

*N − m*)/

*N*for this nonsinglet to remain untested. Consequently, Eve has at least a probability (

*N − m*)/

*N*of cheating successfully. To prevent this from happening, it is necessary for

*m*to be of order

*N*. Even when

*m*equals

*N −*1, the probability for Eve to cheat successfully is still at least 1/

*N*. For this to be exponentially small in

*k*, the number of photons transmitted

*N*, must be exponentially large in

*k*.

A much more efficient way of verifying a quantum state exists. It is due to the random- hashing idea by BDSW (18). (BDSW proposed it for error correction, but here we use it for verification.) It is in the same spirit of a classical random-hashing scheme which we will now describe.

#### A classical verification scheme.

Imagine a game in which Eve locks an N*-bit string*x* in a box and Alice and Bob are allowed to ask a small number *m* < *N* of “fair” questions about it, which Eve must answer truthfully. A fair question is a yes or no question whose answer is “yes” for exactly half of all*N*-bit strings. Thus, Is the first bit 1? and Are the first and third bits equal? are fair questions, but Are all the bits 1's? is unfair. If all of Eve's answers are consistent with the assumption that the string *x* is all 1's, Alice and Bob must “accept” the string. Otherwise, Alice and Bob must “reject” the string. Finally, Eve opens the box and shows Alice and Bob the string to prove that she has answered faithfully. Eve wins if the string is not all 1's and yet Alice and Bob have accepted the string. [Alice and Bob win if the string is not all 1's and they have rejected the string. If the string is, in fact, all 1's, the game is a draw].*

If Alice and Bob ask only single-digit questions of the form Is the k*th bit a 1? then Eve has a good chance of winning by choosing a string with a single 0 at a random location. However, if Alice and Bob instead ask Eve about the parities of random subsets of the bits, they quite likely catch any string that is not all 1s.*

For example, if the unknown string is x* = 1101 and Alice and Bob choose a subset consisting of the second and third bits (this can be represented conveniently by an index string *s* = 0110), the parity *x · s* is 1. This test reveals that *x*is not all 1's, because an all-1's four-bit string would have had parity 0 on this subset. More generally, the parity of a subset*s* of the bits in a string *x* is the inner product, or modulo-2 sum of the bit-wise AND of strings *x* and*s*, and it is denoted by *x · s*. [In this example, *x · s* = 1 · 0 + 1 · 1 + 0 · 1 + 1 · 0 = 1 (mod 2).] The probability that two different strings give the same answer for *m* iterations of random parity check is no more than 2*
^{−m}
* (*18*). Thus, by checking only a few subset parities (say 20), Alice and Bob can reduce their chance of accepting an *x* that is not all 1s to less than one in a million.*

Eve must not know the index strings beforehand. Otherwise, she could always cheat successfully, in a similar way as a smuggler who knows beforehand which of the several bags a custom inspector will open in an airport. Indeed, because the string has N* bits and there are only *m *constraints (generated by *m*rounds of parity verification), there are clearly exponentially many (namely, 2*
^{N − m}
*), strings that will pass the test. However, because Eve does not know the index strings beforehand and because the index strings are chosen randomly, Eve effectively has to put her bet on a single string without prior knowledge. We see from the last paragraph that any string *x* ≠ 11 ⋯ 1 chosen by Eve has only an exponentially small probability (2*
^{−m}
*) of passing the verification test.*

#### Our quantum verification scheme.

Now, we construct an efficient quantum verification scheme that is similar to the classical verification scheme that we have just described. Consider the so-called Bell basis, Ψ^{±} and Φ^{±}, where(1)and(2)With the convention in (18*), Bell basis vectors are represented by two classical bits*
(3)(Because Bell basis vectors are maximally entangled, one should never think of them as direct product states.) A complete basis for N*-ordered pairs of qubits (what we shall call *N*-bell basis) consists of products of Bell basis vectors, each of which is described by a 2*N*-bit string. In the absence of an eavesdropper, Alice and Bob share *N* singlets, whose state is described by a 2*N*-bit string of 1̃'s, |1̃1̃⋯1̃〉.*

What happens when there is an eavesdropper? Recall that we allow Eve to not merely act on the N* EPR pairs while they are being shared but to actually prepare them in an arbitrary state of her choosing and then give them to Alice and Bob. The pairs may be entangled among themselves as well as with a probe in Eve's hands (*14*). A system described by any mixed state can be equivalently described by a pure state of a larger system consisting of the original system and an ancilla (*10, 14*). As discussed by Deutsch *et al*. (*14*), by considering the larger system instead, we shall, without a loss of generality, consider that Eve prepares a pure state*
(4)where i_{k}
* denotes the state of the *k*th pair, which runs from0̃0̃ to 1̃1̃, α*
_{i1,}
_{i2,}
_{⋯,}
_{iN,}
_{j}
*'s are some complex coefficients, and the |*j*〉 values form an orthonormal basis for the ancilla. Each state |*u*〉 represents a particular cheating strategy chosen by Eve.*

The goal of a quantum verification scheme is to verify that the string describing the state of the N* pairs is, in fact, all1̃'s. We now construct an efficient quantum verification scheme based on the quantum random-hashing idea by BDSW (*18*). BDSW showed that one can compute the parity of any subset of the 2*N*-bit string by using local operations and classical communication only (*35*). The parity is “collected” into a single destination pair; it is determined by the outcomes of measurements performed on that pair, which has to be discarded afterward. More specifically, the parity is found by noting whether the measurement outcomes on the two members of the destination pair are parallel or antiparallel.*

If Eve prepares a classical mixture of products of Bell states, it is not too difficult to show that classical arguments apply directly to the quantum verification problem and Eve's probability of cheating successfully is negligible [see (36*) for details].*

Why do classical arguments work for a quantum problem?

However, instead of preparing a classical mixture of products of Bell states, in the most general eavesdropping strategy as shown in Eq. 4, Eve prepares a general state, which is entangled with her probe. The big question is Can Eve prepare a more general state to enhance her probability of cheating successfully? The crux of our paper is the following claim: If Eve prepares a general state to cheat in the BDSW random-hashing verification scheme, her probability of cheating successfully will be exactly the same as in the situation when she premeasures that state along the *N*-Bell basis before handing it over to Alice and Bob. In other words, a general state offers no advantage over a mixture of products of Bell states. With this quantum to classical reduction result, (36) applies to any eavesdropping strategy. This proves that Eve's probability of cheating successfully is negligible and our QKD scheme is secure against all possible attacks.

#### Proof of our claim.

Consider the following observables on a state |u*〉 of*N *pairs of qubits shared between Alice and Bob. We define these observables by their actions on the 2*
^{2N} N*-Bell states, which form a complete basis. Let*W*, defined by *W|w〉 = w|w〉*, be the observable that gives the 2*N*-bit string representing the state *w* in BDSW notation. For any index string *s*, let *Q_{s}
*, defined by *Q_{s}|w〉 =*(*s · w*)|w〉, be the observable that gives the parity of the subset *s* of the bits. Finally, let*R* = |1̃1̃⋯1̃〉〈1̃1̃⋯1̃| be the projector onto a state of *N* singlets. All the above operators refer to a single basis (namely, the *N*-Bell basis). Because all the observables (*R, W, *and*Q_{s}
*) are simultaneously diagonalizable with respect to the *N*-Bell basis, *R* and all the*Q_{s}
* values commute with *W*. Therefore, neither the value of *R* nor any of the*Q_{s}
* values are affected by a prior measurement of*W*. In other words, for any state |*u*〉 that Eve might have supplied, neither the sequence of subset parities measured in the verification stage nor the result of the final hypothetical measurement of *R* would have been affected if Eve had premeasured |*u〉 *in Bell basis (that is, made a measurement of *W*) before handing the state to Alice and Bob. Incidentally, the fact that a premeasurement does not change the outcomes of some subsequent measurements is highly reminiscent of work by Griffiths and Niu (*37*).*

Subtleties in our proof.

The following example illustrates the computation of parities and the subtleties involved. Suppose Alice and Bob share three pairs of qubits. With the procedure specified in BDSW, the computation of the parity of the first subset (for example, *s*
_{1} = 001101) can be done by the circuit diagram shown in Fig. 1A. The parity is collected into a single pair and is determined by whether that pair gives a parallel or antiparallel outcome when both members are measured along the *z* axis.

The computation itself, up to phases, performs a permutation on the space of all 2*N*-bit strings. After the computation, the measured pair is dropped from consideration, and only two pairs remain. The computation of the parity of the second subset (for example,*s*
_{2} = 1001) by the BDSW procedure is shown inFig. 1B. After the computation, another pair is measured and dropped from consideration. Therefore, only a single pair of the original three is left after the computation of the two parities (for*s*
_{1} and *s*
_{2}). A simple unitary description (10) of the overall computation is that it maps, up to phases, the state |1̃1̃1̃1̃1̃1̃〉 to |1̃0̃1̃1̃1̃1̃〉. Suppose also that, on passing the verification test, Alice and Bob generate their secret key by measuring the remaining pair along the *z* axis, with an “up” for Alice's result meaning “0” and a “down” meaning “1.”

A number of subtleties deserve careful discussions. First, as in the classical case, the choice of subsets can be announced only after Alice and Bob receive all of their quantum particles. So long as Eve does not know the subsets beforehand, her probability of cheating successfully is exponentially small (see supplementary material, available atwww.sciencemag.org/feature/data/984035.shl).

Second, during the computation of the parities of subsets, the state of the *N* pairs of qubits is transformed by a unitary transformation*U*
_{s1}
_{,s2}
_{,···,sm}, which depends on the subsets *s _{i}
*. But would that unitary transformation

*U*

_{s1}

_{,s2}

_{,···,sm}somehow spoil our reduction argument from a quantum to classical verification? Fortunately, the answer is “no”. Despite the apparent complexity of the parity computation procedure, the bottom-line answer that Alice and Bob obtain is simply the parities (that is, the eigenvalues of the operators

*Q*'s of their choice). Therefore, the verification test proves that, for any general cheating strategy by Eve that passes the test with a probability of at least 2

_{s}^{−r}, the conditional fidelity of the state before the parity computation as

*N*singlets, |1̃1̃⋯1̃〉, is 1 −

*O*(2

^{−(m−r)}). Consequently, the state after the parity computation will, with the same fidelity, be

*U*

_{s1}

_{,s2}

_{,···,sm}|1̃1̃⋯1̃〉.

Third, in our quantum verification procedure, Alice and Bob have to disclose all their measurement outcomes in a public channel. For each measured pair, there are four possible outcomes, ⇅, ⇵, ⇈, and ⇊, thus resulting in two bits of information. This is more than the one-bit (0 or 1) parity information. Now, the question is Can Eve somehow benefit from this additional information? The answer is “no” (this discussion is available atwww.sciencemag.org/feature/data/984035.shl). Finally, the issue of a quantum Trojan horse attack is addressed in (21). This completes our proof of security of QKD.

Discussion.

An important idea behind our quantum to classical reduction is that a quantum mechanical experiment has a classical interpretation whenever observables that refer to only one basis (the *N*-Bell basis in our case) are considered. The fine-grained measurement operators by Alice and Bob along the three random bases do not commute with the Bell-basis projection operators. However, Alice and Bob base their decision on whether to accept the alleged singlets not on those fine-grained measurement results but on the coarse-grained (parallel or antiparallel) ones. Those coarse-grained operators all commute with a complete von Neumann measurement along the Bell basis (38).

Our quantum to classical reduction technique is a powerful tool of widespread applications. It guarantees that one can apply standard results in the classical world (such as probability theory and statistics theory) to the original quantum problem without leading to fallacies. In effect, this means the extension of classical statistical theory to quantum mechanics, resulting in a quantum statistical theory. To illustrate this point, we give two other examples of applications of our quantum to classical reduction result. (i) Suppose two distant observers share *N* pairs of qubits, and estimate the number of singlets in those *N* pairs. By the number of singlets, we mean the expected number of “yes” answers if a singlet or triplet measurement was made on each pair individually. (ii) Under the assumption that signal carriers are perfect single photons, put a probabilistic bound on an eavesdropper's information in BB84 as a function of the error rates of the sampled photons. (These examples are discussed atwww.sciencemag.org/feature/data/984035.shl.)

The second example gives us a quantitative statement on the trade-off between information gain and disturbance (39). This is a strong result to a notoriously difficult problem because (i) the bound applies not merely to a strategy in which Eve couples a probe to each signal particle but to any information extraction strategy that is consistent with quantum mechanics and (ii) the bound can be derived by a random sampling of a small subset. In other words, a concrete experimental random-sampling procedure (rather than an abstract mathematical equation with little physical meaning) is presented here (40).

Finally, let us return to QKD itself. Although we have focused on the case when Alice and Bob receive allegedly good EPR pairs from Eve, our proof of security of QKD also applies to the case when Alice sends qubits (rather than halves of EPR pairs) to Bob. Consider the following situation. Alice prepares *N* EPR pairs in her laboratory. She then chooses the subsets for parity determination beforehand and performs all the computations and measurements on her halves of the*N* EPR pairs in her own laboratory before sending out the other halves to Bob. After Alice's measurements, the subsystem that she sends to Bob is in a pure state; that is, qubits rather than halves of EPR pairs are sent to Bob. However, because Alice's operation is local, it must commute with Eve's eavesdropping operator. Therefore, this qubit-based scheme must be as secure as the original EPR-based scheme. (Just as in the EPR-based case, it is of the utmost importance for Alice to withhold information on the choice of subsets for the parity determination until Bob acknowledges the receipt of quantum transmission. Otherwise, Eve can cheat easily.)

↵* To whom correspondence should be addressed. E-mail: hkl{at}hplb.hpl.hp.com