To appear in the Journal of Modern Optics’ special issue on Quantum Cryptography, 1994

Quantum Oblivious Transfer

Claude Crépeau

École Normale Supérieure ∗

Université de Montréal †

Abstract

In a One-out-of-two Oblivious Transfer, a party Alice has two messages m_{0}, m_{1} that she sends to another party Bob in such a way that he can decide to get either of them at his choosing but not both. Alice never finds out which message Bob received. First introduced by Wiesner as “conjugate coding” this cryptographic tool was later introduced to the world of public-key cryptography, first by Rabin (in a slightly different flavour) and then by Even, Goldreich and Lempel who named it after Rabin’s primitive called Oblivious Transfer. The One-out-of-two Oblivious Transfer was later showed extremely powerful to design general cryptographic tools.

The current paper presents a new design of a One-out-of-two Oblivious Transfer based on the transmission of polarized light, improving the work of Wiesner [17] and Bennett, Brassard, Breidbart and Wiesner [3] and shows that the scheme is robust to general attacks.

1 Introduction

In his now celebrated paper [17] Stephen Wiesner not only introduced the idea that quantum mechanics could be useful to cryptography but also introduced a new cryptographic tool that he called “conjugate coding”. Little did he suspect how powerful his inventions were! Conjugate coding was independently reinvented a decade later by Even, Goldreich and Lempel [12] who named it “one-out-of-two Oblivious Transfer” after another cryptographic tool of similar flavour put forward by Rabin [16] and called “Oblivious Transfer”.

Informally speaking in an Oblivious Transfer, Alice sends a message to Bob that he receives half the time (this fact is out of their control). Alice does not find out what happened. Bob knows if he got the message or nothing. Similarly, in a One-out-of-two Oblivious Transfer, Alice has two messages m_{0}, m_{1} that she sends to Bob in such a way that he can decide to get either of them at his choosing but not both. Alice never finds out which message Bob received.

∗ Laboratoire d’Informatique de l’École Normale Supérieure (CNRS ura1327), 45 rue d’Ulm, 75230 Paris cédex 05, France. e-mail:crepeau@dmi.ens.fr.

†Département IRO, Université de Montréal, C.P. 6128, succursale centre-ville, Montréal (Québec) Canada H3C 3J7

These two simple cryptographic tools have been extensively studied by several researchers because they turned out to be elementary blocks to build more elaborate cryptographic tasks known as “secure computations”. This idea introduced by Yao [18] allows Alice and Bob to compute a two-argument function on data they would like to keep secret from one another. They find out the output of the function but not their respective inputs. It was shown in a computational model that One-out-of-two Oblivious Transfer suffices to perform general secure computations by Goldreich, Micali and Wigderson [13] and later in an abstract (not necessarily computational) model by Kilian [14]. I showed [7] that indeed Rabin’s Oblivious Transfer can also do the job by describing a general technique to turn an Oblivious Transfer into a One-out-of-two Oblivious Transfer. The result of the current paper is an extension of that technique.

Although quite remarkable, Wiesner’s idea of a conjugate coding seemed rather vague. In particular Wiesner’s construction for conjugate coding suffered several major flaws:

• it is trivial to get parts of both messages m_{0} and m_{1}

• his construction relies on error correcting codes that may not even exist

• he himself suggested that general measurements on several photons at once or POVMs could extract both messages completely

The same flaws applied to the scheme of Bennett, Brassard, Breidbart and Wiesner [3] as well. Because of these reasons, it seemed necessary to the author to approach the problem with fresh ideas. One important simplification that Wiesner was not aware of, is that it suffices to have a conjugate coding for one-bit long messages which can be extended to longer strings by the result of [6, 10]. The result of this current paper is to exhibit a protocol for the binary version of One-out-of Two Oblivious Transfer, from now on denoted \binom{2}{1}–OT_{2}, whose security relies on quantum mechanics. Earlier versions of this work were presented in [9, 8].

2 Formal Problem

