Oblivious Transfers and Privacy Amplification

Gilles Brassard^{⋆} and Claude Crépeau^{⋆⋆}

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

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^{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. We address the question of reducing (_{1}^{2})–OT^{k} to (_{1}^{2})–OT. 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^{k} with fewer than about 3.5277 k instances of (_{1}^{2})–OT. The current paper introduces the idea of using privacy amplification as underlying technique to reduce (_{1}^{2})–OT^{k} to (_{1}^{2})–OT. 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 in order to implement (_{1}^{2})–OT^{k}. Moreover, we show that privacy amplification allows for the efficient implementation of (_{1}^{2})–OT^{k} from generalized versions of (_{1}^{2})–OT 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, Reduction Between Protocols, Oblivious Transfer, Privacy Amplification.

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

1 Introduction

One-out-of-two String Oblivious Transfer, denoted (_{1}^{2})–OT^{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 only participate if A cannot 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, 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^{k} to (_{1}^{2})–OT: 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 One-out-of-two Bit Oblivious Transfer. The fact that (_{1}^{2})–OT^{k} can be reduced to (_{1}^{2})–OT is not surprising because a number of authors [Kil88, Cré89, CGT95] have shown that (_{1}^{2})–OT 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 function f from {0, 1}^{n} to {0, 1}^{k} for n as small as possible (n > k), 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 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 to perform one (_{1}^{2})–OT^{k} on k–bit strings. Komlós proved that this approach cannot yield an expansion factor β that is asymptotically better than 3.5277 [CL85]. It was recently proven by Stinson that the same bound applies even to non-linear zigzags [Sti97].

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 to perform one (_{1}^{2})–OT^{k}, and it can be extended to a whole range of generalizations of (_{1}^{2})–OT that could not be used with the reductions based on zigzag functions.

An application of the simplest of our generalizations is also considered: (_{1}^{2})–OT^{k} from A to B can be reduced to (_{1}^{2})–OT in the other direction (from B to A) by only doubling the cost of reducing to (_{1}^{2})–OT 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^{k}(w_{0}, w_{1})(c) from (_{1}^{2})–OT 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(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 instances. In the new approach based on privacy amplification, A reveals the function to B after the necessary (_{1}^{2})–OT’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^{k} can be achieved with βk instances of (_{1}^{2})–OT, s is a safety parameter, and ε is arbitrarily small in the limit of large k, 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})

1 Attributed to Cohen and Lempel in [BCS96]. 2 Attributed to Joe Kilian in [BCS96]. 3 From [BCS96]. 4 From [CZ94] based on a method of [CS91b].

3 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 F_{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^{k} from (_{1}^{2})–OT:

{h | h(x) = Mx, for M a k × n matrix over F_{2}} .

Other, more efficient classes of hash functions can be used, but it is not known if the definition of universal classes is sufficient in general to make our protocol work.

Protocol 3.1 ( (_{1}^{2})–OT^{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(x_{0}^{i}, x_{1}^{i})(c) to B. 3: A picks two random k × n matrices M_{0} and M_{1} over F_{2};

she announces them to B. 4: A sets m_{0} ← M_{0}x_{0}, m_{1} ← M_{1}x_{1}, y_{0} ← m_{0} ⊕ w_{0} and y_{1} ← m_{1} ⊕ w_{1};

she announces y_{0} and y_{1} to B. 5: B recovers w_{c} by computing (M_{c}t) ⊕ y_{c}.

We postpone to Sect. 5 the proof that this protocol is private provided γ ≥ 2 because we shall first generalize it to permit at no extra cost the use of another primitive called XOR Oblivious Transfer. (Informally, a 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. Conversely, A should learn nothing at all. See [BCS96] for a formal information-theoretic definition. We shall later relax the condition to allow B an exponentially small amount of unauthorized information.)

4 XOR Oblivious Transfer

A (_{1}^{2})–XOT is an extension of (_{1}^{2})–OT 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. Note that in our application of (_{1}^{2})–XOT, which is to use it instead of (_{1}^{2})–OT inside Protocol 3.1, an honest B would never requests b_{⊕}. Therefore we can safely use any protocol in which it is merely tolerated that B might learn b_{⊕} in cheating attempts even though A is not required to provide it upon request.

The (_{1}^{2})–XOT comes naturally in a specific implementation of (_{1}^{2})–OT: in [BCR86a] a protocol for (_{1}^{2})–OT 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^{k} rather than simply (_{1}^{2})–OT.

5 Privacy

Consider a variation of Protocol 3.1 in which the transfers at step 2 are performed through (_{1}^{2})–XOT instead of (_{1}^{2})–OT. 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. Moreover, it is obvious from inspection of the protocol that a cheating A cannot obtain any information about B’s secret parameter c. 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 columnvectors of length k, all over F_{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 [BCS96].) 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 F_{2} such that both v_{0} and v_{1} are non-zero^{5}.

Theorem 1. Consider the knowledge that B̃ has about m_{0} and m_{1} immediately after Step 3 of the protocol. Provided γ ≥ 2,

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

5 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 F_{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}.

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}

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 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 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 compute 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. Protocol 3.1 is private even if the transfers at step 2 are performed through (_{1}^{2})–XOT instead of (_{1}^{2})–OT.

Proof. We know from Theorem 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} in a non-trivial way.^{6} 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

6 Of course, 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.

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}. ⊓ ⊔

6 Application: 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 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: two instances of reversed (_{1}^{2})–OT are sufficient to implement (_{1}^{2})–XOT. No such efficient constructions are known that would implement (_{1}^{2})–OT from so few instances of reversed (_{1}^{2})–OT. In other words it is much easier to implement (_{1}^{2})–XOT than (_{1}^{2})–OT from A to B given an (_{1}^{2})–OT channel from B to A. This is fine because we just showed that (_{1}^{2})–XOT is just as good as (_{1}^{2})–OT for the purpose of implementing (_{1}^{2})–OT^{k}. Therefore, (_{1}^{2})–OT^{k} from A to B can be implemented from slightly more than 4k instances of (_{1}^{2})–OT from B to A. This is a three-fold improvement over [CS91a].

7 Generalized Oblivious Transfer

A (_{1}^{2})–GOT 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. As was the case with (_{1}^{2})–XOT in Sect. 4, one may think of a (_{1}^{2})–GOT protocol as merely tolerating the fact that a cheating B might learn f(b_{0}, b_{1}) for some f rather than specifying that any such f can be learned at B’s whim.

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}}. The notations 0 and 1 are used for the projection functions b_{0}0b_{1} = b_{0} and b_{0}1b_{1} = b_{1}. We say that a function f(b_{0}, b_{1}) is biased if the probability that f(b_{0}, b_{1}) = 1 is not 1/2 when b_{0} and b_{1} are chosen randomly and independently according to the uniform distribution. The ordinary (_{1}^{2})–OT is a special case of (_{1}^{2})–GOT 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 √ √ √  √ √  √ √ √

