Efficient Cryptographic Protocols based on Noisy Channels

Claude Crépeau Université de Montréal ^{*}

April 9, 1996

Abstract

The Wire-Tap Channel of Wyner [20] 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 [20] who showed that two honest parties, say Alice and Bob, can exchange a secret key on which an eavesdropper Eve may obtain only a small fraction of the information as long as Alice and Bob are connected by a Binary Symmetric Channel of better quality than a similar Channel connecting them to Eve. Maurer [17] has later showed that even if Eve’s Channel is better but independent of the Channel between Alice and Bob, the same result is possible. More recently, a result of Bennett, Brassard, Crépeau and Maurer [1] provides a technique called Generalized Privacy Amplification to ensure that Eve’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 [10], 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 [21] and later extended to “Mental Games” by Goldreich, Micali and Wigderson [12].

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

* Département IRO, Université de Montréal, C.P. 6128, succursale centre-ville, Montréal (Québec), Canada H3C 3J7. e-mail: crepeau@iro.umontreal.ca.

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 [15, 8].

The current paper considers a scenario where only two people, Alice and Bob, 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 Alice and Bob 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 model of errors: the binary symmetric channel. In the binary symmetric channel Alice sends a bit to Bob 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.

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

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

1: Alice picks r ∈R {0, 1} and runs BS_{ϵ}(r) with Bob who gets r′,

2: Bob announces y ← x ⊕ r′ to Alice,

3: Alice returns y ⊕ r.

In general, for the binary symmetric channel, any protocol may be inverted by permuting Alice and Bob and replacing BS_{ϵ} by \overline{BS}_{ϵ}.

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.

It is a well known fact [16, chap. 17, prob. (30)] that a random binary matrix G of size Rn × n defines a binary linear code with minimal distance at least ϵn except with probability 2^{(R+H(ϵ)−1)n}.

Some of the codes we use in this paper are efficiently decodable. For instance, concatenated code used in Section 4 may be efficiently decoded. In some situations the information to be decoded 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 [16] 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]. Let H(x) = −x lg x − (1 − x) lg(1 − x) be the binary entropy function. It is shown in [1] that

Theorem 2.1 For any δ > 0 and all sufficiently large n

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

where s = n(H(ϵ) − δ) − r.

Let syn : {0, 1}^{n} → {0, 1}^{t} be a linear function. According to [2, 5, 1] for the special case where syn is a rank t linear function we have

Theorem 2.2 For any σ ∈ {0, 1}^{t}, δ > 0 and all sufficiently large n

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

where s = n(H(ϵ) − δ) − r.

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

3 Bit Commitment