Formally speaking we describe a two-party protocol that satisfies the natural constraints (see below) of correctness and privacy of a \binom{2}{1}–OT_{2}. For a more thorough description of these concepts, we refer the reader to [8], but some intuition follows. Let V_{P} (H, b_{0}, b_{1}, c) be the random variable that describes the information that a party P has at the end of its interaction through the protocol executed on inputs b_{0}, b_{1}, c and where H (for History) is the random variable describing the a priori information the party P has before entering the protocol. Finally, we denote H(X) = − ∑_{x} P [X = x] log P [X = x] the entropy function of the random variable X.

Correctness: It should be that when Alice and Bob follow the protocol and start with Alice’s input bits ⟨b_{0}, b_{1}⟩ and Bob’s input bit ⟨c⟩ they finish with Bob getting b_{c}.

Intuitively, this constraint means that if the protocol is executed as described, it will accomplish the task it was designed for.

Privacy: It should be that whatever program, Ã, Alice runs she does not find out about c, that is for all H, b_{0}, b_{1}

H(c|VÃ(H, b_{0}, b_{1}, c)) = H(c|H, b_{0}, b_{1})

and that whatever program, B̃, Bob runs he does not find out information about more than one of b_{0}, b_{1}, that is for all H, c, b

H(b_{0}|VB̃(H, b_{0}, b, c), b) = H(b_{0}|H, c, b)

or

H(b_{1}|VB̃(H, b, b_{1}, c), b) = H(b_{1}|H, c, b).

Intuitively, these constraints mean that if a party is honest it is impossible for his (or her) opponent to gain “illegal” information about his input. For Alice it simply means that she learns nothing about c. For Bob it is somewhat more elaborate: in an ideal execution of a \binom{2}{1}–OT_{2} (a situation in which Bob is simply given b_{c} and no protocol actually takes place) Bob would be allowed to obtain a bit b which is either b_{0} or b_{1}. Therefore the rightmost expressions are Bob’s uncertainty about b_{0} or b_{1} given the other bit b as if it were obtained through the ideal \binom{2}{1}–OT_{2}. On the left side we must consider Bob’s uncertainty about b_{0} or b_{1} after running the protocol and after being given the other bit b. In particular, a protocol in which Bob learns b_{0} ⊕ b_{1}, although it contains no information about neither of b_{0} nor b_{1} individually, would not be private since H(b_{0}|VB̃(H, b_{0}, b, c), b) = H(b_{1}|VB̃(H, b, b_{1}, c), b) = 0.

The protocol we describe in the next section is of probabilistic nature. We cannot show that this protocol perfectly satisfies the constraints we just mentioned. Nevertheless, we show the next best thing, that the constraints are satisfied in a statistical sense: after an amount of work in O(n) time the protocol will satisfy for some positive constant ε < 1

Statistical Correctness: It should be that, except with probability at most ε^{n}, when Alice and Bob follow the protocol and start with Alice’s input bits ⟨b_{0}, b_{1}⟩ and Bob’s input bit ⟨c⟩ they finish with Bob getting b_{c}.

Statistical Privacy: It should be that, except with probability at most ε^{n}, whatever program, Ã, Alice runs she does not find out much about c, that is for all H, b_{0}, b_{1}

H(c|VÃ(H, b_{0}, b_{1}, c)) ≥ H(c|H, b_{0}, b_{1}) − ε^{n}

and that whatever program, B̃, Bob runs he does not find out much information about more than one of b_{0}, b_{1}, that is for all H, c, b

H(b_{0}|VB̃(H, b_{0}, b, c), b) ≥ H(b_{0}|H, c, b) − ε^{n}

or

H(b_{1}|VB̃(H, b, b_{1}, c), b) ≥ H(b_{1}|H, c, b) − ε^{n}.

3 Protocol for Quantum Oblivious Transfer

Let \begin{matrix}c \\ ◯ \end{matrix}^{|} denote the random variable that takes the binary value 0 with probability \frac{1}{2} and 1 with probability \frac{1}{2}. Also, denote by [ ]_{i} the selection function such that [a_{0}, a_{1}, ..., a_{k}]_{i} = a_{i}. Let ↔ ↕ = (|↔⟩, |↕⟩) and ↗ ↙ ↘ ↖ = (| ↗ ↙ ⟩, | ↘ ↖ ⟩) denote respectively the bases of rectilinear and diagonal polarization in the quantum state space of a photon.

3.1 The formal protocol

Protocol 3.1 ( \binom{2}{1}–OT_{2}(b_{0}, b_{1})(c) )

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

