Cryptology ePrint Archive: Report 2003/165
Commitment Capacity of Discrete Memoryless Channels
Andreas Winter, Anderson C. A. Nascimento, Hideki Imai
Abstract: In extension of the bit commitment task and following work initiated by Crepeau and Kilian, we introduce and solve the problem of characterising the optimal rate at which a discrete memoryless channel can be used for bit commitment. It turns out that the answer is very intuitive: it is the maximum equivocation of the channel (after removing trivial redundancy), even when unlimited noiseless bidirectional side communication is allowed.
By a well-known reduction, this result provides a lower bound on the channel's capacity for implementing coin tossing, which we conjecture to be an equality.
The method of proving this relates the problem to Wyner's wire--tap channel in an amusing way. We also discuss extensions to quantum channels.
Category / Keywords: foundations / Commitment Schemes, Information Theory, Noisy Channels
Date: received 11 Aug 2003
Contact author: anderson at imailab iis u-tokyo ac jp
Available formats: PDF | BibTeX Citation
Version: 20030811:153225 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]