Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:cs/0304014

Commitment Capacity of Discrete Memoryless Channels

Andreas Winter, Anderson C. A. Nascimento, Hideki Imai

Published Apr 10, 2003• 17 citations
arXivHTMLPDF

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.

DOI
10.48550/arxiv.cs/0304014

Related papers

Efficient Protocols Achieving the Commitment Capacity of Noisy Correlations

Hideki Imai, Kirill Morozov, Anderson C. A. Nascimento +1 more

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).

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•25 citations

On Commitment over General Compound Channels

Anuj Kumar Yadav, Manideep Mamindlapally, Pranav Joshi +1 more

As computation and communication become increasingly ubiquitous, data security remains a key consideration. Hence, cryptographic primitives lie at the heart of several modern digital technologies. In this work, we study one such important cryptographic primitive called commitment. Here two parties, say Alice and Bob, aim to realize a protocol with the following functionality: Alice seeks to share or commit to a bit string securely with Bob with the requirement that the string is hidden from Bob until she chooses to reveal it to him. Bob wants to ensure that the protocol binds Alice to her original choice of bit string by allowing him to successfully detect when she cheats at the time of revealing her string. This seemingly elementary cryptographic functionality is extremely powerful and finds wide use in technologies like blockchains, digital contracts, cryptocurrencies, etc.. More generally, commitment has also been widely studied for applications like sealed-bid auctions, distributed coin tossing, etc.. Building on Wyner's classic work on wiretap channels, unconditionally-secure or information-theoretically secure protocols have been realized for a wide variety of problems, including commitment, using noisy channels as a resource. Crucially, however, the security guarantees are intimately tied to the knowledge of the noise statistics; these could be compromised when noise statistics are imprecisely known. In this work, we seek to study information-theoretically secure commitment over a class of unreliable noisy channels called compound channels. In particular, we study commitment over compound discrete memoryless channels (compound-DMCs) where the instantiated channel is known to be a DMC but its realization or channel state is not known exactly and can only be localized to a potential set of possible states. We precisely characterize the optimal throughput or commitment capacity over general compound DMCs. We also study the effect of state-awareness at the two parties, when the parties are honest and when they are malicious, on the commitment capacity of such compound DMCs. Interestingly, we show that committer-side state-awareness can non-trivially increase the commitment throughput over the compound DMC which is not the case when one has only receiver-side state awareness. In particular, we completely characterize the commitment capacity for all state-aware configurations for compound DMCs.

International Conference on Communication Systems & Networks (COMSNETS)•Jan 4, 2022•3 citations

The Gaussian wire-tap channel

S. Leung-Yan-Cheong, Martin E. Hellman

Wyner's results for discrete memoryless wire-tap channels are extended to the Gaussian wire-tap channel. It is shown that the secrecy capacity Cs is the difference between the capacities of the main and wire.tap channels. It is further shown that Rd= Cs is the upper boundary of the achievable rate-equivocation region.

IEEE Transactions on Information Theory•Jul 1, 1978•1,977 citations

Commitment Capacity under Cost Constraints

Manideep Mamindlapally, Anuj Kumar Yadav, Manoj Mishra +1 more

We study the problem of commitment over channels under cost constraints. Commitment is a widely studied cryptographic primitive, where two mutually distrustful parties, say Alice and Bob, interact over two phases of a protocol, viz., commit phase followed by reveal phase, to achieve commitment on a bit string available to Alice. Commitment (over the string) is said to occur if (i) Alice commits to the string which remains securely hidden from Bob at the end of the commit phase involving Alice's transmission to Bob, and (ii) Alice reveals a string to Bob and Bob is able to successfully detect whether the string is the committed one or not. When Alice and Bob are computationally unbounded, i.e., under the information-theoretic setting, it is well known that even a single bit commitment is impossible when the channel available to Alice and Bob is noiseless. Noisy channels, however, offer the potential of non-zero commitment rate, and thus, are a valuable resource. We study information-theoretically secure commitment over noisy discrete memoryless channels (DMCs). The largest commitment throughput over noisy channels is called the commitment capacity or simply capacity. In this work, we completely characterize via a single-letter expression, the commitment capacity of DMCs under general cost constraints; this generalizes the previously known result in the absence of such cost constraints. We show that cost constrained commitment capacity of any given DMC can significantly differ from its unconstrained value. We also present a dual capacity characterization in terms of output distributions. Interestingly, we show that every input distribution achieving the capacity results in the same output distribution; the latter is the unique optimizer of our dual capacity expression.

IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•7 citations

Rates for bit commitment and coin tossing from noisy correlation

H. Imai, Joern Mueller-Quade, Anderson C. A. Nascimento +1 more

This paper studies the optimisation of the channel with cryptographic primitives such as coin tossing and oblivious transfer by committing to a set of strings. The main contribution of this paper is that the commitment is possible from any nontrivial correlation at rates when the sender is Alice and Bob, those rates are optimal. Also the coin tossing capacity is infinite for every channel having a positive bit commitment rate.

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•15 citations

On the Commitment Capacity of Unfair Noisy Channels

Claude Crépeau, Rafael Dowsley, Anderson C. A. Nascimento

