Quantum Oblivious Mutual Identification

Claude Crépeau^{1}^{2} and Louis Salvail^{2}

1 LIENS, (CNRS ura1327) École Normale Supérieure, 45 rue d’Ulm, 75230 Paris CÉDEX 05, France. e-mail: crepeau@dmi.ens.fr. 2 Département d’Informatique et R.O., Université de Montréal, C.P. 6128, succursale centre-ville, Montréal (Québec), Canada H3C 3J7. e-mail: salvail@iro.umontreal.ca.

Abstract. We consider a situation where two parties, Alice and Bob, share a common secret string and would like to mutually check their knowledge of that string. We describe a simple and efficient protocol based on the exchange of quantum information to check mutual knowledge of a common string in such a way that honest parties will always succeed in convincing each other, while a dishonest party interacting with an honest party will have vanishingly small probability of convincing him. Moreover, a dishonest party gains only a very small amount of information about the secret string from running the protocol: whoever enters the protocol with no knowledge of the secret string would have to enter this protocol an exponential number of times in order to gain non-negligible information about the string. Our scheme offers an efficient identification technique with a security that depends on no computational assumption, only on the correctness of quantum mechanics. We believe such a system should be used in smartcards to avoid frauds from typing PIN codes to dishonest teller machines.

1 Introduction

Weren’t you worried the last time you typed your PIN (Personal Identification Number) to an unknown teller machine that it could be a fake and that its sole purpose could be to steal your PIN? According to a recent headline of the NY Times [26] maybe you should worry:

“One Less Thing to Believe In: Fraud at Fake Cash Machine”

The problem with current identification systems is that the customer must trust the equipment to which he types his PIN. It is completely trivial to modify a teller machine to memorize the PIN numbers that people type to it. PINs are meant to be checked, not given. (Consult [1] for an extensive study of frauds at teller machines.)

Of course, it is always possible to completely solve the problem of identification and authentication of messages by classical methods [9] that require exchanging passwords which length are proportional to the number of uses. Unfortunately, this is completely impractical: we want to rely on the existence of a short secret to check identity.

A similar approach has been suggested in a computational model through the construction of pseudo-random generators [7] or pseudo-random families of functions [17] which requires only short secrets seeds. These solutions make sense only in a context where we put computational restrictions on the participants. For powerful parties it is trivial to fake identities.

In the computational model, more sophisticated tools were developed for this purpose: Zero-Knowledge Proofs of Identity [15] introduced in order to provide means by which an honest party may convince another party of his identity in a way that cannot be replayed successfully to another party. This is true even if the verifying party tries his best to extract valuable information out of the proving party. Moreover, a dishonest party attempting to prove an invalid identity will be detected by the verifying party except with vanishingly small probability.

Non-Computational Protocols

The major drawback with these proofs and other computational techniques is that deep down their security must rely on some computational assumption: the proof of knowledge can be checked if the identifying string is the solution to some hard public problem. If one can solve this problem, he can fake identities. This is the case even if we build the protocol from perfect cryptographic tools such as ideal Bit Commitment or ideal Oblivious Transfer.

In the current paper, we consider a situation where two parties, Alice and Bob, share a common secret string and would like to mutually check their knowledge of that string without disclosing it. This problem has been extensively studied by Fagin, Naor and Winkler [14] who provide a large number of scenarios where the problem may be considered. From the cryptographic point of view only one of their solutions may be considered secure: a solution based on the existence of a one-out-of-two Oblivious Transfer [13] which uses Ω(n^{2}) Transfers to do the job for an n-bit secret string.

We describe a simple and efficient protocol based on the exchange of quantum information to check mutual knowledge of a common string in such a way that honest parties will always succeed in convincing each other (except with vanishingly small probability), while a dishonest party interacting with an honest party will have only vanishingly small probability of convincing him. Moreover, a dishonest party gains only a very small amount of information about the secret string from running the protocol: whoever enters the protocol with no knowledge of the secret string would have to enter this protocol an exponential number of times in order to gain non-negligible information about the string.

Our scheme, based on coding theory, depends on no computational assumption, has a total running time of O(n^{2.376}) and a total of O(n^{2}) photons are transmitted (if implemented with a one-out-of-two Oblivious Transfer, only O(n) such Transfers are necessary). We also present a scheme which uses only O(n) photons but that cannot tolerate the transmission errors of a real quantum channel. We suggest the reader consults [8] for more details of quantum cryptography.

We believe such a system should be used in smartcards to avoid frauds from typing PIN codes to dishonest teller machines. A PIN could still be used to activate the functions of the card but it should be typed directly to the card (a device you might as well trust since your bank gives it to you, and they have your money anyway!). The card would identify itself with tellers only through our mechanism: no PIN ever exchanged.

The practical difficulty of our scheme is to embed the necessary technology for the Quantum Oblivious Transfer on a card. Since none of the technology is very fancy we believe such cards could be mass produced (see Section 4.6).

2 Preliminaries

