We propose a new concept of secure list decoding, which is related to bit-string commitment. While the conventional list decoding requires that the list contains the transmitted message, secure list decoding requires the following additional security conditions to work as a modification of bit-string commitment. The first additional security condition is the receiver’s uncertainty for the transmitted message, which is stronger than the impossibility of the correct decoding, even though the transmitted message is contained in the list. The other additional security condition is the impossibility for the sender to estimate another element of the decoded list except for the transmitted message. The first condition is evaluated by the equivocation rate. The asymptotic property is evaluated by three parameters, the rates of the message and list sizes, and the equivocation rate. We derive the capacity region of this problem. We show that the combination of hash function and secure list decoding yields the conventional bit-string commitment. Our results hold even when the input and output systems are general probability spaces including continuous systems. When the input system is a general probability space, we formulate the abilities of the honest sender and the dishonest sender in a different way.
We propose a new concept of secure list decoding, which is related to bit-string commitment. While the conventional list decoding requires that the list contains the transmitted message, secure list decoding requires the following additional security conditions to work as a modification of bit-string commitment. The first additional security condition is the receiver’s uncertainty for the transmitted message, which is stronger than the impossibility of the correct decoding, even though the transmitted message is contained in the list. The other additional security condition is the impossibility for the sender to estimate another element of the decoded list except for the transmitted message. The first condition is evaluated by the equivocation rate. The asymptotic property is evaluated by three parameters, the rates of the message and list sizes, and the equivocation rate. We derive the capacity region of this problem. We show that the combination of hash function and secure list decoding yields the conventional bit-string commitment. Our results hold even when the input and output systems are general probability spaces including continuous systems. When the input system is a general probability space, we formulate the abilities of the honest sender and the dishonest sender in a different way.
We study commitment scheme for classical-quantum channels. To accomplish this we define various notions of commitment capacity for these channels and prove matching upper and lower bound on it in terms of the conditional entropy. Our achievability (lower bound) proof is quantum generalisation of the work of one of the authors (arXiv:2103.11548) which studied the problem of secure list decoding and its application to bit-string commitment. The techniques we use in the proof of converse (upper bound) is similar in spirit to the techniques introduced by Winter, Nascimento and Imai (Cryptography and Coding 2003) to prove upper bound on the commitment capacity of classical channels. However, generalisation of this technique to the quantum case is not so straightforward and requires some new constructions, which can be of independent interest.
We study commitment scheme for classical-quantum channels. To accomplish this we define various notions of commitment capacity for these channels and prove matching upper and lower bound on it in terms of the conditional entropy. Our achievability (lower bound) proof is quantum generalisation of the work of one of the authors (arXiv:2103.11548) which studied the problem of secure list decoding and its application to bit-string commitment. The techniques we use in the proof of converse (upper bound) is similar in spirit to the techniques introduced by Winter, Nascimento and Imai (Cryptography and Coding 2003) to prove upper bound on the commitment capacity of classical channels. However, generalisation of this technique to the quantum case is not so straightforward and requires some new constructions, which can be of independent interest.
We study commitment scheme for classical-quantum channels. To accomplish this we define various notions of commitment capacity for these channels and prove matching upper and lower bound on it in terms of the conditional entropy. Our achievability (lower bound) proof is quantum generalisation of the work of one of the authors (arXiv:2103.11548) which studied the problem of secure list decoding and its application to bit-string commitment. The techniques we use in the proof of converse (upper bound) is similar in spirit to the techniques introduced by Winter, Nascimento and Imai (Cryptography and Coding 2003) to prove upper bound on the commitment capacity of classical channels. However, generalisation of this technique to the quantum case is not so straightforward and requires some new constructions, which can be of independent interest.
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.
In the commitment problem, two mutually distrustful parties Alice and Bob interact in a two-phase protocol, viz., commit and reveal phase, to achieve commitment over a bit string that Alice possesses. The protocol successfully achieves commitment if, firstly, Alice can commit to sharing a string with Bob, with the guarantee that this string remains hidden from Bob until she chooses to reveal it to him. Secondly, when Alice does reveal a string, Bob is able to detect precisely whether the revealed string is different from the one Alice committed to sharing. Information-theoretically secure commitment is impossible if Alice and Bob communicate only noiselessly; however, communication using a noisy channel can be a resource to realize commitment. Even though a noisy channel may be available, it is possible that the corresponding channel law is imprecisely known or poorly characterized. We define and study a compound-binary symmetric channel (compound-BSC) which models such a scenario. A compound-BSC is a BSC whose transition probability is fixed but unknown to either party; the set of potential values which this transition probability can take, though, is known to both parties a priori. In this work, we completely characterize the maximum commitment throughput or commitment capacity of a compound-BSC. We provide an optimal, computationally-efficient scheme for our achievability, and we derive a converse for general alphabet compound DMCs, which is then specialized for compound-BSCs.
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.