Oblivious Transfers and Intersecting Codes

Gilles Brassard^{∗}

Université de Montréal †

Claude Crépeau^{‡}

Université de Montréal †

École Normale Supérieure §

Miklós Sántha^{¶}

Université Paris–Sud ∥

Abstract

Assume A owns t secret k–bit strings. She is willing to disclose one of them to B, at his choosing, provided he does not learn anything about the other strings. Conversely, B does not want A to learn which secret he chose to learn. A protocol for the above task is said to implement One-out-of-t String Oblivious Transfer, denoted (_{1}^{t})–OT_{2}^{k}. This primitive is particularly useful in a variety of cryptographic settings. An apparently simpler task corresponds to the case k = 1 and t = 2 of two one-bit secrets: this is known as One-out-of-two Bit Oblivious Transfer, denoted (_{1}^{2})–OT_{2}. We address the question of implementing (_{1}^{t})–OT_{2}^{k} assuming the existence of a (_{1}^{2})–OT_{2}. In particular, we prove that unconditionally secure (_{1}^{2})–OT_{2}^{k} can be implemented from Θ(k) calls to (_{1}^{2})–OT_{2}. This is optimal up to a small multiplicative constant. Our solution is based on the notion of self-intersecting codes. Of independent interest, we give several efficient new constructions for such codes. Another contribution of this paper is a set of information-theoretic definitions for correctness and privacy of unconditionally-secure oblivious transfer.

∗ Supported in part by Canada’s nserc and Québec’s fcar.

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

‡ Supported in part by Québec’s fcar.

§ CNRS URA 1327. Laboratoire d’Informatique de l’École Normale Supérieure, 45 rue d’Ulm, 75230 Paris CEDEX 05, France.

¶Part of this research was supported by the Alexander von Humboldt Fellowship and by the ESPRIT Working Group 7097 RAND.

∥ CNRS URA 410. Laboratoire de Recherche en Informatique, Université Paris–Sud, Bâtiment 490, 91405 Orsay, France. e-mail: santha@lri.fr.

1 Introduction

The equivalence between cryptographic primitives is a major research topic [6, 11, 16, 30, 12, 25, 13, 31, 18, 19, 15, 17]. A large number of cryptographic protocols have been shown equivalent to one another.

One-out-of-two String Oblivious Transfer, denoted (_{1}^{2})–OT_{2}^{k}, is a primitive that originates with [43] (under the name of “multiplexing”), a paper that marked the birth of quantum cryptography. According to this primitive, one party A owns two secret k–bit 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 not participate if A can obtain information about c. Independently from [43] but inspired by [39], a natural restriction of this primitive was introduced subsequently in [20] with applications to contract signing protocols: One-out-of-two Bit Oblivious Transfer, denoted (_{1}^{2})–OT_{2}, concerns the case k = 1 in which w_{0} and w_{1} are single-bit secrets, generally called b_{0} and b_{1} in that case. In the other direction, a natural extension of (_{1}^{2})–OT_{2}^{k} called andos (for All-or-Nothing Disclosure of Secrets) was introduced in [6] but is denoted (_{1}^{t})–OT_{2}^{k} in the current paper: here A owns t secret k–bit strings w_{0}, w_{1}, …, w_{t−1} and B wants to learn w_{c} for a secret integer 0 ≤ c < t of his choice. It must be impossible for B to obtain information on more than one w_{i} and for A to obtain information about which secret B learned. Andos has applications to mental poker [10], voting [38], zero-knowledge proofs [2, 33, 41], exchange of secrets [7] and identification [21, 17], to name just a few.

The main contribution of [6] was a reduction of (_{1}^{t})–OT_{2}^{k} to (_{1}^{2})–OT_{2}, i.e. an efficient twoparty protocol to achieve andos based on the assumption of the existence of a protocol for the simpler type of oblivious transfer. The fact that the more general andos can be reduced to (_{1}^{2})–OT_{2} is not surprising because a number of authors [23, 24, 30, 12, 25, 15] have later shown that (_{1}^{2})–OT_{2} is sufficient to implement any two-party computation. Nevertheless, our direct reductions are interesting because of their greater efficiency. Even more efficient direct reductions of this kind were subsequently given in [19]. In the remainder of this section, we review the basic intuition behind the reductions presented in [6]. Section 2 defines formally the type of functions needed to achieve our goal, which we call zigzag functions, and it gives formal definitions for oblivious transfer based on information-theoretic considerations. Section 3 reduces the problem of finding efficient zigzags to the notion of self-intersecting codes [8]. Section 4 surveys techniques for the construction of efficient self-intersecting codes based on our earlier work in [19]. Finally, Section 5 discusses open problems together with a new research direction we are currently investigating: an alternative approach based on privacy amplification [4] to the problem considered in this paper and to a natural generalization. The appendices contain proofs of the main theorems of this paper.

1.1 Oblivious String Transfer: the Basic Reduction

For any n–bit string x, let x^{i} denote the i^{th} bit of x. For a set I = {i_{1}, i_{2}, …, i_{m}} such that 1 ≤ i_{1} < i_{2} < ⋯ < i_{m} ≤ n, we define x^{I} to be the concatenation x^{i_{1}}x^{i_{2}} ⋯ x^{i_{m}}. Assume A and B dispose of a safe protocol to accomplish (_{1}^{2})–OT_{2}. They wish to perform (_{1}^{2})–OT_{2}^{k} over the two k–bit strings w_{0} and w_{1}. First observe that performing (_{1}^{2})–OT_{2} on each pair w_{0}^{i}, w_{1}^{i}, 1 ≤ i ≤ k, in order to implement a (_{1}^{2})–OT_{2}^{k} fails dramatically since a cheating B can get w_{0}^{1} and w_{1}^{2} for instance, i.e. partial information about both w_{0} and w_{1}.

Assume instead that we have a function f : {0, 1}^{n} → {0, 1}^{k} with the property that for every two input strings x_{0}, x_{1} and every disjoint sets I, J ⊆ {1, 2, …, n}, seeing the bits x_{0}^{I} and x_{1}^{J} releases information on at most one of f(x_{0}) or f(x_{1}). We could then use the following protocol to achieve (_{1}^{2})–OT_{2}^{k}.

Protocol 1.1 ( (_{1}^{2})–OT_{2}^{k}(w_{0}, w_{1})(c) )

1: A picks random x_{0}, x_{1} ∈ {0, 1}^{n} such that f(x_{0}) = w_{0} and f(x_{1}) = w_{1}.

2: DO_{i=1}^{n} A transfers z^{i} ← (_{1}^{2})–OT_{2}(x_{0}^{i}, x_{1}^{i})(c) to B.

3: B recovers w_{c} by computing f(z).

This protocol works since an honest B gets x_{c}^{{1,...,n}} and x∅ ; c̄, which gives him full information on w_{c} and no information on wc̄. By the definition of f, on the other hand, a cheating B who gets x_{0}^{I} and xĪ ; 1 for some I ≠ ∅ ≠ Ī cannot get information on both f(x_{0}) and f(x_{1}) simultaneously.

Based on the above protocol, one of the main purposes of this paper is to discuss efficient solutions to the problem of building such functions f.

1.1.1 A Simple Example

Consider the following function f : {0, 1}^{3} → {0, 1}^{2} that can be used to accomplish (_{1}^{2})–OT_{2}^{2} from (_{1}^{2})–OT_{2}, where ⊕ is used to denote the exclusive-or.

f(x^{1}, x^{2}, x^{3}) = (x^{1} ⊕ x^{2}, x^{2} ⊕ x^{3})

If we use this function with the above protocol, we see that if B gets x_{0}^{1}, x_{0}^{2}, x_{0}^{3} at step 2 he will be able to compute (w_{0}^{1}, w_{0}^{2}) = f(x_{0}^{1}, x_{0}^{2}, x_{0}^{3}), and similarly if he gets x_{1}^{1}, x_{1}^{2}, x_{1}^{3}. But if he gets x_{0}^{I} and xĪ ; 1 for some I ≠ ∅ ≠ Ī, then one of I or Ī (call it Y) must be such that #Y = 1. Note that the partial functions f(x^{1}, ∗, ∗), f(∗, x^{2}, ∗) and f(∗, ∗, x^{3}) give all four possible outputs given the four possible inputs. Therefore given only one bit of x, nothing is known about the output of f, i.e. the corresponding w.

1.2 All-or-Nothing Disclosure of Secrets

Assume now A and B dispose of a safe protocol to accomplish (_{1}^{2})–OT_{2}^{k}. They wish to perform (_{1}^{t})–OT_{2}^{k} over the k–bit strings w_{0}, w_{1}, …, w_{t−1}. The idea is for A to choose t − 2 random k–bit strings x_{1}, x_{2}, …, x_{t−2}. Using (_{1}^{2})–OT_{2}^{k}, A offers B to choose to learn one of w_{0} or x_{1}. Then, she offers him to choose between w_{1} ⊕ x_{1} or x_{2} ⊕ x_{1}, and then between w_{2} ⊕ x_{2} or x_{3} ⊕ x_{2}, and so on. (A special case is made for w_{t−1}—see the formal description of the protocol below.) If B wants to learn w_{0}, he must do so in the first instance of (_{1}^{2})–OT_{2}^{k}, but then all information about x_{1} is lost, which precludes learning anything about the other w_{i}’s. If B wants to learn w_{1} instead, he must obtain x_{1} in the first instance of (_{1}^{2})–OT_{2}^{k}—thus forsaking all information about w_{0}—and then w_{1} ⊕ x_{1} in the second instance: this enables him to compute w_{1} = x_{1} ⊕ (w_{1} ⊕ x_{1}) but at the cost of losing all information about x_{2}, and therefore about all subsequent w_{i}’s. Similarly, B can learn any w_{i} at the expense of A’s other secrets. Clearly, A does not learn anything about which secret B chose. A formal description of the protocol follows, in which we consider boolean expressions such as c ≠ i to take binary value 1 when true and 0 when false. For simplicity, from now on we denote w⃗ = w_{0}, w_{1}, …, w_{t−1}.

