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

IEEE International Symposium on Information Theory (ISIT)

Multiplex Coding of Bit Commitment Based on a Discrete Memoryless Channel

H. Yamamoto, Daichi Isami

Published Jun 1, 2007• 7 citations
Publisher

Abstract

The bit commitment can be realized by using a noisy channel. Winter-Nascimento-Imai showed that the bit commitment capacity of a noisy channel is given by Cb= maxpNH(X\Y) where X and Y are the input and output of the channel. In this paper, the idea of a multiplex coding, which was first introduced into the coding problem of a wiretap channel by Kobayashi-Yamamoto-Ogawa, is applied to the bit commitment coding. The coding theorem is proved for the multiplex coding of bit commitment based on a noisy channel, and it is shown that several mutually independent secrets can be committed at the same time via a nosiy channel attaining the perfect secrecy of each secret with the total coding rate log \X\, where \X\ is the cardinality of channel input alphabet.

DOI
10.1109/isit.2007.4557310

Related papers

Secure multiplex coding to attain the channel capacity in wiretap channels

Daisuke Kobayashi, H. Yamamoto, Tomohiro Ogawa

It is known that a message can be transmitted safely against any wiretapper via a noisy channel without a secret key if the coding rate is less than the so-called secrecy capacity $C_S$, which is usually smaller than the channel capacity $C$. In order to remove the loss $C - C_S$, we propose a multiplex coding scheme with plural independent messages. In this paper, it is shown that the proposed multiplex coding scheme can attain the channel capacity as the total rate of the plural messages and the perfect secrecy for each message. The coding theorem is proved by extending Hayashi's proof, in which the coding of the channel resolvability is applied to wiretap channels.

arXiv:cs/0509047•Sep 16, 2005•0 citations

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•27 citations

How to attain the ordinary channel capacity securely in wiretap channels

Daisuke Kobayashi, H. Yamamoto, Tomohiro Ogawa

It is known that a message can be transmitted safely against any wiretap per via a noisy channel without a secret key if the coding rate is less than the so-called secrecy capacity Cs, which is usually smaller than the channel capacity C. In order to remove the loss C - Cs, we propose a multiplex coding scheme with plural independent messages. In this paper, it is shown that the proposed multiplex coding scheme can attain the channel capacity as the total rate of the plural messages and the perfect secrecy for each message. The coding theorem is proved by extending Hayashi's proof, in which the coding of the channel resolvability is applied to the wiretap channel.

IEEE Information Theory Workshop (ITW)•Dec 10, 2005•21 citations

Secure Multiplex Coding Attaining Channel Capacity in Wiretap Channels

Daisuke Kobayashi, H. Yamamoto, Tomohiro Ogawa

It is known that a message can be transmitted safely against any wiretapper via a noisy channel without a secret key if the coding rate is less than the so-called secrecy capacity CS, which is usually smaller than the channel capacity C. In order to remove the loss C-CS, we propose a multiplex coding scheme with plural independent messages. In this paper, it is shown that the proposed multiplex coding scheme can attain the channel capacity as the total rate of the plural messages and the perfect secrecy for each massage. Several bounds of achievable multiplex coding rate region are derived for general wiretap channels in the sense of information-spectral methods, by extending Hayashi's proof, in which the coding of the channel resolvability is applied to wiretap channels. Furthermore, the exact region for deterministic coding is determined for stationary memoryless full-rank wiretap channels.

IEEE Transactions on Information Theory•Sep 25, 2013•36 citations

Secure multiplex coding to attain the channel capacity in wiretap channels

H. Yamamoto

It is known that a message can be transmitted safely against any wiretapper via a noisy channel without a secret key if the coding rate is less than the so-called secrecy capacity CS, which is usually smaller than the channel capacity C. In order to remove the loss C-CS, we propose a multiplex coding scheme with plural independent messages. In this paper, it is shown that the proposed multiplex coding scheme can attain the channel capacity as the total rate of the plural messages and the perfect secrecy for each massage. Several bounds of achievable multiplex coding rate region are derived for general wiretap channels in the sense of information-spectral methods, by extending Hayashi's proof, in which the coding of the channel resolvability is applied to wiretap channels. Furthermore, the exact region for deterministic coding is determined for stationary memoryless full-rank wiretap channels.

IEEE Transactions on Information Theory•Jan 1, 2014•1 citation

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•8 citations
The bit commitment can be realized by using a noisy channel. Winter-Nascimento-Imai showed that the bit commitment capacity of a noisy channel is given by Cb= maxpNH(X\Y) where X and Y are the input and output of the channel. In this paper, the idea of a multiplex coding, which was first introduced into the coding problem of a wiretap channel by Kobayashi-Yamamoto-Ogawa, is applied to the bit commitment coding. The coding theorem is proved for the multiplex coding of bit commitment based on a noisy channel, and it is shown that several mutually independent secrets can be committed at the same time via a nosiy channel attaining the perfect secrecy of each secret with the total coding rate log \X, where \X\ is the cardinality of channel input alphabet.
It is known that a message can be transmitted safely against any wiretapper via a noisy channel without a secret key if the coding rate is less than the so-called secrecy capacity CSC_SCS​, which is usually smaller than the channel capacity CCC. In order to remove the loss C−CSC - C_SC−CS​, we propose a multiplex coding scheme with plural independent messages. In this paper, it is shown that the proposed multiplex coding scheme can attain the channel capacity as the total rate of the plural messages and the perfect secrecy for each message. The coding theorem is proved by extending Hayashi's proof, in which the coding of the channel resolvability is applied to wiretap 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).
It is known that a message can be transmitted safely against any wiretap per via a noisy channel without a secret key if the coding rate is less than the so-called secrecy capacity Cs, which is usually smaller than the channel capacity C. In order to remove the loss C - Cs, we propose a multiplex coding scheme with plural independent messages. In this paper, it is shown that the proposed multiplex coding scheme can attain the channel capacity as the total rate of the plural messages and the perfect secrecy for each message. The coding theorem is proved by extending Hayashi's proof, in which the coding of the channel resolvability is applied to the wiretap channel.
It is known that a message can be transmitted safely against any wiretapper via a noisy channel without a secret key if the coding rate is less than the so-called secrecy capacity CS, which is usually smaller than the channel capacity C. In order to remove the loss C-CS, we propose a multiplex coding scheme with plural independent messages. In this paper, it is shown that the proposed multiplex coding scheme can attain the channel capacity as the total rate of the plural messages and the perfect secrecy for each massage. Several bounds of achievable multiplex coding rate region are derived for general wiretap channels in the sense of information-spectral methods, by extending Hayashi's proof, in which the coding of the channel resolvability is applied to wiretap channels. Furthermore, the exact region for deterministic coding is determined for stationary memoryless full-rank wiretap channels.
It is known that a message can be transmitted safely against any wiretapper via a noisy channel without a secret key if the coding rate is less than the so-called secrecy capacity CS, which is usually smaller than the channel capacity C. In order to remove the loss C-CS, we propose a multiplex coding scheme with plural independent messages. In this paper, it is shown that the proposed multiplex coding scheme can attain the channel capacity as the total rate of the plural messages and the perfect secrecy for each massage. Several bounds of achievable multiplex coding rate region are derived for general wiretap channels in the sense of information-spectral methods, by extending Hayashi's proof, in which the coding of the channel resolvability is applied to wiretap channels. Furthermore, the exact region for deterministic coding is determined for stationary memoryless full-rank wiretap channels.
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.