Oblivious Transfers and Privacy Amplification

12 February 1996

Abstract

Assume A owns two 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 string. 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-two String Oblivious Transfer, denoted (_{1}^{2})–OT_{2}^{k}. This primitive is particularly useful in a variety of cryptographic settings. An apparently simpler task corresponds to the case k = 1 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 reducing (_{1}^{2})–OT_{2}^{k} to (_{1}^{2})–OT_{2}.

This question is not new: it was introduced in 1986. However, most solutions until now have implicitly or explicitly depended on the notion of self-intersecting codes. It can be proved that this restriction makes it asymptotically impossible to implement (_{1}^{2})–OT_{2}^{k} with fewer than about 3.5277 k instances of (_{1}^{2})–OT_{2}. The current paper introduces the idea of using privacy amplification as underlying technique to reduce (_{1}^{2})–OT_{2}^{k} to (_{1}^{2})–OT_{2}. This allows for more efficient solutions at the cost of an exponentially small probability of failure: it is sufficient to use slightly more than 2k instances of (_{1}^{2})–OT_{2} in order to implement (_{1}^{2})–OT_{2}^{k}. Moreover, we show that privacy amplification allows for the efficient implementation of (_{1}^{2})–OT_{2}^{k} from generalized versions of (_{1}^{2})–OT_{2} that would not have been suitable for the earlier techniques based on self-intersecting codes. An application of this more general reduction is given.

Key Words: Information-Theoretic Security, Oblivious Transfer, Privacy Amplification, Reduction Between Protocols.

1 Introduction

