Reductions among oblivious transfers have a long history in cryptography. This paper describes a 21-OT~k protocol that can be reduced to a single execution of UOT by using privacy amplification with extractors. An extractor allows to efficiently isolate the randomness of some source into virtually-random bits, using a small number of perfectly-random bits as a catalyst. With extractors, less information is transmitted and the leaked information is at most 2~(-n~(-1/2-o(1))) bits. The conditions under which the protocol is unconditionally secure are investigated.
. The Wire-Tap Channel of Wyner [19] shows that a Binary Symmetric Channel may be used as a basis for exchanging a secret key, in a cryptographic scenario of two honest people facing an eavesdropper. Later Cr'epeau and Kilian [9] showed how a BSC may be used to implement Oblivious Transfer in a cryptographic scenario of two possibly dishonest people facing each other. Unfortunately this result is rather impractical as it requires\\Omega (n 11 ) bits to be transmitted through the BSC to accomplish a single OT. The current paper provides efficient protocols to achieve the cryptographic primitives of Bit Commitment and Oblivious Transfer based on the existence of a Binary Symmetric Channel. Our protocols respectively require sending O(n) and O(n 3 ) bits through the BSC. These results are based on a technique known as Generalized Privacy Amplification [1] that allow two people to extract secret information from partially compromised data. 1 Introduction The cryptographic power of a no...