Computer Science – Cryptography and Security
Scientific paper
2003-04-10
Proc. 9th Cirencester Crypto and Coding Conf., LNCS 2989, pp 35-51, Springer, Berlin 2003.
Computer Science
Cryptography and Security
20 pages, LaTeX2e
Scientific paper
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.
Imai Hideki
Nascimento Anderson C. A.
Winter Andreas
No associations
LandOfFree
Commitment Capacity of Discrete Memoryless Channels does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Commitment Capacity of Discrete Memoryless Channels, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Commitment Capacity of Discrete Memoryless Channels will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-273992