Security of Quantum Protocols Against Coherent Measurements^{∗}

Andrew Chi-Chih Yao Department of Computer Science

Princeton University Princeton, New Jersey 08544

Abstract

The goal of quantum cryptography is to design cryptographic protocols whose security depends on quantum physics and little else. A serious obstacle to security proofs is the cheaters’ ability to make coherent measurements on the joint properties of large composite states. With the exception of commit protocols, no cryptographic primitives have been proved secure when coherent measurements are allowed. In this paper we develop some mathematical techniques for analyzing probabilistic events in Hilbert spaces, and prove the security of a canonical quantum oblivious transfer protocol against coherent measurements.

1 Introduction

Work on quantum cryptography was started by Wiesner [Wi70] twenty-five years ago. Much knowledge on how to exploit quantum physics for cryptographic purposes has been gained through the work of Bennet and Brassard ([BBBW83][BB84][BBBSS92]), and later Crépeau ([Cr90][BC91][BBCS92][Cr94]). Furthermore, prototypes for implementing some of these algorithms have been built ([BB89][TRT93][TRT94]).

How to design securely the important cryptographic primitive oblivious transfer in quantum cryptography has received much attention in the recent literature [BBCS92][Cr90][Cr94][MS94]. Central to all the proposed protocols is the transmission of a large number of polarized photons from Alice to Bob. At present, the strongest security result [MS94] obtained is that if Bob is allowed to make arbitrary measurements only on individual photons, then neither Alice nor Bob may cheat successfully with more than an exponentially small probability. An interesting open question is whether these oblivious transfer protocols are secure when Bob may store these photons and make coherent measurements, i.e., measuring joint properties of these photons.

Coherent measurements seem to be beyond the current technology ([BBCS92]). However, it is of interest to design secure protocols based solely on quantum physics and not reliant on the limitation imposed by the available technology. It is particularly useful to examine the oblivious transfer primitive in this context, since it forms the basis of many other protocols (see [Ki88]). Previously, only the bit commitment primitive has been shown to have a protocol secure against coherent measurements [BCJL93].

In this paper we prove that the canonical quantum oblivious transfer protocol is secure against coherent measurements. For this extended abstract, we consider only the simplest environment for quantum oblivious tranfer, in which Alice’s n packets of photons each contains exactly one photon, that Bob receives and measures each packet perfectly, and thus Alice’s test accepts the result only when there is perfect agreement between the corresponding bits in positions tested (where Bob’s commited polarizations are the same as Alice’s original ones). The security of the more practical protocols can be proved with modifications similar to those used in [BBCS92], and will be left to the complete paper.

∗This research was supported in part by the National Science Foundation under grant CCR-9301430.

Even for this ideal setting, it is a lengthy task to formulate the oblivious transfer problem precisely and prove a protocol secure. In the next section, we give a general formulation for protocols in the Hilbert space formalism. We then focus our attention on the canonical quantum oblivious transfer protocol, and the associated security problem against a cheating Bob. This way we have a concrete example of the formalism and can present the essence of the general proof without undue notational complications. A sketch of the proof is then given in the last section.

2 Model and Result

A (2-party) quantum protocol is a pair of quantum machines interacting through a quantum channel in some specified way. Initially, each machine is in some mixed quantum state. Formally, consider the direct product H of three Hilbert spaces H_{A}, H_{B}, H_{C}. Alternately between A and B, the party D ∈ {A, B} carries out a measurement on the current mixed state using decompositions controlled in D’s portion of the space (i.e., H_{D} ⊗ H_{C}), which collapses the state according to the result of the measurement; D then carries out a unitary transformation in H_{D} ⊗ H_{C}, which in turn induces a unitary transformation on the space H. The measurements and unitary transformations are designed so that in the end each of A amd B obtains some useful information about their joint initial state.

Although the above description is general enough to incorporate classical computations and transmissions of classical information, it is useful to separate out the classical parts in describing protocols. We also remark that to estimate the resources needed for the protocol one may want to give a less uniform description with H_{A}, H_{B}, H_{C} changing over time. For example, the number of photons used in the second round may be much less than in the first round, and thus can be described by a much smaller H_{C}.

We now specialize to the oblivious transfer problem (first raised by Rabin [Ra81]) whose goal is as follows. Alice has a secret bit β drawn from a certain distribution. At the end of the protocol, either Bob learns the value b (and knows it) or Bob gains no further information about b, with each possibility occurring with probability 1/2; Alice learns nothing about which event takes place.

We consider a canonical quantum oblivious transfer protocol (as in [BBCS92]). Let U = {+, ×}^{n} × {0, 1}^{n}, where +, × stand for the rectlinear and diagonal bases respectively.

