International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Commitment Capacity of Discrete Memoryless Channels

Authors:
Andreas Winter
Anderson C. A. Nascimento
Hideki Imai
Download:
URL: http://eprint.iacr.org/2003/165
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2003-11879,
  title={Commitment Capacity of Discrete Memoryless Channels},
  booktitle={IACR Eprint archive},
  keywords={foundations / Commitment Schemes, Information Theory, Noisy Channels},
  url={http://eprint.iacr.org/2003/165},
  note={ anderson@imailab.iis.u-tokyo.ac.jp 12275 received 11 Aug 2003},
  author={Andreas Winter and Anderson C. A. Nascimento and Hideki Imai},
  year=2003
}