Protocol 1.2 ( (_{1}^{t})–OT_{2}^{k}(w⃗)(c) )

1: A sets x_{0} ← 0^{k}, x_{t−1} ← w_{t−1} and picks random x_{1}, …, x_{t−2} ∈ {0, 1}^{k}.

2: DO_{i=0}^{t−2} A transfers z_{i} ← (_{1}^{2})–OT_{2}^{k}(w_{i} ⊕ x_{i}, x_{i+1} ⊕ x_{i})(c ≠ i) to B.

3: B sets ĉ ← min{t − 2, c} and recovers w_{c} by computing ⨁_{i=0}^{ĉ} z_{i}.

We formally prove in Appendix A that protocols 1.1 and 1.2 accomplish the task they were designed for in a very strong sense defined in section 2.2.

2 Formal Definitions

In this section we first give a formal definition for the notion of zigzag functions. This notion is crucial to understanding the connection between oblivious transfer and self-intersecting codes. Section 2.2 introduces information theoretic definitions for correctness and privacy of a protocol for oblivious transfer. We prove in Appendix A that the protocols of Section 1 are correct and private implementations of their respective version of oblivious transfer.

2.1 Definition of Zigzag Functions

Let F be a finite set.

Definition 2.1 Consider function f : F^{n} → F^{k}. A subset I ⊆ {1, 2, ..., n} biases f if