Step 1: Alice picks a random uniformly chosen u = (a, g) ∈ U, and sends to Bob photons i, 1 ≤ i ≤ n, with polarizations given by bases a[i] and states g[i].

Step 2: Bob picks a random uniformly chosen b ∈ {+, ×}^{n}, measures photons i in bases b[i] and records the results as h[i] ∈ {0, 1}. (Following [MS94], call this the first measurement.) Bob then makes a quantum commit (as in [BCJL93]) of all n pairs (b[i], h[i]) to Alice.

Step 3: Alice picks a random uniformly chosen subset R ⊆ {1, 2, ⋯, n}, and tests the commitment made by Bob at positions in R. If any i ∈ R reveals a[i] = b[i] and g[i] ≠ h[i], then Alice stops the protocol; otherwise, the test result is accepted.

Step 4: Alice announces the base a. Let T_{0} be the set of all 1 ≤ i ≤ n with a[i] = b[i], and let T_{1} be the set of all 1 ≤ i ≤ n with a[i] ≠ b[i]. Bob chooses I_{0}, I_{1} ⊆ T_{0} − R, T_{1} − R with |I_{0}| = |I_{1}| = 0.24n, and sends {I_{0}, I_{1}} in random order to Alice.

Step 5: Alice picks a random s ∈ {0, 1}, and sends s, β_{s} = β ⊕_{i∈I_{s}} g[i] to Bob. Bob computes β = β_{s} ⊕_{i∈I_{s}} h[i], if I_{s} ⊆ T_{0}; otherwise does nothing.

It is clear that the above protocol can be cast in the general form mentioned at the beginning of this section. It is also intuitively clear that the protocol performs correctly if both parties are honest. The harder part is to prove that the protocol satisfies certain desired security conditions even if either party cheats. As mentioned in the Introduction, we focus on the case when Bob is the cheater. (The protocol is also secure against a cheating Alice; we will discuss that further in the complete paper.)

We first give an informal generic description of Bob’s possible strategies against the basic protocol. After Alice sends the photons in Step 1, Bob performs a first measurement J on the photons by possibly interacting them with another quantum system he has prepared. Depending on the measurement result j = j, he then makes quantum commits (b, h) to Alice.

Alice picks a random R, and tests the commitment made by Bob at positions in R. If the test is passed, Alice announces the base a. Bob then chooses I_{0}, I_{1} and sends them to Alice. Alice sends s, β_{s} to Bob.

Bob performs a second measurement with result k = k. Note that the second measurement is chosen after Bob learns the values of a, R, s and β_{s}. Let X be the random variable corresponding to the state of Bob at the end of the protocol (i.e., j, k, a, R, s, β_{s} when available).

In each step of the way, Bob may choose to behave in any way. For the classical steps, this freedom is formulated in the standard cryptological way. For the quantum steps, it means that Bob is allowed to perform an arbitrary measurement followed by a unitary transformation. It is not difficult to formulate the above description in Hilbert space terms.

We state the security result first, and then start to discuss the problem more precisely in mathematical notation. We prove the following security result for the protocol.

Theorem 1 There exist constants ϵ, δ > 0 such that

Pr { Info(β|X) > e^{−ϵn}} ≤ 1/2 + e^{−δn}, where Info(β|X) is the Shannon information H(β)− H(β|X).

We identify each u ∈ U as a unit vector in C^{N} where N = 2^{n}. Let B be the Hilbert space (i.e., the set of states of the outside quantum system prepared by Bob to help him cheat) that Bob employs to interact with u, with η ∈ B being the the vector (initial quantum state) prepared by Bob. Consider the Hilbert space B ⊗ C^{N}, in which Bob performs the first measurement J on the initial vector η ⊗ u. From now on we use the notation W for η ⊗ C^{N}. For any vector u ∈ C^{N}, we use û to denote η ⊗ u.

Bob then makes a unitary transformation in B ⊗ C^{N} corresponding to sending photons for the quantum commit protocol. Alice takes a measurement in C^{N} in accordance with the commit protocol. (Strictly speaking, we should choose a much large N (such as 2^{n^{2}}) so that there is enough states for the commit protocol. We will not do that here, since we will not have to deal with the commit question in this extended abstract.) After some more classical steps, Bob performs the second measurement K on B⊗C^{N}, this time trying to gather as much information as possible about β.

We have given the mathematical formulation for the description of an arbitrary cheating Bob. To analyze the security question, one needs to define probability for various events. We will discuss them in the next section. In the remainder of the current section, we introduce some useful notation.

