Oblivious Transfers and Privacy Amplification

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 ( 2 1 )--OT k 2 . 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 ( 2 1 )--OT 2 . We address the question of reducing ( 2 1 )--OT k 2 to ( 2 1 )--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 ( 2 1 )--OT k 2 with fewer than about 3:5277 k instances of ( 2 1 )--..