It has been shown in [BCR86] that (_{1}^{2})–GOT is a sufficient primitive to implement (_{1}^{2})–OT. The reduction they presented uses Θ(s) runs of (_{1}^{2})–GOT to achieve a single (_{1}^{2})–OT 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^{k} we obtain a global cost of Θ(ks) runs of (_{1}^{2})–GOT per (_{1}^{2})–OT^{k}. Contrary to reductions to (_{1}^{2})–OT, reductions to (_{1}^{2})–GOT must involve a failure probability since it is always possible to get all the information sent by A by selecting the appropriate biased function at each transfer by sheer luck. For example, if B requests x_{0}^{i} ∧ x_{1}^{i} at step 2 of Protocol 3.1 for some i, and if he obtains the value 1, then he knows that both x_{0}^{i} and x_{1}^{i} are equal to 1. Using the new privacy amplification method we obtain a direct reduction of (_{1}^{2})–OT^{k} at a cost of only Θ(k + s) instances of (_{1}^{2})–GOT.

Consider a variation of Protocol 3.1 in which the transfers of step 2 are performed through (_{1}^{2})–GOT instead of (_{1}^{2})–OT. 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. Contrary to the analysis in Sect. 5, it will no longer suffice to take n = γk + s for some γ, but n will nevertheless remain in Θ(k + s)—see the proof of Theorem 3 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̃ obtains 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 3. 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}