Let V ⊆ U be the set of u = (+^{n}, g) with g ∈ {0, 1}^{n}; let V_{d} ⊆ V be the subset of those with number of 1’s in g not greater than d. Note that V = V_{n}. We also may regard V and V_{d} as sets of unit vectors in C^{N}, just as U can be viewed in this fashion.

Consider any finite-dimensional Hilbert space. For any vector v and subspace V, let v_{V} denote the projection of v on V. Let L, M be two subspaces. For any vector w, let χ(w, M, L) =< w, ((w_{M})_{L})_{M} >.

Note that if w ∈ M, then χ(w, M, L) =< w, (w_{L})_{M} >=< w, w_{L} >= ∥w_{L}∥^{2}. In particular, assume that Alice chooses an initial vector u, if L is a subspace corresponding to a result j for Bob’s first measurement, then χ(û, W, L) is equal to the probability for the outcome of the first measurement to be j. The following fact is easy to verify.

Fact 1 Let t_{i}, 1 ≤ i ≤ r be vectors in L forming a complete POV, i.e., ∑_{1≤i≤r} |t_{i} >< t_{i}| = 1 in L. Then

χ(w, M, L) = ∑_{i} | < w, (t_{i})_{M} > |^{2}.

We now introduce some concepts to quantify how much information can be obtained by Bob. Let ℓ_{1} ≤ ℓ_{2} ≤ m be integers. For any F ⊆ {1, 2, ⋯, m} and y = y_{1}y_{2} ⋯ y_{m} ∈ {0, 1}^{m}, the F -parity of y is ⊕_{i∈F} y_{i}. Let Y_{F} be the set of y with F -parity equal to 0. For any probability distribution τ on {0, 1}^{m}, let p(τ, F) = ∑_{y∈Y_{F}} τ(y) and p(τ, ℓ_{1}, ℓ_{2}) be the value of p(τ, F) maximizing the difference |p(τ, F) − 1/2| over all ℓ_{1} ≤ |F | ≤ ℓ_{2}. In other words, p(τ, ℓ_{1}, ℓ_{2}) is the best you can do if you want to choose an F with size between ℓ_{1} and ℓ_{2}, and try to predict accurately the F -parity of a random y distributed according to τ.

3 Proof of the Theorem

Because of the form of Theorem 1, we can assume without loss of generality that the second measurement is taken independent of the two bits s, β_{s}. Let j be any possible result of the first measurement. We further assume that Bob makes an honest commitment (b, h) in Step 2, in the sense that Bob has some specific bits in mind and carry out the quantum commit [BCJL93] dutifully. (It takes extra work to remove these assumptions, which will be given in the complete paper.)

To establish Theorem 1, we give Bob free additional information just before Bob attempts the second measurement K (if Alice has accepted the test result). We supply to Bob the values of g[i] for all positions i with a[i] = b[i]. Recall T_{0} = {i|a[i] = b[i]}, and T_{1} = {i|a[i] ≠ b[i]}. Let g_{0} = (g[i]|i ∈ T_{0}) and g_{1} = (g[i]|i ∈ T_{1}).

Before choosing and performing the second measurement K, Bob has full information about S = (a, R, g_{0}). Let ρ_{j,S,k} denote the probability distribution of g_{1} when the measurement yields result k. Let ϵ = δ = 10^{−6}. Let Y be the event that Alice’s test is passed. Let Z denote the event that |p(ρ_{j,S,k}, 0.12n, 0.24n) − 1/2| > e^{−ϵn}.

We will prove that

Pr{Y ∧ Z | j = j} < O(e^{−δn/64}).  (1)

This immediately leads to Theorem 1, since at least one of I_{0}, I_{1} must have an intersection with T_{1}(a) of size between 0.12n and 0.24n, and Alice may choose that I_{s}. (This is the same argument as was used in [MS94] when only individual measurements are allowed by Bob.)

From now on we consider j to be fixed. Without loss of generality, assume that b = +^{n} and h = 0^{n}. We also suppress j in some notations; for example, ρ_{j,S,k} will be written as ρ_{S,k}. Let L ⊆ B ⊗ C^{N} be the subspace corresponding to J = j. For any a ∈ {+, ×}^{n}, let T_{0}(a) = {i|a[i] = +} and T_{1}(a) = {i|a[i] = ×}.

Let S be the set of S = (a, R, g_{0}) satisfying |T_{s}(a)− 0.5n| ≤ 0.01n and 0.24n ≤ |T_{s}(a) − R| ≤ 0.26n for s ∈ {0, 1}. The following fact is useful.

Fact 2 ∑_{S∉S} Pr{S = S|j = j} ≤ 3e^{−δn}.

