We study lossy source coding under a distortion measure defined by the negative log-likelihood induced by a prescribed conditional distribution $P_{X|U}$. This \emph{log-likelihood distortion} models compression settings in which the reconstruction is a semantic representation from which the source can be probabilistically generated, rather than a pointwise approximation. We formulate the corresponding rate-distortion problem and characterize fundamental properties of the resulting rate-distortion function, including its connections to lossy compression under log-loss, classical rate-distortion problems with arbitrary distortion measures, and rate-distortion with perfect perception.

We propose the problem of wiretapped commitment, where two parties, say committer Alice and receiver Bob, engage in a commitment protocol using a noisy channel as a resource, in the presence of an eavesdropper, say Eve. Noisy versions of Alice's transmission over the wiretap channel are received by both Bob and Eve. We seek to determine the maximum commitment throughput in the presence of eavesdropper, i.e., wiretapped commitment capacity, where in addition to the standard security requirements for two-party commitment, one seeks to ensure that Eve doesn't learn about the commit string. A key interest in this work is to explore the effect of collusion (or lack of it) between the eavesdropper Eve and either Alice or Bob. Toward the same, we present results on the wiretapped commitment capacity under the so-called Y-private regime (when Alice or Bob cannot collude with Eve) and the 2-private regime (when Alice or Bob may collude with Eve).

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.

Given two jointly distributed random variables $\left( {X,Y} \right)$, a functional representation of $X$ is a random variable $Z$ independent of $Y$, and a deterministic function $g\left( { \cdot , \cdot } \right)$ such that $X = g\left( {Y,Z} \right)$. The problem of finding a minimum entropy functional representation is known to be equivalent to the problem of finding a minimum entropy coupling where, given a collection of probability distributions ${P_1}, \ldots ,{P_m}$, the goal is to find a coupling ${X_1}, \ldots ,{X_m}\left( {{X_i} \sim {P_i}} \right)$ with the smallest entropy ${H_\alpha }\left( {{X_1}, \ldots ,{X_m}} \right)$. This paper presents a new information spectrum converse, and applies it to obtain direct lower bounds on minimum entropy in both problems. The new results improve on all known lower bounds, including previous lower bounds based on the concept of majorization. In particular, the presented proofs leverage both - the information spectrum and the majorization - perspectives on minimum entropy couplings and functional representations.

In the classic adversarial communication problem, two parties communicate over a noisy channel in the presence of a malicious jamming adversary. The arbitrarily varying channels (AVCs) offer an elegant framework to study a wide range of interesting adversary models. The optimal throughput or capacity over such AVCs is intimately tied to the underlying adversary model; in some cases, capacity is unknown and the problem is known to be notoriously hard. The omniscient adversary, one which knows the sender’s entire channel transmission a priori, is one of such classic models of interest; the capacity under such an adversary remains an exciting open problem. The myopic adversary is a generalization of that model where the adversary’s observation may be corrupted over a noisy discrete memoryless channel. Through the adversary’s myopicity, one can unify the slew of different adversary models, ranging from the omniscient adversary to one that is completely blind to the transmission (the latter is the well known oblivious model where the capacity is fully characterized).In this work, we present new results on the capacity under both the omniscient and myopic adversary models. We completely characterize the positive capacity threshold over general AVCs with omniscient adversaries. The characterization is in terms of two key combinatorial objects: the set of completely positive distributions and the CP-confusability set. For omniscient AVCs with positive capacity, we present non-trivial lower and upper bounds on the capacity; unlike some of the previous bounds, our bounds hold under fairly general input and jamming constraints. Our lower bound improves upon the generalized Gilbert-Varshamov bound for general AVCs while the upper bound generalizes the well known Elias-Bassalygo bound (known for binary and q-ary alphabets). For the myopic AVCs, we build on prior results known for the so-called sufficiently myopic model, and present new results on the positive rate communication threshold over the so-called insufficiently myopic regime (a completely insufficient myopic adversary specializes to an omniscient adversary). We present interesting examples for the widely studied models of adversarial bit-flip and bit-erasure channels. In fact, for the bit-flip AVC with additive adversarial noise as well as random noise, we completely characterize the omniscient model capacity when the random noise is sufficiently large vis-a-vis the adversary’s budget.

We study commitments over unreliable compound noisy channels, where parties may know the compound channel state but lack control over that state. Commitment is one of the common building blocks for many cryptographic protocols which realize multi-party computational functionalities in a secure manner. A noisy channel, among others, is widely acknowledged as a promising resource for realizing information-theoretically secure cryptographic primitives, including commitment. However, unreliable noisy channels with poorly or imprecisely characterized statistical behaviour can severely degrade commitment guarantees. Our focus is unreliability on account of a compound channel state, albeit under public awareness of that state.Building on prior work, we seek to characterize the optimal commitment throughput or commitment capacity of compound binary symmetric channels when parties may be state-aware. State-awareness implies a passive and publicly known capability of precise channel knowledge (whether said party is honest or dishonest); however, state-awareness precludes any active and private channel state control as in, for instance, the classic unfair noisy channels (UNCs). We present new results on the commitment capacity under all possible configurations where individual parties may (or may not) be state-aware. An important takeaway of our work is the following: even a fairly weak capability of state-awareness (albeit when asymmetric and only at the committer-side) can degrade the commitment throughput to the same extent as under strongly capable parties that can privately control the compound state.

Commitment is an important cryptographic primitive. It is well known that noisy channels are a promising resource to realize commitment in aninformation-theoreticallysecure manner. However, oftentimes, channel behaviour may be poorly characterized thereby limiting the commitment throughput and/or degrading the security guarantees; a particularly problematic situation arises when a dishonest party, unbeknown to the honest one, maliciously alters the channel characteristics. Reverse elastic channels (RECs) are an interesting class of suchunreliablechannels where only a dishonestcommitter, say Alice, can maliciously alter the channel. RECs have attracted recent interest in the study of several cryptographic primitives. Our principal contribution is the REC commitment capacity characterization; this proves a recent related conjecture. A key result is our tight converse which analyses a specific cheating strategy by Alice. Along with elastic channels (ECs), where only a dishonestreceiverBob can alter the channel, RECs are also closely related to the classic unfair noisy channels (UNCs). In stark contrast to UNCs, both RECs and ECs always exhibit positive commitment throughput for all non-trivial channel parameters. Interestingly, our results show that channels with exclusiveone-sided elasticityfor dishonest parties, exhibit a fundamentalasymmetrywhere, a committer with one-sided elasticity has a significantly more debilitating effect on the commitment throughput than a similarly capable receiver.

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