Quantum Oblivious Transfer is Secure Against Individual Measurements (Preliminary Version)

Dominic Mayers ^{⋆} and Louis Salvail ^{⋆⋆}

Département IRO, Université de Montréal C.P. 6128, succursale “A”,Montréal (Québec), Canada H3C 3J7. e-mail: {mayersd}{salvail}@iro.umontreal.ca.

Abstract. In this paper we show that the BBCS-protocol implementing one of the most important cryptographic primitives oblivious transfer, is secure against any individual measurement allowed by quantum mechanics. We analyze the common situation where successive measurements on the same photon could be used to cheat in the protocol. We model this situation by using a single inner-product-preserving operator (IPP) followed by a complete composite outcome Von Neumann measurement. A lower bound on the residual collision entropy is then obtained under the assumption that only individual measurements can be performed. This bound is used to apply privacy amplification techniques in order to conclude the security of the BBCS-protocol.

1 Introduction

With the advent of quantum cryptography, a practical application of quantum information theory has now appeared. Quantum cryptography, like computational complexity based cryptography, seeks to implement the few main primitives sufficient to build almost all complex cryptographic tasks. Working prototypes for some of these primitives have been built and practical applications are being considered [BBBSS, TRT1, TRT2]. However, the full proof of the security of some of these primitives against any attack allowed by quantum mechanics is still missing and this consitutes an interesting and practical challenge for quantum information theorists and cryptographers.

It is a well-known fact that Oblivious Transfer is a primitive sufficient for the realization of any cryptographic protocol involving two parties [Ki]. Oblivious Tranfer allows one party Alice to send a string β ∈ \{0, 1\}^{l} in such a way that Bob will receive it with probability \frac{1}{2} and will know whether he received it or not. Alice knows nothing about what happened to her string.

The BBCS-protocol [BBCS] implements this primitive in the quantum model. In the first part of this protocol, Alice sends to Bob photons polarized using either the rectilinear or the diagonal basis to encode some bits. A secure realisation of oblivious transfer in the continuation of the protocol relies on the fact that if Bob measures these photons at this point he cannot obtain too much information about the bits because he does not know which of the two basis has been used. However, for the continuation Alice must announce all the bases used to send the photons. The obvious problem with the security of this protocol is that, if Bob does not measure the photons and stores them until he learns the bases, then he can obtain all the information about the bits. In that case the overall protocol becomes totally insecure. We refer to the case where Bob does not measure the photons and store them as the photon-storing attack.

To protect Alice against the photon-storing attack the original BBCS-protocol can be modified slightly ([Cr]). The modification is very simple. Before she announces the bases, Alice simply ask Bob to commit the outcome of his measurement as well as the basis that he used. Next, Alice with probability one half requests Bob to open this commitment. If Bob does not read the photon, he

⋆ Supported by Québec FCAR scholarship. ⋆⋆ Supported by an Nserc scholarship.

will fail Alice’s test with probability one quarter, that is, each time he commits the correct basis, but the wrong bit.

To prove the security of this protocol, one needs to consider how much information can be obtained by Bob about the bits. Usually, quantum information theorists use Shannon entropy to measure the amount of ignorance that remains about a quantum system after a measurement. However, to prove the security of the BBCS-protocol and of other similar protocols, the work of [BBCM] have established that another measure of entropy, the collision entropy, turns out to be more adequate. The collision entropy of a distribution of probability f on a set X is simply given by the formula H_{c}(f) = − log ∑_{x∈X} f(x)^{2}. Their work implies that a necessary condition to obtain the security of the BBCS-protocol is that Bob must have some amount of collision entropy about the bits that he received. Thus far this condition has been obtained given the following assumption

Assumption 1 Every measurement is complete.

Obviously quantum mechanics allows measurements that do not respect this assumption. Assumption 1 means that Bob either executes a complete measurement on the photon before he learns the basis or else executes the photon-storing attack.

If we remove assumption 1, Bob may execute an incomplete measurement, obtain just enough information to pass Alice’s test and then store the residual state until he learns the basis. One can see that whereas it is clear that the new protection is sufficient to ensure the security of the protocol against the ordinary photon-storing attack, this is less obvious if we consider the storage of incompletely measured photons.

The difficulty in analysing this situation lies more at the formal level than at the intuitive level. Intuitively, for a given basis used by Alice, if an outcome of the pre-basis measurement provides a lot of information about the initial state, then in the other basis it significantly “disturbs” this state and does not provide much information. Now, each time Bob commits the same basis than Alice uses, Bob must obtain a lot of information about the bit from the pre-basis measurement. However, Bob does not know which basis is chosen by Alice, therefore, half of the time Bob must disturb the initial state and, in these cases, both the pre-basis and the post-basis measurement do not provide much information. This allows us to obtain the desired lower bound for Bob’s total collision entropy. The most straightforward approach to formalize the above discussion, in particular the concept of disturbance, in the context of the most general attack allowed by quantum mechanics, is to use the model for generalised measurements that is described in [Ma]. Using this model and building on the work of [Cr], [BBCM] and [MC], our contribution is to show that with the protection against photon-storing the protocol is secure under the following assumption:

Assumption 2 Every measurement is performed on individual photons.

The case of coherent measurements (i.e., removing assumption 2), in a context where assumption 1 is removed, remains unsolved and is the missing piece in the full proof of the security of the scheme.

2 The BBCS Oblivious Transfer Protocol

2.1 Preliminaries

In the following, x ∈_{R} X denotes a uniformly distributed random element of X. For a, b ∈ {0, 1}^{n}, a ⊕ b for is the bit by bit exclusive-or of the strings a and b.

We denote by + = (|↔⟩, |↕⟩) respectively and × = (| ↗ ↙ ⟩, | ↘ ↖ ⟩) the bases for the rectilinear (“+”) and diagonal (“×”) polarizations in the quantum space of a photon. The [BB84] coding scheme works as follows:

|0⟩_{θ} = \{ \begin{matrix}↔ & if θ = + \\ ↗ ↙ & if θ = × \end{matrix}

and similarily

|1⟩_{θ} = \{ \begin{matrix}↕ & if θ = + \\ ↘ ↖ & if θ = ×. \end{matrix}

For our purpose, an n-bit commitment is a black box primitive defined by

Definition 1. An n-bit commitment allows the committer Bob to commit to the value of a n-bit string in a way that prevents the receiver Alice from learning it without his help. In addition, Bob cannot change the values of these bits without being detected by Alice.

This primitive can be implemented securely in the quantum model against any measurements allowed by quantum mechanics [BCJL]. Thus we can use n-bit commitment as a “black box” exactly matching the properties given in definition 1. We use the particular case of 2-bit commitment and we denote such a commitment by c = (x, y) for x, y ∈ {0, 1}.

2.2 The BBCS-protocol

In this section, we sketch the version of the BBCS-protocol which includes the protection against incomplete measurements. The first part uses the quantum channel. The second part is the additionnal protection (it may also require the quantum channel if quantum commitments are used). The third part consists of a classical exchange of information using a public channel. The three are executed sequentially one after the other.

The Quantum Part. First, Alice sends 4n photons encoding 4n bits using the [BB84] encoding rules. For all i ∈ {1, …, 4n}, let |b_{i}⟩_{θ_{i}} be the quantum state that is sent to represent the bit b_{i} in the basis θ_{i}. Bob then chooses a random basis θ̂_{i}, measures the quantum state |b_{i}⟩_{θ_{i}} for all

i ∈ {1, …, 4n} and obtains |b̂_{i}⟩_{θ_{i}}.

The protection. The idea is very simple and consists of requiring for Bob to produce, for each photon π_{i} sent by Alice, a commitment c_{i} = (θ̂_{i}, b̂_{i}) containing the basis θ̂_{i} and the corresponding bit b̂_{i} resulting from that measurement. Independantly for each of these positions i, Alice flips a coins, if a head is obtained then she asks Bob to open c_{i}. In that case she verifies that

θ̂_{i} = θ_{i} ⇒ b̂_{i} = b_{i}.  (1)

Finally, Alice verifies that relation 1 has not been violated more than a fraction δ of the time. The value δ is a security parameter slightly above the maximum error rate a particular implementation of the protocol can support. If the verification is succesful, then Alice announces all the θ_{i}’s and the classical part of the BBCS-protocol is executed with the N bits b_{i} for which c_{i} has not been opened. Since the commitments are perfectly secure, Alice has no clue whether of I_{s} or I_{1−s} is I_{0}.

The Classical Part. The θ_{i} allow Bob to recognize which positions i are measured in the correct basis (i.e. θ̂_{i} = θ_{i}) and which bits b̂_{i} match b_{i} with probability at least 1 − δ where δ is an upper bound for the error rate of the quantum channel. Using this information Bob can determine two sets I_{0} = {i|θ_{i} = θ̂_{i}} and I_{1} = {i|θ_{i} ≠ θ̂_{i}} from which some arbitrary elements can be added or removed in order to get #I_{0} = #I_{1} = ⌊\frac{N}{2} ⌋ = m. Now, Bob discloses to Alice the sets I_{s} and I_{1−s} for a random bit s that he keeps secret. Alice chooses s′ ∈ {0, 1} at random and publicly announces s′ together with C(b^{(s′)}), where C : {0, 1}^{m} → {0, 1}^{c} is an error-correcting code that allows Bob to correct the transmission errors in I_{s′} for an error-rate up to δ. For every x ∈ {0, 1}^{m}, the value C(x) consists of extra bits that are always sent separately by an error-free channel such as a telephone. The code C is chosen such that if s ≠ s′, then Bob’s uncertainty about the value of b^{(s′)} = {b_{i}|i ∈ I_{s′}} given C(b^{(s′)}) remains high. At this point, if s′ = s then Bob shares the string b^{(s′)} with Alice otherwise he knows little about b^{(s′)}. Adopting privacy amplification techniques [BBR, BBCM], Alice chooses at random from a universal_{2} class of hashing functions [CW] a function h : {0, 1}^{m} → {0, 1}^{l}, where l < n. Then she chooses γ ∈ {0, 1}^{l} such that h(b^{(s′)}) ⊕ γ = β is the string to be transmitted by oblivious transfer and announces both h and γ. Privacy amplification guarantees that, if s ≠ s′ then knowing h, b̂^{(s′)} and a string γ is not sufficient to learn more than a negligeable amount of Shannon information about h(b^{(s′)}) ⊕ γ = β.

3 Known results

To obtain the security of the BBCS-protocol we must consider the possibility of a dishonest Alice and a dishonest Bob separately.

Given the perfect bit commitment scheme [BCJL], Alice has no clue on which I_{s} or I_{1−s} is the set of reliable photons. Thus, she has no way to cheat the protocol i.e. she does not know whether β is received or not.

The security against Bob’s possible behaviour can be obtained by privacy amplification technique. This tool is used in the classical part and requires that after the quantum part Bob has a significant amount of collision entropy about the N bits.

Definition 2. The collision entropy of a distribution of probability f on a set X is

H_{c}(f) = − log P_{c}(f)

where P_{c}(f) is the collision probability defined by

P_{c}(f) = ∑_{x∈X} f(x)^{2}.

In the case, where f is a distribution of Bernoulli, we write H_{c}(f) = H_{c}(p), where p is the probability of sucess.

Let f be the distribution of probability that corresponds to Bob’s knowledge about b^{(s)}, b^{(1−s)} after the measurements. The main theorem of [BBCM] stipulates that if H_{c}(f) ≥ 2t then for h : {0, 1}^{N} → {0, 1}^{t−r}(and t > r) chosen at random from a universal_{2} class of hashing functions [CW], Bob has no more than 2^{−r}/ ln 2 bits of Shannon information except with negligible probability on one of h(b^{(s)}) or h(b^{(1−s)}). Furthermore, Alice has probability exactly \frac{1}{2} of choosing that one and in that case Bob learns almost nothing about β ∈ {0, 1}^{t−r} (except with negligible probability).

If the quantum channel is a noisy channel, then the code C gives extra knowledge about b^{(s)}, b^{(1−s)}. The functions h must remove this information in addition to the information that is obtained by Bob’s measurements. Recent work ([MC]) has determined the extra “shrinking” parameter needed to remove this information as well. If the code C gives c bits of information in order to correct an error-rate δ and if H_{c}(f) ≥ 2t then a universal_{2} class of hashing functions h : {0, 1}^{N} → {0, 1}^{t−r−2c} removes almost all information about one of b^{(s)} or b^{(1−s)} except with negligeable probability. As a consequence, Crépeau’s proof can be extended to the case where the quantum channel is noisy.

In section 4 we show that,under the assumption 2, for almost all execution of the BBCS-protocol protected against photon-storing, there exists t′ > 0 (where t′ is function of δ) such that, for every value of n, Bob’s collision entropy on the N bits is larger than 2t′n excepted with a negligeable probability. Therefore, in the above results, we may replace t by t′n and r by r′n, where r′ < t′.

4 A lower bound for Bob’s total collision entropy

In this section, we prove the following theorem.

Theorem 3. Let f be the distribution of probability that corresponds to Bob’s knowledge, about the bits b_{i}, where open_{i} = 0, after step 5 of the protocol Game(δ, n). Given that the measurements act on individual photons, if Bob has not been rejected at step 4, then excepted with a probability smaller than 2^{−αn}, where α > 0, Bob’s total collision entropy H_{c}(f) is bounded below by 2t′n, where 2t′ = p_{H}H_{c}(p_{I})(4 − \frac{δ}{p_{F}} ), in which p_{F} = \frac{1}{9}(1 − \frac{\sqrt{3}}{2}), p_{H} = \frac{1}{36} and p_{I} = \frac{1}{4}.

Regarding notation, we use the general rule that every random value that is represented by a lowercase letter in the protocol, corresponds to a random variable which we denote by the matching uppercase letter. For example, the bits b_{i} and the basis θ_{i} for the ith photon, become respectively the random variables B_{i} and Θ_{i}.

4.1 Bob’s strategies

The following protocol describes the most general Bob’s strategy. In this protocol, Bob is entirely free of using any useful knowledge that he learned prior to the current instruction.

SubProtocol 4.1 ( Game(δ, n) )

1: Alice sets fail ← 0, N ← 0

2: DO_{i=1}^{4n}

– Alice picks b_{i} ∈_{R} {0, 1} and θ_{i} ∈_{R} {+, ×}

– Alice sends to Bob a photon π_{i} in the quantum state |b_{i}⟩_{θ_{i}}

– Bob chooses a measurement M_{i}, measures π_{i} in order to obtain θ̂_{i} ∈ {+, ×} and b̂_{i} ∈ {0, 1} – Bob sends the 2-bit commitment c_{i} for (b̂_{i}, θ̂_{i}) to Alice

3: DO_{i=1}^{4n}

– Alice picks open_{i} ∈_{R} {0, 1}, if open_{i} = 1 then she asks Bob to unveil the commitment c_{i}

– If open_{i} = 0 then Alice and Bob set N ← N + 1

– Else if c_{i} = (θ_{i}, 1 − b_{i}) then Alice sets fail ← fail + 1 4: If fail ≤ δn then Alice announces her choices θ_{1}, θ_{2}, …, θ_{4n} to Bob otherwise she refuses to continue 5: DO_{i=1}^{4n} Bob chooses M′_{i} to refine the measurement on π_{i} and obtains the result j_{i}.

In this subsection, without loss of generality, we discard from the analysis measurements that results from strategies that are useless to Bob and discuss the connection between the useful measurements (i.e., the undiscarded measurements), their classical outcomes and variables such as θ̂_{i}, b̂_{i} that are used in the protocol.

In the protocol Game(δ, n), Bob executes two measurements on each photon: the pre-basis measurement M_{i} and the post-basis measurement M′_{i}. However, the effect of these two measurements on the ith photon as well as their classical outcomes can be seen as coming from a single measurement, which we call the ith measurement. We must keep in mind that, in accordance with Bob’s strategy, this measurement is a random variable that depends upon other random variables, including the basis Θ_{i}.

It is shown in [Ma] that any possible choice of Bob for the ith measurement can be represented by a single IP P transformation from the initial space of states to a larger space of states followed by an ordinary von Neumann measurement on the latter. Let U_{i} be the IPP transformation that is associated with the ith measurement. We may assume that this measurement is complete because it is not advantageous for Bob to leave any residual information out in the final state of the photon. Therefore, this measurement can be represented by an orthonormal basis in the final space of states for the transformation U_{i}. The vectors in this basis are denoted |r_{i}⟩, where r_{i} represents the outcome of the ith measurement; it includes both, the classical outcome of the pre-basis measurement and the classical outcome of the post-basis measurement.

Using the pre-basis measurement outcome (that is included in r_{i}), Bob determines a pair c_{i} = (θ̂_{i}, b̂_{i}) = f(r_{i}) that he commits to Alice. Bob has no advantage in using a randomized function f, because he wants to obtain c_{i} that minimize the possibility that fail increases (the outcome r_{i} is random, but not f). Also, because Bob wants to make the most incomplete pre-basis measurement as possible, it is best for him to make a pre-basis measurement in which there is not more than one outcome for each non zero probability value of C_{i}, i.e., f is injective. Taking advantage of this, we identify the outcome r_{i} of the ith measurement with the triplet (j_{i}, θ̂_{i}, b̂_{i}), where j_{i} is the post-measurement outcome and (θ̂_{i}, b̂_{i}) is the pair c_{i} that is committed, which pair may now be considered as the pre-basis measurement outcome.

Now, let us consider the dependencies or independencies that exists among the variables of the protocol. Because it includes the post-basis measurement, the ith measurement may depend upon the basis Θ_{i} that is announced by Alice, however, the outcome C_{i} of the pre-basis measurement is independent of the basis Θ_{i}, because the density matrices associated with the two values of Θ_{i} are identical. After the pre-basis measurement, since Bob has already commited the pair c_{i}, he has no way to reduce its chance of being caught and, therefore, having the post-basis measurement depends upon previous outcomes is totally useless. From this one obtains that the distribution on the quadruplets (Θ_{i}, B_{i}, Open_{i}, J_{i}),i = 1, …, 4n, given fixed values for C_{1}, …, C_{4n} is a distribution of independent quadruplets. In other words, once we have fixed the values of C_{1}, …, C_{4n}, the measurements are fixed and, in that case, variables that are associated with distinct measurements become completely independents.

4.2 The main idea

This subsection analyses the mecanism that is used in the protocol to guaranty that Bob’s total collision entropy H_{c} is bounded. This analysis is developped in a context, where Bob has made all of his 4n commitments and he is waiting for Alice to ask the openning of about half of the commitments. Therefore, we fix the sequence of pairs c_{i} = (θ̂_{i}, b̂_{i}), i = 1, …, 4n, that are commited.

With regard to this analysis, the most important aspect of the protocol is that if Bob is not rejected then the variable fail must be smaller than δn and therefore whenever Bob has committed to the correct basis (θ̂_{i} = θ_{i}). he must have committed to the correct bit (b̂_{i} = b_{i}). This means that, whenever Bob is not rejected, he has a lot of information about most bits b_{i}, where θ_{i} = θ̂_{i}. Therefore, most contributions to Bob’s total collision entropy H_{c} must occur when θ_{i} ≠ θ̂_{i}. Furthermore, even if θ_{i} ≠ θ̂_{i}, we cannot assume that, for every outcome j_{i}, Bob obtains only a small amount of collision information. In particular, Bob could learn a lot about B_{i} for some outcome j_{i} that is unlikely to happen. This suggests that we define a random event ΔH_{i} that will be used to count the random number of bits B_{i} that significatively contribute to Bob’s total collision entropy. The definition of ΔH_{i}, must also take care of the fact that only the N bits B_{i}, where Open_{i} = 0, must contribute to this measure of Bob’s ignorance.

Definition 4. The event ΔH_{i} for the triplets of random variables (Θ_{i}, Open_{i}, J_{i}) is defined as the set of triplets (θ̂_{i}^{c}, 0, j_{i}), where

(∀b) P r(B_{i} = b|Θ_{i} = θ̂_{i}^{c} ∧ R_{i} = (θ̂_{i}, b̂_{i}, j_{i})) > p_{I},  (2)

where p_{I} = 1/4

Equation 2 means that

H_{c}(B_{i}|Θ_{i} = θ_{i} ∧ R_{i} = (θ̂_{i}, b̂_{i}, j_{i})) > −lg(p_{I}^{2} + (1 − p_{I})^{2}) = lg(8/5),

where the left side of the inequality is Bob’s collision entropy on the bit B_{i}. The purpose of this definition is to find a lower bound on Bob’s total collision entropy, however we are not going to find the best bound. In computing this bound we will ignore the photons π_{i} for which the event ΔH_{i} has a low probability, even though some of these other photons may also contribute to Bob’s collision entropy. Furthermore, the value p_{I} = 1/4 that is used in the definition of ΔH_{i} has been chosen without much consideration for optimization.

Now, the main idea is to show that if the probability of the event ΔH_{i} is small then the probability that the variable F ail increases is large. To go ahead with this idea we define two sets Γ_{H} and Γ_{F}.

Definition 5. The set Γ_{H} is the set of photons π_{i}, for which

P r(ΔH_{i}|C_{i} = (θ̂_{i}, b̂_{i})) ≥ p_{H},

where p_{H} = \frac{1}{36}.

For every i ∈ Γ_{H}, the variable H_{c} has a probability at least p_{H} of being incremented by lg(8/5) bits. As for the parameter p_{I} = 1/4 in ΔH_{i}, the parameter p_{H} = 1/36 has been chosen without much consideration for optimization.

Definition 6. The set Γ_{F} is the set of photons π_{i}, for which

P r(B_{i} = b̂_{i}^{c} ∧ Θ_{i} = θ̂_{i} ∧ Open_{i} = 1|C_{i} = (θ̂_{i}, b̂_{i})) ≥ p_{F} (p_{I}, p_{H}),

where

p_{F} (p_{I}, p_{H}) = \frac{1}{8}(1 − 2\sqrt{p_{I}(1 − p_{I})})(1 − 4p_{H})

For every i ∈ Γ_{F}, the variable F ail has a probability at the least p_{F} of being incremented.

4.3 The main lemma

Now, we are ready to state a lemma that expresses the main idea that has been introduced in the preceding section. Subsequently, this lemma is used to prove the theorem.

Lemma 7 (Main lemma). For every execution of the protocol Game(δ, n), if Γ_{H} and Γ_{F} are defined as above, then Γ_{H}^{c} ⊆ Γ_{F}, where Γ_{H}^{c} is the complement of Γ_{H} with respect to the 4n photons.

To introduce the proof of this main lemma we begin by considering a simpler situation where, Bob does not use Θ_{i} to choose the ith measurement. Let Φ(j_{i}θ_{i}b_{i}) represents the transition amplitude from the initial state |b_{i}⟩_{θ_{i}} to the final state |j_{i}θ̂_{i}b̂_{i}⟩. If Bob obtains a lot of information from the result (j_{i}θ̂_{i}, b̂_{i}) (when θ_{i} = θ̂_{i}^{c}) then, one can easily show, using Baye’s rule to compute the aposteriori probability, that one of the two amplitudes Φ(j_{i}θ̂_{i}^{c}0) and Φ(j_{i}θ̂_{i}^{c}1) must be small with respect to the other one. To show that in this case the variable F ail is likely to be incremented, we must make use of the fact that if, for this measurement, Alice had used the other basis, then the two corresponding amplitudes would have about the same magnitude. To see this, we simply use

(∀b_{i}) Φ(j_{i}θ̂_{i}b_{i}) = (1/\sqrt{2})(Φ(j_{i}θ̂_{i}^{c}0) ± Φ(j_{i}θ̂_{i}^{c}1)).

which implies that the magnitude of these two transition amplitudes is between \frac{1}{\sqrt{2}}| |Φ(j_{i}θ̂_{i}^{c}b_{i}^{c})| −

|Φ(j_{i}θ̂_{i}^{c}b_{i})| | and \frac{1}{\sqrt{2}}| |Φ(j_{i}θ̂_{i}^{c}b_{i}^{c})|+|Φ(j_{i}θ̂_{i}^{c}b_{i})| |. This means that the wrong bit b̂_{i}^{c} must have occurred with some probability that cannot be very far away From 1/2. Now, in this situation, fail increases if Open_{i} = 1 and Θ_{i} = θ̂_{i}, therefore it increases with a probability that is not far from 1/8.

Now let us return to the real protocol, where Bob is allowed to change the post-basis measurement in accordance with the value of Θ_{i}. In this situation, the preceding discussion does not directly apply. In particular, it is a loss of generality to conclude that a large difference in the amplitude Φ(j_{i}θ̂_{i}^{c}0) and Φ(j_{i}θ̂_{i}^{c}1) implies that the physical amplitudes Φ(j_{i}θ̂_{i}0) and Φ(j_{i}θ̂_{i}1) have similar magnitude. One must rather consider fictitious amplitudes defined in the following way,

Φ^{f}(j_{i}θ_{i}^{c}b_{i}) = \frac{1}{\sqrt{2}}(Φ(j_{i}θ_{i}0) ± Φ(j_{i}θ_{i}1)).

For each individual result r_{i} = (j_{i}θ̂_{i}b̂_{i}), these fictitious amplitudes do not have a direct physical interpretation in the protocol. To physically interpret the squares of their magnitudes as a probability one must consider a fictitious Bob who does not use the basis θ_{i} to determine the post-basis measurement. However, we do not have to physically interpret them at all. They are simply, in a basis of our choice, the components of a matrix that represents the measurement that is made by Bob. However, because the pre-basis measurement is independent of Θ_{i}, the following vectors,

|Φ(θ_{i}^{c}b_{i})⟩ = ∑_{j_{i}} Φ^{f}(j_{i}θ_{i}^{c}b_{i}) |j_{i}θ̂_{i}b̂_{i}⟩,  (3)

are not fictitious, they are more than columns in a matrix, they correspond, up to an IPP transformation, to the projected states that result from the pre-basis measurement when the initial state is |b_{i}⟩_{θ_{i}^{c}} and the outcome is (θ̂_{i}, b̂_{i}).

Now, as in the simpler case that we have dicussed above, one can see that if the genuine amplitudes in the basis Θ_{i} = θ̂_{i}^{c} have very different magnitudes, then their corresponding fictitious amplitudes in the other basis Θ_{i} = θ̂_{i} must have similar magnitudes. The crucial point is that, if this is true for a set of outcomes I_{i} with significant probability, then the corresponding vectors defined by formula 3 will have about the same norm. Because the square of these vectors correspond to the probabilities of the corresponding transitions, this means that with significant probability Bob has chosen the wrong bit B_{i} and this is enough to bound the collision entropy. The proof of the lemma is a formalization of the above discussion.

Proof of the lemma. The proof consists in using i ∈ Γ_{H}^{c} to obtain i ∈ Γ_{F}. We first consider the set Γ_{H}^{c}. The event ΔH_{i} that is used in the definition of Γ_{H} is the conjonction of three events: Θ_{i} = θ̂_{i}^{c}, Open_{i} = 0 and ¬I_{i}, where the event I_{i}, for the random variable Θ_{i} and J_{i} is defined as the set of pairs (θ_{i}, j_{i}) such that

(∃b) P r(B_{i} = b|Θ_{i} = θ_{i} ∧ R_{i} = (j_{i}θ̂_{i}, b̂_{i})) ≤ p_{I}.  (4)

Using definition 5 and the fact that P r(Open_{i} = 0 ∧ Θ_{i} = θ̂_{i}^{c}|C_{i} = (θ̂_{i}, b̂_{i})) = 1/4, we obtain that Γ_{H}^{c} is the set of photons π_{i} such that

Pr(I_{i}|Θ_{i} = θ̂_{i}^{c} ∧ C_{i} = (θ̂_{i}, b̂_{i})) ≥ 1 − 4p_{H} = 8/9.  (5)

Let us expand the formula 5.

Pr(I_{i}|Θ_{i} = θ̂_{i}^{c} ∧ C_{i} = (θ̂_{i}, b̂_{i}))

= \frac{∑_{(_{θ_{i}^{c}},j_{i})∈I_{i}} P r(J_{i} = j_{i} ∧ Θ_{i} = θ̂_{i}^{c} ∧ C_{i} = (θ̂_{i}b̂_{i}))}{P r(Θ_{i} = θ̂_{i}^{c} ∧ C_{i} = (θ̂_{i}b̂_{i}))}

= \frac{∑_{(_{θ_{i}^{c}},j_{i})∈I_{i}} P r(R_{i} = (j_{i}θ̂_{i}b̂_{i}) ∧ Θ_{i} = θ̂_{i}^{c})}{P r(Θ_{i} = θ̂_{i}^{c} ∧ C_{i} = (θ̂_{i}b̂_{i}))}

= \frac{∑_{(_{θ_{i}^{c}},j_{i})∈I_{i}} P r(R_{i} = (j_{i}θ̂_{i}b̂_{i}))}{P r(C_{i} = (θ̂_{i}b̂_{i}))}

We obtain that, for i ∈ Γ_{H}^{c},

∑_{(_{θ_{i}^{c}},j_{i})∈I_{i}} P r(R_{i} = (j_{i}θ̂_{i}^{c}b̂_{i})) ≥ (1 − 4p_{H})P r(C_{i} = (θ̂_{i}b̂_{i}))  (6)

Now, we reexpress in terms of the amplitudes Φ the condition (θ̂_{i}^{c}, j_{i}) ∈ I_{i}. According to formula 4, this condition means

(∃b_{i}) P r(B_{i} = b_{i}|Θ_{i} = θ̂_{i}^{c} ∧ R_{i} = (j_{i}θ̂_{i}, b̂_{i})) ≤ p_{I}

(∃b_{i}) \frac{P r(B_{i} = b_{i} ∧ Θ_{i} = θ̂_{i}^{c} ∧ R_{i} = (j_{i}θ̂_{i}, b̂_{i}))}{P r(Θ_{i} = θ̂_{i}^{c} ∧ R_{i} = (j_{i}θ̂_{i}, b̂_{i}))} ≤ p_{I}

(∃b_{i}) P r(R_{i} = j_{i}θ̂_{i}b̂_{i}|Θ_{i} = θ̂_{i}^{c} ∧ B_{i} = b_{i}) ≤ 2p_{I}P r(R_{i} = j_{i}θ̂_{i}b̂_{i})  (7)

For the L.H.S we have

P r(R_{i} = j_{i}θ̂_{i}b̂_{i}|Θ_{i} = θ̂_{i}^{c} ∧ B_{i} = b_{i}) = |Φ(j_{i}θ̂_{i}^{c}b_{i})|^{2}

For the R.H.S we have

(∀θ_{i}) 2P r(R_{i} = j_{i}θ̂_{i}b̂_{i}) = |Φ(j_{i}θ_{i}0)|^{2} + |Φ(j_{i}θ_{i}1)|^{2}  (8)

We obtain that (θ̂_{i}^{c}, j_{i}) ∈ I_{i} is equivalent to

(∃b_{i}) |Φ(j_{i}θ̂_{i}^{c}b_{i})|^{2} ≤ p_{I}(|Φ(j_{i}θ̂_{i}^{c}0)|^{2} + |Φ(j_{i}θ̂_{i}^{c}1)|^{2})  (9)

Now, to show that π_{i} ∈ Γ_{F}, we want to use the inequalities 9 and 6 (given by i ∈ Γ_{H}^{c}) to obtain

∥ |Φ(θ̂_{i}, b̂_{i}^{c})⟩∥^{2} = ∑_{j_{i}} |Φ^{f}(j_{i}, θ̂_{i}, b̂_{i}^{c})|^{2} = P r(C_{i} = (θ̂_{i}, b̂_{i})|Θ_{i} = θ̂_{i} ∧ B_{i} = b̂_{i}^{c}) ≥ p_{F} ,

where p_{F} is given in definition 6. We make use of the constraint 9 on the amplitudes Φ(·) to obtain a lower bound on each of the ficticious amplitude Φ^{f}(·). The magnitude of the fictitious amplitudes Φ^{f}(j_{i}θ̂_{i}b̂_{i}^{c}) is given by

|Φ^{f}(j_{i}θ̂_{i}b̂_{i}^{c})| = \frac{1}{\sqrt{2}}|Φ(j_{i}θ̂_{i}^{c}0) ± Φ(j_{i}θ̂_{i}^{c}1)|

Now, if the magnitude square of the smallest Φ is smaller than p_{I}(|Φ(·)|^{2} +|Φ(·)|^{2}) then the biggest is bigger than (1 − p_{I})(|Φ(·)|^{2} + |Φ(·)|^{2}). The lower bound is obtained by taking the extreme case. We obtain

(∀b_{i}) |Φ^{f}(j_{i}θ̂_{i}^{c}b_{i})|^{2} ≥ f(p_{I})(|Φ^{f}(j_{i}θ̂_{i}^{c}0)|^{2} + |Φ^{f}(j_{i}θ̂_{i}^{c}1)|^{2})  (10)

where

f(p_{I}) = \frac{1}{2}(1 − 2\sqrt{p_{I}(1 − p_{I})})

After summing the inequality 10, with b_{i} = b̂_{i}^{c}, using formula 8 and 6, we obtain

P r(C_{i} = (θ̂_{i}b̂_{i})|Θ_{i} = θ̂_{i} ∧ B_{i} = b̂_{i}^{c}) ≥ 2f(p_{I})(1 − 4p_{H})P r(C_{i} = (θ̂_{i}b̂_{i}))

From which we have

P r(B_{i} = b̂_{i}^{c} ∧ Θ_{i} = θ̂_{i} ∧ C_{i} = (θ̂_{i}b̂_{i})) ≥ \frac{1}{2}f(p_{I})(1 − 4p_{H})P r(C_{i} = (θ̂_{i}, b̂_{i}))

P r(B_{i} = b̂_{i}^{c} ∧ Θ_{i} = θ̂_{i} ∧ Open_{i} = 1|C_{i} = (θ̂_{i}b̂_{i})) ≥ \frac{1}{4}f(p_{I})(1 − 4p_{H}).

Therefore, we have that i ∈ Γ_{F}, with

p_{F} = \frac{1}{4}f(p_{I})(1 − 4p_{H}) = \frac{1}{8}(1 − 2\sqrt{p_{I}(1 − p_{I})})(1 − 4p_{H})

and this concludes the proof of the lemma. ⊓ ⊔ Proof of the theorem. We want to prove that for every sequence c_{1}, …, c_{4n}, Bob’s total collision entropy is bounded below (by the same bound). Let n_{H} and n_{F} be the sizes of Γ_{H} and Γ_{F} respectively. For c_{1}, …, c_{4n} fixed, n_{H} and n_{F} are also fixed. Basically, the lemma says that n_{F} ≥ 4n − n_{H} or equivalently n_{H} ≥ 4n − n_{F}. Using the aposteriori independence of the bits B_{i}, we have that at the end of the protocol Bob’s total collision entropy is the sum of the collision entropy of each bit B_{i}, where Open_{i} = 0. Now, let Γ_{ΔH} be the set of photons i ∈ Γ_{H}, where (θ_{i}, open_{i}, j_{i}) ∈ ΔH_{i}. Let H_{c}(p_{I}) = −lg(p_{I}^{2}+(1−p_{I})^{2}) = lg(8/5). From what we said above, we obtain that Bob’s collision entropy is greather than n_{ΔH} ×H_{c}(p_{I}), where n_{ΔH} is the size of Γ_{ΔH}. Now, using the independence between variables that are associated with distinct measurements, we have that n_{ΔH} is a binomial with parameters p_{H} = 1/8 and n_{H}. Similarly, the distribution of F ail is a binomial with parameter p_{F} and n_{F}. Now, let us assume that Bob’s strategy is such that there is a non negligeable probability that Alice does not refuse to continue with the protocol. This implies that n_{F} × p_{F} ≤ (δ + ϵ)n for any ϵ > 0 except with negligeable probability. Therefore, we have n_{H} ≥ (4 − \frac{(δ+ϵ)}{p_{F}})n. This gives us that Bob’s total collision entropy is greater that [H_{c}(p_{I})p_{H}(4−δ/p_{F})−ϵ′]n for any ϵ′ > 0 excepted with an exponentially small probability. ⊓ ⊔

5 Conclusion

We have shown that the BBCS-protocol is secure if all measurements are performed individually on the received photons. Individual measurements are interesting because they are easier to effect than coherent measurements. The main open question is to enhance the proof to the case of coherent measurements. It would be interesting to find a better bound for the collision entropy in order to minimize the shrinking parameter for the hashing function used in the privacy amplification stage.

References

[BB84] C.H. Bennett, G. Brassard, Quantum Cryptography: Public key distribution and coin tossing, Proc. of IEEE International Conference on Computers, Systems, and Signal Processing, Banglore, India, December 1984, pp. 175–179.

[BBBSS] Bennett, C. H., Bessette, F., Brassard, G., Salvail, L. and Smolin, J., “Experimental quantum cryptography”, Journal of Cryptology, vol. 5, no. 1, 1992, pp. 3 – 28. Previous version in Advances in Cryptology — Eurocrypt ’90 Proceedings, May 1990, Springer – Verlag, pp. 253 – 265.

[BBCM] C.H. Bennett, G. Brassard, C. Crépeau, U. Maurer, Privacy Amplification Against Probabilistic Information, to be published.

[BBCS] C.H. Bennett, G. Brassard, C. Crépeau, M.-H. Skubiszewska, Practical Quantum Oblivious Transfer, In proceedings of CRYPTO’91, Lecture Notes in Computer Science, vol 576, Springer Verlag, Berlin, 1992, pp 351–366.

[BBR] C.H. Bennett, G. Brassard, J.-M. Robert, Privacy Amplification by Public Discussion, SIAM Journal on Computing, Vol. 17, No.2, 1988, pp. 210–229.

[BCJL] G. Brassard, C. Crépeau, R. Jozsa, D. Langlois, A quantum bit commitment scheme provably unbreakable by both parties, Proceeding of the 34th annual IEEE Symposium on Foundations of Computer Science, November 1993,pp. 362–371.

[Cr] C. Crépeau, Quantum Oblivious Transfer, submitted to the Journal of Modern Optics’special issue on Quantum Cryptography,1994.

[CW] J. L. Carter, M. N. Wegman, Universal Classes of Hash Functions, Journal of Computer and System Science, Vol. 18, 1979, pp.143–154.

[Ma] D. Mayers, Quantum Transformation and Generalized Measurements, to appears.

[MC] C. Cachin, U. Maurer, Linking Reconciliation and Privacy Amplification, to appear in the proceeding of Eurocrypt’94.

[Ki] J. Kilian. Founding cryptography on oblivious transfer. In Proc. 20th ACM Symposium on Theory of Computing, pp. 20–31, Chicago, 1988. ACM.

[TRT1] Townsend, P. D., Rarity, J. G. and Tapster, P. R., “Single photon interference in a 10 km long optical fibre interferometer”, Electronics Letters, vol. 29, no. 7, 1 April 1993, pp. 634 – 635.

[TRT2] Townsend, P. D., Rarity, J. G. and Tapster, P. R., “Enhanced single photon visibility in a 10km long prototype quantum cryptography channel”,Electronics Letters, to appear.

This article was processed using the LaTEX macro package with LLNCS style