Proof After the first measurement with result j = j, the system is up to a normalization factor in the mixed state ∑_{u∈U} |û_{L} >< û_{L}|. We will show that for this mixed state, the probability of |T_{s}(a) − 0.5n| ≥ 0.01n for some s ∈ {0, 1} is less than e^{−δn}.

This clearly implies Fact 2, since for any given s and a, T_{s}(a) − R is statistically a uniform random subset of T_{s}(a); and for 0.49n ≤ |T_{s}(a)| ≤ 0.51n, the probability for |T_{s}(a) − R| to be outside the range of 0.24n to 0.26n is less than e^{−δn}.

Let v be any unit vector in L. Consider the mixed state (up to a normalization factor)

∑_{u∈U} |(û)_{v} >< (û)_{v}|.  (2)

It suffices to show that, for this mixed state, the probability of |T_{1}(a) − 0.5n| ≥ 0.01n is less than e^{−δn}. (The s = 0 case is implied by this result, since |T_{0}(a)| = n − |T_{1}(a)|.)

By the definition of projection, one can write v_{W} as η ⊗ ∑_{α∈V} λ_{α}α. Let U_{m} ⊆ U be the set of (a, g) with |T_{1}(a)| = m. Then the probability of |T_{1}(a)| = m is proportional to

∑_{u∈U_{m}} | < û, v > |^{2}

= ∑_{u∈U_{m}} | < u, ∑_{α∈V} λ_{α}α > |^{2}

= ∑_{α,β∈V} ∑_{u∈U_{m}} λ_{α}λ_{β}^{∗} < u, α >< β, u > .

A calculation shows that ∑_{u∈U_{m}} < u, α >< β, u > is equal to 0 if α ≠ β and \binom{n}{m}2^{m}(2^{−m/2})^{2} = \binom{n}{m} if α = β. It follows that the probability of |T_{1}(a)| = m is exactly \binom{n}{m}/2^{n} for the mixed state (2), and hence the probability of |T_{1}(a) − 0.5n| ≥ 0.01n is less than e^{−δn}. This proves Fact 2. □

To prove (1), we first consider a special case. Let ϵ′ = 1/40. Assume that L has the following low weight property: the projection of every vector v ∈ L on W is of the form û where u is a linear combination of vectors in V_{ϵ′n}. Lemma 1 For any S ∈ S and any k,

Pr{Z | j = j, S = S, k = k} = 0.

Proof Let S = (a, R, g_{0}^{(0)}). Let m = |T_{1}(a)| ≥ 0.49n. Let v = t_{k} ∈ L be the vector corresponding to the measurement result k = k. By assumption, one can write v_{W} as η ⊗ ∑_{α∈V_{ϵ′n}} λ_{α}α.

We are interested in the probability distribution of the string g_{1} = (g_{1}[i]|i ∈ T_{1}(a)) ∈ {0, 1}^{m}. For each x ∈ {0, 1}^{m}, let u_{x} = (a, g) where g_{0} = g_{0}^{(0)} and g_{1} = x.

Let γ = ∑_{y} | < û_{y}, v > |^{2}. Then

ρ_{S,k}(x) = | < û_{x}, v > |^{2}/γ.

Consider any F ⊆ T_{1}(a) with 0.12n ≤ |F | ≤ 0.24n. We have

γ ∑_{x∈Y_{F}} ρ_{S,k}(x)

= ∑_{x∈Y_{F}} | < û_{x}, v > |^{2}

= ∑_{x∈Y_{F}} | < û_{x}, v_{W} > |^{2}

= ∑_{x∈Y_{F}} ∑_{α,β∈V_{ϵ′n}} λ_{α}λ_{β}^{∗} < u_{x}, α >< β, u_{x} >

= ∑_{α,β∈V_{ϵ′n}} λ_{α}λ_{β}^{∗} ∑_{x∈Y_{F}} < u_{x}, α >< β, u_{x} > .

Let V′ be the set of all α = (+^{n}, g) ∈ V_{ϵ′n} with g[i] = g_{0}^{(0)}[i] for all i ∈ T_{0}[a]. Let α = (+^{n}, g_{α}), β = (+^{n}, g_{β}) ∈ V′. For any x, let σ_{x} be the number of positions i ∈ T_{1}(a) satisfying g_{α}[i] ≠ g_{β}[i] and g[i] = 1 (where u_{x} = (a, g)). Then < u_{x}, α >< β, u_{x} >= (−1)^{σ_{x}}2^{−m}. In particular, | < u_{x}, α > |^{2} = 2^{−m}. If α ≠ β, there must be an equal number of x ∈ Y_{F} with even and odd σ_{x}, as the Hamming distance between α and β is ≤ 2ϵ′n < |F |. This implies ∑_{x∈Y_{F}} < u_{x}, α >< β, u_{x} >= 0.