• Alice picks a random bit r_{i} ← \begin{matrix}c \\ ◯ \end{matrix}^{|}

• Alice picks a random bit β_{i} ← \begin{matrix}c \\ ◯ \end{matrix}^{|} and defines her emission basis (|φ_{i}⟩, |φ_{i}^{⊥}⟩) ← [↔ ↕ , ↗ ↙ ↘ ↖]_{β_{i}} • Alice sends to Bob a photon π_{i} with polarization [|φ_{i}⟩, |φ_{i}^{⊥}⟩]_{r_{i}}

• Bob picks a random bit β′_{i} ← \begin{matrix}c \\ ◯ \end{matrix}^{|} and measures photon π_{i} in basis (|θ_{i}⟩, |θ_{i}^{⊥}⟩) ← [↔ ↕ , ↗ ↙ ↘ ↖]_{β′_{i}}

• Bob sets r′_{i} ← \{ \begin{matrix}0 & if π_{i} is observed as |θ_{i}⟩ \\ 1 & if π_{i} is observed as |θ_{i}^{⊥}⟩ \end{matrix}

2: Alice announces her choices β_{1}β_{2}...β_{n} to Bob.

3: Bob randomly selects two subsets I_{0}, I_{1} ⊂ {1, 2, ..., n} subject to |I_{0}| = |I_{1}| = n/3, I_{0} ⋂ I_{1} = ∅ and ∀i ∈ I_{0}, β_{i} = β′_{i}, and he announces ⟨I_{c}, I\overline{c}⟩ to Alice

4: Alice receives ⟨J_{0}, J_{1}⟩, computes and sends b̂_{0} ← b_{0} ⊕ ⨁_{j∈J_{0}} r_{j} and b̂_{1} ← b_{1} ⊕ ⨁_{j∈J_{1}} r_{j}

5: Bob receives ⟨b̂_{0}, b̂_{1}⟩ and computes b_{c} ← b̂_{c} ⊕ ⨁_{j∈I_{0}} r′_{j}

3.2 Intuition behind the protocol

Intuitively, random bits r_{1}r_{2}...r_{n} are chosen by Alice in step 1 and are sent to Bob via an ambiguous coding referred to as the BB84 coding [1]: when Alice and Bob choose the same emission and reception basis, the bit received is the same as what was sent and uncorrelated otherwise. Given that Bob finds out Alice’s choices of bases at step 2, he can tell in which situation each bit was. Bob then builds two subsets: one I_{0} that will allow him to get b_{c}, and one I_{1} that will spoil b\overline{c}. The calculations of steps 4–5 are such that all the bits in a subset must be known by Bob in order for him to be able to obtain the output bit connected to that subset.

4 Analysis

In the basic version of the protocol we make the strong assumption that Bob must read the photons sent by Alice as they come: he cannot wait and read them later, individually or together. We shall remove this assumption later. We also assume that the channel used for the quantum transmission is free of errors, so that it is guaranteed that r′_{i} = r_{i} whenever β′_{i} = β_{i}. We now show that under these assumptions this protocol satisfies the statistical version of the above constraints.

4.1 Correctness

We show that most of the time the output is correct if the parties abide to their prescribed protocol. In a given run of the protocol, Bob will succeed in computing b_{c} properly provided #{i|β_{i} = β′_{i}} ≥ n/3 because in that case he can form I_{0} as prescribed and then he can compute the output bit as b̂_{c} ⊕ ⨁_{j∈I_{0}} r′_{j} which is

b̂_{c} ⊕ ⨁_{j∈I_{0}} r′_{j} = b_{c} ⊕ ⨁_{j∈J_{c}} r_{j} ⊕ ⨁_{j∈I_{0}} r′_{j} = b_{c} ⊕ ⨁_{j∈I_{0}} r_{j} ⊕ r′_{j}

because J_{c} is I_{0}. Since β_{i} = β′_{i} → r_{j} ⊕ r′_{j} = 0 makes all the right terms vanish, we end up with

b̂_{c} ⊕ ⨁_{j∈I_{0}} r′_{j} = b_{c}.

Therefore the protocol gives the correct output unless #{i|β_{i} = β′_{i}} < n/3 in which case Bob is unable to form the set I_{0} as prescribed. The probability of this event is given by

P [#{i|β_{i} = β′_{i}} < n/3] = P [∑_{i=1}^{n} β_{i} ⊕ β′_{i} > 2n/3] ≤ P [|n/2 − ∑_{i=1}^{n} β_{i} ⊕ β′_{i}| > n/6]

Given that P [β_{i} ⊕ β′_{i} = 1] = \frac{1}{2} this earlier expression can be easily bounded by

≤ 2e^{−n/36} ≤ (0.973)^{n}

using Bernstein’s law of large numbers [15].

4.2 Privacy

We analyse the privacy of each party individually as if he or she were facing a malicious opponent.

4.2.1 Privacy for Bob

In order to show the protocol private for Bob we show that no malicious Ã can find out information about c. Indeed we show that Theorem 4.1 For all H, b_{0}, b_{1}

H(c|VÃ(H, b_{0}, b_{1}, c)) = H(c|H, b_{0}, b_{1}).

Proof. The only things Ã gets through the protocol are the sets J_{0}, J_{1}. Therefore we have that her final information is VÃ = ⟨H, b_{0}, b_{1}, J_{0}, J_{1}⟩. Now notice that the distribution of J_{0}, J_{1}

depends only on the fact that the β_{i}’s announced by Ã are or not the same as the β′_{i}’s used by Bob and not at all on c. Since the β′_{i}s are chosen randomly and independently by Bob, J_{0} and J_{1} will have uniform distribution over all possible pairs of disjoint subsets of size n/3 for c = 0 as well as for c = 1. Therefore since Ã learns nothing about the β′_{i}’s

H(c|VÃ(H, b_{0}, b_{1}, c)) = H(c|⟨H, b_{0}, b_{1}, J_{0}, J_{1}⟩) = H(c|H, b_{0}, b_{1}).

4.1

4.2.2 Privacy for Alice

Without loss of generality, since we assume that B̃ is limited to making immediate measurements in each iteration of step 1, we might as well assume that he makes a complete Von Neumann measurement for some orthogonal basis (|θ_{i}⟩, |θ_{i}^{⊥}⟩) since any gentler measurement would give him only lower success probability with respect to guessing r_{i}. We can therefore analyse only those B̃ that follow such a strategy because other ones could not do better. We may also denote, without loss of generality, r′_{i} to be the result of his measurement as defined in step 1. Let S_{5}(H, b_{0}, b_{1}, c) be B̃’s information before step 5 of the protocol. By the end of the protocol he gets VB̃(H, b_{0}, b_{1}, c) = ⟨S_{5}(H, b_{0}, b_{1}, c), b̂_{0}, b̂_{1}⟩. When no confusion arise we simply write S_{5} and VB̃ instead of these complete expressions. Let m be such that

| ∏_{j∈J_{m}}(||⟨θ_{j}|[↔, ↗ ↙]_{β_{j}}⟩||^{2} − 1/2)| ≤ | ∏_{j∈J\overline{m}}(||[⟨θ_{j}|[↔, ↗ ↙]_{β_{j}}⟩||^{2} − 1/2)| .  (1)

We show that

Theorem 4.2 There exists a positive ε < 1 such that for all H, c, b\overline{m} we get

H(b_{m}|VB̃(H, b_{0}, b_{1}, c), b\overline{m}) ≥ H(b_{m}|H, c, b\overline{m}) − ε^{n}.

Proof.

H(b_{m}|VB̃, b\overline{m}) = H(b_{m}|S_{5}, b̂_{0}, b̂_{1}, b\overline{m})
= H(b_{m}|S_{5}, b̂_{m}, b\overline{m})

Since b̂\overline{m} contains solely imperfect information about b\overline{m},

it cannot be informative about b_{m} in a way that b\overline{m} would not.

= H(b_{m}|S_{5}, b\overline{m}) + H(b_{m}|S_{5}, b̂_{m}, b\overline{m}) − H(b_{m}|S_{5}, b\overline{m})
= H(b_{m}|H, c, b\overline{m}) + H(b_{m}, S_{5}, b̂_{m}, b\overline{m}) − H(S_{5}, b̂_{m}, b\overline{m}) − H(b_{m}, S_{5}, b\overline{m}) + H(S_{5}, b\overline{m})

the leftmost term is due to the fact that b_{0}, b_{1} are not used by Alice until step 5

= H(b_{m}|H, c, b\overline{m}) + H(b̂_{m}|S_{5}, b_{0}, b_{1}) − H(b̂_{m}|S_{5}, b\overline{m})

Therefore it suffices to show

H(b̂_{m}|S_{5}, b\overline{m}) − H(b̂_{m}|S_{5}, b_{0}, b_{1}) ≤ ε^{n}.

For that purpose we compute

P [b̂_{m} = 0 | S_{5}, b_{0}, b_{1}] = P [ ⨁_{j∈J_{m}} r_{j} = b_{m}| S_{5}, b_{0}, b_{1}]

We see that this is almost the same whatever b_{m} is:

P [ ⨁_{j∈J_{m}} r_{j} = 0| S_{5}, b_{0}, b_{1}] = P [ ⨁_{j∈J_{m}} r_{j} = 0| r′_{1}...r′_{n}θ_{1}...θ_{n}β_{1}...β_{n}]

since the r_{i}’s are only dependent on the r′_{i}’s, θ_{i}’s and β_{i}’s.

= \frac{1}{2} ± \frac{1}{2} ( ∏_{j∈J_{m}} 2P [r′_{j} = r_{j}] − 1)

the sign is “+” if ⨁_{j∈J_{m}} r′_{j} = 0, and it is “−” otherwise.

= \frac{1}{2} ± \frac{1}{2} ( ∏_{j∈J_{m}} 2||⟨θ_{j}|[↔, ↗ ↙]_{β_{j}}⟩||^{2} − 1)
since P [r′_{j} = r_{j}] = ||⟨θ_{j}|[↔, ↗ ↙]_{β_{j}}⟩||^{2}.

We get the same result by setting b_{m} = 1 instead of 0 but with the opposite sign. We conclude from this that for b ∈ {0, 1}

|P [b̂_{m} = b|S_{5}, b_{0}, b_{1}] − \frac{1}{2}| ≤ \frac{1}{2}| ∏_{j∈J_{m}} 2||⟨θ_{j}|[↔, ↗ ↙]_{β_{j}}⟩||^{2} − 1|

Now based on the fact that m was chosen so to satisfy equation (1) it suffices to show that

| ∏_{j∈J_{0}∪J_{1}} 2||⟨θ_{j}|[↔, ↗ ↙]_{β_{j}}⟩||^{2} − 1| ≤ α^{n}  (2)

for some α < 1 to conclude that

| ∏_{j∈J_{m}} 2||⟨θ_{j}|[↔, ↗ ↙]_{β_{j}}⟩||^{2} − 1| ≤ (\sqrt{α})^{n} .  (3)

Finally to prove that claim we need the following easily proven fact:

Fact 4.3 For any Von Neumann measurement (|θ_{j}⟩, |θ_{j}^{⊥}⟩) at least one of the following holds

\frac{\sqrt{2} − 1}{2\sqrt{2}} ≤ ||⟨θ_{j}|↔⟩||^{2} ≤ \frac{\sqrt{2} + 1}{2\sqrt{2}} or \frac{\sqrt{2} − 1}{2\sqrt{2}} ≤ ||⟨θ_{j}| ↗ ↙ ⟩||^{2} ≤ \frac{\sqrt{2} + 1}{2\sqrt{2}}

This means that because the β_{j} are chosen at random, in each position j

P [|2||⟨θ_{j}|[↔, ↗ ↙]_{β_{j}}⟩||^{2} − 1| ≤ \frac{1}{\sqrt{2}}] ≥ \frac{1}{2}

Therefore the set of positions

\{j : |2||⟨θ_{j}|[↔, ↗ ↙]_{β_{j}}⟩||^{2} − 1| > \frac{1}{\sqrt{2}}\}

will have size no more than \frac{7n}{12} except with probability bounded by 2e^{−n/144} by Bernstein’s law of large number. In that case we have that equations (2) and (3) are satisfied with α = (\frac{1}{2})^{1/24}. In conclusion, only with probability no more than 2e^{−n/144} will

|P [b̂_{m} = 0|S_{5}, b_{0}, b_{1}] − 1/2| > 2^{−n/48}

Therefore H(b̂_{m}|S_{5}, b_{0}, b_{1}) will be roughly 1−(\frac{1}{2})^{n/48} and since H(b̂_{m}|S_{5}, b_{0}, b_{1}) ≤ H(b̂_{m}|S_{5}, b\overline{m}) ≤ 1 we conclude that for some positive ε < 1

H(b̂_{m}|S_{5}, b\overline{m}) − H(b̂_{m}|S_{5}, b_{0}, b_{1}) ≤ ε^{n}.

4.2

5 Relaxing our Assumption

In the above proof of privacy for Alice we had to make the strong assumption that B̃ must make his measurements right away when he receives the photons. Of course from a theoretical point of view this assumption is quite unsatisfactory because B̃ could in principle store the photons sent by Alice and wait until she discloses the bases before measuring them, which would allow him to obtain both of Alice’s bits with certainty.

However we describe next a variation of the protocol of section 3 that more or less forces B̃ to make immediate measurements on the received photons. For this we use a bit commitment scheme. A bit commitment scheme goes as follows: Assume that Bob has a bit x in mind, to which he would like to be committed toward Alice. That is, Bob wishes, through a procedure commit(x), to provide Alice with a piece of evidence that he has a bit x in mind and that he cannot change it. Meanwhile, Alice should not be able to tell from that evidence what x is. At a later time, Bob can reveal, through a procedure unveil(x), the value of x and prove to Alice that the piece of evidence sent earlier really corresponded to that bit.

Recently Brassard, Crépeau, Jozsa and Langlois [5] have described a bit commitment scheme based on quantum physics that they have proved secure according to the rules of quantum mechanics. This formal proof was the first ever of the security of a cryptographic protocol based on quantum mechanics. Therefore Bob and Alice can use their quantum channel in the reverse direction to perform the bit commitment necessary for the \binom{2}{1}–OT_{2} described next. As we will later see in section 6, it turns out that it can even be done without reversing the channel.

The idea behind this modified protocol is that each time Alice was sending a random r_{i} to Bob in the original protocol she now sends two random bits r_{i}, r_{n+i}. One of them will become r_{i}, while the other will be used to challenge the fact that Bob makes immediate measurements of the photons. Alice gets Bob to commit to the bits that he received and the bases that he used to measure them. Before going ahead with r_{i}, say, Alice checks that Bob had committed properly to r_{n+i} when he read that bit in the basis that she used to encode it. If at any stage Alice observes a mistake (β_{n+i} = β′_{n+i} but r_{n+i} ≠ r′_{n+i}), she stops further interaction with Bob who is definitely not performing his legal protocol (this should never happen if Bob follows his protocol). If Bob manages to keep Alice satisfied, he must be making immediate measurements that are very close to measuring along the standard bases. The modified protocol is:

Protocol 5.1 ( \binom{2}{1}–OT_{2}(b_{0}, b_{1})(c) )

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

• Alice picks a random bit r_{i} ← \begin{matrix}c \\ ◯ \end{matrix}^{|}

• Alice picks a random bit β_{i} ← \begin{matrix}c \\ ◯ \end{matrix}^{|} and defines her emission basis (|φ_{i}⟩, |φ_{i}^{⊥}⟩) ← [↔ ↕ , ↗ ↙ ↘ ↖]_{β_{i}} • Alice sends to Bob a photon π_{i} with polarization [|φ_{i}⟩, |φ_{i}^{⊥}⟩]_{r_{i}}

• Bob picks a random bit β′_{i} ← \begin{matrix}c \\ ◯ \end{matrix}^{|} and measures photon π_{i} in basis (|θ_{i}⟩, |θ_{i}^{⊥}⟩) ← [↔ ↕ , ↗ ↙ ↘ ↖]_{β′_{i}}

• Bob sets r′_{i} ← \{ \begin{matrix}0 & if π_{i} is observed as |θ_{i}⟩ \\ 1 & if π_{i} is observed as |θ_{i}^{⊥}⟩ \end{matrix}

1.5: DO_{i=1}^{n}

• Bob runs commit(r′_{i}), commit(β′_{i}), commit(r′_{n+i}), commit(β′_{n+i}) with Alice

• Alice picks c_{i} ← \begin{matrix}c \\ ◯ \end{matrix}^{|} and announces it to Bob

• Bob runs unveil(r′_{nc_{i}+i}), unveil(β′_{nc_{i}+i})

• Alice checks that β_{nc_{i}+i} = β′_{nc_{i}+i} → r_{nc_{i}+i} = r′_{nc_{i}+i}.

• if c_{i} = 0 then Alice sets β_{i} ← β_{n+i} and r_{i} ← r_{n+i} and Bob sets β′_{i} ← β′_{n+i} and r′_{i} ← r′_{n+i}

2: Alice announces ...

3: Bob randomly selects ...

4: Alice receives ...

5: Bob receives ...

This modified protocol will clearly be as correct as the original since only a few checks are added but basically everything is computed just as before. As for the privacy, it remains just the same for Bob but things are a little tricky for Alice. It is not completely clear that B̃ could not adopt a strategy to read each photon with an incomplete measurement very close to the standard bases, but that allows him to save a little bit of the information in the photon π_{i} in such a way that he can later exploit that leftover information and the fact that he learns Alice’s bases to gather significant information on both b_{0} and b_{1}. This seems extremely unlikely since those measurements would have to be close enough to the standard ones so that Bob would still be able to satisfy Alice’s checks, but such that the leftover information is still rather large. Unfortunately, at this time we do not have a complete proof that such a thing is impossible. Indeed, this problem is more or less equivalent to showing that the quantum key distribution protocol of Bennett and Brassard [2] cannot be attacked in a similar fashion.

6 Remarks

First, notice that the protocol can be used directly to implement a one-out-of-three Oblivious Transfer (\binom{3}{1}–OT_{2}) since at step 3 Bob could build three sets I_{0}, I_{1} and I_{2} of size n/3 instead of only the first two and thus receive one bit out of three. This may be useful in certain applications.

Also, it may seem a limitation that a Quantum Bit Commitment is used from Bob to Alice in the current protocol as it implies that the quantum channel is implemented in both directions. As a matter of fact, it is as easy to get a protocol that will have photons only flowing from Bob to Alice as suggested by the following variation of the protocol. Based on a simple observation of Louis Salvail, this protocol uses the fact that the distribution of the r′_{i}’s and β′_{i}’s with respect to the r_{i}’s and β_{i}’s is the same whether the photons flow from Alice to Bob or vice versa. This protocol is exactly the same as Protocol 5.1 except for the first step, which is accomplished in the reverse direction.

Protocol 6.1 ( \binom{2}{1}–OT_{2}(b_{0}, b_{1})(c) )

1: DO_{i=1}^{2n}
• Bob picks a random bit r′_{i} ← \begin{matrix}c \\ ◯ \end{matrix}^{|}
• Bob picks a random bit β′_{i} ← \begin{matrix}c \\ ◯ \end{matrix}^{|} and defines his emission basis (|θ_{i}⟩, |θ_{i}^{⊥}⟩) ← [↔ ↕ , ↗ ↙ ↘ ↖]_{β′_{i}}
• Bob sends to Alice a photon π_{i} with polarization [|θ_{i}⟩, |θ_{i}^{⊥}⟩]_{r′_{i}}
• Alice picks a random bit β_{i} ← \begin{matrix}c \\ ◯ \end{matrix}^{|} and measures photon π_{i} in basis (|φ_{i}⟩, |φ_{i}^{⊥}⟩) ← [↔ ↕ , ↗ ↙ ↘ ↖]_{β_{i}}
• Alice sets r_{i} ← \{ \begin{matrix}0 & if π_{i} is observed as |φ_{i}⟩ \\ 1 & if π_{i} is observed as |φ_{i}^{⊥}⟩ \end{matrix}

...

The fact that the protocol for \binom{2}{1}–OT_{2} in one direction is sufficient to accomplish the same protocol in the reverse direction has been established earlier in the literature by Crépeau and Sántha [11]. Therefore more elaborate protocols involving \binom{2}{1}–OT_{2} in both directions can be implemented with photons flowing in a single direction.

7 Conclusion and Open Questions

We have presented in this paper a protocol for \binom{2}{1}–OT_{2} based on quantum physics that is proven secure as long as the parties are not allowed to store photons or more precisely the quantum information they carry. We have also presented an improved protocol that apparently removes this restriction but it remains an open problem to provide a proof of this claim. Again, this open problem is very similar to the open problem of demonstrating the security of the quantum key distribution protocol of Bennett and Brassard [2] at very low error rates.

This paper has not considered the fact that the actual quantum channel [2] is not error-free and the fact that single photons are hard to generate. These problems are treated in [4].

Acknowledgements

I wish to thank Charles H. Bennett, Gilles Brassard, Artur Ekert, Richard Jozsa, Joe Kilian, Denis Langlois, Silvio Micali, Louis Salvail, Marie–Hélène Skubiszewska, and an anonymous referee for support, suggestions and comments at different stages of this work. I would also like to thank the Rank Foundation (England), the I.S.I. & Elsag-Baley (Italy), and the I.E.S.S. (Germany) for making possible the 1993 workshops on quantum information theory and quantum cryptography that made such research and the writing of this paper possible.

References

[1] Bennett, C. H. and Brassard, G., “Quantum cryptography: Public-key distribution and coin tossing”, In Proceedings of the International Conference on Computers, Systems and Signal Processing, Bangalore, India, December 1984, pp. 175 – 179.

[2] Bennett, C. H., Bessette, F., Brassard, G., Salvail, L. and Smolin, J., “Experimental quantum cryptography”, Journal of Cryptology, vol. 5, 1992, pp. 3 – 28.

[3] Bennett, C. H., Brassard, G., Breidbart, S. and Wiesner, S., “Quantum cryptography, or unforgeable subway tokens”, In Proceedings of Crypto 82, Plenum Press, 1982, pp. 267 – 275.

[4] Bennett, C. H., Brassard, G., Crépeau, C. and Skubiszewska, M.–H., “Practical quantum oblivious transfer”, In Advances in Cryptology: Proceedings of Crypto ’91, Lecture Notes in Computer Science, Vol. 576, pp. 351–366. Springer-Verlag, 1992.

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

[6] Brassard, G., Crépeau, C. and Robert, J.–M., “Information theoretic reductions among disclosure problems”, In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science, November 1986, pp. 168 – 173.

[7] Crépeau, C., “Equivalence between two flavours of oblivious transfers”, In Advances in Cryptology: Proceedings of Crypto ’87, Lecture Notes in Computer Science, August 1987, pp. 350 – 354.

[8] Crépeau, C., Correct and Private Reductions among Oblivious Transfers, Ph.D. Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, February 1990.

[9] Crépeau, C. and Kilian, J., “Achieving oblivious transfer using weakened security assumptions”, In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, October 1988, pp. 42 – 52.

[10] Crépeau, C. and Sántha, M., “Efficient reduction among oblivious transfer protocols based on new self-intersecting codes”, In Proceedings of Sequences 91: Methods in Communication, Security and Computer Science, June 1991, pp. 360 – 368, Springer – Verlag.

[11] Crépeau, C. and Sántha, M., “On the reversibility of oblivious transfer”, In Advances in Cryptology: Proceedings of Eurocrypt ’91, volume 547 of Lecture Notes in Computer Science, pp. 106–113, Springer-Verlag, 1991.

[12] Even, S., Goldreich, O. and Lempel, A., “A randomized protocol for signing contracts”, Communications of the ACM, vol. 28, 1985, pp. 637 – 647.

[13] Goldreich, O., Micali, S. and Wigderson, A., “How to play any mental game, or: A completeness theorem for protocols with honest majority”, In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, May 1987, pp. 218 – 229.

[14] Kilian, J., “Founding cryptography on oblivious transfer”, In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 1988, pp. 20 – 31.

[15] Kranakis, E., Primality and Cryptography, Wiley–Teubner Series in Computer Science, 1986.

[16] Rabin, M. O., “How to exchange secrets by oblivious transfer”, technical report tr–81, Aiken Computation Laboratory, Harvard University, 1981.

[17] Wiesner, S., “Conjugate coding”, Sigact News, vol. 15, no. 1, 1983, pp. 78 – 88; Manuscript written circa 1970, unpublished until it appeared in SIGACT News.

[18] Yao, A. C.–C., “Protocols for secure computations”, In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, November 1982, pp. 160 – 164.