Noisy channels are a foundational resource for constructing cryptographic primitives such as string commitment and oblivious transfer. The noisy channel model has been extended to unfair noisy channels, where adversaries can influence the parameters of a memoryless channel. In this work, we introduce the unstructured noisy channel model as a generalization of the unfair noisy channel model to allow the adversary to manipulate the channel arbitrarily subject to certain entropic constraints. We present a string commitment protocol with established security and derive its achievable commitment rate, demonstrating the feasibility of commitment against this stronger class of adversaries. Furthermore, we show that the entropic constraints in the unstructured noisy channel model can be derived from physical assumptions such as noisy quantum storage. Our work thus connects two distinct approaches to commitment, i.e., the noisy channel and physical limitations.
Noisy channels are a foundational resource for constructing cryptographic primitives such as string commitment and oblivious transfer. The noisy channel model has been extended to unfair noisy channels, where adversaries can influence the parameters of a memoryless channel. In this work, we introduce the unstructured noisy channel model as a generalization of the unfair noisy channel model to allow the adversary to manipulate the channel arbitrarily subject to certain entropic constraints. We present a string commitment protocol with established security and derive its achievable commitment rate, demonstrating the feasibility of commitment against this stronger class of adversaries. Furthermore, we show that the entropic constraints in the unstructured noisy channel model can be derived from physical assumptions such as noisy quantum storage. Our work thus connects two distinct approaches to commitment, i.e., the noisy channel and physical limitations.
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.
Realizing fundamental cryptographic primitives with unconditional security is a central topic in information-theoretic cryptography. These primitives can be realized based on physical assumptions, such as the existence of noisy channels, an upper bound on the storage capacity, or the laws of quantum mechanics. Palmieri and Pereira [1] demonstrated that delays in communication channels can be used as a reasonable and effective assumption to obtain an unconditionally secure oblivious transfer protocol against honest-but-curious adversaries. While any oblivious transfer protocol secure against malicious adversaries can be used to implement commitment, the reduction does not work if the oblivious transfer protocol is only secure against honest-but-curious adversaries. Thus, the question of obtaining a secure commitment protocol based on channel delays is still open. In this paper, we provide a concrete protocol for implementing string commitments based on packet reordering – a consequence of channel delays in packet networks.
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.
Commitment is a key primitive which resides at the heart of several cryptographic protocols. Noisy channels can help realize information-theoretically secure commitment schemes; however, their imprecise statistical characterization can severely impair such schemes, especially their security guarantees. Keeping our focus on channel ‘unreliability’ in this work, we study commitment over unreliable continuous alphabet channels called the Gaussian unfair noisy channels or Gaussian UNCs.We present the first results on the optimal throughput or commitment capacity of Gaussian UNCs. It is known that ‘classical’ Gaussian channels have infinite commitment capacity, even under finite transmit power constraints. For ‘unreliable’ Gaussian UNCs, we prove the surprising result that their commitment capacity may be finite, and in some cases, zero. When commitment is possible, we present achievable rate lower bounds by constructing positive-throughput protocols under given input power constraint, and (two-sided) channel elasticity at committer Alice and receiver Bob. Our achievability results establish an interesting fact – Gaussian UNCs with zero elasticity have infinite commitment capacity. This result brings a completely new perspective as to why classic Gaussian channels, i.e., Gaussian UNCs with zero elasticity, have infinite capacity. Finally, we precisely characterize the positive commitment capacity threshold for a Gaussian UNC in terms of the channel elasticity, when the transmit power tends to infinity.
Commitment is a key primitive which resides at the heart of several cryptographic protocols. Noisy channels can help realize information-theoretically secure commitment schemes, however, their imprecise statistical characterization can severely impair such schemes, especially their security guarantees. Keeping our focus on channel unreliability in this work, we study commitment over unreliable continuous alphabet channels called the Gaussian unfair noisy channels or Gaussian UNCs. We present the first results on the optimal throughput or commitment capacity of Gaussian UNCs. It is known that classical Gaussian channels have infinite commitment capacity, even under finite transmit power constraints. For unreliable Gaussian UNCs, we prove the surprising result that their commitment capacity may be finite, and in some cases, zero. When commitment is possible, we present achievable rate lower bounds by constructing positive - throughput protocols under given input power constraint, and (two-sided) channel elasticity at committer Alice and receiver Bob. Our achievability results establish an interesting fact - Gaussian UNCs with zero elasticity have infinite commitment capacity - which brings a completely new perspective to why classic Gaussian channels, i.e., Gaussian UNCs with zero elasticity, have infinite capacity. Finally, we precisely characterize the positive commitment capacity threshold for a Gaussian UNC in terms of the channel elasticity, when the transmit power tends to infinity.
In this work, we study commitment over a class of channels called reverse elastic channels (RECs). In the commitment problem, two mutually distrustful parties, say Alice and Bob, seek to commit on a bit string available to Alice. The parties interact via a commitment protocol comprising two phases, viz., commit phase followed by reveal phase. Alice commits to a string, and transmits it to Bob securely in a manner Bob cannot learn it until Alice chooses to reveal it; at the time of reveal, however, Bob can successfully detect if Alice cheats. It is well known that noisy channels are a promising resource to realize information-theoretically secure commitment; however, oftentimes, channel behaviour may be poorly characterized thereby limiting the commitment throughput and/or degrading the security guarantees. Particularly problematic is a scenario where dishonest parties can actively alter the channel characteristics. RECs are an interesting class of such unreliable channels, where essentially only a dishonest committer Alice can meaningfully alter the channel; RECs have attracted active recent interest. Our principal contribution is the REC commitment capacity characterization for all parameters; this proves a recent related conjecture. Apart from presenting an achievable scheme, a key result in our work is a tight converse which analyses a specific cheating strategy by Alice. The significance of RECs stems from the fact that along with elastic channels (ECs), where only a dishonest receiver Bob can alter the channel, these two channel models represent special cases of the more widely studied unfair noisy channels (UNCs). Interestingly, for a given set of parameters, our result shows that the REC commitment capacity is no larger than that for the ECs. Furthermore, similar to the ECs, RECs offer non-trivial commitment throughput for all meaningful parameters; this is in stark contrast to UNCs where the throughput may possibly be zero.