For all other α, β ∈ V_{ϵ′n}, it is easy to see that < u_{x}, α >< β, u_{x} >= 0 for all x. Thus, ∑_{x∈Y_{F}} < u_{x}, α >< β, u_{x} >= 0 for all α ≠ β. This leads to

γ ∑_{x∈Y_{F}} ρ_{S,k}(x)

= ∑_{α∈V_{ϵ′n}} ∑_{x∈Y_{F}} |λ_{α}|^{2}| < u_{x}, α > |^{2}

+ ∑_{α,β∈V_{ϵ′n}} λ_{α}λ_{β}^{∗} ∑_{x∈Y_{F}} < u_{x}, α >< β, u_{x} >

= 2^{−m}|Y_{F} | ∑_{α∈V′} |λ_{α}|^{2}

= (1/2) ∑_{α∈V′} |λ_{α}|^{2}.

A similar calculation (summing x over all m-bit strings) shows that γ = ∑_{α∈V′} |λ_{α}|^{2}. This shows that ∑_{x∈Y_{F}} ρ_{S,k}(x) = 1/2. This proves Lemma 1. □

It follows from Fact 2 and Lemma 1 that

Pr{Y ∧ Z | j = j}

≤ ∑_{S∉S} Pr{S = S|j = j} +

∑_{S∈S} ∑_{k} Pr{S = S, k = k|j = j}

× Pr{Z | j = j, S = S, k = k}

≤ 3e^{−δn}.

This proves (1) for the Special Case. We now turn to the general case. Our plan is show that we can approximate the quantity | < û_{x}, v > |^{2} = | < û_{x}, (t_{k})_{W} > |^{2} by | < û_{x}, (t_{k})_{W_{1}} > |^{2} sufficiently accurately that we can carry out the calculations in the proof of Lemma 1 for the general case.

Let W_{1} ⊆ W be the subspace spanned by η ⊗ v where v ∈ V_{ϵ′n}; let W_{2} ⊆ W be the subspace spanned by η ⊗ v where v ∈ V_{n} − V_{ϵ′n}.

Recall that, for any u ∈ U, χ(û, W, L) is equal to the probability of j = j when Alice initially prepares the photons in state u. Thus, for any D ⊆ U, \frac{1}{|D|} ∑_{u∈D} χ(û, W, L) is the probability of j = j, given that initially u is randomly chosen from D.

For each S = (a, R, g_{0}), let Γ_{S} ⊆ U be the set of u = (a, g) consistent with S. Let ξ_{S} be the probability that Alice accepts the test result, given that S is the current state with j being the result of the first measurement. (In the present situation, ξ_{S} is either 0 or 1.)

Definition Let T be the set of S satisfying

ξ_{S} ∑_{u∈Γ_{S}} χ(û, W_{2}, L) ≤ e^{−δn/4} ∑_{u∈Γ_{S}} χ(û, W, L).

For any S = (a, R, g_{0}), consider the second measurement t_{1}, t_{2}, ⋯, t_{ℓ} (with ∑_{k} |t_{k} >< t_{k}| = 1 on L) chosen by Bob.

Definition Let K_{0}(S) denote the set of the measurement results k such that

ξ_{S} ∑_{u∈Γ_{S}} | < û, (t_{k})_{W_{2}} > |^{2}

≤ e^{−δn/8} ∑_{u∈Γ_{S}} | < û, (t_{k})_{W} > |^{2}.

Let T′ = T ∩ S. There are two phenomena we like to demonstrate. First, take a random execution of the protocol, we show that we get an S ∈ T′ and k ∈ K_{0}(S) with probability 1 − O(e^{−δn/8}); this is (essentially) done in the next two lemmas. Second, S ∈ T′ and k ∈ K_{0}(S) implies that we can replace W by W_{1} when we do certain calculations involving a random u from Γ_{S}.

Lemma 2 states that, conditioned on j = j, the probability for S ∉ T is less than e^{−δn/4}. The 2^{n} factor on the left-hand side comes from the fact that S is defined as (a, g_{0}, R), and thus each u has 2^{n} S with u ∈ Γ_{S}. Lemma 2

\frac{1}{2^{n}} \frac{1}{|U|} ∑_{S∉T} ∑_{u∈Γ_{S}} χ(û, W, L)

≤ e^{−δn/4} \frac{1}{|U|} ∑_{u∈U} χ(û, W, L).

Proof We delay the proof to the end of this section. □ Lemma 3 If S ∈ T , then

∑_{k∉K_{0}(S)} ∑_{u∈Γ_{S}} | < û, (t_{k})_{W} > |^{2}