provided n is chosen appropriately in Θ(k + 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 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 2e^{−25a(γk+s)/1024} ≈ 2^{−(γk+s)} according to Bernstein’s law of large numbers [Rén70, Chap. VII, Sect. 4, Theorem 2], 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 can only (1/3)^{7(γk+s)}/2–bias the value of g(m_{0}, m_{1}). (In general, δ–biasing each of x_{1}, x_{2}, ..., x_{l} allows to (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 4. 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} + \frac{1}{2^{k}} ∑_{g∈G} s(g, x) × (2p_{g} − 1)

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}.
⊓ ⊔

8 Open Problems

The value of n used in our proof of Theorem 3 is in Θ(k + s) but we conjecture that it could be made significantly smaller in terms of the hidden constant, perhaps as small as 2k + s.

As a further generalization, consider any α < 2. An α–(_{1}^{2})–UOT 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 random variable 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. To see that this is genuinely more general than (_{1}^{2})–GOT, consider the case in which B would request to see both bits through a binary symmetric channel with error rate 11%. Because H_{2}(11%) ≈ 0.5, this would give B one bit of information about the two bits of A. However, this scenario cannot be simulated with (_{1}^{2})–GOT.

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

Conjecture 6. If conjecture 5 fails as stated, it works if Shannon entropy is replaced with Rényi entropy of order ρ in the definition of α–(_{1}^{2})–UOT for all ρ > 1 [Cac97] or perhaps merely for ρ = 2 [BBCM95].

Acknowledgements

We thank Dominic Mayers and Louis Salvail for their help, comments, suggestions and support.

References

[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”, Proceedings of 27th Annual IEEE Symposium on Foundations of Computer Science, 1986, pp. 168 – 173.

[BCR86a] G. Brassard, C. Crépeau and J.–M. Robert, “All-or-nothing disclosure of secrets”, 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”, IEEE Transactions on Information Theory, Vol. 42, no. 6, November 1996, pp. 1769 – 1780.

[Cac97] C. Cachin, “Smooth entropy and Rényi entropy”, Advances in Cryptology: Proceedings of Eurocrypt ’97, Springer-Verlag, 1997.

[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é89] C. Crépeau, “Verifiable disclosure of secrets and application”, Advances in Cryptology: Proceedings of Eurocrypt ’89, Springer-Verlag, 1990, pp. 181 – 191.

[Cré90] 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.

[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, Springer-Verlag, 1995, pp. 110 – 123.

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

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

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

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

[Rén70] A. Rényi, Probability Theory, North Holland, 1970.

[Sti97] D. R. Stinson, Private communication, 12 February 1997.

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

A Appendix: Information Theoretic Definition of Generalized 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 Sect. 7, a (_{1}^{2})–GOT is a cryptographic protocol for two participants that enables a sender A to transfer a one-bit function of two bits b_{0} or b_{1} to a receiver B who chooses secretly which function f(b_{0}, b_{1}) 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 f of B.

Formally speaking we describe a two-party protocol that satisfies the following constraints of correctness and privacy, similar to those introduced for (_{1}^{2})–OT in [BCS96].

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 l.h.s. and the r.h.s. are the same. When required, we shall use more flexible definitions that would allow an exponentially small probability of failure or amount of unauthorized information leakage. Details are left to the reader.

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

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

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

– 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 . (2)

Intuitively, condition (1) means that if the protocol is executed as described, it will accomplish the task it was designed for: B receives bit f(b_{0}, b_{1}) 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.

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 8 (Privacy). Protocol [Ā, B̄] is private for (_{1}^{2})–GOT 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  (3)

– ∀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.  (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 F through the protocol. On the other hand, condition (4) means that B̃ may acquire only one bit of deterministic information about B_{0}, B_{1} through the protocol. We do not require that B̃ be given F (B_{0}, B_{1}) because there is no way to prevent him from obtaining any other F̃(B_{0}, B_{1}) through otherwise honest use of the protocol.

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