Assume that a party, Alice, has a bit b in mind, to which she would like to be committed toward another party, Bob. That is, Alice wishes, through a procedure BC(b), to provide Bob with a piece of evidence w that she has a bit b in mind and that she cannot change it (unicity). Meanwhile, Bob should not be able to tell from that evidence what b is (confidentiality). At a later time, Alice can reveal, through an unveiling procedure UN(b, p), the value of b and prove through p to Bob 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 [14, 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

3.1.1 Intuition behind Protocols BC & UN

After establishing a proper error-correcting code, Alice sends a codeword from that code to Bob through the BS_{ϵ}. The code is such that Bob should have many candidates for Alice’s codeword after seeing it through the BS_{ϵ}. The secret bit of Alice is given by applying a random function from a universal_{2} class to the codeword. To unveil her bit, Alice discloses her codeword. She should not be able to announce two codewords that Bob will find close enough to what he saw to believe her.

3.1.2 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: Bob chooses and announces to Alice a binary linear [n, k, d]-code C with parameters k = (1 − H(ϵ) + δ)n and d ≥ γϵn.

2: Alice

• picks a random n-bit string m and announces it to Bob,

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

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

• returns c, b.

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

Bob keeps c′ secret forever, whereas Alice keeps b and c secret until (and if) unveiling takes place. If Alice subsequently decides to unveil her commitment, she initiates the next protocol with Bob.

There exists a positive number λ < γ(1/2 − ϵ)/2 such that an honest Alice is likely to satisfy the following with overwhelming probability while a dishonest Alice 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 Bob accepts else Bob rejects.

3.1.3 Details of the Protocol

In the above Protocol BC we ask Bob to choose a code with specific parameters. The effect of these parameters on the security of the protocol explain why we require Bob to do this job and not Alice: the bigger d is, the more unlikely it is for Alice to cheat and the bigger k is, the more unlikely it is for Bob 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 Section 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 2^{(R+H(ϵ)−1)n}, thus Bob has an exponentially small probability of having d too small when he picks a k × n matrix at random. Alice 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

Confidentiality Let C and M be the random variables describing Bob’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.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.1 For any all sufficiently large n

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

Unicity An honest Alice sends a random codeword c through the channel. Consider the random variable d_{H}(c, BS_{ϵ}(c)). It is easy to calculate that E(d_{H}(c, BS_{ϵ}(c))) = ϵn and by Bernstein’s law of large numbers Prob [d_{H}(c, BS_{ϵ}(c)) > ϵn + λn] is exponentially small in n for all λ sufficiently small, and all sufficiently large n. A dishonest Alice 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 Alice will succeed except with probability exponentially small in n, while a dishonest Alice will succeed to open both ways only with probability exponentially small in n.

4 Oblivious Transfer

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

Similarly, in an Oblivious Transfer [18], Alice sends a message to Bob that he receives with probability ϵ (this fact is out of their control) while the empty string ε is otherwise received. Alice does not find out what happened. Bob knows if he got the message or nothing. Independently from [19] but inspired by [18], (_{1}^{2})–OT_{2} was introduced subsequently in [11] 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 [21] 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 [12] and later in an abstract (not necessarily computational) model by Kilian [15]. 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

4.1.1 Basic Idea

Simulate OT_{ϵ}(b) with protocol ÔT_{ϵ}(b) obtained by sending b twice through the binary symmetric channel and then reduce (_{1}^{2})–OT_{2} to ÔT_{ϵ}(b) with a Protocol similar to that of [7].

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

1: Alice runs BS_{ϵ}(b)BS_{ϵ}(b) with Bob who receives b_{0}b_{1}.

2: if b_{0} = b_{1} then Bob returns b_{0} else Bob returns ε.

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

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

Let α = ϵ^{2} + (1 − ϵ)^{2} be the probability that Bob receives a bit. If instead Alice is dishonest and sends b̄b or bb̄ through the binary symmetric channel then the probability that Bob receives a bit is 2ϵ = 1 − α. If no extra checks are performed, Alice 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 Alice 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 Alice could perform that is also solved in Protocol 4.3.

4.1.2 Intuition behind Protocol (_{1}^{2})–ÔT_{2}

For this first protocol we assume Alice behaves honestly and will remove this assumption in the final protocol. The idea of the first protocol is that Alice sends n/α random bits r_{1}, r_{2}, ..., r_{n/α} to Bob using ÔT_{ϵ}. Bob should receive roughly n of these and lose (1 − α)n/α. Bob 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 Bob, while string r_{Ic̄} should be entirely unknown by Bob. Nevertheless, because ÔT_{ϵ} is imperfect, we expect an average of \frac{ϵ^{2}}{α} n differences between r_{I_{c}} and r′_{I_{c}}.

To correct these errors a code with minimum distance greater than 4\frac{ϵ^{2}}{α} n is established between the parties. The errors are corrected by having Alice send the syndrome of the two words syn(r_{I_{0}}), syn(r_{I_{1}}). Using r′_{I_{c}} and syn(r_{I_{c}}), Bob 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 greater than n/2.

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

4.1.3 First Protocol

Let γ be a number greater than 1.

Protocol 4.2 ( (_{1}^{2})–ÔT_{2}(b_{0}, b_{1})(c) )

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

2: Bob picks two random disjoint sets I_{0}, I_{1} s.t. |I_{0}| = |I_{1}| = n, (∀i [i ∈ I_{c} ⇒ r′_{i} ≠ ε]) or (∀i [r′_{i} ≠ ε ⇒ i ∈ I_{c}]) and sends I_{0}, I_{1}.

3: Alice and Bob agree on a parity check matrix H of a concatenated code C with parameters [n, k > (1/2 + δ)n, d > 4γ \frac{ϵ^{2}}{α} n].

4: Alice

• 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: Bob

• 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}}).