≤ e^{−δn/8} ∑_{u∈Γ_{S}} χ(u, W, L).

Proof Otherwise, we have from the definition of K_{0}(S),

ξ_{S} ∑_{k∉K_{0}(S)} ∑_{u∈Γ_{S}} | < û, (t_{k})_{W_{2}} > |^{2}

> ∑_{k∉K_{0}(S)} ∑_{u∈Γ_{S}} e^{−δn/8}| < û, (t_{k})_{W} > |^{2}

> e^{−δn/8}e^{−δn/8} ∑_{u∈Γ_{S}} χ(u, W, L),

contradicting the assumption S ∈ T . This proves Lemma 3. □

Now for the second step. Let S ∈ T′ and k ∈ K_{0}(S). We show that either ξ_{S} ≤ e^{−δn/16} or

Pr{Z | j = j, S = S, k = k} < O(e^{−δn/64}). (3)

(We do not take advantage of the fact ξ_{S} being either 0 or 1, to keep the discussion more general than needed for the present case.)

Equation (3) is the analog of Lemma 1 for the general case. As in the special case discussed at the start of this section, (3) and the discussions preceding it imply immediately (1) and hence Theorem 1.

If ξ_{S} ≤ e^{−δn/16}, then we are done. Assume ξ_{S} > e^{−δn/16}. Since k ∈ K_{0}(S), we have

ξ_{S} ∑_{u∈Γ_{S}} | < û, (t_{k})_{W_{2}} > |^{2}

≤ e^{−δn/8} ∑_{u∈Γ_{S}} | < û, (t_{k})_{W} > |^{2}.

As ξ_{S} > e^{−δn/16}, we have

∑_{u∈Γ_{S}} | < û, (t_{k})_{W_{2}} > |^{2}

< e^{−δn/16} ∑_{u∈Γ_{S}} | < û, (t_{k})_{W} > |^{2}. (4)

Let Γ′_{S} be the set of u ∈ Γ_{S} satisfying

| < û, (t_{k})_{W_{2}} > |^{2} ≤ e^{−δn/32}| < û, (t_{k})_{W} > |^{2}.

Then

∑_{u∈Γ_{S}−Γ′_{S}} | < û, (t_{k})_{W} > |^{2}

≤ e^{−δn/32} ∑_{u∈Γ_{S}} | < û, (t_{k})_{W} > |^{2};

since otherwise, we have

∑_{u∈Γ_{S}−Γ′_{S}} | < û, (t_{k})_{W_{2}} > |^{2}

> e^{−δn/32} ∑_{u∈Γ_{S}−Γ′_{S}} | < û, (t_{k})_{W} > |^{2}

> e^{−δn/32}e^{−δn/32} ∑_{u∈Γ_{S}} | < û, (t_{k})_{W} > |^{2},

contradicting (4). This means that, taking a random u chosen according to ρ_{S,k}, the probability of u ∈ Γ′_{S} being true is greater than 1 − e^{−δn/32}.

Take any u ∈ Γ′_{S}. Then

| < û, (t_{k})_{W_{2}} > | ≤ e^{−δn/64}| < û, (t_{k})_{W} > |.

Hence

| < û, (t_{k})_{W_{1}} > | = | < û, (t_{k})_{W} > − < û, (t_{k})_{W_{2}} > | ≥ | < û, (t_{k})_{W} > | − | < û, (t_{k})_{W_{2}} > | ≥ (1 − e^{−δn/64})| < û, (t_{k})_{W} > |.

Thus,

| < û, (t_{k})_{W_{1}} > |^{2}
≤ | < û, (t_{k})_{W} > |^{2}
≤ (1 + O(e^{−δn/64}))| < û, (t_{k})_{W_{1}} > |^{2}.

To summarize, we have shown that for a typical S that passes Alice’ test, the information (about the initial vector u) available to Bob after the second measurement is almost identical to that in the special case discussed earlier. The arguments used in the proof of Lemma 1 can then be used to prove (3).

To complete the proof of Theorem 1, it remains to prove Lemma 2, to which we now turn our attention.

Let ξ_{u} be the probability that Alice accepts the test, conditioned on u being the initial vector and the first measurement yielding result j. Note that ξ_{u} = 2^{−n} ∑_{S,u∈Γ_{S}} ξ_{S}.

Fact 3 Let α, β ∈ V_{n}. If α ≠ β, then ∑_{u∈U} ξ_{u} < u, α >< β, u >= 0.

Proof It can be verified by a simple calculation. □

Fact 4 Let α ∈ V_{n} − V_{ϵ′n}. Then ∑_{u∈U} ξ_{u}| < u, α > |^{2} < 2^{(1−δ)n}.