∃w_{0}, w_{1} ∈ F^{k}, x ∈ F^{n} [#{z ∈ F^{n}|z^{I} = x^{I}, f(z) = w_{0}} ≠ #{z ∈ F^{n}|z^{I} = x^{I}, f(z) = w_{1}}] (1)

Intuitively, I biases f if knowledge of the entries x^{I} of an otherwise unknown vector x ∈ F^{n} may give information on f(x).

Definition 2.2 An (n, k)-zigzag (over F) is a function f : F^{n} → F^{k} such that

∀I, J ⊆ {1, 2, ..., n} [I ∩ J = ∅ ⇒ I or J does not bias f]  (2)

or equivalently:

∀I ⊆ {1, 2, ..., n} [I or Ī does not bias f] .  (3)

Definition 2.3 Consider a function g : ℕ → ℕ. A family of functions {f_{i}}_{i∈ℕ} is a g(k)–zigzag family if for each integer k there exists at least one i such that f_{i} : F^{g(k)} → F^{k} is a (g(k), k)–zigzag. This zigzag family is good if g(k) ∈ O(k) and is efficient if there exists an efficient algorithm D to find at least one such i for any given k. Moreover, D must produce an efficient algorithm E_{i} to compute f_{i} and an efficient algorithm C_{i} to produce random preimages of f_{i} chosen according to the uniform distribution. Thus, for any w ∈ F^{k} and x ∈ F^{g(k)}, x may be produced from a call on C_{i}(w) only if f_{i}(x) = w, in which case it is produced with probability 2^{k−g(k)}. Note that algorithm C_{i} must be probabilistic for this notion to make sense. In all cases, algorithms are considered efficient provided their expected running time is upper-bounded by a polynomial in the value of k.

In general, algorithm D may be probabilistic: there may exist several different (g(k), k)–zigzags for each k and D(k) may produce a different one each time it is invoked. Among probabilistic zigzag families, we distinguish between Monte Carlo and Las Vegas families. A Las Vegas zigzag family respects the above definition unconditionally: no matter which probabilistic choices are taken by D(k), it is guaranteed that the resulting function is a (g(k), k)–zigzag. A Monte Carlo zigzag family allows for a small probability of failure: it may happen that a call on D(k) produces a function that is not a zigzag. No warning is generally given when this occurs. However, the probability of failure must be exponentially small in k.

In the special case of a deterministic zigzag family, for which algorithm D is deterministic, there is no reason for i to be different from k and we may as well require that f_{k} : F^{g(k)} → F^{k} be a (g(k), k)–zigzag for each k.

Our goal is to find efficient g(k)–zigzag families for the smallest possible function g(k). Note that efficient zigzag families are precisely what is needed to implement protocol 1.1 efficiently. Given k, which is the length of the two strings w_{0} and w_{1} that A wants to involve in the protocol, A and B use D(k) to agree on f_{i}, E_{i} and C_{i}; A uses C_{i} to produce x_{0} and x_{1} from w_{0} and w_{1} in step 1; and B uses E_{i} to compute w_{c} from z at step 3.

2.2 Information-Theoretic Definition of Oblivious Transfer

A cryptographic protocol is a multi-party synchronous program that describes for each party the computations to be performed or the messages to be sent to some other party at each point in time. The protocol terminates when no party has any message to send or information to compute. The protocols we describe in this paper all take place between two parties A and B. We denote by Ā and B̄ the honest programs to be executed by A and B: honest parties behave according to Ā and B̄ and no other program. In the following definitions of correctness and privacy we also consider alternative dishonest programs Ã and B̃ executed by A or B in a effort to obtain unauthorized information from one another. The definitions specify the result of honest parties interacting together through a specific protocol as well as the possible information leakage of an honest party facing a dishonest party. We are not concerned with the situation where both parties may be dishonest as they can do anything they like in that case; we are only concerned with protecting an honest party against a dishonest party. At the end of each execution of a protocol, each party will issue an “accept” or “reject” verdict regarding their satisfaction with the behaviour of the other party. Two honest parties should always issue “accept” verdicts at the end of their interactions. An honest party will issue a “reject” verdict at the end of a protocol if he received some message from the other party of improper format or some message not satisfying certain conditions specified by the protocol. We also implicitly assume certain time limits for each party to issue messages to each other: after a specified amount of time a party will give up interacting with the other party and issue a “reject” verdict.

As discussed in the Introduction, a (_{1}^{2})–OT_{2} is a cryptographic protocol for two participants that enables a sender A to transfer one of two bits b_{0} or b_{1} to a receiver B who chooses secretly which bit b_{c} he gets. This is done in an all-or-nothing fashion, which means that B cannot get partial information about b_{0} and b_{1} at the same time, however malicious or (computationally) powerful he is, and that A finds out nothing about the choice c of B. Generalization of (_{1}^{2})–OT_{2} include the (_{1}^{2})–OT_{2}^{k}, in which the bits b_{0} and b_{1} are replaced by k–bit strings w_{0} and w_{1}, and (_{1}^{t})–OT_{2}^{k}, in which A has several k–bit strings w_{0}, w_{1}, …, w_{t−1} from which B is given to choose one. The choice c is now from the set T = {0, 1, …, t − 1}.

Formally speaking we describe a two-party protocol that satisfies the following constraints of correctness and privacy. These notions have been defined before for general protocols by Crépeau [13], Micali and Rogaway [36] and Beaver [1] using simulators. In this paper, we use the language of information theory to express definitions similar to those introduced by Crépeau [14]. Our goal is not to discuss definitions for general two-party protocols: we restrict our study to oblivious transfers.

2.2.1 Correctness

Let [P_{0}, P_{1}](a)(b) be the random variable (since P_{0} and P_{1} may be probabilistic programs) that describes the outputs obtained by A and B when they execute together the programs P_{0} and P_{1} on respective inputs a and b. Similarly, let [P_{0}, P_{1}]^{∗}(a)(b) be the random variable that describes the total information (including not only messages received and issued by the parties but also the result of any local random sampling they may have performed) acquired during the execution of protocol [P_{0}, P_{1}] on inputs a, b. Let [P_{0}, P_{1}]_{P} (a)(b) and [P_{0}, P_{1}]_{P}^{∗} (a)(b) be the marginal random variables obtained by restricting the above to only one party P. The latter is often called the view of P [26]. In the following definition, the equality sign (=) means that the distributions on the left-hand side and the right-hand side are the same. The symbol “ϵ” stands for the empty string.

Definition 2.4 (Correctness) Protocol [Ā, B̄] is correct for (_{1}^{t})–OT_{2}^{k} if

• ∀w⃗ ∈ F^{tk}, c ∈ T

Prob {[Ā, B̄](w⃗)(c) ≠ (ϵ, w_{c})} = 0  (4)

• for any program Ã there exists a probabilistic program S̃ s.t. ∀w⃗ ∈ F^{tk}, c ∈ T

([Ã, B̄]B (w⃗)(c) | B accepts ) = ([Ā, B̄]B (S̃(w⃗))(c) | B accepts ) .  (5)

Intuitively, condition (4) means that if the protocol is executed as described, it will accomplish the task it was designed for: B receives word w_{c} and A receives nothing. Condition (5) means that in situations in which B does not abort, A cannot induce a distribution on B’s output using a dishonest Ã that she could not induce simply by changing the input words and then being honest (which she can always do without being detected). This second condition, called awareness in [36], is concerned with the future use of the outputs of a protocol. If the output of a protocol is to be used later in another protocol we wish to guarantee that the output distribution of the first protocol corresponds to the expected output distribution prescribed by the task definition. Otherwise trouble may force a party to abort and thus disclose situational information about past executions of the protocol. Although some authors [36] insist that correctness and privacy must be defined together in the general case, the particular case of oblivious transfers allows for independent definitions. Here, no correctness condition involving B̃ is necessary since A receives no output.

2.2.2 Privacy

Let W⃗ = W_{0}, W_{1}, ..., W_{t−1} and C be the random variables taking values over F^{tk} and T that describe A’s and B’s inputs. We assume that both A and B are aware of the joint probability distribution of these random variables P_{W⃗ ,C}. A sample w⃗, c is generated from that distribution and w⃗ is provided as A’s secret input while c is provided as B’s secret input.

We assume for the next definition that the reader is familiar with the notion of entropy H (X) of a random variable X. The mutual information of two random variables X, Y is given by I (X; Y) = H (X) − H (X | Y) and conditioned by a third random variable Z, I (X; Y | Z) = H (X | Z) − H (X | Y, Z).

Definition 2.5 (Privacy) Protocol [Ā, B̄] is private for (_{1}^{t})–OT_{2}^{k} if ∀W⃗ ∈ F^{tk}, C ∈ T

• for any program Ã

I (C; [Ã, B̄]A^{∗}(W⃗)(C) | W⃗ ) = 0  (6)

• for any program B̃ there exists a random variable C̃ = ξ(C) ∈ T s.t.

I (W⃗; [Ā, B̃]B^{∗}(W⃗)(C) | C, WC̃) = 0.  (7)

The above two conditions are designed to guarantee that each party is limited to the information he or she should get according to the honest task definition. Condition (6) means that Ã cannot acquire any information about C through the protocol. Condition (7) means that B̃ may acquire information about only one of W_{0}, W_{1}, ..., W_{t−1} through the protocol. In particular, no joint information about the t words may be obtained by the protocol. This is why our condition assumes that B̃ is given one of the words. We do not require that B̃ be given W_{C} because there is no way to prevent him from obtaining any other WC̃ through otherwise honest use of the protocol.

One of the main results of this paper is to provide a transformation of any protocol for (_{1}^{2})–OT_{2} satisfying the above constraints into a protocol for (_{1}^{t})–OT_{2}^{k} also satisfying these constraints. Please consult Appendix A for proofs that protocols 1.1 and 1.2 are correct and private when based on a correct and private (_{1}^{2})–OT_{2}.

Nevertheless, few protocols for (_{1}^{2})–OT_{2} actually satisfy the above constraints perfectly. In general, the above constraints are only satisfied statistically; statistical versions of constraints (4), (6) and (7) are obtained by replacing the right-hand side zero by an exponentially decreasing function in a security parameter s and by changing the equality (=) in constraint (5) by statistical indistinguishability (for a precise definition of this notion, consult [26] for instance). Protocols 1.1 and 1.2 may also be used to transform a protocol for (_{1}^{2})–OT_{2} satisfying statistical correctness and privacy into a protocol for (_{1}^{t})–OT_{2}^{k} also satisfying these statistical constraints.

3 Linear Zigzags

In order to generalize the simple example of section 1.1.1, we shall look at linear families of functions, i.e. functions f : 𝔽^{n} → 𝔽^{k} that are defined by a k × n matrix M over field 𝔽 as f(x) = Mx, where both input x ∈ 𝔽^{n} and output f(x) ∈ 𝔽^{k} are considered as column vectors. For instance, the function f of section 1.1.1 is defined by

M = ( \begin{matrix}1 & 1 & 0 \\ 0 & 1 & 1 \end{matrix} )

over the field 𝔽_{2} of integers modulo 2 in which addition and multiplication correspond to the boolean exclusive-or and conjunction, respectively.

The use of linear functions has the advantage that it is efficient to compute them and to compute random preimages of arbitrary points in 𝔽^{k}. Therefore, families of linear functions are efficient in the sense of Definition 2.3 provided they can be constructed efficiently. In other words, there must be an efficient algorithm D that produces (the encoding of) a k × g(k) matrix over 𝔽 that defines a (g(k), k)–zigzag for each integer k. Different matrices may be produced on different calls on D(k) if the zigzag family is probabilistic, and it may happen with vanishingly small probability that a call on D(k) produces a matrix that does not define a zigzag at all if the family is allowed to be Monte Carlo.

3.1 Matrix Characterization

Given a k × n matrix M over field 𝔽 and integer i, 1 ≤ i ≤ n, let M^{i} be the i^{th} column of M. For a set of indices I = {i_{1}, i_{2}, …, i_{m}} such that 1 ≤ i_{1} < i_{2} < ⋯ < i_{m} ≤ n, we define M^{I} to be the matrix obtained by the concatenation of columns M^{i_{1}}M^{i_{2}} ⋯ M^{i_{m}}. Remember that we defined earlier a similar notion z^{I} for vectors that restricts z to its components specified by I. Zigzag characterization (3) for f(x) = Mx is equivalent to the characterization given by the following proposition.

Proposition 3.1 A k × n matrix M over 𝔽 defines a linear zigzag if and only if

∀I ⊆ {1, 2, ..., n} [M^{I} or M Ī has rank k]  (8)

Proof. We show that for all I, I does not bias Mx ⇔ M Ī has rank k.

∀w_{0}, w_{1} ∈ 𝔽^{k}, x ∈ 𝔽^{n} [#{z ∈ 𝔽^{n}|z^{I} = x^{I}, Mz = w_{0}} = #{z ∈ 𝔽^{n}|z^{I} = x^{I}, Mz = w_{1}}]

⇔ #{z ∈ 𝔽^{n}|z^{I} = x^{I}, M^{I}z^{I} + M ĪzĪ = w_{0}} = #{z ∈ 𝔽^{n}|z^{I} = x^{I}, M^{I}z^{I} + M ĪzĪ = w_{1}}
⇔ #{z ∈ 𝔽^{n}|z^{I} = x^{I}, M^{I}x^{I} + M ĪzĪ = w_{0}} = #{z ∈ 𝔽^{n}|z^{I} = x^{I}, M^{I}x^{I} + M ĪzĪ = w_{1}}
⇔ #{z ∈ 𝔽^{n}|z^{I} = x^{I}, M ĪzĪ = w_{0} − M^{I}x^{I}} = #{z ∈ 𝔽^{n}|z^{I} = x^{I}, M ĪzĪ = w_{1} − M^{I}x^{I}}
⇔ #{z ∈ 𝔽^{n}|M ĪzĪ = w_{0}} = #{z ∈ 𝔽^{n}|M ĪzĪ = w_{1}}

since w − M^{I}x^{I} is a cyclic permutation of the elements of 𝔽^{k}

⇔ M Ī has rank k.

3.2 A Trivial Lower Bound

Since our goal is to determine the smallest function g for which we can find efficient g(k)–zigzag families, we now give a simple lower bound.

Proposition 3.2 For any linear g(k)–zigzag family, it must be that g(k) ≥ 2k − 1.

Proof. For any matrix of size k × n for n < 2k − 1, any subset I such that #I = k − 1 cannot have rank k, nor can Ī since #Ī = n − #I = n − k + 1 < 2k − 1 − k + 1 = k. Note that the bound g(k) ≥ 2k − 1 applies for any field 𝔽.

3.3 Code Characterization

We now introduce a new characterization of the matrices that define zigzag functions in terms of the words of a code generated by the rows of the matrix. For this purpose we need the following definition.

Definition 3.3 We say that two vectors v_{0}, v_{1} ∈ 𝔽^{n} intersect if they have at least one nonzero component in common, i.e. if there exists an i, 1 ≤ i ≤ n, such that v_{0}^{i}v_{1}^{i} ≠ 0.

Proposition 3.4 A k × n matrix M satisfies characterization (8) if and only if M satisfies

∀a, b ∈ 𝔽^{k} \ {0^{k}} [aM and bM intersect ] .  (9)

Proof. We actually show ¬(8) ⇔ ¬(9).

⇒ Suppose ∃I such that M^{I} and M Ī have rank less than k. Then there exists a nonzero vector a such that aM^{I} = 0^{#I} and a non-zero vector b such that bM Ī = 0^{n−#I}. For those two vectors we have that aM and bM do not intersect because for all i, (aM)^{i} = 0 or (bM)^{i} = 0.

⇐ Suppose that ∃a, b ∈ 𝔽^{k} \ {0^{k}} such that for all i, (aM)^{i} = 0 or (bM)^{i} = 0. Let I be the set of indices such that (aM)^{i} = 0. Clearly, aM^{I} = 0^{#I} which implies that M^{I} has rank less than k. Similarly, we have that (bM)^{i} = 0 for i ∈ Ī. This means that bM Ī = 0^{n−#I} which implies that M Ī has rank less than k.

A Simple Family The matrix M of Section 1.1.1 is the generating matrix of a [3, 2, 2] code C with the above intersecting property. Using iterated direct product on C, a family of [3^{s}, 2^{s}, 2^{s}] intersecting codes C^{s} was obtained by Miklós [37], Cohen & Lempel [8] and Brassard, Crépeau & Robert [6]. Next section is devoted to the general study of these codes.

4 Intersecting Codes

Consider M as the generating matrix of a linear code. Proposition 3.4 states that M defines an (n, k)-zigzag exactly if the [n, k, d] code generated by M is such that any two codewords c_{1}, c_{2} must intersect (not counting the zero codeword). The minimal distance d of the code is uniquely defined by M but is irrelevant at this point.

Such self-intersecting codes^{1} [8] have been studied in the past. For instance, Cohen and Lempel [8] have shown that the dual of BCH codes of length n = 2^{m} − 1 and design distance 2t + 1 < \frac{1}{3}2^{m/2} + 3 are intersecting. Retter [40] showed that most (classical) Goppa codes (see [34]) of rate less than 0.0817 are intersecting.

Define ⋂(k) = min {n : there exists a binary [n, k, d] intersecting code}. Katona and Srivastava [28] have tabulated the value of ⋂(k) for 1 ≤ k ≤ 5, while Sloane [42] followed by Cohen and Zemor [9] have provided upper bounds on several extra values, as shown in Figure 1.

\begin{matrix}k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 17 \\ ⋂(k) & 1 & 3 & 6 & 9 & 13 & 15 & 21 & 25 & 29 & 30 & 41 & 46 & 51 & 53 & 54 & 63 \end{matrix}

Figure 1: small values of ⋂(k). Bold values are known to be exact.

Katona and Srivastava also derived a lower bound on the asymptotic behaviour of ⋂(k)/k by combining the McEliece-Rodemich-Rumsey-Welch bound for binary linear codes with the simple bound obtained by observing that if M defines an [n, k, d] intersecting code then d ≥ k. A corresponding upper bound was given by Komlós (reported in [37, 8]). These bounds are the following:

3.5277 < lim inf_{k→∞} \frac{⋂(k)}{k} ≤ lim sup_{k→∞} \frac{⋂(k)}{k} < 4.8188.

These bounds imply that, asymptotically, binary [ck, k, d] intersecting codes exist for c > 4.8188 but not for c < 3.5277. Nevertheless, no efficient zigzag family can be inferred from the above results because even if most codes satisfy the property, it is not clear how to obtain efficiently one that is guaranteed to satisfy it.

The current section focuses on the polynomial-time constructibility of such zigzag families. First we use in Section 4.1 the fact proven in Appendix B that for α = log_{4/3} 4 ≈ 4.8188 and any γ > α, a random k × γk binary matrix defines a (γk, k)–zigzag with probability asymptotically close to 1, while a random k × λk binary matrix for any λ < α defines a (λk, k)-zigzag with probability asymptotically close to 0. In both cases, the convergence is exponentially fast in k. (The first part of this result is implied by the proof of Cohen and Lempel [8] of Komlós’ bound.) This yields an obvious Θ(k^{2})–time Monte Carlo binary γk–zigzag family for any γ > α.

1For the rest of this paper we omit the word “self” as no other type of intersecting codes are considered.

We have considered using pairs of intersecting codes but asymptotically we get the same results.

Then, we show that the concatenation of intersecting codes yields an intersecting code, and we use this fact in three constructions. Section 4.3 applies this technique to the Monte Carlo family derived in section 4.1 to improve it to a Θ(k^{2})–time Las Vegas binary 2γk–zigzag family for any γ > α. Section 4.4 presents an “efficient” O(k^{32})–time deterministic binary O(k)–zigzag family based on the algebraic-geometric codes of Goppa [27]. Finally, Section 4.5 uses the concatenation method in a construction reminiscent of that of Justesen codes to obtain an O(k^{4})–time deterministic binary O(k)–zigzag family.

4.1 Monte Carlo Construction

In this section, we determine precisely the size of random matrices over 𝔽_{2} that define binary linear zigzags. If k denotes the number of rows, then there is a threshold function t(k), which is linear in k, such that a random binary matrix with more than t(k) columns defines a linear zigzag with high probability, whereas a random binary matrix with less than t(k) columns does not define a linear zigzag, also with high probability.

Theorem 4.1 Set α = log_{4/3} 4, and let M be a random k × n matrix over 𝔽_{2}. Then for every constant ε > 0, there exists a constant 0 < η < 1 such that we have the following two propositions:

1. If n ≥ (1 + ε)αk, then Prob {M defines a linear zigzag} > 1 − η^{k}, and

2. If n ≤ (1 − ε)αk, then Prob {M does not define a linear zigzag} > 1 − η^{k}.

The proof of this theorem may be found in Appendix B. Although the first part of this result is implied by the proof of Cohen and Lempel [8] of Komlós’ bound, we nevertheless include it in our proof since it is only one line.

Remark A similar analysis for the case of matrices over 𝔽_{q} shows that for any ε > 0, a random 𝔽_{q}-matrix of size k × (2 + ε)k has asymptotic probability 1 of being a zigzag, as q → ∞. This is optimal according to Proposition 3.2.

Time Complexity As mentioned before, Proposition 1 yields an efficient Monte Carlo binary γk–zigzag family for any γ > α. The running time of this construction is Θ(k^{2}). On the other hand, Proposition 2 shows that this bound is optimal in the sense that this technique cannot yield a binary λk–zigzag family for any λ < α.

4.2 Intersecting Concatenated Codes

In the remainder of this section, we consider several constructions of intersecting codes based on concatenation [22, 34]. We need the following Lemma, first used implicitly in [19]:

Lemma 4.1 Let C_{o} be an [n_{o}, k_{o}, d_{o}] intersecting code over 𝔽_{q^{m}} and C_{i} be an [n_{i}, k_{i}, d_{i}] intersecting code over 𝔽_{q} with m = k_{i}. The concatenated code C = C_{o} ⋆ C_{i} over 𝔽_{q} is an [n_{o}n_{i}, k_{o}k_{i}, ≥ d_{o}d_{i}] intersecting code.

Proof. The fact that the resulting code has parameters [n_{o}n_{i}, k_{o}k_{i}, ≥ d_{o}d_{i}] is well known. Consider two non-zero codewords c_{0} and c_{1} of the concatenated code C. By construction, both c_{0} and c_{1} are made of n_{o} blocks of n_{i} 𝔽_{q}-symbols and must have been obtained through non-zero codewords c_{0}^{o} and c_{1}^{o} of the outer code C_{o}. By assumption, c_{0}^{o} and c_{1}^{o} intersect in at least one position j, thus block j of both c_{0} and c_{1} are non-zero codewords of the inner code C_{i}. By assumption, these blocks intersect and thus c_{0} and c_{1} intersect as well.

The following constructions are based on a simple observation of [19]: if M defines an [n, k, d] code for some d > \frac{n}{2} then it must intersect (by a pigeon-hole argument: any two codewords of such a code intersect). Unfortunately, for binary codes, Plotkin’s bound [34] implies that [n, k, \frac{n}{2} + 1] codes can only exist for n > 2^{k}, which would result in terribly wasteful zigzags. But for larger fields we can exploit this idea and then combine it with concatenation to build intersecting codes over 𝔽_{2}.

4.3 Las Vegas Construction

Although the result of section 4.1 implies that binary linear (O(k), k)-zigzags exist and can be obtained easily by picking one at random, it does not provide an efficient way of building a guaranteed zigzag. The problem of checking if a random matrix defines a zigzag seems rather hard: it is trivially solvable in exponential time but no polynomial-time algorithm for this problem is known. Nevertheless, using concatenation we can build from a random matrix defining a zigzag, new matrices exponentially larger with no extra effort to check if they also define a zigzag. Therefore, the exponential time necessary to check if a random matrix defines a zigzag becomes negligible with respect to the full size of the matrix. Joe Kilian [32] inspired by the concatenation method of [19] has exploited this into a Las Vegas construction of intersecting codes that we now describe.

Construction Consider any γ > α = log_{4/3} 4.

• Use a [2^{m}, 2^{m−1}, 2^{m−1} + 1] extended Reed-Solomon code over 𝔽_{2^{m}} as outer code C_{o}.

• Pick random m×γm binary matrices until one is found that defines an intersecting code (this is checked by an exhaustive verification procedure) and use it as inner code C_{i}.

The resulting C = C_{o} ⋆ C_{i} is a [2γk, k, d] binary intersecting code for k = m2^{m−1} and some d. Thus, for any choice of γ > α, this yields a (2γk, k)–zigzag when k = m2^{m−1}. Although this construction is limited to values of k of that precise form, a similar construction using an incomplete outer Reed-Solomon code yields a similar expansion factor for any value of k. Details of this generalization are left to the reader.

As observed by Cohen and Lempel in [8], since the Reed-Solomon codes are minimumdistance separable, it is impossible that similar codes with a smaller minimal distance intersect. Since the size of the random inner code is also optimal in the sense of the previous section, we conclude that this technique cannot yield (2λk, k)–zigzag for λ < α.

Time Complexity By the result of Section 4.1, m × γm matrices defining an intersecting code always exist and for sufficiently large m, at least half of these matrices have this property. Thus only a constant number of matrices must be tested on the average.

Checking whether or not a matrix M has the property requires to find all the codewords generated by M, which takes time in O(m2^{m}), and to check that each pair of codewords intersect, which takes time in O(m2^{2m}). The total average running time is therefore in O(k^{2}) since k = m2^{m−1}.

4.4 Deterministic Construction à la Goppa

An alternative to Reed-Solomon codes for getting outer codes with d > n/2, first put forward by Crépeau and Sántha [19], is to use algebraic-geometric (AG) codes of Goppa [27]. We rely on the work of Katsman, Tsfasman and Vlǎduţ [29] for their polynomial construction.

Proposition 4.2 ([35]) If q = p^{2m} for some prime p, it is possible to construct in polynomial time [N, K, D] codes over 𝔽_{q} with parameters everywhere along the line of equation

\frac{K}{N} + \frac{D}{N} = 1 − \frac{1}{\sqrt{q} − 1}.

Corollary 4.3 For q > 9, some AG–code of length N has minimal distance at least N/2+1.

Construction Let q = 2^{2m} for m > 1, and let Γ_{q} = \frac{1}{2} − \frac{1}{\sqrt{q}−1}.

• Use an [N, Γ_{q}N, N/2 + 1] AG–code over 𝔽_{q} for outer code C_{o}.

• Use any [n_{i}, 2m, d_{i}] intersecting binary code as inner code C_{i}.

The result C = C_{o} ⋆ C_{i} is a [n_{i}N, 2mΓ_{q}N, d] binary intersecting code with d ≥ d_{i}(N/2 + 1).

Examples With m = 2 this construction yields [27k/2, k, d] binary intersecting codes for k = 2N/3, if we use the [9, 4, 4] inner code of the simple family defined in Section 3.3. If, as in [19], we restrict our attention to inner codes that are members of that family, the best field is 𝔽_{256} with an expansion factor of 7.7885, that is m = 4 yielding [405k/52, k, d] binary intersecting codes for k = 52N/15. More recently, through this same construction, Cohen and Zemor [9] have obtained a better expansion factor (6.4138) for m = 5 using the binary [30, 10, 11] intersecting inner code of the dual BCH code type [8].

Time Complexity This is the drawback of this approach: current constructions of AG– codes require O(k^{32}) operations. Thus, although the construction is polynomial-time, it is quite impractical.

4.5 Deterministic Construction à la Justesen

We now take a deterministic approach similar to the construction of Justesen [34] for efficiently constructible good families of codes. Consider for α_{1}, α_{2}, ..., α_{a} ∈ 𝔽_{q^{m}} \ {0^{m}} the following codes of length n = (a + 1)m over 𝔽_{q}:

C_{α_{1},α_{2},...,α_{a}} = {[u, α_{1}u, α_{2}u, ..., α_{a}u] : u ∈ 𝔽_{q^{m}}}.

Denote h_{q}(x) the q-ary entropy function h_{q}(x) = x log_{q}(q − 1) − x log_{q} x − (1 − x) log_{q}(1 − x).

Theorem 4.4 Some of the codes C_{α_{1},α_{2},...,α_{a}} of length n = (a + 1)m have minimal distance larger than γn as long as h_{q}(γ) < a/(a + 1) and m is large enough.

Proof. Notice that if (α_{1}, α_{2}, ..., α_{a}) ≠ (α′_{1}, α′_{2}, ..., α′_{a}) then

C_{α_{1},α_{2},...,α_{a}} ⋂ C_{α′_{1},α′_{2},...,α′_{a}} = {0^{n}}

since any vector [u, v_{1}, v_{2}, ..., v_{a}] with non-zero u uniquely defines

(α_{1}, α_{2}, ..., α_{a}) = (v_{1}u^{−1}, v_{2}u^{−1}, ..., v_{a}u^{−1}).

Therefore a given vector [u ≠ 0, v_{1}, v_{2}, ..., v_{a}] belongs to a single C_{α_{1},α_{2},...,α_{a}}. The number of non-zero words of length n = (a + 1)m and weight less or equal to γn is [34]

∑_{i=1}^{γ(a+1)m} \binom{(a + 1)m}{i}(q − 1)^{i} ≤ q^{(a+1)mh_{q}(γ)}.

Since each such word belongs to a single code, only q^{(a+1)mh_{q}(γ)} of these codes may have minimal distance smaller than or equal to γn. The total number of C_{α_{1},α_{2},...,α_{a}} is (q^{m} − 1)^{a}. Therefore codes C_{α_{1},α_{2},...,α_{a}} with minimal distance at least γn exist provided (q^{m})^{(a+1)h_{q}(γ)} < (q^{m} − 1)^{a}. This is guaranteed whenever h_{q}(γ) < a/(a + 1) and m is large enough that (q^{m})^{δ} < q^{m} − 1, where δ = (a + 1)h_{q}(γ)/a < 1.

Corollary 4.5 From the above we get the following for large enough m:

• For q > 60, some [n = 3m, m, d] code C_{α,β} achieves d > n/2.

• For q > 3, some [n = 10m, m, d] code C_{α_{1},α_{2},...,α_{9}} achieves d > n/2.

These codes are intersecting.

Construction Let q = 2^{b} for some b > 0 and a be such that h_{q}(1/2) < a/(a+1). Consider any m large enough that q^{(a+1)mh_{q}(1/2)/a} < q^{m} − 1. Take N = mq^{m}.

• Use a [q^{m}, q^{m}/2, q^{m}/2 + 1] extended Reed-Solomon code over 𝔽_{q^{m}} as primary outer code C_{o}.

• Search through all the C_{α_{1},α_{2},...,α_{a}} of length n = (a + 1)m over 𝔽_{q} until an intersecting [(a + 1)m, m, d_{i}] code is found and use it as primary inner code C_{i}.

• Use any [n_{i}, b, d_{i}] intersecting binary code as secondary inner code C_{I}.

The result C_{O} = C_{o} ⋆C_{i} is an [(a+1)N, N/2, d_{O}] intersecting code over 𝔽_{q}, while C = C_{O} ⋆C_{I} is a binary [(a + 1)n_{i}N, bN/2, d] intersecting code for some d_{O} and d.

Examples

• For b = 6 we get that C_{o} is a [64^{m}, 64^{m}/2, 64^{m}/2 + 1] code, C_{i} a [3m, m, d_{i}] code and C_{I} a [15, 6, 6] code, yielding a [15k, k, d] binary intersecting code, for k = 3m64^{m}.

• For b = 2 we get that C_{o} is a [4^{m}, 4^{m}/2, 4^{m}/2 + 1] code, C_{i} a [10m, m, d_{i}] code and C_{I} a [3, 2, 2] code, yielding a [30k, k, d] binary intersecting code, for k = m4^{m}.

As in Section 4.3 a construction using an incomplete outer Reed-Solomon code yields a similar expansion factor for any value of k. Details of this generalization are left to the reader.

Time Complexity The first example above is the fastest deterministic construction known to the authors of a good family of intersecting codes and thus of a good zigzag family. For k = 3m64^{m}, in the worst case only (64^{m} − 1)^{2} < (k/ lg k)^{2} codes C_{α,β} will be tested for self-intersection. Testing each such code requires comparing 64^{2m} pairs of codewords of length 3m. This requires O(k^{2}/ lg k) operations. Therefore the total running time is in O(k^{4}/(lg k)^{3}) in the worse case.

5 Ongoing Research and Open Questions

We have shown how to construct linear-size zigzags both by probabilistic and deterministic polynomial-time methods. The exact complexity of the decision problem “Given a matrix M, is it the generator of a zigzag?” still has to be determined (the best we can say is that it is in co -NP). Another open problem is to construct over 𝔽_{q} some zigzag that will do better than the asymptotic bounds of Section 4.1. Finally we ask if non-linear functions can generate smaller zigzags than linear functions.

An important fact about the method based on zigzag functions considered in this paper is that, by definition of the zigzag, there is no way for B to learn information about both w_{0} and w_{1} even though the zigzag function is known before he gets to choose which bits to obtain through the (_{1}^{2})–OT_{2} instances in Protocol 1.1 (unless a Monte Carlo zigzag family is used). We are currently investigating [5] another approach to the problem of reducing (_{1}^{2})–OT_{2}^{k} to (_{1}^{2})–OT_{2}, in which A does not reveal the function to B until after the necessary (_{1}^{2})–OT_{2}’s have been performed.

Our new approach is based on privacy amplification, a technique invented in [4] and refined in [3]. Assume A knows a random n–bit string x about which B has partial information. Privacy amplification allows A to shrink x to a shorter string y about which B has an arbitrarily small amount of information even if he knows the recipe used by A to transform x into y. Intuitively, this can be used to implement (_{1}^{2})–OT_{2}^{k}(w_{0}, w_{1})(c) from (_{1}^{2})–OT_{2} because A can offer B to read one of two random strings x_{0} or x_{1} by a simple sequence of (_{1}^{2})–OT_{2}(x_{0}^{i}, x_{1}^{i})(c_{i}). Subsequently, A tells B how to transform x_{0} into w_{0} and x_{1} into w_{1} by way of privacy amplification. An honest B who accessed all the bits of x_{c} can reconstruct w_{c} from this information. But a dishonest B who accessed some of the bits of x_{0} and some of the bits of x_{1} will not have enough information on at least one of them to infer any information on the corresponding w or even joint information on both w_{0} and w_{1}.

Privacy amplification allows for a protocol that is simpler, more general and more efficient than the zigzag-based solution investigated in this paper, but at the cost of a vanishingly small failure probability. More specifically, 2k + s instances of (_{1}^{2})–OT_{2} are sufficient to implement (_{1}^{2})–OT_{2}^{k} so that the probability that a cheating B may learn information on both strings is exponentially small in s. This is significantly better than all the methods based on zigzag functions provided a probability of failure is tolerable. Moreover, it allows the implementation of (_{1}^{2})–OT_{2}^{k} at no extra cost if the underlying (_{1}^{2})–OT_{2} goes in the other direction, i.e. from B to A, or if it permits B to choose not only one bit or the other, but also their exclusive-or. A drawback of this approach is that a new function must be generated and transmitted at each run of the protocol. We postpone our detailed exposition of this alternative technique because our research is still ongoing [5]. In particular, we wish to investigate the extent of its generality.

Acknowledgments

We thank P. Barbaroux, J. Buchmann, I. B. Damgård, W. Fernandez De La Vega, A. Joux, L. Salvail and J. Stern for their help, comments and suggestions. Special thanks to J.–M. Robert for his earlier collaboration on this topic, O. Goldreich and S. Micali for suggesting characterization (8), J. Kilian for Construction 4.3, D. Mayers and J. van de Graaf for helpful discussions on the definitions of Section 2.2. Claude thanks S. Goldwasser for introducing him to Goppa codes, P. Elias for providing an extensive bibliography on the topic and G. Cohen for valuable information about his earlier research on intersecting codes.

References

[1] D. Beaver, “Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority”, Journal of Cryptology, Vol. 4, no. 2, 1991, pp. 75 – 122.

[2] M. Bellare and S. Micali, “Non-interactive oblivious transfer and applications”, Advances in Cryptology: Crypto ’89 Proceedings, Springer-Verlag, 1990, pp. 547 – 559.

[3] C. H. Bennett, G. Brassard, C. Crépeau and U. M. Maurer, “Generalized privacy amplification”, IEEE Transactions on Information Theory, Vol. 41, no. 6, November 1995, pp. 1915 – 1923.

[4] C. H. Bennett, G. Brassard and J.–M. Robert, “Privacy amplification by public discussion”, SIAM Journal on Computing, Vol. 17, no. 2, April 1988, pp. 210 – 229.

[5] G. Brassard and C. Crépeau, “Oblivious transfers and privacy amplification”, manuscript, 1996.

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

[7] R. Cleve, “Controlled gradual disclosure schemes for random bits and their applications”, Advances in Cryptology: Crypto ’89 Proceedings, Springer-Verlag, 1990, pp. 573 – 588.

[8] G. Cohen and A. Lempel, “Linear intersecting codes”, Discrete Mathematics, Vol. 56, 1985, pp. 35 – 43.

[9] G. Cohen and G. Zemor, “Intersecting codes and independent families”, IEEE Transactions on Information Theory, Vol. 40, no. 6, November 1994, pp. 1872 – 1881.

[10] C. Crépeau, “A zero-knowledge poker protocol that achieves confidentiality of the players’ strategy or how to achieve an electronic poker face”, Advances in Cryptology: Crypto ’86 Proceedings, Springer-Verlag, 1987, pp. 239 – 247.

[11] C. Crépeau, “Equivalence between two flavours of oblivious transfers (abstract)”, Advances in Cryptology: Crypto ’87 Proceedings, Springer-Verlag, 1988, pp. 350 – 354.

[12] C. Crépeau, “Verifiable disclosure of secrets and applications”, Advances in Cryptology: Eurocrypt ’89 Proceedings, Springer-Verlag, 1990, pp. 150 – 154.

[13] C. Crépeau, Correct and private reductions among oblivious transfers, PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1990. (Supervised by Silvio Micali.)

[14] C. Crépeau, “Quantum oblivious transfer”, Journal of Modern Optics, Vol. 41, no. 12, December 1994, pp. 2445 – 2454.

[15] C. Crépeau, J. van de Graaf and A. Tapp, “Committed oblivious transfer and private multi-party computations”, Advances in Cryptology: Crypto ’95 Proceedings, Springer-Verlag, 1995, pp. 110 – 123.

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

[17] C. Crépeau and L. Salvail, “Oblivious verification of common string”, CWI Quarterly, Vol. 8, no. 2, June 1995, pp. 97 – 109.

[18] C. Crépeau and M. Sántha, “On the reversibility of oblivious transfer”, Advances in Cryptology: Eurocrypt ’91 Proceedings, Springer-Verlag, 1992, pp. 106 – 113.

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

[20] S. Even, O. Goldreich and A. Lempel, “A randomized protocol for signing contracts”, Advances in Cryptology: Proceedings of Crypto ’82, Plenum Press, New York, 1983, pp. 205 – 210.

[21] R. Fagin, M. Naor and P. Winkler, “Comparing common secret information without leaking it”, Communications of the ACM, submitted for publication, 1994.

[22] G. D. Forney, Concatenated Codes, The M.I.T. Press, 1966.

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

[24] O. Goldreich and R. Vainish, “How to solve any protocol problem—an efficiency improvement”, Advances in Cryptology: Crypto ’87 Proceedings, Springer-Verlag, 1988, pp. 73 – 86.

[25] S. Goldwasser and L. Levin, “Fair computation of general functions in presence of immoral majority”, Advances in Cryptology: Crypto ’90 Proceedings, Springer-Verlag, 1991, pp. 77 – 93.

[26] S. Goldwasser, S. Micali and C. Rackoff, “The knowledge complexity of interactive proof-systems”, SIAM Journal on Computing, Vol. 18, 1989, pp. 186 – 208.

[27] V. D. Goppa, “Codes on algebraic curves”, Soviet Mathematical Doklady, Vol. 24, no. 1, 1981, pp. 170 – 172.

[28] G. Katona and J. Srivastava, “Minimal 2–coverings of finite affine spaces based on GF (2) ”, Journal of Statist. Plann. Inference, Vol. 8, 1983, pp. 375 – 388.

[29] G. L. Katsman, M. A. Tsfasman and S. G. Vlǎduţ, “Modular curves and codes with a polynomial construction”, IEEE Transactions on Information Theory, Vol. 30, no. 2, March 1984, pp. 353 – 355.

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

[31] J. Kilian, “A general completeness theorem for two-party games”, Proceedings of 23rd Annual ACM Symposium on Theory of Computing, 1991, pp. 553 – 560.

[32] J. Kilian, Personal communication.

[33] J. Kilian, S. Micali and R. Ostrovsky, “Minimum resource zero-knowledge proofs”, Proceedings of 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 474 – 479.

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

[35] Yu. I. Manin and S. G. Vlǎduţ, “Linear codes and modular curves” (in Russian), Sovr. Prob. Mat., Viniti, 1984.

[36] S. Micali and P. Rogaway, “Secure computation”, Advances in Cryptology: Crypto ’91 Proceedings, Springer-Verlag, 1992, pp. 392 – 404.

[37] D. Miklós, “Linear binary codes with intersecting properties”, Discrete Applied Mathematics, Vol. 9, no. 2, 1984, pp. 187 – 196.

[38] H. Nurmi, A. Salomaa and L. Santean, “Secret ballot elections in computer networks”, Computers & Security, Vol. 10, no. 6, 1991, pp. 553 – 560.

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

[40] C. T. Retter, “Intersecting goppa codes”, IEEE Transactions on Information Theory, Vol. 35, 1989, pp. 822 – 829.

[41] A. De Santis, G. Di Crescenzo and G. Persiano, “Zero-knowledge arguments and publickey cryptography”, Information and Computation, Vol. 121, no. 1, 1995, pp. 23 – 40.

[42] N. J. A. Sloane, “Covering arrays and intersecting codes”, Journal of Combinatorial Designs, Vol. 1, 1993, pp. 51 – 63.

[43] S. Wiesner, “Conjugate coding”, Sigact News, Vol. 15, no. 1, 1983, pp. 78 – 88. Original manuscript written circa 1970.

A Proofs of Correctness and Privacy

Both Protocol 1.1 and Protocol 1.2 were described for the specific set F = {0, 1}. As a matter of fact, they would work equally well for any finite set F. Thus in the proofs we do not consider any particular F.

A.1 Protocol 1.1

We show that given that f is an (n, k)-zigzag, protocol 1.1 is correct and private. We assume the existence of a correct and private sub-protocol [Ū, V̄] for (_{1}^{2})–OT_{2}.

Theorem A.1 Protocol 1.1 is correct.

Proof.

Condition (4): Since [Ū, V̄] is correct for (_{1}^{2})–OT_{2} by assumption, B gets the desired values x_{c}^{i} at step 2. By definition of x_{0}, x_{1} at step 1, it is clear that the value computed at step 3 is indeed w_{c} = f(x_{c}).

Condition (5): By assumption [Ū, V̄] is correct for (_{1}^{2})–OT_{2} and therefore for any program Ũ_{i} there exists a probabilistic program S̃_{i} s.t. ∀b_{0}^{i}, b_{1}^{i} ∈ F, c ∈ {0, 1}

([Ũ_{i}, V̄]B (b_{0}^{i}, b_{1}^{i})(c) | B accepts ) = ([Ū, V̄]B (S̃_{i}(b_{0}^{i}, b_{1}^{i}))(c) | B accepts ) .  (10)

We now describe the program for S̃ as a function of Ã. On input (w_{0}, w_{1}), for 1 ≤ i ≤ n, run protocol [Ã, B̄] on inputs (w_{0}, w_{1})(0) until the i^{th} execution of (_{1}^{2})–OT_{2}. Call Ũ_{i} the behaviour of Ã from that point on until the end of that execution. Let b_{0}^{i}, b_{1}^{i} be the inputs to (_{1}^{2})–OT_{2} used by Ã if such inputs exist and otherwise let b_{0}^{i}, b_{1}^{i} be anything as they are irrelevant anyway. By assumption, there exists S̃_{i} that satisfies (10). S̃ sets (z_{0}^{i}, z_{1}^{i}) ← S̃_{i}(b_{0}^{i}, b_{1}^{i}). If at any point B̄ aborts then S̃ aborts as well. Finally, S̃ returns f(z_{0}), f(z_{1}). If A runs S̃ and then Ā instead of running Ã then B will see the same output distribution.

Theorem A.2 Protocol 1.1 is private.

Proof. First notice that neither step 1 nor step 3 involve information transfers from either parties. Thus the only possible step in which A or B could learn something about their respective inputs is step 2.

Condition (6): By assumption [Ū, V̄] is private for (_{1}^{2})–OT_{2} and thus ∀X_{0}^{i}, X_{1}^{i} ∈ F, C ∈ {0, 1} and any program Ũ

I (C; [Ũ, V̄]A^{∗}(X_{0}^{i}, X_{1}^{i})(C) | X_{0}^{i}, X_{1}^{i}) = 0.

Therefore A learns nothing about C through any of the iterations of step 2 either. Which means that ∀W_{0}, W_{1} ∈ F^{k}, C ∈ {0, 1} and for any program Ã

I (C; [Ã, B̄]A^{∗}(W_{0}, W_{1})(C) | W_{0}, W_{1}) = 0.

Condition (7): By assumption [Ū, V̄] is private for (_{1}^{2})–OT_{2} and therefore for each i ∀X_{0}^{i}, X_{1}^{i} ∈ F, C ∈ {0, 1} and for any program Ṽ there exists a random variable C̃_{i} = ξ_{i}(C) ∈ {0, 1} s.t.

I ((X_{0}^{i}, X_{1}^{i}); [Ū, Ṽ]B^{∗}(X_{0}^{i}, X_{1}^{i})(C) | C, Xi ; C̃_{i}) = 0

and therefore

I ((X_{0}, X_{1}); [Ā, B̃]B^{∗}(W_{0}, W_{1})(C) | C, X1 ; C̃_{1}, X2 ; C̃_{2}, ..., Xn ; C̃_{n}) = 0

which implies

I ((W_{0}, W_{1}); [Ā, B̃]B^{∗}(W_{0}, W_{1})(C) | C, X1 ; C̃_{1}, X2 ; C̃_{2}, ..., Xn ; C̃_{n}) = 0

which is the same as

H ((W_{0}, W_{1}) | [Ā, B̃]B^{∗}(W_{0}, W_{1})(C), C, X1 ; C̃_{1}, X2 ; C̃_{2}, ..., Xn ; C̃_{n} ) =

H ((W_{0}, W_{1}) | C, X1 ; C̃_{1}, X2 ; C̃_{2}, ..., Xn ; C̃_{n} ) .  (11)

From here on, we omit C as everything is conditioned by it. Let C̃ be the random variable such that

C̃ = \{ \begin{matrix}0 & if \{i : C̃_{i} = 1\} does not bias f \\ 1 & otherwise \end{matrix} .

Since f is a zigzag only WC̃ is biased by the Xi ; C̃_{i}’s and thus there exists a random variable ŴC̃ = Φ(WC̃) such that

H ((W_{0}, W_{1}) | X1 ; C̃_{1}, X2 ; C̃_{2}, ..., Xn ; C̃_{n} ) = H ((W_{0}, W_{1}) | ŴC̃) .  (12)

Now suppose

H ((W_{0}, W_{1}) | [Ā, B̃]B^{∗}(W_{0}, W_{1})(C), ŴC̃ ) < H ((W_{0}, W_{1}) | ŴC̃) .

This would imply by equations (11) and (12) to appear in IEEE Transactions on Information Theory 23

H ((W_{0}, W_{1}) | [Ā, B̃]B^{∗}(W_{0}, W_{1})(C), ŴC̃ ) <

H ((W_{0}, W_{1}) | [Ā, B̃]B^{∗}(W_{0}, W_{1})(C), X1 ; C̃_{1}, X2 ; C̃_{2}, ..., Xn ; C̃_{n} )

which is impossible since ŴC̃ can be deduced from X1 ; C̃_{1}, X2 ; C̃_{2}, ..., Xn ; C̃_{n}. Thus we also have

H ((W_{0}, W_{1}) | [Ā, B̃]B^{∗}(W_{0}, W_{1})(C), ŴC̃ ) = H ((W_{0}, W_{1}) | ŴC̃) .

Now using on both sides of the equality a property of the entropy function

H (X|Y) = H (Y |X) + H (X) − H (Y)

we obtain

H ([Ā, B̃]B^{∗}(W_{0}, W_{1})(C), ŴC̃ | (W_{0}, W_{1}))−H ([Ā, B̃]B^{∗}(W_{0}, W_{1})(C), ŴC̃)+H ((W_{0}, W_{1})) =

H ( ŴC̃ | (W_{0}, W_{1})) − H \binom{}{WC̃} + H ((W_{0}, W_{1}))

and thus

H ([Ā, B̃]B^{∗}(W_{0}, W_{1})(C) | (W_{0}, W_{1})) = H ([Ā, B̃]B^{∗}(W_{0}, W_{1})(C), ŴC̃) − H \binom{}{WC̃} .

But by definition of the right-hand side

H ([Ā, B̃]B^{∗}(W_{0}, W_{1})(C) | (W_{0}, W_{1})) = H ([Ā, B̃]B^{∗}(W_{0}, W_{1})(C) | ŴC̃) .

This clearly implies that the same is true for WC̃

H ([Ā, B̃]B^{∗}(W_{0}, W_{1})(C) | (W_{0}, W_{1})) = H ([Ā, B̃]B^{∗}(W_{0}, W_{1})(C) | WC̃)

leading by inversion of the previous steps to the result

I ((W_{0}, W_{1}); [Ā, B̃]B^{∗}(W_{0}, W_{1})(C) | C, WC̃) = 0.

to appear in IEEE Transactions on Information Theory 24

A.2 Protocol 1.2

We assume the existence of a correct and private sub-protocol [Ū, V̄] for (_{1}^{2})–OT_{2}^{k}. Theorem A.3 Protocol 1.2 is correct. Proof. Condition (4): Let Ā and B̄ be as in protocol 1.2. From the description of the protocol we find

[Ā, B̄](w_{0}, w_{1}, ..., w_{t−1})(c) = (ϵ, ⨁_{i=0}^{ĉ} z_{i}).

Thus we have to show ⨁_{i=0}^{ĉ} z_{i} = w_{c}. Remember from the protocol that

z_{i} = \{ \begin{matrix}w_{i} ⊕ x_{i} & if c = i \\ x_{i+1} ⊕ x_{i} & if c ≠ i. \end{matrix}

First, consider the case c = ĉ < t − 1.

⨁_{i=0}^{ĉ} z_{i} = ⨁_{i=0}^{c} z_{i}
= z_{c} ⊕ z_{c−1} ⊕ ... ⊕ z_{0}
= w_{c} ⊕ x_{c} ⊕ x_{c} ⊕ x_{c−1} ⊕ ... ⊕ x_{2} ⊕ x_{1} ⊕ x_{1} ⊕ x_{0}
= w_{c} ⊕ x_{0}
= w_{c}

Second, consider the case c = t − 1.

⨁_{i=0}^{ĉ} z_{i} = ⨁_{i=0}^{t−2} z_{i}
= x_{t−1} ⊕ x_{t−2} ⊕ x_{t−2} ⊕ x_{t−3} ⊕ ... ⊕ x_{2} ⊕ x_{1} ⊕ x_{1} ⊕ x_{0}
= x_{t−1} ⊕ x_{0}
= w_{t−1}
= w_{c}

Therefore we find [Ā, B̄](w_{0}, w_{1}, ..., w_{t−1})(c) = (ϵ, w_{c}) as required. Condition (5): By assumption [Ū, V̄] is correct for (_{1}^{2})–OT_{2}^{k} and therefore for any program Ũ_{i} there exists a probabilistic program S̃_{i} s.t. ∀y_{0}^{i}, y_{1}^{i} ∈ F^{k}, e ∈ {0, 1}

([Ũ_{i}, V̄]B (y_{0}^{i}, y_{1}^{i})(e) | B accepts ) = ([Ū, V̄]B (S̃_{i}(y_{0}^{i}, y_{1}^{i}))(e) | B accepts ) . (13)

We now describe the program for S̃ as a function of Ã. On input w⃗, for 0 ≤ i ≤ t−2, run protocol [Ã, B̄] on inputs (w⃗)(0) until the i^{th} execution of (_{1}^{2})–OT_{2}^{k}. Call Ũ_{i} the behaviour of Ã from that point on until the end of that execution. Let y_{0}^{i}, y_{1}^{i} be the inputs to (_{1}^{2})–OT_{2}^{k} used by Ã if such inputs exist and otherwise let y_{0}^{i}, y_{1}^{i} be anything as they are irrelevant anyway. By assumption, there exists S̃_{i} that satisfies (13). S̃ sets (z_{0}^{i}, z_{1}^{i}) ← S̃_{i}(y_{0}^{i}, y_{1}^{i}). If at any point B̄ aborts then S̃ aborts as well. Finally, S̃ returns z_{0}^{0}, z_{1}^{0} ⊕ z_{0}^{1}, z_{1}^{1} ⊕ z_{0}^{2}, ..., z_{1}^{t−3} ⊕ z_{0}^{t−2}, z_{1}^{t−2} ⊕ z_{0}^{t−1}, z_{1}^{t−2} ⊕ z_{1}^{t−1}. If A runs S̃ and then Ā instead of running Ã then B will see the same output distribution.

Theorem A.4 Protocol 1.2 is private.

Proof. As for Protocol 1.1 neither step 1 nor step 3 involve information transfers from either parties. Thus the only possible step in which A or B could learn something about their respective inputs is step 2.

Condition (6): By assumption [Ū, V̄] is private for (_{1}^{2})–OT_{2}^{k} and thus ∀Y_{0}^{i}, Y_{1}^{i} ∈ F^{k}, C ∈ T and any program Ũ

I (C; [Ũ, V̄]A^{∗}(Y_{0}^{i}, Y_{1}^{i})(C ≠ i) | Y_{0}^{i}, Y_{1}^{i}) = 0.

Therefore A learns nothing about C through any of the iterations of step 2 either. Which means that ∀W⃗ ∈ F^{kt}, C ∈ T and for any program Ã

I (C; [Ã, B̄]A^{∗}(W⃗)(C) | W⃗ ) = 0.

Condition (7): By assumption [Ū, V̄] is private for (_{1}^{2})–OT_{2}^{k} and therefore for each i ∀Y_{0}^{i}, Y_{1}^{i} ∈ F^{k}, C ∈ T and for any program Ṽ there exists a random variable C̃_{i} = ξ_{i}(C) ∈ {0, 1} s.t.

I ((Y_{0}^{i}, Y_{1}^{i}); [Ū, Ṽ]B^{∗}(Y_{0}^{i}, Y_{1}^{i})(C ≠ i) | C, Y i ; C̃_{i}) = 0

where

Y i ; C̃_{i} = \{ \begin{matrix}W_{i} ⊕ X_{i} & if C̃_{i} = 0 \\ X_{i+1} ⊕ X_{i} & if C̃_{i} = 1 \end{matrix}

and therefore

I ((W⃗ , X⃗); [Ā, B̃]B^{∗}(W⃗)(C) | C, Y 1 ; C̃_{1}, Y 2 ; C̃_{2}, ..., Y t−2 ; C̃_{t−2}) = 0

which means

I (W⃗; [Ā, B̃]B^{∗}(W⃗)(C) | C, Y 1 ; C̃_{1}, Y 2 ; C̃_{2}, ..., Y t−2 ; C̃_{t−2}) = 0

which is the same as

H (W⃗ | [Ā, B̃]B^{∗}(W⃗)(C), C, Y 1 ; C̃_{1}, Y 2 ; C̃_{2}, ..., Y t−2 ; C̃_{t−2} ) =

H (W⃗ | C, Y 1 ; C̃_{1}, Y 2 ; C̃_{2}, ..., Y t−2 ; C̃_{t−2} ) .  (14)

Let C̃ be the random variable such that

C̃ = min_{i}{C̃_{i} = 0 or i = t − 1}.

By definition of the Y i ; C̃_{i}’s and because of the fact that the X_{i}’s are uniformly selected at random we get

H (W⃗ | C, Y 1 ; C̃_{1}, Y 2 ; C̃_{2}, ..., Y t−2 ; C̃_{t−2} ) = H (W⃗ | C, X_{0}, X_{1}, ..., XC̃, WC̃, Y_{C̃+1}, ..., Y t−2 ; C̃_{t−2}) =

H (W⃗ | C, WC̃) .  (15)

Now suppose

H (W⃗ | [Ā, B̃]B^{∗}(W⃗)(C), C, WC̃ ) < H (W⃗ | C, WC̃) .

This would imply by equations (14) and (15)

H (W⃗ | [Ā, B̃]B^{∗}(W⃗)(C), C, WC̃ ) <

H (W⃗ | [Ā, B̃]B^{∗}(W⃗)(C), C, Y 1 ; C̃_{1}, Y 2 ; C̃_{2}, ..., Y t−2 ; C̃_{t−2} )

which is impossible since WC̃ can be deduced from Y 1 ; C̃_{1}, Y 2 ; C̃_{2}, ..., Y t−2 ; C̃_{t−2}. Thus we also have

H (W⃗ | [Ā, B̃]B^{∗}(W⃗)(C), C, WC̃ ) = H (W⃗ | C, WC̃)

or equivalently

I (W⃗; [Ā, B̃]B^{∗}(W⃗)(C) | C, WC̃) = 0.

B Proof of Theorem 4.1

Theorem 4.1 Set α = log_{4/3} 4, and let M be a random k × n matrix over 𝔽_{2}. Then for every constant ε > 0, there exists a constant 0 < η < 1 such that we have the following two propositions:

1. If n ≥ (1 + ε)αk, then Prob {M defines a linear zigzag} > 1 − η^{k}, and

2. If n ≤ (1 − ε)αk, then Prob {M does not define a linear zigzag} > 1 − η^{k}.

Proof. Let a ≠ b be two non-zero binary row vectors of length k, and set S = {a, b}. Clearly M defines a linear zigzag if and only if for every such S, aM and bM intersect. Let D_{S} be the event that aM and bM do not intersect, and let X_{S} be the associated indicator random variable. As every bit in aM and bM is 1 with probability 1/2, we have

E[X_{S}] = Prob \{D_{S}\} = (\frac{3}{4})^{n} .

Let us define the random variable X = ∑_{S} X_{S}. Then M defines a linear zigzag if and only if X = 0. By linearity of the expectation,

E[X] = \binom{2^{k} − 1}{2} (\frac{3}{4})^{n} .

Proposition 1: n ≥ (1 + ε)αk. Then we have:

Prob \{X > 0\} ≤ E[X] < 2^{2k} (\frac{3}{4})^{n} ≤ (\frac{1}{4})^{εk} .

Proposition 2: n ≤ (1 − ε)αk. Then using Chebishev’s inequality, we have:

Prob \{X = 0\} ≤ Prob \{|X − E[X]| ≥ E[X]\} ≤ \frac{Var(X)}{E[X]^{2}}.

We will show that Var(X) is exponentially small compared to E[X]^{2}. Let a_{1} ≠ b_{1} and a_{2} ≠ b_{2} be non-zero row vectors of length k, and set S_{1} = {a_{1}, b_{1}} and S_{2} = {a_{2}, b_{2}}. Since X_{S_{1}} and X_{S_{2}} are 0-1 random variables, we have:

Var(X) = ∑_{S_{1},S_{2}} cov(X_{S_{1}}, X_{S_{2}}) = ∑_{S_{1},S_{2}} E[X_{S_{1}}](E[X_{S_{2}}|X_{S_{1}} = 1] − E[X_{S_{2}}]).

If the random variables X_{S_{2}} and X_{S_{1}} are not independent, then we will bound cov(X_{S_{1}}, X_{S_{2}}) from above by E[X_{S_{1}}]E[X_{S_{2}}|X_{S_{1}} = 1]. If X_{S_{2}} and X_{S_{1}} are independent, then cov(X_{S_{1}}, X_{S_{2}}) = 0. The proof works out because for most S_{1} and S_{2} they are indeed independent. We will prove this with the help of the following lemma:

Lemma B.1 Let M = (m_{i}^{j}) be a random k ×n binary matrix. If for some t > 0, {a_{1}, … a_{t}} is a linearly independent family of vectors of length k, then a_{1}M, …, a_{m}M are independent random variables.

Proof. Let us fix t binary vectors {b_{1}, … b_{t}} of length n. Let A be the t × k matrix whose i^{th} row is a_{i}, and similarly let B be the t × n matrix whose ith row is b_{i}. We will show that

Prob {AM = B} = 2^{−tn}.

We can suppose without loss of generality that the first t columns of A have rank t. Let us choose anyhow c_{i}^{j} ∈ 𝔽_{2} for i = t + 1, …, k and j = 1, …, n, and let us fix m_{i}^{j} = c_{i}^{j}. Let Â be the truncation of A to its first t columns, and let M̂ be the truncation of M to its first t rows. Finally let B̂ = (b̂_{i}^{j}) be the t × n matrix where b̂_{i}^{j} = b_{i}^{j} + ∑_{l=t+1}^{k} a_{i}^{l}c_{l}^{j}. The matrix Â is regular, therefore we have

Prob {ÂM̂ = B̂} = 2^{−tn}.

This implies the result since this is true for every choice of c_{i}^{j}.

It follows that the random variables X_{S_{1}} and X_{S_{2}} are independent when the family of vectors U = {a_{1}, b_{1}, a_{2}, b_{2}} is linearly independent. Thus we have to consider the covariances of only those random variables X_{S_{1}} and X_{S_{2}} where there is some linear dependence among the vectors of U. We will distinguish two cases according to the rank of U.

Case 1: rank(U) = 3. Then there exist coefficients α_{1}, β_{1}, α_{2}, β_{2} ∈ 𝔽_{2}, not all 0, such that α_{1}a_{1} + β_{1}b_{1} + α_{2}a_{2} + β_{2}b_{2} = 0. The number of such families is O(2^{3k}). Since a_{1} ≠ b_{1}, a_{2} ≠ b_{2} and the elements of U are non-zero vectors, we can suppose without loss of generality that α_{1} = α_{2} = 1. Therefore we are left with the following possible dependencies among the members of U: a_{2} = a_{1} or a_{2} = a_{1} + b_{1} or a_{2} = a_{1} + b_{2} or a_{2} = a_{1} + b_{1} + b_{2}.

Let us suppose that a_{1}M and b_{1}M do not intersect. Then we claim that in case of any of the above dependencies, the probability that a_{2}M and b_{2}M do not intersect either is at most (\frac{5}{6})^{n}. The proper analysis is quite similar in the four cases, let us consider here in details for example the case when a_{2} = a_{1}. Let 1 ≤ i ≤ n be an index. The string a_{1}^{i}b_{1}^{i} with probability \frac{1}{3} takes each of the values 00, 01 and 10. Since b_{2}^{i} = 1 with probability \frac{1}{2} independently from the value of a_{1}^{i}b_{1}^{i}, we have

Prob \{a_{2}^{i}b_{2}^{i} = 11|a_{1}^{i}b_{1}^{i} ≠ 11\} = \frac{1}{3} × 0 + \frac{1}{3} × 0 + \frac{1}{3} × \frac{1}{2} = \frac{1}{6}.

This is true independently for every i, and the claim follows. Therefore the total contribution to the variance of these families with respect to E[X]^{2} is

O (\frac{2^{3k}(\frac{3}{4})^{n}(\frac{5}{6})^{n}}{E[X]^{2}} ) = O ((\frac{(\frac{10}{9})^{α}}{2} )^{k}) .

Case 2: rank(U) = 2. Then S_{1} = S_{2}, and the number of such families is \binom{2^{k}−1}{2}. In this case E[X_{S_{1}}]E[X_{S_{2}}|X_{S_{1}} = 1] = E[X_{S_{1}}], and the total contribution to the variance with respect to E[X]^{2} is at most

\frac{1}{E[X]} = O ((\frac{1}{4})^{εk}) .