4.1.4 Details and discussion of Protocol (_{1}^{2})–ÔT_{2}

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 small enough ϵ the conditions of Step 3 can be satisfied. Therefore, contrary to Protocol BC, this new protocol works only for certain values of ϵ and not for all ϵ. Note that the code is used also to fill in missing bits in r_{I_{c}} when less than n “good” bits are received at Step 1.

Bob 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 (1 + δ)n/2 good bits in at least one of I_{0} or I_{1}. Since k > (1/2 + δ)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, Bob cannot learn both of Alice’s bits.

Unfortunately, Alice can cheat this protocol in two different ways that allow her to figure out Bob’s secret input c: at Step 2 Alice 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 Bob and at Step 4 she can send a “bad” syndrome leading Bob to a decoding error. In the first cheat, “bad” pairs are more likely to end up in the “bad” set thus indicating to Alice which one is more likely to be the “good” and “bad” sets. In the second cheat, if Alice makes only one syndrome bad then Bob might have to abort depending on which bit he is trying to get. Protocol 4.3 solves these two problems.

4.1.5 Intuition behind Protocol (_{1}^{2})–OT_{2}

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

More precisely, Protocol (_{1}^{2})–ÔT_{2} is repeated n^{2} times. We combine the n^{2} instances of (_{1}^{2})–ÔT_{2} in such a way that Alice must cheat in each instance if she wants to discover the value of c. Protocol ÔT is used a total of n^{3}/α times. In order to obtain information Alice 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 Alice uses less than n^{2} bad pairs, she finds out nothing about c. Similarly, if Alice sends bad syndromes in protocol (_{1}^{2})–ÔT_{2} with probability 1/2 she will be detected by Bob because he reads according to a random choice. If she uses O(n) such syndromes it is almost certain that Bob 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} Bob is trying to get, Alice must find

out all the c_{ℓ}.

4.1.6 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 (_{1}^{2})–ÔT_{2}.

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

1: Alice 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: Bob picks n^{2} random bits c_{1}, c_{2}, ..., c_{n^{2}}.

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

1. Alice runs (_{1}^{2})–ÔT_{2}(b_{ℓ,0}, b_{ℓ,1})(c_{ℓ}) with Bob who gets b′_{ℓ},

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

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

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

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

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

4.1.7 Details of the Protocol

The test of Step 3.2 is to decide if the syndrome sent by Alice 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 Bob is almost certain that Alice has not cheated n^{2} times over the n^{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 Alice sends valid pairs r_{i}r_{i} in Protocol clearly we have

E (∑_{i=1}^{n^{2}} ∑_{j=1}^{n/α} z_{i,j}) = n^{3}. On the other hand, if Alice is dishonest and wants to take advantage

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}^{n/α} z_{i,j}) ≤ n^{3} −(2α−1)n^{2} =

n^{3} − (1 − 2ϵ)^{2}n^{2}.

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

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

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

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

Sketch of proof. Follows from Bernstein’s law of large numbers.

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

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

Finally, for the same reasons discussed in Section 4.1.4, because of Privacy Amplification Bob cannot obtain information about both b_{0} and b_{1} through the instances of protocol (_{1}^{2})–ÔT_{2}.

5 Conclusion and Open Question

We have obtained two new protocols for the cryptographic primitives of Bit Commitment and Oneout-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_{2} 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_{2} 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_{2} with only O(n^{2}) uses of the BSC and thus any two-party computation at a cost of O(n^{4}) uses of the BSC per gate.

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, to appear November 1995.

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

[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] W. Diffie and M. E. Hellman, “New directions in cryptography”, IEEE Transactions on Information Theory, Vol. IT–22, 1976, pp. 644 – 654.

[11] 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.

[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] S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proofsystems. SIAM Journal on Computing, 18:186–208, 1989.

[15] J. Kilian, Founding cryptography on Oblivious transfer, 20^{th} ACM Symposium on Theory of Computation, 1988.

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

[17] U. M. Maurer, “Secret key agreement by public discussion from common information”, IEEE Transactions on Information Theory, Vol. IT–39, 1993, pp. 733–742.

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

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

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

[21] 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.