Efficient Cryptographic Protocols Based on Noisy Channels

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épeau 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 Ω(n11) 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(n3) 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.