Efficient Cryptographic Protocols Based on Noisy Channels.
Claude Crepeau
Abstract: The Wire-Tap Channel of Wyner shows that a Binary Symmetric Channel may be used as a basis for exchanging a secret key. Later, Crepeau and Kilian showed how a BSC may be used to implement Oblivious Transfer. Unfortunately, this result is rather impractical as it requires $n sup 11$ bits to be sent through the BSC to accomplish a single OT. The current paper provides efficient protocols to achieve Bit Commitment and Oblivious Transfer based on the existence of a BSC. Our protocols respectively use the BSC $n$ times and $n sup 3$ times. These results are based on a technique known as Generalized Privacy Amplification.
Keywords: Oblivious Transfer, Bit Commitment, Noisy Channel, Error-Correcting Codes, Protocols, Information Theory
comment: received March 5th, 1997. comment: to appear in Proceedings of Eurocrypt '97.
contact author: crepeau@iro.umontreal.ca
Fetch PostScript file of the full paper.