2.1 Notations and Tools

For b ∈ \{0, 1\} we define the selection function (x, y)_{[b]} = \{ \begin{matrix}x & if b = 0 \\ y & if b = 1 \end{matrix} where

x and y are scalars. In general, if x and y are vectors with n components and b ∈ {0, 1}^{n} then (x, y)_{[b]} is the concatenation of (x_{i}, y_{i})_{[b_{i}]} for all i ∈ {1, 2, …, n}. If we use a single x instead of a pair then (x)_{[b]} is the concatenation of the x_{i}’s for b_{i} = 1. For instance (1001)_{[1010]} = 10. We denote by Δ(s, ŝ) the Hamming distance between s and ŝ.

Now let us define what we mean by a secure identification protocol in our context. Suppose ϕ_{(n)} ∈_{R} {0, 1}^{n} is the secret information shared by Alice and Bob. In the following we write Bob^{∗} (resp. Alice^{∗}) to designate somebody trying to impersonate Bob (resp. Alice).

Definition 1. Bob^{∗} (or Alice^{∗}) has almost no information about ϕ indexed by a security parameter n, ϕ = {ϕ_{(n)} ∈_{R} {0, 1}^{n}}_{n>0}, if Bob^{∗}’s (or Alice^{∗}’s) information about ϕ can be modeled by a set Φ = {Φ_{(n)} ⊆ {0, 1}^{n}}_{n>0} such that for some α > 0 and all sufficiently large n we have:

\frac{#Φ_{(n)}}{#\{0, 1\}^{n}} ≥ 1 − 2^{−αn} and P (ϕ_{(n)} ∉ Φ_{(n)}) < 2^{−αn}

and for each ϕ′ ∈ Φ_{(n)} we have:

P (ϕ_{(n)} = ϕ′|ϕ_{(n)} ∈ Φ_{(n)}) = \frac{1}{#Φ_{(n)}} .

The Shannon information given by Φ about ϕ is such that

I(ϕ_{(n)}|Φ_{(n)}) ≤ 2^{−_{α}n}, α̂ > 0.

Without loss of generality, we use ϕ for an instance ϕ_{(n)} whenever the context permits. We denote by ϕ_{i} the ith bit of ϕ.

An identification scheme hides the secret information ϕ if when a cheating party runs the protocol with no information about ϕ he ends up with almost no information about ϕ.

Definition 2. An identification scheme hides the secret information ϕ shared by Alice and Bob, if for some α′ > 0, when Bob^{∗} (or Alice^{∗}), who starts with no information about ϕ, cheats the protocol poly(n) times, he has probability greater than 1 − 2^{−α′n} to end up with almost no information about ϕ.

The random variable ϕ^{∗} denotes the choice made by Alice^{∗} or Bob^{∗} to run the protocol given that she (or he) has almost no information about ϕ.

If a malicious party P^{∗} has almost no information about ϕ then he cannot guess any bit ϕ_{i} with non-negligible bias.

Property 1 If P^{∗} has almost no information about ϕ = {ϕ_{(n)} ∈_{R} {0, 1}^{n}}_{n>0} there exists β > 0 such that for all ϕ^{∗} ∈ {0, 1}^{n} and each position i independently, |P (ϕ_{i}^{∗} = ϕ_{i}) − \frac{1}{2}| ≤ 2^{−βn}.

If P^{∗} has almost no information about ϕ and executes a protocol leaking almost no information about ϕ then P^{∗} has still almost no information.

Property 2 If Φ_{0}, Φ_{1} are two sets that give almost no information about ϕ then Φ = Φ_{0} ∩ Φ_{1} gives almost no information about ϕ.

These two properties are straightforward applications of the above definitions.

2.2 Simple Quantum Transmission

In this paper we consider the most simple idealization of a quantum transmission. There is only four different ways to transmit photons corresponding to the four polarization angles 0^{∘}, 45^{∘}, 90^{∘}, 135^{∘} that we denote |↔⟩, | ↗ ↙ ⟩, |↕ ⟩, | ↘ ↖ ⟩ respectively. If Alice wants to send b ∈ {0, 1}, she used the following encoding rules:

1. b = 0 is randomly encoded by |↔⟩ or | ↗ ↙ ⟩.

2. b = 1 is randomly encoded by |↕ ⟩ or | ↘ ↖ ⟩.

At the receiving end Bob chooses how he measures the incoming photon either by reading it in rectilinear basis (|↔⟩, |↕ ⟩), denoted ↔ ↕, or in the diagonal basis (| ↗ ↙ ⟩, | ↘ ↖ ⟩), denoted ↗ ↙ ↘ ↖. We suppose this is the only choice he can make. If the photon π encodes a bit b in the rectilinear (resp. diagonal) basis and the receiver measures it in the rectilinear (resp. diagonal) basis then he gets the bit b (except if an error occurred during transmission). If π is measured in the diagonal (resp. in the rectilinear) basis then a random bit is received. For a basis ϕ ∈ {↔ ↕ , ↗ ↙ ↘ ↖ } and a bit b we write ϕ_{[b]} for the transmission of the encoded bit b in a photon polarized in the basis ϕ. For more details about how quantum transmission works in general consult [8].

3 A basic quantum identification

Suppose Alice and Bob who have the secret string ϕ^{A} and ϕ^{B} respectively want to test whether ϕ^{A} = ϕ^{B} without revealing their values. In order to achieve this, they are willing to use quantum and public channels. The transmission of c ∈_{R} {0, 1} polarized in basis ϕ ∈_{R} {↔ ↕ , ↗ ↙ ↘ ↖ } hides all information about ϕ to anybody who has almost no a priori information on the values of c and ϕ. This suggests the use of the secret ϕ^{A} to encode securely the transmission basis.

Suppose Alice and Bob share ϕ = ϕ^{A} = ϕ^{B} ∈_{R} {↔ ↕ , ↗ ↙ ↘ ↖ }^{n}. In order for Alice to prove to Bob that she knows ϕ, she could transmit a random string c taken from a sparse but large subset of {0, 1}^{n} polarized in basis ϕ. Therefore, it suffices for Alice to choose a random codeword c from a code C_{n} which she sends to Bob. He then measures it in ϕ to obtain the decoded string ĉ. If the quantum channel is noiseless then ĉ = c. (In the more realistic case, the quantum channel would be modeled as a binary symmetric channel with parameter ϵ.) If there is a large number of codewords in C_{n} it could be the case that measuring c in basis ϕ^{∗} hides almost all information about ϕ. Conversely if Alice does not know ϕ it could be very unlikely that she succeeds to send ĉ close to a codeword c, as long as codewords are not too close to each other. Protocol ident(ϕ^{A}, ϕ^{B}), shown below, implements this idea given ϵ the error rates of the quantum channel.

Protocol 3.1 ( ident(ϕ^{A}, ϕ^{B}) )

1: Alice and Bob agree on a binary linear (n, k_{n}, d_{n})-code C_{n} ∈ C by specifying a generating matrix G for C_{n}. 2: Alice chooses a random word x ∈R {0, 1}^{k_{n}} and takes c = xG.

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

– Alice sends to Bob a photon polarized in ϕ_{i}^{A}_{[c_{i}]}.

– Bob measures the incoming photon in the basis ϕ_{i}^{B} and obtains ĉ_{i}. 4: Bob accepts if when decoding ĉ, he obtains c′ ∈ C_{n} such that Δ(c′, ĉ) ≤ (ϵ + ϵ_{0})n for ϵ_{0} > 0.

Suppose Alice and Bob share the same private sequence ϕ = ϕ^{A} = ϕ^{B}. This implies that, for any ϵ_{0} > 0 and except with vanishingly small probability, Bob will decode ĉ as c which is at Hamming distance less than (ϵ + ϵ_{0})n from ĉ given n sufficiently large.

Now consider a malicious Alice (denoted by Alice^{∗}) is trying to impersonate the real Alice. We assume that Alice^{∗} knows almost nothing about ϕ^{B} at the beginning. Therefore she will have roughly half the positions different from Bob and thus sends random bits in half the positions. It is easy to show that if the minimum distance d_{n} of C_{n} is such that d_{n} > 2n(ϵ + ϵ_{0}), Alice^{∗} will be detected with probability greater than 1 − 2^{−αn} for α > 0. By this attempt, she will not learn more than a vanishingly small amount of Shannon information about ϕ^{B}.

3.1 ident(ϕ, ϕ^{∗}) with a dishonest Bob

Let ϕ ∈_{R} {↔ ↕ , ↗ ↙ ↘ ↖ }^{n} be Alice’s secret and let c be the transmitted random codeword taken from C_{n}. Bob^{∗} chooses a set of bases ϕ^{∗} and measures each photon i in the basis ϕ_{i}^{∗} in order to obtain ĉ. Roughly speaking, one half of the bases of ϕ^{∗} will match with the bases of ϕ. Thus approximatively half of the bits he will receive are the bits of the codeword sent by Alice. The other bits (the positions i for which ϕ_{i} ≠ ϕ_{i}^{∗}) are not correlated with the bits transmitted. For Bob^{∗} to be unable to determine a substantial amount of information about ϕ, the code must be chosen so that any half of the bits of the codewords are purely random. Hence, if the proportion of the bits Bob^{∗} sees about a codeword is random and the rest of the bits he received are not correlated (thus random) the thing he gets is a purely random string. Given that the same would happend for all but a few ϕ^{∗} almost no further information about ϕ can be determined.

A similar concept in a different setting was studied by [4],[24] ((n, j, k)– functions) and [10] (t–resilient functions). The next definition is taken from [4].

Definition 3 [4]. For any integers n, j, k such that n ≥ j + k, j > 0 and k > 0, a function f : GF (Q)^{n} → GF (Q)^{j} is (n, j, k) if, no matter how one fixes any k of its inputs, each of the Q^{j} outputs can be produced in exactly Q^{n−j−k} different ways by varying the remaining n − k symbols.

If each symbol of f(x) is obtained by computing a weighted sum on a subset of the digits in x then f(x) is said to be xor-(n, j, k). In [4] the function f is from n–bit strings to j–bit strings, here we consider an arbitrary field. The following theorem showing how to construct (n, j, k)–functions, was originally proved for functions over binary strings. It is straightforward to generalize it to functions over arbitrary fields.

Theorem 4 [4]. For a set of values (n, j, k), there exists an xor-(n, j, k)-function from GF (Q)^{n} to GF (Q)^{j} if and only if there exists an [n, j, k + 1] linear codes C_{n} over GF (Q).

If G is the generating matrix of a [n, j, k + 1]-code C_{n} then the function f(x) = Gx^{T} (x^{T} is x transposed) is xor − (n, j, k). Saying that f is (n, j, k) implies that f^{−1}(x) is a set which have uniform projection on any k coordinates [10]:

Definition 5 [10]. A set S ⊆ GF (Q)^{n} has a uniform projection on any j components if for all ω ∈ {0, 1}^{n} of weight j and all a ∈ GF (Q)^{k}, the set S_{ω,a} = \{x ∈ S : (⊥, x)_{[ω]} = a\} is such that #S_{ω,a} = \frac{#S}{Q^{k}}.

If f(x) = Gx^{T} is (n, j, k) then f^{−1}(x) = Hx^{T}, where H is the parity check matrix for C_{n}. The matrix H is also the generating matrix for the dual C_{n}^{⊥} of C_{n}. The next theorem makes the connection between uniform projections and some conditions on the dual of the codes C_{n}.

Theorem 6. If there exists a family of codes C = {C_{n}}_{n>0} such that for n sufficiently large the dual C_{n}^{⊥} of C_{n} has minimum distance d′_{n} with \frac{d′_{n}}{n} ≥ ζ > \frac{1}{2}, protocol ident(ϕ^{A}, ϕ^{∗}) hides almost all information about ϕ^{A} to Bob^{∗} except with probability exponentially small in n. This holds given an idealized quantum transmission.

proof sketch: By property 1, except with vanishingly small probability Δ(ϕ^{∗}, ϕ^{A}) ≥ (1 − ζ)n. Thus, the number of positions for which Bob^{∗} sees the bits of c is less than ζn. Let H be the generating matrix for C_{n}^{⊥} of minimum distance ζn. The function Hx^{T} has uniform projection on any ζn components. Thus, any ζn bits of a codeword c (those for which Hc^{T} = 0) are random when c ∈_{R} C_{n}. Since the other (1 − ζ)n positions are random, the string ĉ he received is purely random. Therefore, the set Φ_{1} = {ϕ|Δ(ϕ, ϕ^{∗}) ≥ (1 − ζ)n} models the knowledge leaked to Bob^{∗} by the actual execution of the protocol. It is easy to show that Φ_{1} gives almost no information about ϕ. Let Φ_{0} be the model for Bob^{∗}’s knowledge about ϕ^{A} before the actual execution. The set Φ = Φ_{0} ∩ Φ_{1} models Bob^{∗}’s knowledge after the current execution given he had almost no information when entering the protocol. By property 2 the set Φ gives almost no information about ϕ^{A}. For Bob^{∗} executing poly(n) times the protocol, the set

Φ = ⋂_{i=1}^{poly(n)} Φ_{i}

where Φ_{i} models the information leaked about ϕ for the ith execution gives almost no information about ϕ^{A}. We conclude that ident(ϕ^{A}, ϕ^{∗}) hides almost all information about ϕ^{A} to Bob^{∗}. ⊓ ⊔

3.2 Code Properties

Over the last few sections we have suggested some conditions on our codes. Let us now summarize the properties that families of codes C must satisfy to guarantee the security of protocol ident(ϕ^{A}, ϕ^{B}) while preserving efficiency of the scheme.

1. Given our mode of transmission via the quantum channel, we want C to be a family of binary codes.

2. Each C_{n} ∈ C must be efficiently constructible and efficiently decodable.

3. Each C_{n} ∈ C must have minimal distance d_{n} such that \frac{d_{n}}{n} ≥ 2(ϵ + ϵ_{0}) for ϵ_{0} > 0.

4. The dual C_{n}^{⊥} of C_{n} ∈ C must have minimal distance d′_{n} such that \frac{d′_{n}}{n} ≥ ζ for ζ > \frac{1}{2}.

The set of conditions above is bad news. First of all, these conditions cannot be satisfied because of Plotkin’s bound on codes [20] when ζ > \frac{1}{2}. Fortunately, modifications to the protocol (for instance by using more than two transmission bases) open the possibility of relaxing this condition to ζ > 0. But even then, no known family of codes satisfies these four conditions at once. It is nevertheless easy to find codes meeting any three of them. For instance, concatenated codes [16] achieve conditions 1, 2 and 3, random binary linear codes meet conditions 1,3 and 4, while Reed-Solomon codes meet 2,3 and 4.

It is common in coding theory to take care of arbitrary long messages via block codes. These codes are of no help in our setting because their duals have small minimum distance. This is easy to see since it is sufficient to observe a constant number of bits to tell if a word is a candidate codeword or not.

On top of these problems due to coding theory, more fundamental problems arise from our protocol: we have made a very strong assumption that Alice^{∗} and Bob^{∗} send and receive photons in only two possible bases. In reality we would have to deal with the fact that they can use very different quantum states and quantum measurements. It is indeed completely unknown to us if this protocol is safe under these general conditions.

The main problem in quantum cryptography is to provide proofs for the security of cryptographic primitives assuming the most general quantum measurements an opponent could make. Nevertheless, the full security of the quantum bit commitment primitive has been obtained in [5] and quantum oblivious transfer has been shown secure against a large set of measurements[21]. Basing our identification scheme on such primitives gives more freedom on the codes while, at the same price, providing security against any quantum measurements. Oblivious transfer has already been used by [14] to solve the problem of identification. In the next section, we present a different solution based on quantum oblivious transfer and theorem 6.

4 The Final Protocol

No existing family of codes meets the four conditions above. One way around this problem is to drop condition 1. To do so we need a means of transferring elements of a larger field GF (Q) at once. This is exactly the purpose of a \binom{2}{1}–OST, a One-Out-of-Two Oblivious String Transfer [11]. We can thus modify our protocol to use this primitive instead of the quantum transmission of section 3. A nice side effect of this modification is that transmission errors also go away.

Doing this modification is not very costly since a \binom{2}{1}–OST can be implemented using a constant number of \binom{2}{1}–OT_{2} [11], which in turn can be obtained from the quantum transmission [6]. The solution we describe next works over GF (4) (and thus we use a \binom{2}{1}–OT_{4}).

The Appendix provides a modified protocol (from [6]) for Quantum Oblivious Transfer (\binom{2}{1}–OT_{4}) sufficient for this application. That protocol also relies on the existence of a bit commitment. To avoid computational assumptions again at that level we recommend using the Quantum Bit Commitment Scheme of [5]. The protocol of the next subsection combined with the one from the Appendix constitute the complete Quantum Oblivious Mutual Identification.

4.1 Protocol

Suppose Alice and Bob share ϕ = ϕ^{A} = ϕ^{B} ∈_{R} {0, 1}^{n}. In order for Alice to prove to Bob that she knows ϕ, she transmits a random string c taken from a sparse but large set C, in such a way that if they agree on the same ϕ he receives c and verifies that it belongs to C, but otherwise receives a rather random string which is unlikely to be in C.

More precisely, let M be a random n × k matrix over GF (4). (In banking applications, M is chosen by the bank and may be made public.) Let C_{n} be the [n, k_{n}, d_{n}] linear code over GF (4) generated by M. Let C_{n}^{⊥} be the [n, n − k_{n}, d′_{n}] linear code over GF (4) dual to C_{n}.

Protocol 4.1 ( identOT (ϕ^{A})(ϕ^{B}) )

1: Alice picks r, s ∈R {00, 01, 10, 11}^{n}.
2: DO_{i=1}^{n} Alice runs \binom{2}{1}–OT_{4}(r_{i}, s_{i})(ϕ_{i}^{B}) with Bob who receives v_{i}.
3: Bob picks x, y ∈R {00, 01, 10, 11}^{n} and announces it to Alice.
4: Alice picks c ∈R C_{n}, computes and sends u ← c ⊕ (r ⊕ x, s ⊕ y)_{[ϕ^{A}]}.
5: Bob accepts only if u ⊕ v ⊕ (x, y)_{[ϕ^{B}]} ∈ C_{n}.

In the above protocol, in contrast to protocol 3.1, the randomization of step 3 is necessary because the \binom{2}{1}–OT_{4} no longer provides the fact that a random element is obtained when ϕ_{i}^{∗} ≠ ϕ_{i}^{B}, and we do not want Alice to take advantage of that fact. From the previous sections it is now easy to see why the protocol is correct and secure.

4.2 identOT (ϕ, ϕ) with honest parties

If Alice and Bob share the same private sequence ϕ = ϕ^{A} = ϕ^{B} then

u ⊕ v ⊕ (x, y)_{[ϕ]} = c ⊕ (r ⊕ x, s ⊕ y)_{[ϕ]} ⊕ (r, s)_{[ϕ]} ⊕ (x, y)_{[ϕ]} = c.

Therefore Bob accepts.

4.3 identOT (ϕ^{∗}, ϕ^{B}) with a dishonest Alice

Suppose a malicious Alice (denoted by Alice^{∗}) tries to impersonate the real Alice. We assume that Alice^{∗} knows almost nothing about ϕ^{B} at the beginning. This section specifies code parameters that allow Bob to reject Alice^{∗} with probability exponentially close to one.

Now we show how to choose the parameter k of code in order to eliminate the chances that Alice^{∗} identify as Alice successfully.

Theorem 7. If d_{n} ∈ Ω(n) Bob will reject Alice^{∗} except with probability exponentially small in n. proof sketch: Bob’s final calculation is u ⊕ v ⊕ (x, y)_{[ϕ^{B}]} which by definition of v is u ⊕ (r ⊕ x, s ⊕ y)_{[ϕ^{B}]}. Alice^{∗}, who knows r, s, x, y may try to choose a u cleverly to make this a codeword for as many ϕ^{B} as possible. We show this is not possible.

First notice that for any fixed r, s, when x, y are uniformly chosen at random Δ(r⊕x, s⊕y) ≈ 3n/4. By the assumption that Alice^{∗} has almost no information about ϕ^{B} we know that the number of equally likely candidates for ϕ^{B} is roughly 2^{n}. Fix a u and a ϕ^{B} and assume the corresponding word has syndrome S. We know that all the ϕ′ that are different from ϕ^{B} in the positions where r ⊕ x and s ⊕ y are the same will not change the result of the calculation. Therefore roughly 2^{n/4} values of ϕ^{B} will yield the same result with syndrome S.

On the other hand, any ϕ′ that differ from ϕ^{B} in positions where r⊕x and s⊕y are different will yield a different result. As long as the number of differences is no more than d_{n}/2 the resulting words cannot have the same syndrome because this would imply that the code contains a word of weight less than d_{n} and no other word of syndrome S can be closer than the one we started from. Therefore 2^{n/4} ∑_{i=1}^{d_{n}/2} \binom{3n/4}{i} possibilities for ϕ^{B} will yield results of another syndrome and each of these is associated to a single word of syndrome S.

In conclusion, for any fixed u and S, there is always at least ∑_{i=1}^{d_{n}/2} \binom{3n/4}{i} times more possibilities for ϕ^{B} that do not yield a word of syndrome S than those that yield a word of syndrome S. If d_{n} ≥ 2δn for some constant δ, this value is roughly 2^{\frac{3H(δ)}{4} n}. Therefore the probability that Alice^{∗} gets Bob to accept is no more than 2^{−αn} with α = 3H(δ)/4.

⊓ ⊔

We need to know more than just the fact that Alice^{∗} will fail most of the time: we show that in the case of failure she cannot learn much about ϕ_{B}.

Theorem 8. If d_{n} ∈ Ω(n) Alice^{∗} learns almost nothing about ϕ_{B}, except with probability exponentially small in n.

proof sketch: By the same counting argument as above, there cannot be more than 2^{(1−3h(ϵ)/4)n} possibilities of ϕ_{B} that would yield codewords. When rejected, Alice^{∗}’s only gain in knowledge is that the real ϕ_{B} was not one of those. Thus she can eliminate only that many strings. ⊓ ⊔

The consequence of these theorems is that with probability 1 − 2^{−αn} Alice will be rejected and in that case she may discard only 2^{(1−3h(ϵ)/4)n} strings as candidates for ϕ^{B}. She will thus still have almost no information about ϕ^{B} even after discarding poly(n) × 2^{(1−3h(ϵ)/4)n} strings.

4.4 identOT (ϕ^{A}, ϕ^{∗}) with a dishonest Bob

Now we analyze the situation from the point of view of an honest Alice facing a malicious Bob^{∗}.

Theorem 9. Except with exponentially small probability in n, Protocol identOT (ϕ) hides all information about ϕ^{A} to Bob^{∗} if the code is a [n, k_{n}, d_{n}]–code with a dual [n, n − k_{n}, d′_{n}]–code such that d′_{n} ≥ (\frac{1}{2} + γ)n for 0 < γ < \frac{1}{2}. proof sketch: For each position i such that ϕ_{i}^{∗} = ϕ_{i}^{A}, Bob will get the codeword position c_{i} of c. The #\{i|ϕ_{i}^{A} = ϕ_{i}^{∗}\} is at most (\frac{1}{2} + γ)n except with probability smaller than 2e^{−γ^{2}n}. The remaining positions (j) of (x, y)_{[ϕ^{B}]} ⊕u⊕v for ϕ_{j}^{∗} ≠ ϕ_{j}^{A} are not correlated with c_{j} as long as r and s were originally chosen at random. Since the dual has minimum distance d′ > (\frac{1}{2} + γ)n we conclude that theorem 6 applies and that Protocol IdentOT hides the information ϕ^{A} to Bob^{∗}. ⊓ ⊔

Example: Codes with such properties exist over GF (4). For instance, a random n × 0.91n 4-ary matrix is likely to define a [n, 0.91n, 0.02n] code with a [n, 0.09n, 0.52n] dual code. Assymptoticaly, the probability that such a matrix do not define a code with these parameters is exponentially small in n.

4.5 Complexity

Protocol 4.1 runs in time O(n^{2}) (to choose a codeword) and uses O(n) \binom{2}{1}–OT_{4}, where n is the security parameter. When combined with the sub-protocol from the Appendix the total running time of the final protocol becomes O(n^{3}) and a total of O(n^{2}) photons are transmitted. The running time decreases to O(n^{2.376}) if more efficient codes such as the Superconcentrator Codes of Spielman [25] are used in the protocol of the Appendix in both the Oblivious Transfer and the Bit Commitment (time O(n^{2})) and if all the commitments are done at once in order to save on the time necessary to compute the hash function (O(n) products of a vector by a matrix with a total of O(n^{3}) operations may be replaced by a matrix product which takes only time O(n^{2.376})).

We must point out that despite the fact that our Protocol 4.1 is more efficient than that of Fagin, Naor and Winkler [14] in terms of \binom{2}{1}–OT_{2}, when used together with the Quantum Oblivious Transfer their protocol can be made as efficient as ours in terms of photons. This is because their protocol requires n transfers of n-bit strings (which implies Ω(n^{2}) \binom{2}{1}–OT_{2}) while our protocol requires only n transfers of 2-bit strings (which can be done with O(n) \binom{2}{1}–OT_{2}). The fact is that the Quantum Oblivious Transfer can be used to transfer 1, 2 or up to O(n) bits at no extra cost. In order to have a real gain in terms of photons transmitted we need a Quantum O-T that requires only a constant number of photons to transfer a constant number of bits (see open problem 3).

4.6 Implementation Remarks

The protocol from the appendix uses quantum transmission both for Oblivious Transfer and Bit Commitment. At first glance, it seems like the quantum transmission of data must go in both directions, since the Oblivious Transfer goes from Alice to Bob and the Bit Commitment goes the other way. As pointed out in [12], there is no need for photons traveling both ways. These two protocols may be implemented with the photons going in a single direction. It does not matter who send the photons to who, the same result can be achieved from them. (A similar idea was suggested by Hans-Joachim Knobloch [19].)

Because of the above remark, in a smartcard scenario it suffices to implement on the card the technology for sending polarized photons: a weak light source with a multiple polarizer system. As for the ATM it would have to use the more elaborate technology for making polarization measurements on the incoming photons. Since the distance between the sender and receiver could be of a few millimeters the actual error rate of the quantum transmission would be extremely low (error rates of 0.5% have been observed on hundreds of meters [22]).

5 Conclusion and Open Questions

We have presented a protocol for mutual identification based on the existence of an Oblivious Transfer and have shown improvements to the Quantum Oblivious Transfer in order to combine them in an efficient Quantum Mutual Identification Protocol. Here is a few open problems:

1. It would be interesting to show that the protocol of section 3 is secure even if the participants use arbitrarily complicated physics.

2. Find binary codes satisfying conditions 2,3, and 4.

3. Find a reduction of \binom{2}{1}–OST to the quantum transmission that requires only a constant number of photons per word of constant length.

4. Implement the necessary technology on a smartcard!

Acknowledgments

We would like to thank Thomas Beth, Gilles Brassard, Artur Ekert, Richard Jozsa, Denis Langlois, and Bill Wootters for their interest in this research.

References

1. Anderson, R.J., “Why Cryptosystems Fail”, in Proceedings of the 1993 ACM Conference in Computer and Communications Security pp 215 - 227

2. Ash, R., Information Theory, John Wiley & Sons, 1965.

3. Bennett, C.H., 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.

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

5. Brassard, G., 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.

6. Bennett, C.H., 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.

7. Brassard, G., On computationally secure authentication tags requiring short secret shared keys, Advances in Cryptology: Proceedings of CRYPTO 82, Plenum Press, 1983, pp.79–86.

8. Brassard, G., Cryptology column — Quantum cryptography: A bibliography, Sigact News, vol. 24, no. 3, 1993, pp.16–20.

9. Carter, J.L., M. N. Wegman, New Hash Functions and Their Use in Authentication and Set Equality, Journal of Computer and System Sciences, Vol. 22, 1981, pp. 265–279.

10. Chor, B., O. Goldreich, J. Hastad, J. Freidman, S. Rudich, R. Smolensky, The bit extraction problem or t–resilient functions, Proc. 26th IEEE Symposium on Foundation of Computer Science, Portland, Oregon, 1985, pp.396–407.

11. Crépeau, C. and M. Sántha. Efficient reductions among oblivious transfer protocols based on new self-intersecting codes. In Sequences II, Methods in Communications, Security, and Computer Science, pp. 360–368. Springer-Verlag, 1991.

12. Crépeau, C., Quantum Oblivious Transfer, Journal of Modern Optics, Dec. 1994.

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

14. Fagin, R., M. Naor and P. Winkler, Comparing Common Secret Information without Leaking it, submitted for publication, Communications of the ACM, 1994.

15. Fiat, A and A. Shamir. How to prove yourself: practical solutions to identification and signature problems. In A. M. Odlyzko, editor, Proceedings CRYPTO 86, pages 186–194. Springer, 1987. Lecture Notes in Computer Science No. 263.

16. Forney, G. D., Concatenated Codes, The M.I.T. Press, 1966.

17. Goldreich, O., S. Goldwasser, and S. Micali. How to construct random functions. In Proceedings of the 25th IEEE Symposium on Foundations of Computer Science, pp. 464–479, Singer Island, 1984. IEEE.

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

19. Knobloch, H.-J.,personal communication through T. Beth.

20. Mac Williams, F.J. and N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.

21. Mayers, D., L. Salvail, Quantum Oblivious Transfer is Secure Against Individual Measurements, In the Proceedings of PHYSCOMP 94, Dallas, 1994, pp. 69–77.

22. Muller, A., Breguet, J. and Gisin, N., Experimental demonstration of quantum cryptography using polarized photons in optical fiber over more than 1 km In Europhysics Letters, vol. 23, no. 6, 20 August 1993, pp..383–388.

23. Rabin, M. O., How to exchange secrets by oblivious transfer, Technical Memo TR–81, Aiken Computation Laboratory, Harvard University, 1981.

24. Robert, J.-M., Détection et correction d’erreur en cryptographie, Master thesis, Département d’informatique et de Recherche Opérationnelle, Université de Montréal, Montréal, Québec, Canada, 1985.

25. Spielman, D., Linear-time Codable and Decodable Error-Correcting Codes. In Proc. 27th ACM Symposium on Theory of Computing, 1995. ACM.

26. One Less Thing to Believe In: Fraud at Fake Cash Machine, New York Times, 13 May 1993, pp. A1 & B9.

Appendix

We refer the reader to [6, 5, 12] for more details on this protocol. Here ϵn is a limit on the number of errors that can be tolerated from real noise. The actual error rate ϵ′ should be less than ϵ in order to reject an honest Alice accidentally only with probability exponentially small in n.

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

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

– Alice picks r_{i} ∈R {0.1} and β_{i} ∈R {↔ ↕ , ↗ ↙ ↘ ↖ },

– Bob picks β′_{i} ∈R {↔ ↕ , ↗ ↙ ↘ ↖ },

– Alice sends to Bob a photon π_{i} with polarization β_{i[r_{i}]},

– Bob measures photon π_{i} in basis β′_{i} and obtains a bit r′_{i}. 2: Bob runs commit(r′_{1}r′_{2}...r′_{n}β′_{1}β′_{2}...β′_{n}) with Alice. 3: Alice picks a random bit t and announces it to Bob. 4: if t = 0 then

– Bob runs unveil(r′_{1}r′_{2}...r′_{n}β′_{1}β′_{2}...β′_{n}),

– Alice checks that #{i | β_{i} = β′_{i} and r_{i} ≠ r′_{i}} < ϵn,

– Alice and Bob restart the protocol. 5: Alice announces her choices β_{1}β_{2}...β_{n} to Bob. 6: Bob randomly selects two subsets I_{0}, I_{1} ⊂ {1, ..., n} subject to |I_{0}| = |I_{1}| = n/2, I_{0} ⋂ I_{1} = ∅ and ∀i ∈ I_{0}, β_{i} = β′_{i} or ∀i ∈ I_{1}, β_{i} ≠ β′_{i}, and announces I_{c}, Ic̄ to Alice.

7: Alice

– receives J_{0}, J_{1}, and defines w_{0} ← r_{j_{1}^{0}}r_{j_{2}^{0}}...r_{j_{n/2}^{0}} and w_{1} ← r_{j_{1}^{1}}r_{j_{2}^{1}}...r_{j_{n/2}^{1}}

with j_{l}^{b} ∈ J_{b} and j_{l}^{b} < j_{l+1}^{b} for b ∈ {0, 1} and 1 ≤ l < n/2,

– computes their syndromes S_{0} ← Syn(w_{0}) and S_{1} ← Syn(w_{1})

with respect to an agreed upon linear code C (consult [6] for details),

– picks a random privacy amplification function h : {0, 1}^{n/2} → {0, 1}^{2},

– computes q̂_{0} ← q_{0} ⊕ h(w_{0}) and q̂_{1} ← q_{1} ⊕ h(w_{1}),

– sends S_{0}, S_{1}, h, q̂_{0}, q̂_{1} to Bob.

8: Bob

– receives S_{0}, S_{1}, h, q̂_{0}, q̂_{1},

– computes a word ŵ of syndrome S_{c} using the decoding algorithm of C from word w′ = r′_{i_{1}}r′_{i_{2}}...r′_{i_{n/2}} with i_{l} ∈ I_{0} and i_{l} < i_{l+1} for 1 ≤ l < n/2,

– computes and returns q_{c} ← q̂_{c} ⊕ h(ŵ).

The privacy amplification function used in Step 7 can be a the concatenation of the XOR of two random subsets of the bits of its input. In the Bit Commitment protocol of Step 2, a single privacy amplification function can be used for all of them.

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