Proof Let ℓ be the number of 1’s in α; by definition, ℓ > ϵ′n. For any a ∈ {+, ×}^{n}, let #a denote the number of i with a[i] = + and α[i] = 1. Divide U into U_{1} ∪ U_{2}, where U_{1} is the set of u = (a, g) with #a ≥ ℓ/4, and U_{2} is the set of those u with #a < ℓ/4.

Let u = (a, g) ∈ U. Then | < u, α > |^{2} = 0 unless g[i] = α[i] whenever a[i] = +, and in this latter case | < u, α > |^{2} = 2^{−(n−r_{a})} where r_{a} is the number of +’s in a. It follows that

∑_{u∈U_{2}} | < u, α > |^{2}

≤ ∑_{0≤m<ℓ/4} ∑_{0≤m′≤n−ℓ} \binom{ℓ}{m}\binom{n − ℓ}{m′}

×2^{n−(m+m′)}2^{−(n−(m+m′))}

≤ 2^{(1−δ)n}/2.

Now, note that any u ∈ U_{1} must satisfy ξ_{u} ≤ 2^{−δn}/2.

We have thus

∑_{u∈U} ξ_{u}| < u, α > |^{2}

≤ ∑_{u∈U_{2}} | < u, α > |^{2} + ∑_{u∈U_{1}} ξ_{u}| < u, α > |^{2}

< 2^{(1−δ)n} + (2^{−δn}/2) ∑_{u∈U_{1}} | < u, α > |^{2}

≤ 2^{(1−δ)n}.

This proves Fact 4. □ Fact 5

∑_{u∈U} ξ_{u}χ(û, W_{2}, L) ≤ e^{−δn/2} ∑_{u∈U} χ(û, W, L),

Proof Choose any orthonormal base t_{1}, t_{2}, ⋯, t_{ℓ} for L. By Fact 1, we have

∑_{u∈U} ξ_{u}χ(û, W_{2}, L)

= ∑_{u∈U} ξ_{u} ∑_{i} | < û, (t_{i})_{W_{2}} > |^{2}

= ∑_{i} ∑_{u∈U} ξ_{u}| < û, (t_{i})_{W_{2}} > |^{2}. (5)

We will prove that for each i

∑_{u∈U} ξ_{u}| < û, (t_{i})_{W_{2}} > |^{2}

≤ e^{−δn/2} ∑_{u∈U} | < û, (t_{i})_{W} > |^{2}. (6)

Clearly, (5), (6) and Fact 1 imply

∑_{u∈U} ξ_{u}χ(û, W_{2}, L)

≤ e^{−δn/2} ∑_{u∈U} ∑_{i} | < û, (t_{i})_{W} > |^{2}

= e^{−δn/2} ∑_{u∈U} χ(û, W, L).

To prove (6), assume that (t_{i})_{W} = η ⊗∑_{α∈V_{n}} λ_{α}α. Then (t_{i})_{W_{2}} = η ⊗ ∑_{α∈V_{n}−V_{ϵ′n}} λ_{α}α. Thus,

∑_{u∈U} ξ_{u}| < û, (t_{i})_{W_{2}} > |^{2}

= ∑_{u∈U} ξ_{u}| < u, ∑_{α∈V_{n}−V_{ϵ′n}} λ_{α}α > |^{2}

= ∑_{u∈U} ∑_{α,β∈V_{n}−V_{ϵ′n}} ξ_{u}λ_{α}λ_{β}^{∗} < u, α >< β, u >

= ∑_{α,β∈V_{n}−V_{ϵ′n}} λ_{α}λ_{β}^{∗} ∑_{u∈U} ξ_{u} < u, α >< β, u > .

Using Facts 3, 4, we then have

∑_{u∈U} ξ_{u}| < û, (t_{i})_{W_{2}} > |^{2}

= ∑_{α∈V_{n}−V_{ϵ′n}} |λ_{α}|^{2} ∑_{u∈U} ξ_{u}| < û, α > |^{2}

≤ 2^{(1−δ)n} ∑_{α∈V_{n}−V_{ϵ′n}} |λ_{α}|^{2}.  (7)

Similarly, we have

∑_{u∈U} | < û, (t_{i})_{W} > |^{2}

= ∑_{α,β∈V_{n}} λ_{α}λ_{β}^{∗} ∑_{u∈U} < u, α >< β, u >

= ∑_{α∈V_{n}} |λ_{α}|^{2}2^{n}

≥ 2^{n} ∑_{α∈V_{n}−V_{ϵ′n}} |λ_{α}|^{2}.  (8)

Clearly, (7) and (8) imply (6), and hence Fact 5. □ We now prove Lemma 2. Assume to the contrary,

