Efficient Cryptographic Protocols based on Noisy Channels

Claude Crépeau^{⋆}

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: crepeau@iro.umontreal.ca.

Abstract. The Wire-Tap Channel of Wyner [19] shows that a Binary Symmetric Channel may be used as a basis for exchanging a secret key, in a cryptographic scenario of two honest people facing an eavesdropper. Later Crépeau and Kilian [9] showed how a BSC may be used to implement Oblivious Transfer in a cryptographic scenario of two possibly dishonest people facing each other. Unfortunately this result is rather impractical as it requires Ω(n^{11}) bits to be transmitted through the BSC to accomplish a single OT. The current paper provides efficient protocols to achieve the cryptographic primitives of Bit Commitment and Oblivious Transfer based on the existence of a Binary Symmetric Channel. Our protocols respectively require sending O(n) and O(n^{3}) bits through the BSC. These results are based on a technique known as Generalized Privacy Amplification [1] that allow two people to extract secret information from partially compromised data.

1 Introduction

The cryptographic power of a noisy channel has been demonstrated by Wyner [19] who showed that two honest parties, say A and B, can exchange a secret key on which an eavesdropper E may obtain only a small fraction of the information as long as A and B are connected by a Binary Symmetric Channel of better quality than a similar Channel connecting them to E. More recently, a result of Bennett, Brassard, Crépeau and Maurer [1] provides a technique called Generalized Privacy Amplification to ensure that E’s information is an arbitrary small fraction of a bit under the same conditions.

But cryptography is no longer interested solely in protecting communications. As a result of public-key cryptography, a large number of other cryptographic tasks have emerged. Examples of such tasks are Coin-flipping by telephone [3] and Mental Poker. These may involve two or more parties, some of which may be dishonest. The general concept of Distributed Function Evaluation was first introduced by Yao [20] and later extended to “Mental Games” by Goldreich, Micali and Wigderson [12].

⋆ Supported in part by Québec’s FCAR and Canada’s NSERC.

Distributed Function Evaluation and Mental Games are multi-party algorithms which involve secret data that the parties want to keep from one another. In the model where we are ready to accept computational assumptions, such general tasks can be achieved from basic assumptions such as the existence of a One-Way Trapdoor Function [12].

The lesson derived in the computational model is that very simple protocols are sufficient to achieve the general ones. The two primitives known as Bit Commitment (defined in Section 3) and Oblivious Transfer (defined in Section 4) are elementary protocols that are sufficient in general to accomplish any Mental Games, even in a non-computational scenario [14, 8].

The current paper considers a scenario where only two people, A and B, are involved and where we put no limitation on their computing power. If we made no further assumption, it would be impossible to accomplish Mental Games. Thus, the extra assumption we make is that A and B are connected by a Binary Symmetric Channel (BS_{ϵ}), that is a channel that will change the value of a bit b with probability ϵ as it travels from one party to the other.

A first protocol to accomplish Oblivious Transfer from a Noisy Channel was presented in [9]. Unfortunately, that protocol is quite complex and requires Ω(n^{11}) bits sent through the BSC to perform a single Oblivious Transfer, where n is a security parameter that specifies the reliability of the protocol. As a consequence, any two-party computations may be performed from the assumption that there exists a reliable BSC. The current solution is by far more efficient than those suggested earlier. The current paper provides a protocol for Bit Commitment that uses O(n) times the BS_{ϵ} and a protocol for Oblivious Transfer that uses O(n^{3}) times that primitive, where n is a security parameter that specifies the probabilities of failure of the protocols. These probabilities are all exponentially small in n.

2 General Tools

2.1 Error Channel

We consider a standard error model: the binary symmetric channel. In the binary symmetric channel A sends a bit to B that is flipped with probability ϵ

