Efficient Protocols Achieving the Commitment Capacity of Noisy Correlations
- 1 July 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21578095,p. 1432-1436
Abstract
Bit commitment is an important tool for constructing zero-knowledge proofs and multi-party computation. Unconditionally secure bit commitment can be based, in particular, on noisy channel or correlation where noise considered a valuable resource. Recently, Winter, Nascimento and Imai introduced the concept of commitment capacity, the maximal ratio between the length of a string which the sender commits to and the number of times the noisy channel/correlation is used. They also proved that for any discrete memoryless channel there exists a secure protocol achieving its commitment capacity however, no particular construction was given. Solving their open question, we provide an efficient protocol for achieving the commitment capacity of discrete memoryless systems (noisy channels and correlations)Keywords
This publication has 12 references indexed in Scilit:
- Rates for bit commitment and coin tossing from noisy correlation2004
- Continuity of quantum conditional informationJournal of Physics A: General Physics, 2004
- Commitment Capacity of Discrete Memoryless Channels2003
- On the (Im)possibility of Basing Oblivious Transfer and Bit Commitment on Weakened Security Assumptions1999
- A Pseudorandom Generator from any One-way FunctionSIAM Journal on Computing, 1999
- Generalized privacy amplificationIEEE Transactions on Information Theory, 1995
- Bit commitment using pseudorandomnessJournal of Cryptology, 1991
- Minimum disclosure proofs of knowledgeJournal of Computer and System Sciences, 1988
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- A Mathematical Theory of CommunicationBell System Technical Journal, 1948