\frac{1}{2^{n}} ∑_{S∉T} ∑_{u∈Γ_{S}} χ(û, W, L) > e^{−δn/4} ∑_{u∈U} χ(û, W, L).

Then, from the definition of T and the above inequality, we have

\frac{1}{2^{n}} ∑_{all S} ξ_{S} ∑_{u∈Γ_{S}} χ(û, W_{2}, L)

≥ \frac{1}{2^{n}} ∑_{S∉T} ξ_{S} ∑_{u∈Γ_{S}} χ(û, W_{2}, L)

> \frac{1}{2^{n}} e^{−δn/4} ∑_{S∉T} ∑_{u∈Γ_{S}} χ(û, W, L)

> e^{−δn/2} ∑_{u∈U} χ(û, W, L).  (9)

Now

∑_{all S} ξ_{S} ∑_{u∈Γ_{S}} χ(û, W_{2}, L)

= ∑_{u∈U} 2^{n}χ(û, W_{2}, L)\frac{1}{2^{n}} ∑_{S,u∈Γ_{S}} ξ_{S}

= ∑_{u∈U} 2^{n}χ(û, W_{2}, L)ξ_{u},  (10)

From (9) and (10) we have

∑_{u∈U} ξ_{u}χ(û, W_{2}, L) > e^{−δn/2} ∑_{u∈U} χ(û, W, L),

contradicting Fact 5. This proves Lemma 2 and thus Theorem 1.

References

[BB84] C. Bennet and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing,” Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, Bangalore, India, December 1984, 175-179.

[BB89] C. Bennet and G. Brassard, “The dawn of a new era for quantum cryptography: the experimental prototype is working,” SIGACT News, 20 (1989), 78-82.

[BBBSS92] C. Bennet, F. Bessette, G. Brassard, L. Salvail and J. Smolin, “Experimental quantum cryptography,” Journal of Cryptology, 5 (1992), 3-28.

[BBBW83] C. Bennet, G. Brassard, S. Breidbard, and S. Wiesner, “Quantum cryptography, or unforgeable subway tokens,” in Advances in Cryptology: Proceedings of CRYPTO’82, Plenum Press, 1983, 267-275.

[BBCS92] C. Bennet, G. Brassard, C. Crépeau, and M.-H. Skubiszewska, “Practical quantum oblivious transfer,” in Proceedings of CRYPTO’91, Lecture Notes in Computer Science, Volume 576, Springer-Verlag, Berlin, 1992, 351-366.

[BC91] G. Brassard and C. Crépeau, “Quantum bit commitment and coin tossing protocols,” in Advances in Cryptology: Proceedings of CRYPTO’90, Lecture Notes in Computer Science, Volume 537, Springer-Verlag, Berlin, 1991, 49-61.

[BCJL93] G. Brassard, C. Crépeau, R. Jozsa, and D. Langlois, “A quantum bit commitment scheme provably unbreakable by both parties,” Proceedings of 1993 IEEE Annual Symposium on Foundations of Computer Science, November 1993, 362-369.

[Cr90] C. Crépeau, “Correct and private reductions among oblivious transfers,” Ph.D. thesis, Department of EECS, MIT, 1990.

[Cr94] C. Crépeau, “Quantum oblivious transfer,” in Journal of Modern Optics, special issue on quantum cryptography, to appear.

[Ki88] J. Kilian, “Founding cryptography on oblivious transfer,” Proceedings of 1988 ACM Annual Symposium on Theory of Computing, May 1988, 20-31.

[Ma94b] D. Mayers, “Quantum transformation and generalized measurements,” preprint, distributed at Workshop on Quantum Computing and Communication, National Institute of Standards and Technology, Gaithersburg, Maryland, August 18-19, 1994.

[MS94] D. Mayers and L. Salvail, “Quantum oblivious transfer is secure against individual measurements,” preprint, distributed at Workshop on Quantum Computing and Communication, National Institute of Standards and Technology, Gaithersburg, Maryland, August 18-19, 1994.

[Ra81] M. Rabin, “How to exchange secrets by oblivious transfer,” technical report TR-81, Aiken Computation Laboratory, Harvard University, 1981.

[TRT93] P. Townsend, J. Rarity, and P. Tapster, “Single photon interference in a 10km long optical fibre interferometer,” Electronic letters, 29 (1993), 634-635.

[TRT94] P. Townsend, J. Rarity, and P. Tapster, “Enhanced single photon visibility in a 10km long prototype quantum cryptography channel,” Electronic letters, to appear.

[Wi70] S. Wiesner, “Conjugate coding,” SIGACT News 15 (1983), 78-88; manuscript circa 1970.