BS_{ϵ}(x) = \{ \begin{matrix}x̄ & with prob. ϵ \\ x & with prob. 1 − ϵ. \end{matrix}

By extension, we also write BS_{ϵ}(w) as a shorthand for BS_{ϵ}(w_{1})BS_{ϵ}(w_{2})...BS_{ϵ}(w_{n}) when w = w_{1}w_{2}...w_{n} is an n–bit word. Let H(ϵ) = −ϵ lg ϵ − (1 − ϵ) lg(1 − ϵ) be the binary entropy function. We define the channel capacity of the BS_{ϵ} to be C_{ϵ} = 1 − H(ϵ).

A nice property of the binary symmetric channel is that it is totally symmetrical between the participants: if B wants to send a bit x via BS_{ϵ}(x) to A when it is only available from A to B, they can do as follows:

Protocol 2.1 ( \overline{BS}_{ϵ}(x) )

1: A picks r ∈R {0, 1} and runs BS_{ϵ}(r) with B who gets r′,
2: B announces y ← x ⊕ r′ to A,
3: A returns y ⊕ r.

In general, for the binary symmetric channel, any protocol may be inverted by permuting A and B and replacing BS_{ϵ} by \overline{BS}_{ϵ}. Therefore the protocols of sections 3 and 4 may be achieved from a noisy channel running either way. This is not the case with all channels. The following is an example of the opposite type.

An alternative to the binary symmetric channel would have been to consider the erasure channel where bits are either received without errors, or completly lost with probalities 1 − ϵ and ϵ. However this situation has been previously analyzed since the erasure channel is the same as Rabin’s Oblivious Transfer [16]. Protocols for Bit Commitment and (_{1}^{2})–OT using Rabin’s O.T. are available in [14] and [7].

2.2 Coding theory

An [n, k, d] linear code C is a linear subspace of {0, 1}^{n} of dimension k (and cardinality 2^{k}) such that no two words c_{1}, c_{2} from C are such that d_{H}(c_{1}, c_{2}) < d, except if c_{1} = c_{2}, where d_{H}(x, y) is the Hamming distance between x and y: the number of positions where they differ.

Such a code is defined as the linear combinations of the rows of a generating matrix G of dimension k × n. Alternatively, C may be defined as the kernel of a parity check matrix H of dimension n × (n − k). Knowledge of G or H is computationally equivalent as it is easy to get one from the other.

For section 3 we need the well known fact [15, chap. 17, prob. (30)] that there exists a constant ρ > 1 such that a random binary matrix G of size Rn×n defines a binary linear code with minimal distance at least ϵn except with probability not greater than ρ^{(R−C_{ϵ})n}, for values of R < C_{ϵ}.

For section 4 we need codes that are efficiently decodable with high correction rate and high dimension. For this purpose we use concatenated codes defined in [11] that are efficiently encoded and decoded. Asymptotically, very long [n, Rn, d] concatenated codes may be constructed in such a way that for every ϵ > 0 there exists a constant ρ > 1 such that the codes fail to correct ϵn errors except with probability not greater than ρ^{(R−C_{ϵ})n}, for values of R < C_{ϵ} (although the minimum distance d may be somewhat smaller than ϵn). Please consult [11] for more information on asymptotic performances of concatenated codes.

In some situations the information transmitted is not a codeword. In such a case, as long as the syndrome syn(w) = H^{⊤}w of a word w is known the decoding algorithm may be used to recover w from a noisy version of that word and the value of syn(w). Please consult [15] for more information on coding theory.

2.3 Generalized Privacy Amplification

Let W be a random variable uniformly distributed over {0, 1}^{n} and let BS_{ϵ}(W) be another random variable obtained from W through a binary symmetric channel of error rate ϵ, i.e.

Prob [BS_{ϵ}(W) = v|W = w] = (1 − ϵ)^{n−d_{H}(w,v)}ϵ^{d_{H}(w,v)}.

Let G be a random variable taking values g : {0, 1}^{n} → {0, 1}^{r} uniformly distributed from a universal_{2} class of hash functions [6]. It is shown in [1] that

Theorem 1. For any δ > 0 and all sufficiently large n, for s = n(H(ϵ) − δ) − r

H(G(W)|BS_{ϵ}(W), G) ≥ r − \frac{2^{−s}}{ln 2} .

Moreover, according to [2, 5, 1] for the special case where we have a linear function syn : {0, 1}^{n} → {0, 1}^{t}

Theorem 2. For any σ ∈ {0, 1}^{t}, δ > 0 and all sufficiently large n , for s = n(H(ϵ) − δ) − r

H(G(W)|syn(W) = σ, BS_{ϵ}(W), G) ≥ r − \frac{2^{t−s}}{ln 2} .

Since H(G(W)|syn(W) = σ, BS_{ϵ}(W), G) = r means that no information about G(W) is given by syn(W) = σ, BS_{ϵ}(W), G, the above result is exponentially close to the best possible: the latter contains almost no information about G(W).

3 Bit Commitment

Assume that a party, A, has a bit b in mind, to which she would like to be committed toward another party, B. That is, A wishes, through a procedure BC(b), to provide B with a piece of evidence w that she has a bit b in mind and that she cannot change it (binding). Meanwhile, B should not be able to tell from that evidence what b is (concealing). At a later time, A can reveal, through an unveiling procedure UN(b, p), the value of b and prove through p to B that the piece of evidence sent earlier (w) really corresponded to that bit.

Bit commitment schemes have several applications in the field of cryptographic protocols. In particular one can implement zero-knowledge proofs of a variety of statements using bit commitment schemes [13, 4]. The first implementations of bit commitment schemes were given in a computational complexity scenario [3]. Unfortunately, proofs of their (computational) security have always required an unproven assumption since otherwise they would imply very strong results such as P ≠ N P.

This section is inspired by that work of [5] to achieve Bit Commitment in the model of Quantum Cryptography.

3.1 Bit Commitment from Binary Symmetric Channel

Intuition behind Protocols BC & UN After establishing a proper errorcorrecting code, A sends a codeword from that code to B through the BS_{ϵ}. The code is such that B should have many candidates for A’s codeword after seeing it through the BS_{ϵ}. The secret bit of A is given by applying a random function from a universal_{2} class to the codeword. To unveil her bit, A discloses her codeword. She should not be able to announce two codewords that B will find close enough to the word he received to believe her.

Formal Protocol Let ϵ be the error probability of the channel, and γ < 1 be a positive number. Let δ > 0 be such that H(ϵ) − δ > H(γϵ) and such that (H(ϵ) − δ)n is an integer. The following protocols work for any value of ϵ such that 0 < ϵ < 1/2, in contrast to the protocols of Section 4.

Protocol 3.1 ( BC(b) )

1: B chooses and announces to A a binary linear [n, k, d]-code C with parameters k = (1 − H(ϵ) + δ)n and d ≥ γϵn.

2: A

– picks a random n-bit string m and announces it to B,

– picks a random codeword c ∈ C such that c ⊙ m = b,

– DO_{i=1}^{n} runs BS_{ϵ}(c_{i}) with B who receives c′_{i},

– returns c, b. 3: B sets c′ ← (c′_{1}c′_{2} … c′_{n}) and returns (C, m, c′).

B keeps c′ secret forever, whereas A keeps b and c secret until (and if) unveiling takes place. If A subsequently decides to unveil her commitment, she initiates the next protocol with B. There exists a positive number λ < γ(1/2 − ϵ)/2 such that an honest A is likely to satisfy the following with overwhelming probability while a dishonest A is unable to open the commitment as both bits with overwhelming probability.

Protocol 3.2 ( UN(c, b), (C, m, c′) )

1: if (c ∈ C) ∧ (b = c ⊙ m) ∧ (d_{H}(c, c′) < ϵn + λn)

then B accepts else B rejects.

Details of the Protocol In the above Protocol BC we ask B to choose a code with specific parameters. The effect of these parameters on the security of the protocol explain why we require B to do this job and not A: the bigger d is, the more unlikely it is for A to cheat and the bigger k is, the more unlikely it is for B to cheat. Coding theory give us limits on how big d and k can be at the same time. In order to have them as large as possible at the same time, the best construction known to this day is to pick the generating matrix of the code at random. Nevertheless, in this case the value of k is easy to figure out from the matrix (the rank of the matrix) while the exact value of d is more difficult to determine. All we know is that it is likely to be high.

As discussed in Sect. 2.2, a random binary matrix G of size Rn × n defines a binary linear code with minimal distance at least ϵn except with probability ρ^{(R−C_{ϵ})n}, thus B has an exponentially small probability of having d too small when he picks a k × n matrix at random. A can easily verify that the value of k is correct.

The random vector m is used to define a Privacy Amplification Function of {0, 1}^{n} to {0, 1}.

3.2 Analysis of the Protocol

Concealing Let C and M be the random variables describing B’s possibilities for c and m. Before c is sent through the BSC, C is uniformly distributed among all the possible codewords of C and M among all possible n–bit strings. Let 0 < δ′ < δ. We are in the scenario of Theorem 2 with r = 1, t = (H(ϵ) − δ)n, and s = (H(ϵ)−δ′)n−1. We therefore conclude that seeing a codeword c through a BSC and learning m is not enough to know much about c ⊙ m:

Theorem 3. For any all sufficiently large n

H(C ⊙ M|syn(C) = (0, 0, ..., 0), BS_{ϵ}(C), M) ≥ 1 − \frac{2^{(δ′−δ)n+1}}{ln 2} .

Binding An honest A sends a random codeword c through the channel. Consider the random variable d_{H}(c, BS_{ϵ}(c)). It is clear that E(d_{H}(c, BS_{ϵ}(c))) = ϵn and by Bernstein’s law of large numbers [17, Chap. VII, Sect. 4, Theorem 2] Prob [d_{H}(c, BS_{ϵ}(c)) > ϵn + λn] is exponentially small in n for all λ sufficiently small, and all sufficiently large n. A dishonest A sends any word w through the channel and later would like to claim c_{0} or c_{1} to unveil as 0 or 1. One of these, say c_{z}, is such that d_{H}(c_{z}, w) > γϵn/2. Consider the random variable d_{H}(c_{z}, BS_{ϵ}(w)). It is easy to calculate that E(d_{H}(c_{z}, BS_{ϵ}(w))) ≥ ϵn+γ(1/2−ϵ)n and by Bernstein’s law of large numbers Prob [d_{H}(c_{z}, BS_{ϵ}(w)) < ϵn + γ(1/2 − ϵ)n − λn] is exponentially small in n for all λ sufficiently small, and all sufficiently large n.

Thus any λ < γ(1/2 − ϵ)/2 will satisfy our requirements that an honest A succeeds except with probability exponentially small in n, while a dishonest A succeeds to open both ways only with probability exponentially small in n.

4 Oblivious Transfer

One-out-of-two Oblivious Transfer, denoted (_{1}^{2})–OT, is a primitive that originates with [18] (under the label of “multiplexing”). According to this primitive, one party A owns two secret strings w_{0} and w_{1}, and another party B wants to learn w_{c} for a secret bit c of his choice. A is willing to collaborate provided that B does not learn any information about wc̄, but B will only participate if A cannot obtain information about c.

Similarly, in an Oblivious Transfer [16], A sends a message to B that is received with probability ϵ (this fact is out of their control) while the message is otherwise lost. A does not find out what happened. B knows if he got the message or nothing. We note this protocol OT_{ϵ}. Independently from [18] but inspired by [16], (_{1}^{2})–OT was introduced subsequently in [10] with applications to contract signing protocols.

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 [20] allows A and B 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 [12] and later in an abstract (not necessarily computational) model by Kilian [14]. Crépeau 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 section is an extension of that technique.

4.1 Oblivious Transfer from Binary Symmetric Channel

Basic Idea For ϵ > 1/2, simulate OT_{ϵ}(b) with protocol ÔT_{ϵ}(b) obtained by sending b twice through the BSC of error probability φ = \frac{1−\sqrt{2ϵ−1}}{2} and then reduce (_{1}^{2})–OT to ÔT_{ϵ}(b) with a Protocol similar to that of [7].

Protocol 4.1 ( ÔT_{ϵ}(b) )

1: A runs BS_{φ}(b)BS_{φ}(b) with B who receives b_{0}b_{1}, for φ = \frac{1−\sqrt{2ϵ−1}}{2} .
2: if b_{0} = b_{1} then B returns b_{0} else B returns ε.

The problems with this approach are that ÔT_{ϵ}(b) makes errors and that A can send bad pairs b̄b: if A is honest and sends bb through the binary symmetric channel then

Prob [ÔT_{ϵ}(b) = x] = \{ \begin{matrix}(1 − φ)^{2} & if x = b \\ φ^{2} & if x = b̄ \\ 2φ(1 − φ) & if x = ε \end{matrix}

B receives a bit with probability ϵ = φ^{2} + (1 − φ)^{2}. If instead A is dishonest and sends b̄b or bb̄ through the binary symmetric channel then the probability that B receives a bit is 1 − ϵ = 2φ(1 − φ). If no extra checks are performed, A could send bad pairs and figure out in Protocol 4.2 which set is good and which set is bad by the fact that good pairs are more likely to have been received.

The errors are first solved (in Protocol 4.2) by the same trick as in [2] using codes to fix them, while the cheating by A is later taken care of (in Protocol 4.3) by running statistics on the frequency of bb pairs. Protocol 4.2 introduces another kind of cheating A could perform that is also solved in Protocol 4.3.

Intuition behind Protocol \binom{2}{1}–ÔT For this first protocol we assume A behaves honestly and will remove this assumption in the final protocol. The idea of the first protocol is that A sends 2n random bits r_{1}, r_{2}, ..., r_{2n} to B using ÔT_{ϵ}. B should receive roughly 2ϵn of these and lose 2(1 − ϵ)n. B forms two sets I_{0}, I_{1} of size n and thus defines two strings r′_{I_{0}}, r′_{I_{1}} of size n (r′ restricted to I_{0} and I_{1}). String r_{I_{c}} should be entirely known by B, while string r_{Ic̄} should be partially unknown by B. Nevertheless, because ÔT_{ϵ} is imperfect, we expect an average of \frac{φ^{2}}{ϵ} n differences between r_{I_{c}} and r′_{I_{c}}.

A code is established between the parties to correct more than \frac{φ^{2}}{ϵ} n errors except with exponentially small probability in n.

The errors are corrected by having A send the syndrome of the two words syn(r_{I_{0}}), syn(r_{I_{1}}). Using r′_{I_{c}} and syn(r_{I_{c}}), B may recover r_{I_{c}} except with small probability of failure. Nevertheless, this correction information is not sufficient to find out both words r_{I_{c}}, r_{Ic̄} accurately, as long as the dimension of the code is somewhat greater than ϵn.

A privacy amplification function is finally used to extract one secret bit per string, so that one bit may be recovered by B but not both. This function is the scalar product by a random n-bit word m.

Imcomplete Protocol Let γ be a number greater than 1.

Protocol 4.2 ( \binom{2}{1}–ÔT(b_{0}, b_{1})(c) )

1: DO_{i=1}^{2n} A picks a random bit r_{i} and runs ÔT_{ϵ}(r_{i}) with B who gets r′_{i}.

2: B picks and sends two random disjoint sets I_{0}, I_{1} s.t. |I_{0}| = |I_{1}| = n, and (∀i ∈ I_{c} [r′_{i} ≠ ε]). 3: A and B agree on a parity check matrix H of a concatenated code C with parameters [n, k > (ϵ + δ)n, d] correcting γ \frac{φ^{2}}{ϵ} n errors.

4: A

– computes and sends s_{0} ← syn(r_{I_{0}}) and s_{1} ← syn(r_{I_{1}}),

– picks and sends a random n-bit word m,

– computes and sends b̂_{0} ← b_{0} ⊕ (m ⊙ r_{I_{0}}) and b̂_{1} ← b_{1} ⊕ (m ⊙ r_{I_{1}}).

5: B

– recovers r_{I_{c}} using r′_{I_{c}}, s_{c} and the decoding algorithm of C,

– computes and returns b̂_{c} ⊕ (m ⊙ r_{I_{c}}).

Details and discussion of Protocol \binom{2}{1}–ÔT The code used for this protocol requires the extra property that it must be efficiently decodable. This can be done by using concatenated codes. For φ < 0.1982 the conditions of Step 3 can be satisfied. Therefore, contrary to Protocol BC, this new protocol works only for reliable enough channels BS_{φ} (not for all φ).

B is unable to cheat this protocol because whatever way he splits the “good” bits (r′_{i} ≠ ε) between I_{0}, I_{1}, he will not be able to put more (ϵ + δ/2)n good bits in at least one of I_{0} or I_{1}. Since k > (ϵ + δ)n then syn(r_{I_{0}}), syn(r_{I_{1}}) each contain n − k bits of information, i.e. no more than (1 − ϵ − δ/2)n bits. Thus, at least one of the two words r_{I_{0}}, r_{I_{1}} will be undetermined by at least δn/2 = n−(1+δ)n/2−(1/2−δ)n bits. Using privacy amplification, this word will contain an exponentially small amount of information about its related bit. Therefore, B cannot learn both of A’s bits.

Unfortunately, A can cheat this protocol in two different ways that allow her to figure out B’s secret input c: at Step 2 A can send “bad” pairs r_{i}r̄_{i} or r̄_{i}r_{i} instead of r_{i}r_{i} increasing the probability that it is lost (r′_{i} = ε) by B and at Step 4 she can send a “bad” syndrome leading B to a decoding error. In the first cheat, “bad” pairs are more likely to end up in the “bad” set thus indicating to A which one is more likely to be the “good” and “bad” sets. In the second cheat, if A makes only one syndrome bad then B might have to abort depending on which bit he is trying to get. Protocol 4.3 solves these two problems.

Intuition behind Protocol (_{1}^{2})–OT The general idea of this new protocol is to repeat Protocol \binom{2}{1}–ÔT several times for random b_{ℓ,0}, b_{ℓ,1} and c_{ℓ} and combine these instances in such a way to prevent A’s cheating as above.

More precisely, Protocol \binom{2}{1}–ÔT is repeated n^{2} times. We combine the n^{2} instances of \binom{2}{1}–ÔT in such a way that A must cheat in each instance if she wants to discover the value of c. Protocol ÔT is used a total of 2n^{3} times. In order to obtain information A must send at least n^{2} bad pairs in these protocols. This will make a statistical difference that will be detected with probability almost 1. If A uses less than n^{2} bad pairs, she finds out nothing about c. Similarly, if A sends bad syndromes in protocol \binom{2}{1}–ÔT with probability 1/2 she will be detected by B because he reads according to a random choice. If she uses O(n) such syndromes it is almost certain that B will detect her cheating.

Let n be an odd number. The instances are combined by requesting that

b_{ℓ,0} ⊕ b_{ℓ,1} = b_{0} ⊕ b_{1} for 1 ≤ ℓ ≤ n^{2}. Let b_{0,0} = ⨁_{ℓ=1}^{n^{2}} b_{ℓ,0} and b_{0,1} = ⨁_{ℓ=1}^{n^{2}} b_{ℓ,1}. These

requirements cause that ⨁_{ℓ=1}^{n^{2}} b_{ℓ,c_{ℓ}} = b_{0,z} for z = ⨁_{ℓ=1}^{n^{2}} c_{ℓ}. Thus in order to find out

which of b_{0,0} or b_{0,1} B is trying to get, A must find out all the c_{ℓ}.

Full Protocol Let γ be a number greater than 1 and n be an odd number. An extra index ℓ is added to each variable of the ℓ^{th} iteration of \binom{2}{1}–ÔT.

Protocol 4.3 ( (_{1}^{2})–OT(b_{0}, b_{1})(c) )

1: A picks n^{2} random bits b_{1,0}, b_{2,0}, ..., b_{n^{2},0} and sets b_{ℓ,1} ← b_{0} ⊕ b_{1} ⊕ b_{ℓ,0}, for 1 ≤ ℓ ≤ n^{2}. 2: B picks n^{2} random bits c_{1}, c_{2}, ..., c_{n^{2}}.

3: DO_{ℓ=1}^{n^{2}}

1. A runs \binom{2}{1}–ÔT(b_{ℓ,0}, b_{ℓ,1})(c_{ℓ}) with B who gets b′_{ℓ},

2. if d_{H}(r_{ℓ,I_{ℓ,c_{ℓ}}} , r′_{ℓ,I_{ℓ,c_{ℓ}}}) > γ \frac{φ^{2}}{ϵ} n then B aborts.

4: if (#\{ℓ, i | r′_{ℓ,i} ≠ ε\} < 2ϵn^{3} − \frac{(1−2φ)^{2}}{2} n^{2}) then B aborts

else B computes and sends c′ ← c ⊕ (⨁_{ℓ=1}^{n^{2}} c_{ℓ}).

5: A computes and sends b̂_{0} ← b_{0} ⊕ (⨁_{ℓ=1}^{n^{2}} b_{ℓ,c′} ) and b̂_{1} ← b_{1} ⊕ (⨁_{ℓ=1}^{n^{2}} b_{ℓ,c̄′} )

to B.

6: B computes and returns b̂_{c} ⊕ (⨁_{ℓ=1}^{n^{2}} b′_{ℓ}).

Details of the Protocol The test of Step 3.2 is to decide if the syndrome sent by A was valid. The value γ \frac{φ^{2}}{ϵ} n is the scope of the decoding algorithm of the concatenated code. If the decoded word was further than this distance then clearly the syndrome was wrong. If the test of Step 4 is negative then B is almost certain that A has not cheated n^{2} times over the 2n^{3} transmissions.

4.2 Analysis of the protocol

Let z_{i,j} = \{ \begin{matrix}0 & if r′_{i,j} = ε \\ 1 & if r′_{i,j} ≠ ε \end{matrix} . When A sends valid pairs r_{i,j}r_{i,j} in Protocol 4.3 clearly

we have E (∑_{i=1}^{n^{2}} ∑_{j=1}^{2n} z_{i,j}) = 2ϵn^{3}. On the other hand, if A wants to take advan-

tage of this kind of cheating, she must cheat in each of the n^{2} iterations of the protocol (if not she will loose completely one of the c_{ℓ} and thus c). In that case

we get E (∑_{i=1}^{n^{2}} ∑_{j=1}^{2n} z_{i,j}) ≤ ϵ(2n^{3} − n^{2}) + (1 − ϵ)n^{2} = 2ϵn^{3} − (1 − 2φ)^{2}n^{2}.

Theorem 4. There exists a constant ρ < 1 with the following properties: when A does not use “bad” pairs then

Prob [∑_{i=1}^{n^{2}} ∑_{j=1}^{2n} z_{i,j} < 2ϵn^{3} − \frac{(1 − 2φ)^{2}}{2} n^{2}] < ρ^{n}

whereas, when she cheats n^{2} times,

Prob [∑_{i=1}^{n^{2}} ∑_{j=1}^{2n} z_{i,j} > 2ϵn^{3} − \frac{(1 − 2φ)^{2}}{2} n^{2}] < ρ^{n}.

Proof (sketch). Follows from Bernstein’s law of large numbers.

Thus, except with exponentially small probability, an honest A will pass the test of Step 4 while a dishonest A will fail that same test.

If A is honest, the probability that more than γ \frac{φ^{2}}{ϵ} n errors occur during transmission by accident is exponentially small. Thus an honest A who sends correct syndromes, is unlikely to fail the test of Step 3.2 while a dishonest A who deliberately sends a wrong syndrome will be detected with probability 1/2, if B happens to use that syndrome at random.

Finally, for the same reasons discussed in Sect. 3.2, because of Privacy Amplification B cannot obtain information about both b_{0} and b_{1} through the instances of protocol \binom{2}{1}–ÔT.

5 Conclusion and Open Question

We have obtained two new protocols for the cryptographic primitives of Bit Commitment and One-out-of-Two Oblivious Transfer based on the existence of a BSC using Privacy Amplification. The protocol for BC requires O(n) uses of the BSC, while the protocol for (_{1}^{2})–OT requires O(n^{3}) uses of the BSC. If we combine these protocols with the protocol of Crépeau, van de Graaf and Tapp [8] for Private Multi-Party Computation to achieve any two-party function evaluation which requires O(n^{2}) BCs and O(n) (_{1}^{2})–OT per gate, we end up with a protocol requiring a total of O(n^{4}) uses of the BSC per gate of the computation. Our main open question is to obtain (_{1}^{2})–OT with only O(n^{2}) uses of the BSC and thus any two-party computation at a cost of O(n^{3}) uses of the BSC per gate. Another open question is to find an equally efficient protocol for (_{1}^{2})–OT using a BS_{ϵ} for values of ϵ above 0.1982.

6 Acknowledgments

We thank Gilles Brassard, Jeroen van de Graaf, Joe Kilian, Ueli Maurer, Alain Tapp, and Louis Salvail for support, suggestions and comments on this work.

References

1. C.H. Bennett, G. Brassard, C. Crépeau, and U.M. Maurer. Generalized Privacy Amplification. IEEE Transaction on Information Theory, Volume 41, Number 6, November 1995, pp. 1915–1923.

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

3. M. Blum. Coin flipping by telephone. In Proceedings of IEEE Spring Computer Conference, pages 133–137. IEEE, 1982.

4. G. Brassard, D. Chaum, and C. Crépeau. Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences, 37:156–189, 1988.

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

6. J. L. Carter and M. N. Wegman, “Universal classes of hash functions”, Journal of Computer and System Sciences, Vol. 18, 1979, pp. 143–154.

7. C. Crépeau. Equivalence between two flavours of oblivious transfers (abstract). In C. Pomerance, editor, Advances in Cryptology: Proceedings of Crypto ’87, pages 350–354, Springer-Verlag, 1988.

8. C. Crépeau, J. van de Graaf and A. Tapp. Committed Oblivious Transfer and Private Multi-Party Computations. Advances in Cryptology: Proceedings of Crypto ’95, August 1995, pp. 110–123.

9. C. Crépeau and J. Kilian. Achieving oblivious transfer using weakened security assumptions. In 29^{th} Symposium on Foundations of Computer Science, pages 42–52. IEEE, 1988.

10. S. Even, O. Goldreich, and A. Lempel. A randomized protocol for signing contracts. In R. L. Rivest, A. Sherman, and D. Chaum, editors, Proceedings CRYPTO 82, pages 205–210, Plenum Press, New York, 1983.

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

12. O. Goldreich, S. Micali and A. Wigderson, How to play any mental game, or: A completeness theorem for protocols with honest majority In Proc. 19th ACM Symposium on Theory of Computing, pages 218–229, ACM, 1987.

13. O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity, or All languages in N P have zero-knowledge proof systems. Journal of the ACM, 38:691–729, 1991.

14. J. Kilian, Founding cryptography on Oblivious transfer, 20^{th} ACM Symposium on Theory of Computation, 1988, pp. 20–31.

15. F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, 1977.

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

17. A. Rényi, Probability Theory, North Holland, 1970.

18. S. Wiesner. Conjugate coding. SIGACT News, 15(1):78–88, 1983. Manuscript written circa 1970, unpublished until it appeared in SIGACT News.

19. A. D. Wyner, “The wire-tap channel”, Bell System Technical Journal, Vol. 54, no. 8, 1975, pp. 1355–1387.

20. 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.

This article was processed using the L^{A}TEX macro package with LLNCS style