0 blivious Transfers and Privacy Amplification

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 (:)-OTk. 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, de-noted (:)-OT. We address the question of reducing (:)-OTk to (:)-OT. This question is not new: it was introduced in 1986. However, most so-lutions 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 (:)-OTk with fewer than about 3.5277k instances of (:)-OT. The current paper introduces the idea of using privacy amplification as underlying technique to reduce (:)-Ork to (:)-OT. This allows for more efficient solutions at the cost of an expo-nentially small probability of failure: it is sufficient t,o use slightly more than 2k instances of (:)-OT in order to implement (f)-OTk. Moreover, we show that privacy amplification allows for the efficient implementa-tion of (:)-OTk from generalized versions of (:)-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