Noisy channels are a valuable resource from a cryptographic point of view. They can be used for exchanging secret-keys as well as realizing other cryptographic primitives such as commitment and oblivious transfer. To be really useful, noisy channels have to be considered in the scenario where a cheating party has some degree of control over the channel characteristics. Damgård et al. (EUROCRYPT 1999) proposed a more realistic model where such level of control is permitted to an adversary, the so called unfair noisy channels, and proved that they can be used to obtain commitment and oblivious transfer protocols. Given that noisy channels are a precious resource for cryptographic purposes, one important question is determining the optimal rate in which they can be used. The commitment capacity has already been determined for the cases of discrete memoryless channels and Gaussian channels. In this work we address the problem of determining the commitment capacity of unfair noisy channels. We compute a single-letter characterization of the commitment capacity of unfair noisy channels. In the case where an adversary has no control over the channel (the fair case) our capacity reduces to the well-known capacity of a discrete memoryless binary symmetric channel.

arXiv:1905.10921•IEEE Transactions on Information Theory•Jan 17, 2020•15 citations
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.
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).
As computation and communication become increasingly ubiquitous, data security remains a key consideration. Hence, cryptographic primitives lie at the heart of several modern digital technologies. In this work, we study one such important cryptographic primitive called commitment. Here two parties, say Alice and Bob, aim to realize a protocol with the following functionality: Alice seeks to share or commit to a bit string securely with Bob with the requirement that the string is hidden from Bob until she chooses to reveal it to him. Bob wants to ensure that the protocol binds Alice to her original choice of bit string by allowing him to successfully detect when she cheats at the time of revealing her string. This seemingly elementary cryptographic functionality is extremely powerful and finds wide use in technologies like blockchains, digital contracts, cryptocurrencies, etc.. More generally, commitment has also been widely studied for applications like sealed-bid auctions, distributed coin tossing, etc.. Building on Wyner's classic work on wiretap channels, unconditionally-secure or information-theoretically secure protocols have been realized for a wide variety of problems, including commitment, using noisy channels as a resource. Crucially, however, the security guarantees are intimately tied to the knowledge of the noise statistics; these could be compromised when noise statistics are imprecisely known. In this work, we seek to study information-theoretically secure commitment over a class of unreliable noisy channels called compound channels. In particular, we study commitment over compound discrete memoryless channels (compound-DMCs) where the instantiated channel is known to be a DMC but its realization or channel state is not known exactly and can only be localized to a potential set of possible states. We precisely characterize the optimal throughput or commitment capacity over general compound DMCs. We also study the effect of state-awareness at the two parties, when the parties are honest and when they are malicious, on the commitment capacity of such compound DMCs. Interestingly, we show that committer-side state-awareness can non-trivially increase the commitment throughput over the compound DMC which is not the case when one has only receiver-side state awareness. In particular, we completely characterize the commitment capacity for all state-aware configurations for compound DMCs.
We study the problem of commitment over channels under cost constraints. Commitment is a widely studied cryptographic primitive, where two mutually distrustful parties, say Alice and Bob, interact over two phases of a protocol, viz., commit phase followed by reveal phase, to achieve commitment on a bit string available to Alice. Commitment (over the string) is said to occur if (i) Alice commits to the string which remains securely hidden from Bob at the end of the commit phase involving Alice's transmission to Bob, and (ii) Alice reveals a string to Bob and Bob is able to successfully detect whether the string is the committed one or not. When Alice and Bob are computationally unbounded, i.e., under the information-theoretic setting, it is well known that even a single bit commitment is impossible when the channel available to Alice and Bob is noiseless. Noisy channels, however, offer the potential of non-zero commitment rate, and thus, are a valuable resource. We study information-theoretically secure commitment over noisy discrete memoryless channels (DMCs). The largest commitment throughput over noisy channels is called the commitment capacity or simply capacity. In this work, we completely characterize via a single-letter expression, the commitment capacity of DMCs under general cost constraints; this generalizes the previously known result in the absence of such cost constraints. We show that cost constrained commitment capacity of any given DMC can significantly differ from its unconstrained value. We also present a dual capacity characterization in terms of output distributions. Interestingly, we show that every input distribution achieving the capacity results in the same output distribution; the latter is the unique optimizer of our dual capacity expression.
Noisy channels are a valuable resource from a cryptographic point of view. They can be used for exchanging secret-keys as well as realizing other cryptographic primitives such as commitment and oblivious transfer. To be really useful, noisy channels have to be considered in the scenario where a cheating party has some degree of control over the channel characteristics. Damgård et al. (EUROCRYPT 1999) proposed a more realistic model where such level of control is permitted to an adversary, the so called unfair noisy channels, and proved that they can be used to obtain commitment and oblivious transfer protocols. Given that noisy channels are a precious resource for cryptographic purposes, one important question is determining the optimal rate in which they can be used. The commitment capacity has already been determined for the cases of discrete memoryless channels and Gaussian channels. In this work we address the problem of determining the commitment capacity of unfair noisy channels. We compute a single-letter characterization of the commitment capacity of unfair noisy channels. In the case where an adversary has no control over the channel (the fair case) our capacity reduces to the well-known capacity of a discrete memoryless binary symmetric channel.