The equivalence between cryptographic primitives is a major research topic [BCR86, Cré88, CK88, Kil88, Cré89, GL89, Cré90, Kil91, CS91a, CS91b, CGT95, CS95, BCS96]. 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 [Wie70] (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 [Wie70] but inspired by [Rab81], a natural restriction of this primitive was introduced subsequently in [EGL83] 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.

Techniques were introduced in [BCR86] and refined in [CS91b, BCS96] to reduce (_{1}^{2})–OT_{2}^{k} to (_{1}^{2})–OT_{2}: several two-party protocols were given to achieve One-out-of-two String Oblivious Transfer based on the assumption of the availability of a protocol for the simpler Oneout-of-two Bit Oblivious Transfer. The fact that (_{1}^{2})–OT_{2}^{k} can be reduced to (_{1}^{2})–OT_{2} is not surprising because a number of authors [GMW87, GV87, Kil88, Cré89, GL89, CGT95] have shown that (_{1}^{2})–OT_{2} is sufficient to implement any two-party computation. Our interest in direct reductions is their far greater efficiency. With the exception of [CS91a], all previous direct reductions that we are aware of [BCR86, CS91b, BCS96] are based on a notion called zigzag functions, whose construction is reduced to finding particular types of error-correcting codes called self-intersecting codes. In a nutshell, this approach consists in selecting once and for all a suitable zigzag function f from {0, 1}^{n} to {0, 1}^{k} for n > k as small as possible, so that if x_{0} is a random preimage of w_{0} and x_{1} is a random preimage of w_{1}, and if B is given to choose via (_{1}^{2})–OT_{2} to see the i^{th} bit of either x_{0} or x_{1}, 1 ≤ i ≤ n, then no information can be inferred on at least one of w_{0} or w_{1}. This approach has led to various reductions with expansion factors β ranging from 4.8188 to 18, that is various polynomial-time constructible methods using n = βk instances of (_{1}^{2})–OT_{2} to perform one (_{1}^{2})–OT_{2}^{k} on k–bit strings. Komlós proved that this approach cannot yield an expansion factor β that is asymptotically better than 3.5277 [CL85].

The current paper exploits a new approach to this problem using privacy amplification, a notion first introduced in the context of key exchange protocols [BBR88]. The new approach allows for a solution requiring only slightly more than 2k instances of (_{1}^{2})–OT_{2} to perform one (_{1}^{2})–OT_{2}^{k}, and it can be extended to a whole range of generalizations of (_{1}^{2})–OT_{2} that could not be used with the reductions based on self-intersecting codes.

An application of the simplest of our generalizations is also considered: (_{1}^{2})–OT_{2}^{k} from A to B can be reduced to (_{1}^{2})–OT_{2} in the other direction, ie from B to A, by only doubling the cost of reducing to (_{1}^{2})–OT_{2} from A to B. This improves on an earlier result of [CS91a].

2 Privacy Amplification Method

Assume A knows a random n–bit string x about which B has partial information. Privacy amplification is a technique invented in [BBR88] and refined in [BBCM95] that allows A to shrink x to a shorter string w about which B has an arbitrarily small amount of information even if he knows the recipe used by A to transform x into w. 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 tried to access 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_{i} or even joint information on both w_{0} and w_{1}.

An important fact about the method based on zigzag functions considered in earlier papers is that 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 of x_{0} and x_{1} to obtain through the (_{1}^{2})–OT_{2} instances. In the new approach based on privacy amplification, A reveals the function to B after the necessary (_{1}^{2})–OT_{2}’s have been performed. This allows for a protocol that is simpler, more general and more efficient, but at the cost of a vanishingly small probability of failure. A drawback of this approach is that a new function must be generated and transmitted at each run of the protocol.

The following table compares the efficiency of the earlier methods to that of privacy amplification. The column “expansion factor” gives a number β so that a (_{1}^{2})–OT_{2}^{k} can be achieved with βk instances of (_{1}^{2})–OT_{2}. Thus we see that the privacy amplification method is preferable provided a probability of failure can be tolerated.

expansion failure

construction

Method  factor probability  time
Monte Carlo Zigzag^{1} 4.8188 + ε  2^{−s}  O(k^{2})
Las Vegas Zigzag^{2}  9.6377 + ε  0  O(k^{2})
Zigzag à la Justesen^{3}  18  0  O(k^{4})
Zigzag à la Goppa^{4}  6.4103  0  O(k^{32})
Privacy Amplification 2 + ε  2^{−s}  O(k^{2})

1Attributed to Cohen and Lempel in [BCS96].

2Attributed to Joe Kilian in [BCS96].

3From [BCS96].

4From [CZ94] based on a method of [CS91b].

2.1 The New Protocol

Let s be a security parameter chosen by A and B so that they agree to tolerate a probability 2^{−s} of failure. Let γ be a constant to be determined later, let n = γk + s, and let 𝔽_{2} denote the field of integers modulo 2.

Privacy amplification is based on the general notion of universal classes of hash functions [CW79]. For sake of simplicity, we use a specific class of hash functions in our protocol to implement (_{1}^{2})–OT_{2}^{k} from (_{1}^{2})–OT_{2}: {h | h(x) = Mx, for M a k × n matrix over 𝔽_{2}}. Other, more efficient classes of hash functions can be used, but it is not known if the definition of universal_{2} classes is sufficient in general to make our protocol work.

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

1: A picks two random n–bit strings x_{0} and x_{1}.

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

3: A picks two random k × n matrices M_{0} and M_{1} over 𝔽_{2} and announces them to B.

4: A sets y_{0} ← M_{0}x_{0} ⊕ w_{0} and y_{1} ← M_{1}x_{1} ⊕ w_{1} and announces y_{0} and y_{1} to B.

5: B recovers w_{c} by computing M_{c}t ⊕ y_{c}.

We postpone to section 2.3 the proof that this protocol is private^{5} for an appropriate choice of γ because we shall first generalize it to permit at no extra cost the use of another primitive called XOR Oblivious Transfer.

2.2 XOR Oblivious Transfer

A (_{1}^{2})–XOT_{2} is an extension of (_{1}^{2})–OT_{2} that enables a sender A to transfer to a receiver B either one bit among b_{0} and b_{1} or their exclusive-or, at B’s choice. More formally, A inputs b_{0} and b_{1} into the protocol, B inputs c ∈ {0, 1, ⊕}, and B learns b_{c} while A learns nothing, where for convenience we use b_{⊕} to denote b_{0} ⊕ b_{1}. As usual, this is done in an all-or-nothing fashion: B cannot get more information about b_{0} and b_{1} than b_{0}, b_{1} or b_{⊕}, however malicious or (computationally) powerful he is.

The (_{1}^{2})–XOT_{2} comes naturally in a specific implementation of (_{1}^{2})–OT_{2}: in [BCR86a] a protocol for (_{1}^{2})–OT_{2} is given under the assumption that deciding quadratic residuosity modulo a composite number is hard. In that implementation, the possibility that B̃ obtains b_{⊕} arises naturally and some effort is made to prevent it. The current paper shows that this effort was unnecessary if the final goal is to implement (_{1}^{2})–OT_{2}^{k} rather than simply (_{1}^{2})–OT_{2}.

5 Informally, the protocol is private if B cannot learn information on both w_{0} and w_{1} except perhaps with negligible probability. In addition, B must not be able to obtain joint information on w_{0} and w_{1} except for what follows from his a priori knowledge and his learning one of the two strings. We shall later relax the condition to allow B an exponentially small amount of unauthorized information. Please consult the Appendix for a formal definition of this notion.

We consider XOR oblivious transfers for two additional reasons:

• Protocol 2.1 above works equally well using (_{1}^{2})–XOT_{2} instead of (_{1}^{2})–OT_{2} ;

• (_{1}^{2})–XOT_{2} can be implemented from only two instances of a reversed (_{1}^{2})–OT_{2} (from B to A). Therefore, (_{1}^{2})–OT_{2}^{k} from A to B can be implemented from slightly more than 4k instances of (_{1}^{2})–OT_{2} from B to A, a three-fold improvement over [CS91a].

This first result is discussed in section 2.3, while the second is seen in section 2.4.

2.3 Privacy

Consider a variation of Protocol 2.1 in which the transfers at step 2 are performed through (_{1}^{2})–XOT_{2} instead of (_{1}^{2})–OT_{2}. Even though this makes no difference if B follows the protocol honestly, it gives him additional opportunities for cheating if he so desires. Our goal is to show that whatever program B̃ is ran by B, he is not able to obtain information on both w_{0} and w_{1}, except with a probability that is exponentially small in the security parameter s. From now on, think of x_{0} and x_{1} as column-vectors of length n, and of m_{0} = M_{0}x_{0} and m_{1} = M_{1}x_{1} as column-vectors of length k, all over 𝔽_{2}. First, we show that immediately after Step 3 of the protocol, whatever program B̃ is ran by B, he will have no information about one of m_{0} or m_{1} and no information allowing him to connect m_{0} and m_{1} (such as m_{0} ⊕ m_{1} for instance), except with exponentially small probability. (Formally, there will be some bit c̃ such that the first three steps of the protocol would give no additional information to B̃ about the pair (m_{0}, m_{1}) than if he were simply told the value of mc̃—see the Appendix.) We conclude the result about w_{0} and w_{1} at the end of the protocol from the fact that m_{0} and m_{1} are used as one-time pads to transfer them.

Suppose B̃ reads the bits x_{c_{i}}^{i} with c_{i} ∈ {0, 1, ⊕} at his choosing. Let g be a non-trivial linear function of m_{0} and m_{1}. In other words, g(m_{0}, m_{1}) = v_{0}m_{0} ⊕ v_{1}m_{1} for some line-vectors v_{0} and v_{1} of length k over 𝔽_{2} such that both v_{0} and v_{1} are non-zero^{6}.

Theorem 2.1 Consider the knowledge that B̃ has about m_{0} and m_{1} immediately after Step 3 of the protocol.

Prob (∃ non-trivial g such that B̃ knows g(m_{0}, m_{1})) < 2^{−s}

provided γ ≥ 2.

Proof. We first describe the condition under which B̃ learns g(m_{0}, m_{1}) at Step 3 of the protocol for some specific non-trivial linear function g. By definition

g(m_{0}, m_{1}) = v_{0}m_{0} ⊕ v_{1}m_{1} = v_{0}M_{0}x_{0} ⊕ v_{1}M_{1}x_{1} = z_{0}x_{0} ⊕ z_{1}x_{1}

6 Note that by virtue of v_{0} and m_{0} being a line-vector and a column-vector, respectively, a “matrix”

multiplication such as v_{0}m_{0} computes the scalar product; similarly, given that x_{0} is also a column-vector, an expression such as v_{0}M_{0}x_{0} makes sense: it is simply an element of 𝔽_{2}. This notation is handy because v_{0}M_{0}x_{0} can be thought of indifferently as either the scalar product of v_{0} with M_{0}x_{0} or of v_{0}M_{0} with x_{0}.

where z_{0} = v_{0}M_{0} and z_{1} = v_{1}M_{1}. Because x_{0} and x_{1} are random, B̃ cannot learn anything about g(m_{0}, m_{1}) at Step 3 unless if he is lucky enough that his choices c_{i} simultaneously follow

c_{i} = \{ \begin{matrix}0 & when (z_{0}^{i}, z_{1}^{i}) = (1, 0) \\ 1 & when (z_{0}^{i}, z_{1}^{i}) = (0, 1) \\ ⊕ & when (z_{0}^{i}, z_{1}^{i}) = (1, 1) \end{matrix}

in all the instances of (_{1}^{2})–XOT_{2} such that z_{0}^{i} and z_{1}^{i} are not both 0. (The value of c_{i} is unimportant when (z_{0}^{i}, z_{1}^{i}) = (0, 0) since neither x_{0}^{i} nor x_{1}^{i} is required in that case to learn g(m_{0}, m_{1}).)

But remember that M_{0} and M_{1} are picked at random and neither v_{0} nor v_{1} is zero. Therefore z_{0} = v_{0}M_{0} and z_{1} = v_{1}M_{1} are random binary strings of length n chosen independently according to the uniform distribution. In particular, z_{0} and z_{1} are independent of B̃’s choices of c_{i}’s. It follows that, for each i, the probability that either (z_{0}^{i}, z_{1}^{i}) = (0, 0) or B̃ chose c_{i} appropriately according to the above case analysis is exactly 1/2. Since B̃ must be lucky for each i, 1 ≤ i ≤ n,

Prob (B̃ learns g(m_{0}, m_{1})) = 2^{−n}

for each non-trivial linear function g, whatever choices B̃ makes for the c_{i}’s. Finally, given that there are less than 2^{2k} such linear functions, we conclude that

Prob (∃ non-trivial g such that B̃ learns g(m_{0}, m_{1})) < 2^{2k−n} = 2^{(2−γ)k−s} ≤ 2^{−s}

provided γ ≥ 2.

Theorem 2.2 Protocol 2.1 is private even if the transfers at step 2 are performed through (_{1}^{2})–XOT_{2} instead of (_{1}^{2})–OT_{2}.

Proof. We know from Theorem 2.1 that, except with probability at most 2^{−s}, B has not learned g(m_{0}, m_{1}) by the end of Step 3 for any linear function g that involves both m_{0} and m_{1}. On the other hand, it is possible for B to learn linear functions of m_{0} or m_{1} alone (by setting all the c_{i} = 0 or c_{i} = 1 as in the honest protocol). It follows that there is a d ∈ {0, 1} such that B learns no non-trivial linear function of m_{d} because if he could learn non-trivial linear functions g_{0}(m_{0}) and g_{1}(m_{1}), he would have learned g_{0}(m_{0}) ⊕ g_{1}(m_{1}), a non-trivial linear function of both m_{0} and m_{1}. We can say something stronger: not only does B learn no non-trivial linear function of m_{d}, but he learns no information of any kind that involves m_{d}. This is true because m_{0} and m_{1} are purely random and the only source of information that B has about them (up until Step 3) is given by linear functions of m_{0} and m_{1}. Since m_{d} is used by A at Step 4 as one-time pad to transmit w_{d} to B, it follows that B learns no information of any kind that involves w_{d}.

2.4 Reversing Oblivious Transfer

Consider that A wants to send one of two words w_{0} or w_{1} to B when they only have an (_{1}^{2})–OT_{2} channel running from B to A. A very efficient protocol for sending one of two bits from A to B is given in [CS91a] provided A does not mind the possibility that B might learn the exclusive-or of her two bits. In other words it is much easier to implement (_{1}^{2})–XOT_{2} than (_{1}^{2})–OT_{2} from A to B given an (_{1}^{2})–OT_{2} channel from B to A. This is fine because we just showed that (_{1}^{2})–XOT_{2} is just as good as (_{1}^{2})–OT_{2} for the purpose of implementing (_{1}^{2})–OT_{2}^{k}. For completeness, here is the protocol from [CS91a] to implement (_{1}^{2})–XOT_{2} from an (_{1}^{2})–OT_{2} channel running in the reverse direction.

Protocol 2.2 ( (_{1}^{2})–XOT_{2}(b_{0}, b_{1})(c) )

1: if c = ⊕ then B sets c_{0} ← c_{1} ← 1 else B sets c_{0} ← c̄ and c_{1} ← c.
B picks two random bits x_{0}^{0}, x_{0}^{1} and sets x_{1}^{0} ← x_{0}^{0} ⊕ c_{0} and x_{1}^{1} ← x_{0}^{1} ⊕ c_{1}.
2: B transfers t_{0} ← (_{1}^{2})–OT_{2}(x_{0}^{0}, x_{1}^{0})(b_{0}) and t_{1} ← (_{1}^{2})–OT_{2}(x_{0}^{1}, x_{1}^{1})(b_{1}) to A.
3: A announces u ← t_{0} ⊕ t_{1} to B.
4: B recovers b_{c} by computing u ⊕ x_{0}^{0} ⊕ x_{0}^{1}.

Theorem 2.3 Protocol 2.2 is correct.

Proof. The output calculated by B is

u ⊕ x_{0}^{0} ⊕ x_{0}^{1} = x_{b_{0}}^{0} ⊕ x_{b_{1}}^{1} ⊕ x_{0}^{0} ⊕ x_{0}^{1}
= (x_{b_{0}}^{0} ⊕ x_{0}^{0}) ⊕ (x_{b_{1}}^{1} ⊕ x_{0}^{1})
= (b_{0} ∧ c_{0}) ⊕ (b_{1} ∧ c_{1})
since x_{i}^{j} ⊕ x_{0}^{j} = i ∧ c_{j} for i, j ∈ {0, 1}
= b_{c}.

The fact that this protocol cannot be used by A to find out about c is guaranteed by the fact that (_{1}^{2})–OT_{2} discloses only one of x_{0}^{j} or x_{1}^{j}. Similarly, the fact that B cannot use the protocol to find out more than b_{0}, b_{1} or b_{⊕} is guaranteed by the fact that

• if x_{0}^{0} = x_{1}^{0} and x_{0}^{1} = x_{1}^{1} then B finds out nothing;

• if x_{0}^{0} ≠ x_{1}^{0} and x_{0}^{1} = x_{1}^{1} then B finds out exactly b_{0};

• if x_{0}^{0} = x_{1}^{0} and x_{0}^{1} ≠ x_{1}^{1} then B finds out exactly b_{1};

• if x_{0}^{0} ≠ x_{1}^{0} and x_{0}^{1} ≠ x_{1}^{1} then B finds out exactly b_{⊕}.

2.5 Generalized Oblivious Transfer

A (_{1}^{2})–GOT_{2} is a cryptographic protocol for two participants that enables a sender A to transfer a one-bit function evaluated on (b_{0}, b_{1}) to a receiver B who chooses secretly which one-bit function (f) he gets from her input bits. This is done in an all-or-nothing fashion: B cannot get more information about b_{0} and b_{1} than f(b_{0}, b_{1}) for some f, however malicious or (computationally) powerful he is, and A finds out nothing about the choice f of B.

The following table enumerates all 14 possible non-constant functions from two bits to one. (We ignore the two constant function since they would yield no information if used.) The symbols used refer to the common boolean functions. Example: \overline{∧} stands for \overline{b_{0} ∧ b_{1}}. Only the notations 0 and 1, which are used for the projection functions b_{0}0b_{1} = b_{0} and b_{0}1b_{1} = b_{1}, are not standard. The ordinary (_{1}^{2})–OT_{2} is a special case of (_{1}^{2})–GOT_{2} where B is limited to the functions 0 and 1.

b_{0} b_{1} \overline{∨} \overline{←} \overline{1} \overline{→} \overline{0} ⊕ \overline{∧} ∧ \overline{⊕} 0 → 1 ← ∨
0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1
0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1
1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
biased √ √  √  √ √  √  √ √

Figure 1: the 14 non-constant functions from two bits to one.

It has been shown in [BCR86] that (_{1}^{2})–GOT_{2} is a sufficient primitive to implement (_{1}^{2})–OT_{2}. The reduction they presented uses Θ(s) runs of (_{1}^{2})–GOT_{2} to achieve a single (_{1}^{2})–OT_{2} in such a way that the reduction may fail and give both bits to B with probability 2^{−s}. If this protocol is combined with a standard reduction of (_{1}^{2})–OT_{2}^{k} we obtain a global cost of Θ(ks) runs of (_{1}^{2})–GOT_{2} per (_{1}^{2})–OT_{2}^{k}. Contrary to reductions to (_{1}^{2})–OT_{2}, reductions to (_{1}^{2})–GOT_{2} must absolutely involve an error probability since it is always possible to get all the information sent by A by selecting the appropriate biased function at each transfer. Using the new privacy amplification method we obtain a reduction of (_{1}^{2})–OT_{2}^{k} to (_{1}^{2})–GOT_{2} at a cost of only Θ(k + s).

Consider a variation of protocol 2.1 in which the transfers of step 2 are performed through (_{1}^{2})–GOT_{2} instead of (_{1}^{2})–OT_{2}. Our goal is to show that whatever program B̃ is ran by B, he is not able to obtain non-negligible information on both w_{0} and w_{1}, except with a probability that is exponentially small in the security parameter s. For this we need to make n larger than γk + s, but it will remain in Θ(k + s)—see the proof of Theorem 2.4 for details. First we show that immediately after Step 3 of the protocol, whatever program B̃ is ran by B, he will have negligible information about one of m_{0} or m_{1} and negligible information allowing him to connect m_{0} and m_{1}. We conclude a similar result about w_{0} and w_{1} at the end of the protocol from the fact that m_{0} and m_{1} are used as one-time pads to transfer them.

Suppose B̃ reads the bits x_{c_{i}}^{i} with c_{i} ∈ \{\overline{∨}, \overline{←}, \overline{1}, \overline{→}, \overline{0}, ⊕, \overline{∧}, ∧, \overline{⊕}, 0, →, 1, ←, ∨\} at his choosing. As before, let g be a non-trivial linear function of m_{0} and m_{1}, that is g(m_{0}, m_{1}) = v_{0}m_{0} ⊕ v_{1}m_{1} for some non-zero binary line-vectors v_{0} and v_{1} of length k. We say that B can α–bias a bit if he can guess it with probability better than \frac{1}{2} + α of being correct.

Theorem 2.4 Consider the knowledge that B̃ has about m_{0} and m_{1} immediately after Step 3 of the protocol.

Prob (∃ non-trivial g such that B̃ can 2^{−k−1−s/2}–bias g(m_{0}, m_{1})) < 2^{−s}.

Proof. Let γ and a be constants to be determined later and let n = (a + 1)(γk + s). Let Biased = \{i | c_{i} ∈ \{\overline{∨}, \overline{←}, \overline{→}, \overline{∧}, ∧, →, ←, ∨\}\}, the set of positions where B uses a biased function. If #Biased < a(γk + s) then Theorem 2.1 applies with γ ≥ 2 and n = γk + s. We thus get the desired result. Otherwise #Biased ≥ a(γk + s) is the more interesting case to consider. Consider the set of positions where B̃ has used a biased function. As before, B̃ would have learned g(m_{0}, m_{1}) exactly if he had simultaneously obtained

x_{0}^{i} when (z_{0}^{i}, z_{1}^{i}) = (1, 0)
x_{1}^{i} when (z_{0}^{i}, z_{1}^{i}) = (0, 1)
x_{⊕}^{i} when (z_{0}^{i}, z_{1}^{i}) = (1, 1)

for all i for which z_{0}^{i} and z_{1}^{i} are not both 0.

Remember that M_{0}, M_{1}, x_{0} and x_{1} are picked at random. Thus z_{0} and z_{1} are random binary words of length n. Since B has used a biased function in position i, with probability 1/4 he will have learned both x_{0}^{i} and x_{1}^{i}, and with probability 3/4 he will be able to 1/6–bias x_{0}^{i}, x_{1}^{i} and x_{⊕}^{i}. (This is because each biased function has one output that uniquely defines a specific pair of inputs, while the other output leaves three pairs of inputs equally likely.) This means that in each such position i, B̃ has obtained the bit he needs with probability 7/16 and with probability 9/16 he can only 1/6–bias the bit he needs. Of the a(γk + s) such values of i, less than a(γk + s)/4 of them will fall in the second case with probability at most 2 × e^{−25a(γk+s)/1024} ≈ 2^{−(γk+s)} according to Berstein’s law of large numbers, for a ≈ 28. When 7(γk + s) of the bits involved in the calculation of g(m_{0}, m_{1}) are 1/6–biased, even if all the other bits are exactly known, B’s can only (1/3)^{7(γk+s)}/2–bias the value of g(m_{0}, m_{1}). (In general, if one can δ–bias x_{1}, x_{2}, ..., x_{l}, she can (2δ)^{l}/2–bias x_{1} ⊕ x_{2} ⊕ ... ⊕ x_{l} [Cré90].) It follows that for any set of choices {c_{i}}, and any v_{0}, v_{1} ≠ 0^{k}

Prob (B̃ can 3^{−7(γk+s)}/2–bias g(m_{0}, m_{1})) < 2^{−(γk+s)}.

Finally, given that there are less than 2^{2k} pairs v_{0}, v_{1}, taking γ ≥ 2, and using the fact that 3^{−7(γk+s)}/2 ≤ 2^{−k−1−s/2}, we conclude as desired that

Prob (∃ non-trivial g such that B̃ can 2^{−k−1−s/2}–bias g(m_{0}, m_{1})) < 2^{2k}2^{−(γk+s)} ≤ 2^{−s}.

To conclude that, except with probability 2^{−s}, B has no more than 2^{−s} bit of information on at least one of m_{0} or m_{1} immediately after Step 3, and therefore no more than 2^{−s} bit of information on at least one of w_{0} or w_{1} at the end of the protocol (even if he is given the other string—see the Appendix for formal definitions), it suffices to apply the following theorem with ε = 1/2^{k+1+s/2}.

Theorem 2.5 Let k be an integer and ε ≤ 1/2^{k+1}. Consider a k–bit string m so that B cannot ε–bias any non-trivial linear function of the bits of m. Then B’s information on m in the sense of Shannon is less than (2^{k+1}ε)^{2} bit.

Proof (sketch). Let X be the random variable over the binary strings of length k that corresponds to B’s probability distribution on m. Consider the set G of all non-trivial linear functions on k–bit strings: there are exactly 2^{k} − 1 such functions. For any g ∈ G, let p_{g} be the probability that g(X) = 0. We have \frac{1}{2} − ε < p_{g} < \frac{1}{2} + ε for all g ∈ G by assumption that B cannot ε–bias non-trivial linear functions of the bits of m.

It is easily shown that the probability that X = x for any given string x is given by

Prob (X = x) = 2^{−k} + (∑_{g∈G} s(g, x) × (2p_{g} − 1)) /2^{k}

for some function s : G × {0, 1}^{k} → {−1, 1} whose detail does not concern us. It follows that Prob (X = x) differs from 2^{−k} by less than the largest value of 2p_{g} − 1 in absolute value, which is less than 2ε. The random variable X that would give the most information to B, yet respect the above constraint, would have half the strings with probability 2^{−k} − 2ε and the other half with probability 2^{−k} + 2ε. Therefore,

H(X) ≤ −2^{k−1}(2^{−k} − 2ε) lg(2^{−k} − 2ε) − 2^{k−1}(2^{−k} + 2ε) lg(2^{−k} + 2ε)
= (\frac{(2^{k+1}ε)^{2}}{1 × 2} + \frac{(2^{k+1}ε)^{4}}{3 × 4} + \frac{(2^{k+1}ε)^{6}}{5 × 6} + \frac{(2^{k+1}ε)^{8}}{7 × 8} + ⋯) / ln 2
< (2^{k+1}ε)^{2}.

3 Open Problems

As a further generalization, consider any α < 2. An α–(_{1}^{2})–UOT_{2} is a cryptographic protocol for two participants that enables a sender A to transfer α bits of information, in the sense of Shannon, about two bits (b_{0}, b_{1}) to a receiver B who chooses secretly which information Ω_{(b_{0},b_{1})} he gets from her input bits. We require that Ω_{(x,y)} be a distribution such that H ((B_{0}, B_{1})|Ω_{(B_{0},B_{1})}) ≥ 2 − α when B_{0} and B_{1} are uniformly distributed over {0, 1}. This is done in an all-or-nothing fashion: B cannot get more information about b_{0} and b_{1} than a sample from Ω_{(b_{0},b_{1})} for some Ω, however malicious or (computationally) powerful he is, and that A finds out nothing about the choice Ω of B.

Conjecture 3.1 For all α < 2 (or perhaps merely for all α ≤ 1?), Protocol 2.1 remains private even if occurrences of (_{1}^{2})–OT_{2} are replaced with α–(_{1}^{2})–UOT_{2}, provided n ≥ β_{α}(k +s) for an appropriate constant β_{α} to be determined, where s is the safety parameter.

Conjecture 3.2 If conjecture 3.1 fails as stated, it works if Shannon entropy is replaced with Rényi entropy of order 2 in the definition of α–(_{1}^{2})–UOT_{2} [BBCM95].

References

[Bea91] D. Beaver, “Foundations of Secure Interactive Computing”, Advances in Cryptology: Crypto ’91 Proceedings, Springer-Verlag, 1992, pp. 377 – 391.

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

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

[BCR86] G. Brassard, C. Crépeau and J.–M. Robert, “Information Theoretic Reductions Among Disclosure Problems”, 27^{th} Symp. of Found. of Computer Sci., 1986, pp. 168 – 173.

[BCR86a] G. Brassard, C. Crépeau and J.–M. Robert, “All-or-Nothing Disclosure of Secrets (Extended abstract)”, Advances in Cryptology: Proceedings of Crypto ’86, Springer-Verlag, 1987, pp. 234 – 238.

[BCS96] G. Brassard, C. Crépeau and M. Sántha, “Oblivious Transfers and Intersecting Codes”, Submitted for publication to IEEE Transactions on Information Theory, 1996.

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

[CL85] G. D. Cohen and A. Lempel, “Linear Intersecting Codes”, Discrete Mathematics, Vol. 56, 1985, pp. 35 – 43.

[CZ94] G. D. Cohen and G. Zémor, “Intersecting Codes and Independent Families”, IEEE Transactions on Information Theory, Vol. 40, no. 6, November 1994, pp. 1872 – 1881.

[Cré88] C. Crépeau, “Equivalence Between Two Flavours of Oblivious Transfers (Abstract)”, Advances in Cryptology: Proceedings of Crypto ’87, Springer-Verlag, 1988, pp. 350 – 354.

[Cré89] C. Crépeau, “Verifiable Disclosure of Secrets and Application”, Advances in Cryptology: Proceedings of Eurocrypt ’89, Springer-Verlag, 1989, pp. 181 – 191.

[Cré90] C. Crépeau, Correct and Private Reductions among Oblivious Transfers, PhD thesis, Department of Elec. Eng. and Computer Science, Massachusetts Institute of Technology, 1990. Supervised by Silvio Micali.

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

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

[CK88] C. Crépeau and J. Kilian, “Achieving oblivious transfer using weakened security assumptions”, 28^{th} Symp. on Found. of Computer Sci., 1988, pp. 42 – 52,

[CS95] C. Crépeau and L. Salvail, “Oblivious Verification of Common String”, to appear in CWI Quarterly.

[CS91a] C. Crépeau and M. Sántha, “On the Reversibility of Oblivious Transfer”, Advances in Cryptology: Proceedings of Eurocrypt ’91, Springer-Verlag, 1991, pp. 106 – 113.

[CS91b] C. Crépeau and M. Sántha, “Efficient Reductions Among Oblivious Transfer Protocols Based on New Self-Intersecting Codes”, Sequences II, Methods in Communications, Security and Computer Science, Springer-Verlag, 1991, pp. 360 – 368.

[EGL83] S. Even, O. Goldreich and A. Lempel, “A Randomized Protocol for Signing Contracts”, Proceedings of Crypto 82, Plenum Press, New York, 1983, pp. 205 – 210.

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

[GMR89] S. Goldwasser, S. Micali and C. Rackoff, “The Knowledge Complexity of Interactive Proof-Systems”, SIAM Journal on Computing, Vol. 18, 1989, pp. 186 – 208.

[GMW87] O. Goldreich, S. Micali and A. Wigderson, “How to Play Any Mental Game, or: A Completeness Theorem For Protocols With Honest Majority”, Proc. 19th ACM Symposium on Theory of Computing, 1987, pp. 218 – 229.

[GV87] O. Goldreich, R. Vainish, “How to Solve Any Protocol Problem — An Efficiency Improvement”, Advances in Cryptology: Crypto’87, Springer-Verlag, 1988, pp. 73 – 86.

[Kil88] J. Kilian, “Founding Cryptography on Oblivious Transfer”, Proc. 20th ACM Symposium on Theory of Computing, 1988, pp. 20 – 31.

[Kil91] J. Kilian, “A General Completeness Theorem For Two-party Games”, Proc. 23th ACM Symposium on Theory of Computing, 6 – 8 May 1991, pp. 553 – 560.

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

[Rab81] M. O. Rabin, “How to Exchange Secrets by Oblivious Transfer”, Technical Memo TR–81, Aiken Computation Laboratory, Harvard University, 1981.

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

A Appendix

Appendix A.1 is taken almost verbatim from [BCS96]. On the other hand, Appendix A.2 contains original material.

A.1 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, an (_{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. A generalization of (_{1}^{2})–OT_{2} is 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} from which B is given to choose one.

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 [Cré90], Micali and Rogaway [MR91] and Beaver [Bea91] using simulators. In this paper, we use the language of information theory to express definitions similar to those introduced by Crépeau [Cré94]. Our goal is not to discuss definitions for general two-party protocols: we restrict our study to oblivious transfers.

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 and 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 [GMR89]. In the following definition, the equality sign (=) means that the distributions on the left hand side and the right hand side are the same. When required, we shall use more flexible definitions that would allow an exponentially small probability of failure or an exponentially small amount of unauthorized information leakage. The more flexible definitions could be formalized in much the same way: details are left to the reader.

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

• ∀ w_{0}, w_{1} ∈ {0, 1}^{k}, c ∈ {0, 1}

[Ā, B̄](w_{0}, w_{1})(c) = (ϵ, w_{c})  (1)

• for any program Ã there exists a probabilistic program Ã′ s.t.

∀ w_{0}, w_{1} ∈ {0, 1}^{k}, c ∈ {0, 1}

[Ã, B̄]B (w_{0}, w_{1})(c) | B accepts = [Ā, B̄]B (Ã′(w_{0}, w_{1}))(c) | B accepts . (2)

Intuitively, condition (1) 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 (2) 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 [MR91], 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 [MR91] 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.

Let W_{0}, W_{1} and C be the random variables taking values over {0, 1}^{k} and {0, 1} 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_{0},W_{1},C}. A sample w_{0}, w_{1}, c is generated from that distribution and w_{0}, w_{1} 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 and Y is given by I (X; Y) = H (X) − H (X | Y). Conditioned by a third random variable Z, I (X; Y | Z) = H (X | Z) − H (X | Y, Z).

Definition A.2 (Privacy) Protocol [Ā, B̄] is private for (_{1}^{2})–OT_{2}^{k} if ∀ W_{0}, W_{1} ∈ {0, 1}^{k}, C ∈ {0, 1}

• ∀ w_{0}, w_{1} ∈ {0, 1}^{k} and for any program Ã

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

• ∀ c ∈ {0, 1} and for any program B̃ there exists a random variable C̃ = Ω(C) ∈ {0, 1}

s.t.

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

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 (3) means that Ã cannot acquire any information about C through the protocol. On the other hand, condition (4) means that B̃ may acquire information about only one of W_{0} or W_{1} through the protocol. In particular, no joint information about the two words may be obtained by the protocol. This is why our condition assumes that B̃ is given one of A’s 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.

A.2 Generalized Oblivious Transfer

We have now similar conditions to define Generalized Oblivious Transfer.

Definition A.3 (Correctness) Protocol [Ā, B̄] is correct for (_{1}^{2})–GOT_{2} if

• ∀ b_{0}, b_{1} ∈ {0, 1}, f : {0, 1}^{2} → {0, 1}

[Ā, B̄](b_{0}, b_{1})(f) = (ϵ, f(b_{0}, b_{1}))  (5)

• for any program Ã there exists a probabilistic program Ã′ s.t.

∀ b_{0}, b_{1} ∈ {0, 1}, f : {0, 1}^{2} → {0, 1}

[Ã, B̄]B̄ (b_{0}, b_{1})(f) | B̄ accepts = [Ā, B̄]B̄ (Ã′(b_{0}, b_{1}))(f) | B̄ accepts .  (6)

Let B_{0}, B_{1} and F be the random variables taking values over {0, 1} and {0, 1}^{2} → {0, 1} 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_{B_{0},B_{1},F}. A sample b_{0}, b_{1}, f is generated from that distribution and b_{0}, b_{1} is provided as A’s secret input while f is provided as B’s secret input.

Definition A.4 (Privacy) Protocol [Ā, B̄] is private for (_{1}^{2})–GOT_{2} if ∀ B_{0}, B_{1} ∈ {0, 1}, F : {0, 1}^{2} → {0, 1}

• ∀ b_{0}, b_{1} ∈ {0, 1} and for any program Ã

I (F; [Ã, B̄]A^{∗}(B_{0}, B_{1})(F) | (B_{0}, B_{1}) = (b_{0}, b_{1})) = 0  (7)

• ∀f : {0, 1}^{2} → {0, 1} and for any program B̃ there exists a random variable F̃ = Ω(F) : {0, 1}^{2} → {0, 1} s.t.

I (B_{0}, B_{1}; [Ā, B̃]B^{∗}(B_{0}, B_{1})(F) | F = f, F̃(B_{0}, B_{1})) = 0.  (8)