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

Lecture notes in computer science

Bit String Commitment Reductions with a Non-zero Rate

Anderson C. A. Nascimento, Joern Mueller-Quade, Hideki Imai

Published Jan 1, 2004• 1 citation
Publisher
DOI
10.1007/978-3-540-24660-2_15

Related papers

Implementable Quantum Bit String Commitment

Toyohiro Tsurumaru

IEICE Technical Report; IEICE Tech. Rep.•Jul 13, 2004•0 citations

Efficient Committed Oblivious Transfer of Bit Strings

Mehmet Sabır Kiraz, Berry Schoenmakers, José Villegas

Lecture notes in computer science•Jan 1, 2007•15 citations

Efficient String-Commitment from Weak Bit-Commitment

Kai-Min Chung, Feng-Hao Liu, Chi-Jen Lu +1 more

Lecture notes in computer science•Jan 1, 2010•9 citations

On the Efficiency of Bit Commitment Reductions

Samuel Ranellucci, Alain Tapp, Severin Winkler +1 more

Lecture notes in computer science•Jan 1, 2011•11 citations

Adaptive and Composable Non-interactive String-Commitment Protocols

Huafei Zhu, Tadashi Araragi, Takashi Nishide +1 more

Communications in computer and information science•Jan 1, 2012•0 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
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.