We study the Chernoff-Stein exponent of the following binary hypothesis testing problem: Associated with each hypothesis is a set of channels. A transmitter, without knowledge of the hypothesis, chooses the vector of inputs to the channel. Given the hypothesis, from the set associated with the hypothesis, an adversary chooses channels, one for each element of the input vector. Based on the channel outputs, a detector attempts to distinguish between the hypotheses. We study the Chernoff-Stein exponent for the cases where the transmitter (i) is deterministic, (ii) may privately randomize, and (iii) shares randomness with the detector that is unavailable to the adversary. It turns out that while a memoryless transmission strategy is optimal under shared randomness, it may be strictly suboptimal when the transmitter only has private randomness.

We study communication with consensus over a broadcast channel—the receivers reliably decode the sender’s message when the sender is honest, and their decoder outputs agree even if the sender acts maliciously. We characterize the broadcast channels which permit this Byzantine consensus and determine their capacity. We show that communication with consensus is possible only when the broadcast channel has embedded in it a natural “common channel” whose output both receivers can unambiguously determine from their own channel outputs. Interestingly, in general, the consensus capacity may be larger than the point-to-point capacity of the common channel, i.e., while decoding, the receivers may make use of parts of their output signals on which they may not have consensus provided there are some parts (namely, the common channel output) on which they can agree.

We study the distributed function computation problem with$k$users of which at most$s$may be controlled by an adversary and characterize the set of functions of the sources the decoder can reconstruct robustly in the following sense if the users behave honestly, the function is recovered with high probability (w.h.p.); if they behave adversarially, w.h.p, either one of the adversarial users is identified or the function is recovered with vanishingly small distortion.

Submodular functions are known to satisfy various forms of fractional subadditivity. This work investigates the conditions for equality to hold exactly or approximately in the fractional sub additivity of sub modular functions. We establish that a small gap in the inequality implies that the function is close to being modular, and that the gap is zero if and only if the function is modular. We then present natural implications of these results for special cases of sub modular functions, such as entropy, relative entropy, and matroid rank. As a consequence, we characterize the necessary and sufficient conditions for equality to hold in Shearer's lemma, recovering a result of Ellis et al. (2016) as a special case. We leverage our results to propose a new multivariate mutual information, which generalizes Watanabe's total correlation (1960), Han's dual total correlation (1975), and Csiszar and Narayan's shared information (2004), and analyze its properties. Among these properties, we extend Watanabe's characterization of total correlation as the maximum correlation over partitions to fractional partitions. When applied to matrix determinantal inequalities for positive definite matrices, our results recover the equality conditions of the classical determinantal inequalities of Hadamard, Szász, and Fischer as special cases.

Federated learning with heterogeneous data and personalization has received significant recent attention. Separately, robustness to corrupted data in the context of federated learning has also been studied. In this paper we explore combining personalization for heterogeneous data with robustness, where a constant fraction of the clients are corrupted. Motivated by this broad problem, we formulate a simple instantiation which captures some of its difficulty. We focus on the specific problem of personalized mean estimation where the data is drawn from a Gaussian mixture model. We give an algorithm whose error depends almost linearly on the ratio of corrupted to uncorrupted samples, and show a lower bound with the same behavior, albeit with a gap of a constant factor.

We study the binary hypothesis testing problem where an adversary may potentially corrupt a fraction of the samples. The detector is, however, permitted to abstain from making a decision if (and only if) the adversary is present. We consider a few natural “contamination models” and characterize for them the trade-off between the error exponents of the four types of errors - errors of deciding in favour of the incorrect hypothesis when the adversary is present and errors of abstaining or deciding in favour of the wrong hypothesis when the adversary is absent, under the two hypotheses. All missing proofs may be found in the extended version [1].

We introduce the problem of determining the identity of a byzantine user (internal adversary) in a communication system. We consider a two-user discrete memoryless multiple access channel where either user may deviate from the prescribed behaviour. Since small deviations may be indistinguishable from the effects of channel noise, it might be overly restrictive to attempt to detect all deviations. In our formulation, we only require detecting deviations which impede the decoding of the non-deviating user’s message. When neither user deviates, correct decoding is required. When one user deviates, the decoder must either output a pair of messages of which the message of the non-deviating user is correct or identify the deviating user. The users and the receiver do not share any randomness. The results include a characterization of the set of channels where communication is feasible, and an inner and outer bound on the capacity region. We also show that whenever the rate region has non-empty interior, the capacity region is same as the capacity region under randomized encoding, where each user shares independent randomness with the receiver. We also give an outer bound for this randomized coding capacity region.

We study information leakage through guesswork, the minimum expected number of guesses required to guess a random variable. In particular, we define maximal guesswork leakage as the multiplicative decrease, upon observing$Y$, of the guesswork of a randomized function of$X$, maximized over all such randomized functions. We also study a pointwise form of the leakage which captures the leakage due to the release of a single realization of$Y$. We also study these two notions of leakage with oblivious (or memoryless) guessing. We obtain closed-form expressions for all these leakage measures, with the exception of one. Specifically, we are able to obtain closed-form expression for maximal guesswork leakage for the binary erasure source only; deriving expressions for arbitrary sources appears challenging. Some of the consequences of our results are - a connection between guesswork and differential privacy and a new operational interpretation to maximal$\alpha$-leakage in terms of guesswork.

We study the problem of synthesising a two-user broadcast channel using a common message, where each output terminal shares an independent source of randomness with the input terminal. This generalises two problems studied in the literature (Cuff, IEEE Trans. Inform. Theory, 2013; Kurri et.al., IEEE Trans. Inform. Theory, 2021). We give an inner bound on the tradeoff region between the rates of communication and shared randomness, and a lower bound on the minimum communication rate. Although the bounds presented here are not tight in general, they are tight for some special cases, including the aforementioned problems.

We study the adversarial binary hypothesis testing problem [1] in the sequential setting. Associated with each hypothesis is a closed, convex set of distributions. Given the hypothesis, each observation is generated according to a distribution chosen (from the set associated with the hypothesis) by an adversary who has access to past observations. In the sequential setting, the number of observations the detector uses to arrive at a decision is variable; however there is a constraint on the expected number of observations used. We characterize the closure of the set of achievable pairs of error exponents.

We study communication over a Multiple Access Channel (MAC) where users can possibly be adversarial. The receiver is unaware of the identity of the adversarial users (if any). When all users are non-adversarial, we want their messages to be decoded reliably. When a user behaves adversarially, we require that the honest users’ messages be decoded reliably. An adversarial user can mount an attack by sending any input into the channel rather than following the protocol. It turns out that the 2-user MAC capacity region follows from the point-to-point Arbitrarily Varying Channel (AVC) capacity. For the 3-user MAC in which at most one user may be malicious, we characterize the capacity region for deterministic codes and randomized codes (where each user shares an independent random secret key with the receiver). These results are then generalized for the$k$-user MAC where the adversary may control all users in one out of a collection of given subsets.

We study a secret sharing problem with three secrets where the secrets are allowed to be related to each other, i.e., only certain combinations of the three secrets are permitted. The dealer produces three shares such that every pair of shares reveals a unique secret and reveals nothing about the other two secrets, other than what can be inferred from the revealed secret. For the case of binary secrets, we exactly determine the minimum amount of randomness required by the dealer, for each possible set of permitted combinations. Our characterization is based on new lower and upper bounds.

We study the Chernoff-Stein exponent of the following binary hypothesis testing problem: Associated with each hypothesis is a set of channels. A transmitter, without knowledge of the hypothesis, chooses the vector of inputs to the channel. Given the hypothesis, from the set associated with the hypothesis, an adversary chooses channels, one for each element of the input vector. Based on the channel outputs, a detector attempts to distinguish between the hypotheses. We study the Chernoff-Stein exponent for the cases where the transmitter (i) is deterministic, (ii) may privately randomize, and (iii) shares randomness with the detector that is unavailable to the adversary. It turns out that while a memoryless transmission strategy is optimal under shared randomness, it may be strictly suboptimal when the transmitter only has private randomness.

We study communication with consensus over a broadcast channel - the receivers reliably decode the sender’s message when the sender is honest, and their decoder outputs agree even if the sender acts maliciously. We characterize the broadcast channels which permit this byzantine consensus and determine their capacity.

We study the problem of simulating a two-user multiple-access channel (MAC) over a multiple access network of noiseless links. Two encoders observe independent and identically distributed (i.i.d.) copies of a source random variable each, while a decoder observes i.i.d. copies of a side-information random variable. There are rate-limited noiseless communication links between each encoder and the decoder, and there is independent pairwise shared randomness between all the three possible pairs of nodes. The decoder has to output approximately i.i.d. copies of another random variable jointly distributed with the two sources and the side information. We are interested in the rate tuples which permit this simulation. This setting can be thought of as a multi-terminal generalization of the point-to-point channel simulation problem studied by Bennett et al. (2002) and Cuff (2013). When the pairwise shared randomness between the encoders is absent, the setting reduces to a special case of MAC simulation using another MAC studied by Haddadpour et al. (2013). We establish that the presence of encoder shared randomness can strictly improve the communication rate requirements. We first show that the inner bound derived from Haddadpour et al. (2013) is tight when the sources at the encoders are conditionally independent given the side-information at the decoder. This result recovers the existing results on point-to-point channel simulation and function computation over such multi-terminal networks. We then explicitly compute the communication rate regions for an example both with and without the encoder shared randomness and demonstrate that its presence strictly reduces the communication rates. Inner and outer bounds for the general case are also obtained.

We study the fundamental problem of index coding under an additional privacy constraint that requires each receiver to learn nothing more about the collection of messages beyond its demanded messages from the server and what is available to it as side information. To enable such private communication, we allow the use of a collection of independent secret keys, each of which is shared amongst a subset of users and is known to the server. The goal is to study properties of the key access structures that make the problem feasible and then design encoding and decoding schemes efficient in the size of the server transmission as well as the sizes of the secret keys. We call this theprivate index codingproblem. We begin by characterizing the key access structures that make private index coding feasible. We also give conditions to check if a given linear scheme is a valid private index code. For up to three users, we characterize the rate region of feasible server transmission and key rates, and show that all feasible rates can be achieved using scalar linear coding and time sharing; we also show that scalar linear codes are sub-optimal for four receivers. The outer bounds used in the case of three users are extended to arbitrary number of users and seen as a generalized version of the well-known polymatroidal bounds for the standard non-private index coding. We also show that the presence of common randomness and private randomness does not change the rate region. Furthermore, we study the case where the server has the ability to multicast to any subset of users, and demonstrate how this flexibility can be used to provide privacy and characterize the minimum number of server multicasts required.

We propose a communication model, that we call compound arbitrarily varying channels (CAVC), which unifies and generalizes compound channels and arbitrarily varying channels (AVC). A CAVC can be viewed as a noisy channel with a fixed, but unknown, compound-state and an AVC-state which may vary with every channel use. The AVC-state is controlled by an adversary who is aware of the compound-state. We study three problems in this setting: ‘communication’, ‘communication and compound-state identification’, and ‘communication or compound-state identification’. For these problems, we study conditions for feasibility and capacity under deterministic coding and random coding.

We study the problem of simulating a multiple access channel over a network of noiseless links. Two encoders observe independent and identically distributed (i.i.d.) copies of a source random variable each, while a decoder observes i.i.d. copies of a side-information random variable. There are rate-limited noiseless communication links and independent pairwise shared randomness resources between each encoder and the decoder. The decoder has to output approximately i.i.d. copies of another random variable jointly distributed with the observed random variables. This setting can be thought of as a multi-terminal generalization of the point-to-point channel simulation problem studied by Bennett et al. (2002) and Cuff (2013). General inner and outer bounds on the rate region are derived. For the special case when the sources at the encoders are conditionally independent given the side-information at the decoder, we completely characterize the rate region. Our bounds recover the existing results on deterministic function computation over such multi-terminal networks. We then show through an example that an additional independent source of shared randomness between the encoders that is not available to the decoder strictly improves the communication rates.

The capacity region of several multiuser models in information theory can be enlarged by utilizing feedback of the received symbols. This is in contradiction to the discrete memoryless case, where feedback is known not to change the capacity. In this paper, we consider two broadcast models with noisy feedback from both the receivers. The models are derived from a standard memoryless scalar GBC, where two intermediate passive nodes are assumed to be observing the transmissions via separate noisy links corrupted by independent AWGN. In our first model, the scalar output from each intermediate node is passed through two additional independent AWGN links, called feedback and forward links. The output of the feedback link is observed by the transmitter as feedback, whereas only the forward link is observed by the corresponding decoder. We derive conditions that are both necessary and sufficient for feedback to enlarge the capacity region. In the second model, the two outputs of a standard GBC are observed by the respective decoders, but the transmitter observes the sum of the symbols at the receivers using causal feedback. We show that such a feedback has no effect on the capacity region.

We introduce the problem of determining the identity of a byzantine user (internal adversary) in a communication system. We consider a two-user discrete memoryless multiple access channel where either user may deviate from the prescribed behaviour. Owing to the noisy nature of the channel, it may be overly restrictive to attempt to detect all deviations. In our formulation, we only require detecting deviations which impede the decoding of the non-deviating user's message. When neither user deviates, correct decoding is required. When one user deviates, the decoder must either output a pair of messages of which the message of the non-deviating user is correct or identify the deviating user. The users and the receiver do not share any randomness. The results include a characterization of the set of channels where communication is feasible, and an inner and outer bound on the capacity region.

Generalization error captures the degree to which the output of a learning algorithm overfits the training data. We obtain a family of bounds which generalize the bounds developed by Xu & Raginsky (2017) and Bu, Zou and Veeravalli (2019), under certain assumptions. Our bounds are based on the Rényi analogue of the Donsker-Varadhan representation of Kullback-Leibler divergence. We also obtain bounds on the probability of generalization error which recover the bounds of Esposito, Gastpar and Issa (2020). We also give a multiplicative lower bound on the expected true loss for a 0-1 loss function.

We study common randomness generation problems where$n$players aim to generatesamesequences of random coin flips where some subsets of the players share an independent common coin which can be tossed multiple times, and there is a publicly seen blackboard through which the players communicate with each other. We provide a tight representation of the optimal communication rates via linear programming, and more importantly, propose explicit algorithms for the optimal distributed simulation for a wide class of hypergraphs. In particular, the optimal communication rate in complete hypergraphs is still achievable in sparser hypergraphs containing a path-connected cycle-free cluster of topologically connected components. Some key steps in analyzing the upper bounds rely on two different definitions of connectivity in hypergraphs, which may be of independent interest.

We study a distributed sampling problem where a set of processors want to output (approximately) independent and identically distributed samples from a given joint distribution with the help of a common message from a coordinator. Each processor has access to a subset of sources from a set of independent sources of “shared” randomness. We consider two cases - in the “omniscient coordinator setting”, the coordinator has access to all these sources of shared randomness, while in the “oblivious coordinator setting,” it has access to none. In addition, all processors and the coordinator may privately randomize. In the omniscient coordinator setting, when the subsets at the processors are disjoint (individually shared randomness model), we characterize the rate of communication required from the coordinator to the processors over a multicast link. For the two-processor case, the optimal rate matches a special case of relaxed Wyner's common information proposed by Gastpar and Sula (2019), thereby providing an operational meaning to the latter. We also give an upper bound on the communication rate for the “randomness-on-the-forehead” model where each processor observes all but one source of randomness and present an achievable strategy for the general case where the processors have access to arbitrary subsets of sources of randomness. Also, we consider a more general model where the processors observe components of correlated sources (with the coordinator observing all the components), where we characterize the communication rate when all the processors wish to output the same random sequence. In the oblivious coordinator setting, we completely characterize the trade-off region between the communication and shared randomness rates for the general case where the processors have access to arbitrary subsets of sources of randomness.

It is well known that the capacity region of an average transmit power constrained Gaussian Broadcast Channel (GBC) with independent noise realizations at the receivers is enlarged by the presence of causal noiseless feedback. When the noise variances at the receivers are identical, even passive feedback via independent memoryless Gaussian links can lead to a capacity region enlargement. The last fact remains true even when the feedback noise variance is very high, and available only from one of the receivers. While such capacity enlargements are feasible for several other feedback models in the Gaussian BC setting, it is also known that feedback does not change the capacity region for physically degraded broadcast channels. In this paper, we consider a two user GBC with independent noise realizations at the receivers, where the feedback links from the receivers are corrupted by independent additive Gaussian noise processes. We investigate the set of four noise variances, two forward and two feedback, for which no capacity enlargement is possible. A sharp characterization of this region is derived, i.e., any quadruple outside the presented region will lead to a capacity enlargement, whereas quadruples inside will leave the capacity region unchanged. Our results lead to the conclusion that when the forward noise variances are different, too noisy a feedback from one of the receivers alone is not always beneficial for enlarging the capacity region, be it from the stronger user or the weaker one, in sharp contrast to the case of equal forward noise variances.

We consider a two-user secure computation problem in which Alice and Bob communicate interactively in order to compute some deterministic functions of the inputs. The privacy requirement is that each user should not learn any additional information about a function of the inputs other than what can be inferred from its own input and output. For the distribution-free setting, i.e., when the protocol must be correct and private for any joint input distribution, we completely characterize the set of all securely computable functions. When privacy is required only against Bob who computes a function based on a single transmission from Alice, we show that asymptotically secure computability is equivalent to perfectly secure computability. Separately, we consider an eavesdropper who has access to all the communication and should not learn any information about some function of the inputs (possibly different from the functions to be computed by the users) and show that interaction may be necessary for secure computation.

We study private two-terminal hypothesis testing with simple hypotheses where the privacy goal is to ensure that participating in the testing protocol reveals little additional information about the other user's observation when a user is told what the correct hypothesis is. We show that, in general, meaningful correctness and privacy cannot be achieved if the users do not have access to correlated (but, not common) randomness. We characterize the optimal correctness and privacy error exponents when the users have access to non-trivial correlated randomness (those that permit secure multiparty computation).

We consider a strong coordination setup, where two nodes must produce a joint distribution on their actions that is close in total variation distance to independent and identical copies from a given joint probability distribution. The first node, which we call the encoder, observes an independent and identically distributed (i.i.d.) source. In order to coordinate the source with the reconstructed outputs of the second node (the decoder), they have access to a noiseless rate limited link and common randomness. The decoder also has additional side information. The reconstruction at the decoder is to be coordinated with the source process as well as the available side information. We allow the side information to be driven by another encoding process, which does not share common randomness with the two nodes. General inner and outer bounds on the rate-coordination region for this set up are derived, and our bounds match for an important special case. We also show an example with no encoding of the side information, where coordination of the source and reconstruction can be obtained as a union of three way coordination regions involving the side information as well.

Feedback is known to enlarge the capacity region of a Gaussian Broadcast Channel (GBC) with independent noise realizations at the receivers, and an average power constraint at the transmitter. The capacity enlargement may occur even when there is noisy feedback from only one of the two receivers. However, recent results show the existence of a feedback noise threshold, beyond which one-sided feedback from only the stronger receiver is futile in enlarging the capacity region. The current paper presents a tight characterization of the feedback noise threshold, which separates the regimes where feedback from only the stronger receiver enlarges the capacity or leaves it unchanged. The scheme used to prove this result also leads to some interesting observations on noisy feedback from only the weak receiver.

We consider interactive computation of randomized functions between two users with the following privacy requirement: the interaction should not reveal to either user any extra information about the other user's input and output other than what can be inferred from the user's own input and output. We also consider the case where privacy is required against only one of the users. For both cases, we give single-letter expressions for feasibility and optimal rates of communication. Then we discuss the role of common randomness and interaction in both privacy settings. We also study perfectly secure non-interactive computation when only one of the users computes a randomized function based on a single transmission from the other user. We characterize randomized functions which can be perfectly securely computed in this model and obtain tight bounds on the optimal message lengths in all the privacy settings.

In an action dependent state channel (ADSC), there are two encoders, viz. an action encoder and a channel encoder. We consider a Gaussian ADSC (GADSC) setup where the state process is generated by passing the action symbols through an AWGN channel. The receiver observes the superposition of the channel encoder symbols, state process, and independent AWGN.In our model, in addition to decoding the messages, the receiver is required to produce an estimate of the state process within some prescribed mean-squared error distortion. While joint state estimation and communication for a discrete memoryless ADSC with strictly causal state information has been solved, its non-causal counterpart remains open. We resolve this for the GADSC under average power constraints at the two encoders. Furthermore, we allow an additional independent message stream at the channel encoder and characterize the optimal distortion-rate trade-off region. Interestingly, our results also characterize the capacity region of a state-dependent Gaussian multiple access channel (MAC) with degraded message sets and state estimation constraints.

We study authenticated communication over two-user multiple access channels (MAC) where one of the users is possibly adversarial. When both users behave non-adversarially, we want their messages to be decoded reliably. However, we also want to ensure that an adversarial user cannot cause an undetected error on the other (honest) user's message. We show that the following three-phase scheme is rate-optimal: a standard MAC code is first used to achieve unauthenticated communication; this is followed by two authentication phases where each user authenticates their message treating the other user as a possible adversary. We show that the authentication phases can be very short since this form of authentication itself, when possible, can be achieved for message sets whose size grow doubly exponentially in blocklength. This leads to our result that the authenticated communication capacity region of a discrete memoryless MAC is either zero or the (unauthenticated) MAC capacity region itself. This also, arguably, explains the similar nature of authenticated communication capacity of a discrete memoryless point-to-point adversarial channel recently found by Kosut and Kliewer (ITW, 2018). We also obtain analogous results for additive Gaussian noise channels.

We study a distributed sampling problem where a set of processors want to output correlated sequences of random variables with the help of a coordinator which has access to several independent sources of randomness. Each processor has access to a subset of these sources. When these subsets are pairwise disjoint (individually shared randomness model), we characterize the rate of communication required from the coordinator to the processors over a multicast link. We also give an upper bound on the communication rate for the randomness-on-the-forehead model where each processor observes all but one source of randomness. For the general model, we completely characterize the trade-off region between communication and shared randomness rates when all the processors wish to output the same random sequence.

Communication over a three-user multiple access channel (MAC) is studied when any one of the users may behave adversarially. The capacity region is characterized for randomized codes (where each user shares an independent secret key with the receiver). The capacity region for deterministic codes is also studied. Necessary conditions including a new non-symmetrizability condition is obtained for this capacity region to be non-trivial. It is shown that when none of the users are symmetrizable, the randomized coding capacity region is also achievable with deterministic codes. This is analogous to the result of Ahlswede and Cai (1991) for arbitrarily varying MAC.

A hybrid communication network with a common analog source signal and independent digital data streams at the transmitters of a multiple access network is considered. The receiver has to estimate the analog signal samples with a given fidelity, and decode the digital streams with a low error probability. The main goal of this paper is to characterize the optimal tradeoff between the mean-squared error distortion in source estimation and the data rates available to each user. To this end, we consider a Gaussian multiple access channel (GMAC) setup with additive state, where the state is nothing but a scaled version of the source process itself. The state process is assumed to be non-causally available to all the transmitting nodes. The problem now becomes that of the joint state estimation and message communication in a GMAC with state. We provide a complete characterization of the optimal distortion-rate tradeoff for an N - sender GMAC. Our results show that, similar to the single-user results, it is optimal to amplify the state using uncoded transmissions, whereas the digital streams are superposed using appropriate Gaussian codebooks in conjunction with dirty paper coding (DPC). Since the variance of the additive state is controlled by a scaling factor in our model, we also recover the results for communicating a common source and independent messages over a GMAC without state as a special case.

We consider interactive computation of randomized functions between two users with the following privacy requirement: the interactive communication should not reveal to either user any extra information about the other user's input and output other than what can be inferred from the user's own input and output. We also consider the case where privacy is required against only one of the users. For both cases, we give single-letter expressions for feasibility and optimal rates of communication. Then we discuss the role of common randomness and interaction in both privacy settings.

Two processors output correlated sequences using the help of a coordinator with whom they individually share independent randomness. For the case of unlimited shared randomness, we characterize the rate of communication required from the coordinator to the processors over a broadcast link. We also give an achievable trade-off between the communication and shared randomness rates.

We study the problem of index coding under the privacy requirement that receivers do not learn anything more than the messages they already have as side information and the message they want from the server. To achieve this private index coding, we consider the use of secret keys that are shared among various subsets of users and the server. We characterize key access structures that allow private index coding. For up to three receivers, we characterize the rate region of transmission and key rates and show that scalar coding is optimal; we also show that scalar linear codes are sub-optimal for four receivers. Furthermore, when no keys are available, we consider a weaker notion of privacy analogous to weak security. Finally, for a different setting in which the server is allowed to send messages exclusively to a subset of users, we study the number of transmissions required to achieve error-free decoding and privacy.

A common reconstruction (CR) problem, where the common additive state to a Gaussian broadcast channel (BC) is to be estimated at two receivers, is considered. The state process is assumed to be IID Gaussian, and known non-causally at the encoder. Each receiver has to make separate estimates of the state-process, with the CR constraints that the individual receiver's estimate should match a corresponding estimate at the transmitter. We study the trade-offs between the two distortions and a private rate to the strong receiver. We compute inner and outer bounds which are numerically shown to characterize the optimal performance in several regimes of interest. Interestingly, it is observed that allowing the weak user to decode part of the private message to the stronger user helps the distortion trade-offs, even though the objective concerns only a private rate to the strong user. Also, as a special case of our BC results, we show that Gaussian auxiliaries are optimal for a single user Gaussian CR problem.

We study a lossy source coding problem for an arbitrarily varying remote source (AVRS) which was proposed in a prior work. An AVRS transmits symbols, each generated in an independent and identically distributed manner, which are sought to be estimated at the decoder. These symbols are remotely generated, and the encoder and decoder observe noise corrupted versions received through a two-output noisy channel. This channel is an arbitrarily varying channel controlled by a jamming adversary. We assume that the adversary knows the coding scheme as well as the source data non-causally, and hence, can employ malicious jamming strategies correlated to them. Our interest lies in studying the rate distortion function for codes with a stochastic encoder, i.e, when the encoder can privately randomize while the decoder is deterministic. We provide upper and lower bounds on this rate distortion function.

Recent work by Maddah-Ali and Niesen (2014) introduced coded caching which demonstrated the benefits of joint design of storage and transmission policies in content delivery networks. They studied a setup where a server communicates with a set of users, each equipped with a local cache, over a shared error-free link and proposed an order-optimal caching and delivery scheme. In this paper, we introduce the problem of private coded caching where we impose the additional constraint that no user learns any information about the contents of the files it did not request from what is stored in its cache and the server transmissions. We propose a feasible scheme for this setting and demonstrate its order-optimality by deriving information-theoretic lower bounds.

We study a lossy source coding problem for a memoryless remote source. The source data is broadcast over an arbitrarily varying channel (AVC) controlled by an adversary. One output of the AVC is received as input at the encoder, and another output is received as side information at the decoder. The adversary is assumed to know the source data non-causally, and can employ randomized jamming strategies arbitrarily correlated to the source data. The decoder reconstructs the source data from the encoded message and the side information. We prove upper and lower bounds on the adversarial rate distortion function for the source under randomized coding. Furthermore, we present some interesting special cases of our general setup where the above bounds coincide, and thus, provide their complete rate distortion function characterization.

We consider secure computation of randomized functions by two users, where both the users (Alice and Bob) have inputs, Alice sends a message to Bob over a rate-limited, noise-free link, and then Bob produces the output. We study this problem when privacy is required only against Bob, i.e., from the message, Bob must not learn any information about Alice's input other than what can be inferred by his own input and output. We give a single-letter expression for the optimal rate. We also explicitly characterize securely computable randomized functions when input has full support, which leads to a much simpler expression for the optimal rate. Recently, Data (ISIT 2016) studied the other two cases (first, when privacy is required against both the users; and second, when privacy is required only against Alice) and obtained single-letter expressions for optimal rates in both the scenarios. Yassaee, Gohari, and Aref (IEEE Transactions on Information Theory 2015) studied the case when there is no privacy requirement and obtained a single-letter expression for the optimal rate, when Alice and Bob interact for arbitrary but finite number of rounds, and both of them may produce potentially different outputs.

We study communication systems over the state-dependent channels in the presence of a malicious state-aware jamming adversary. The channel has a memoryless state with an underlying distribution. The adversary introduces a jamming signal into the channel. The message and the entire state sequence are known non-causally to both the encoder and the adversary. This state-aware adversary may choose an arbitrary jamming vector depending on the message and the state vector. Taking an arbitrarily varying channel (AVC) approach, we consider two setups, namely, the discrete memoryless Gel'fand-Pinsker AVC and the additive white Gaussian dirty paper (DP) AVC. We determine the randomized coding capacity of both the AVCs under a maximum probability of error criterion. Similar to other randomized coding setups, we show that the capacity is the same even under the average probability of error criterion. Though the adversary can choose an arbitrary vector jamming strategy, we prove that the adversary cannot affect the rate any worse than when it employs a memoryless strategy, which depends only on the instantaneous state. Thus, the AVC capacity characterization is given in terms of the capacity of the worst memoryless channels with state, induced by the adversary employing such memoryless jamming strategies. For the DP-AVC, it is further shown that among memoryless jamming strategies, none impact the communication more than a memoryless Gaussian jamming strategy which completely disregards the knowledge of the state. Thus, the capacity of the DP-AVC equals that of a standard additive white Gaussian noise (AWGN) channel with two independent sources of AWGN, i.e., the channel noise and the jamming noise.

In this paper, we study the problem of obtaining 1-of-2 string oblivious transfer (OT) between users Alice and Bob, in the presence of a passive eavesdropper Eve. The resource enabling OT in our setup is a noisy broadcast channel from Alice to Bob and Eve. Apart from the OT requirements between the users, Eve is not allowed to learn anything about the users' inputs. When Alice and Bob are honest-but-curious and the noisy broadcast channel is made up of two independent binary erasure channels (connecting Alice-Bob and Alice-Eve), we derive the 1-of-2 string OT capacity for both 2-privacy (when Eve can collude with either Alice or Bob) and 1-privacy (when no such collusion is allowed). We generalize these capacity results to 1-of-N string OT and study other variants of this problem. When Alice and/or Bob are malicious, we present a different scheme based on interactive hashing. This scheme is shown to be optimal for certain parameter regimes. We present a new formulation of multiple, simultaneous OTs between Alice-Bob and Alice-Cathy. For this new setup, we present schemes and outer bounds that match in all but one regime of parameters. Finally, we consider the setup where the broadcast channel is made up of a cascade of two independent binary erasure channels (connecting Alice-Bob and Bob-Eve) and 1-of-2 string OT is desired between Alice and Bob with 1-privacy. For this setup, we derive an upper and lower bound on the 1-of-2 string OT capacity which match in one of two possible parameter regimes.

In this work we introduce a new information-theoretic complexity measure for 2-party functions, called Rényi information complexity. It is a lower-bound on communication complexity, and has the two leading lower-bounds on communication complexity as its natural relaxations: (external) information complexity and logarithm of partition complexity. These two lower-bounds had so far appeared conceptually quite different from each other, but we show that they are both obtained from Rényi information complexity using two different, but natural relaxations: 1. The relaxation of Rényi information complexity that yields information complexity is to change the order of Rényi mutual information used in its definition from infinity to 1. 2. The relaxation that connects Rényi information complexity with partition complexity is to replace protocol transcripts used in the definition of Rényi information complexity with what we term "pseudotranscripts", which omits the interactive nature of a protocol, but only requires that the probability of any transcript given inputs x and y to the two parties, factorizes into two terms which depend on x and y separately. While this relaxation yields an apparently different definition than (log of) partition function, we show that the two are in fact identical. This gives us a surprising characterization of the partition bound in terms of an information-theoretic quantity. We also show that if both the above relaxations are simultaneously applied to Rényi information complexity, we obtain a complexity measure that is lower-bounded by the (log of) relaxed partition complexity, a complexity measure introduced by Kerenidis et al. (FOCS 2012). We obtain a sharper connection between (external) information complexity and relaxed partition complexity than Kerenidis et al., using an arguably more direct proof. Further understanding Rényi information complexity (of various orders) might have consequences for important direct-sum problems in communication complexity, as it lies between communication complexity and information complexity.

In this paper, we introduce the notion of plausible deniability in an information theoretic framework. We consider a scenario where an entity that eavesdrops through a broadcast channel summons one of the parties in a communication protocol to reveal their message (or signal vector). It is desirable that the summoned party has enough freedom to produce a fake output that is likely plausible given the eavesdropper's observation. We examine three variants of this problem-message deniability, transmitter deniability, and receiver deniability. In the first setting, the message sender is summoned to produce the sent message. Similarly, in the second and third settings, the transmitter and the receiver are required to produce the transmitted codeword and the received vector, respectively. For each of these settings, we examine the maximum communication rate that allows a given minimum rate of plausible fake outputs. First, for the message deniability problem, we fully characterize the capacity region for general broadcast channels. Next, for the transmitter deniability problem, we give an achievable region for general broadcast channels by fully characterizing the set of rate pairs' achievable using deterministic coding schemes. Finally, for the receiver deniability problem, we give an achievable rate region for physically degraded broadcast channels.

Recent work by Maddah-Ali and Niesen introduced coded caching which demonstrated the benefits of joint design of storage and transmission policies in content delivery networks. They studied a setup where a server communicates with a set of users, each equipped with a local cache, over a shared error-free link and proposed an order-optimal caching and delivery scheme. In this paper, we introduce the problem of secretive coded caching where we impose the additional constraint that a user should not be able to learn anything, from either the content stored in its cache or the server transmissions, about a file it did not request. We propose a feasible scheme for this setting and demonstrate its order-optimality with respect to information-theoretic lower bounds.

The problem of three-party secure computation, where a function of private data of two parties is to be computed by a third party without revealing information beyond respective inputs or outputs is considered. New and better lower bounds on the amount of communication required between the parties to guarantee zero probability of error in the computation and achieve information-theoretic security are derived. Protocols are presented and proved to be optimal in some cases by showing that they achieve the improved lower bounds.

The problem of multicasting two nested messages is studied over a class of networks known as combination networks. A source multicasts two messages, a common and a private message, to several receivers. A subset of the receivers (called the public receivers) only demand the common message, and the rest of the receivers (called the private receivers) demand both the common and the private message. Three encoding schemes are discussed that employ linear superposition coding, and their optimality is proved in special cases. The standard linear superposition scheme is shown to be optimal for networks with two public receivers and any number of private receivers. When the number of public receivers increases, this scheme stops being optimal. Two improvements are discussed: one using pre-encoding at the source, and one using a block Markov encoding scheme. The rate-regions that are achieved by the two schemes are characterized in terms of feasibility problems. Both inner bounds are shown to be the capacity region for networks with three (or fewer) public and any number of private receivers. Although the inner bounds are not comparable in general, it is shown through an example that the region achieved by the block Markov encoding scheme may strictly include the region achieved by the pre-encoding/linear superposition scheme. Optimality results are founded on the general framework of Balister and Bollobás (2007) for sub-modularity of the entropy function. An equivalent graphical representation is introduced and a lemma is proved that might be of independent interest. Motivated by the connections between combination networks and broadcast channels, a new block Markov encoding scheme is proposed for broadcast channels with two nested messages. The rate-region that is obtained includes the previously known rate-regions. It remains open whether this inclusion is strict.

This paper presents exact capacity characterizations for the case, when a principal, Alice, wants to securely send a message to another principal, Bob, over three network configurations: the parallel edges network, the V-network, and the triangle network. We assume that: 1) a passive eavesdropper, Eve, overhears any one edge in the network; 2) each edge corresponds to an independent broadcast packet erasure channel with arbitrary erasure probabilities; and 3) all legitimate nodes can publicly but causally acknowledge whether they received each packet or not. We develop optimal achievability schemes that are expressed as linear programs (LPs) and share a two-phase structure, where at the first phase, we create secret keys, and at the second phase, we use them to encrypt the transmitted message. Our outer bounds are also expressed through LP formulations. We prove that our schemes are optimal by showing that the optimal solution of the outer bound LP and the optimal solution of the achievability scheme LP coincide.

In secure multiparty computation (MPC), mutually distrusting users collaborate to compute a function of their private data without revealing any additional information about their data to the other users. While it is known that information theoretically secure MPC is possible among n users having access to private randomness and are pairwise connected by secure, noiseless, and bidirectional links against the collusion of less than n/2 users (in the honest-but-curious model; the threshold is n/3 in the malicious model), relatively little is known about the communication and randomness complexity of secure computation, i.e., the amount of communication and randomness required to compute securely. In this paper, we employ information theoretic techniques to obtain lower bounds on communication and randomness complexity of secure MPC. We restrict ourselves to a concrete interactive setting involving three users under which all functions are securely computable against corruption of individual users in the honest-but-curious model. We derive lower bounds for both the perfect security case (i.e., zero-error and no leakage of information) and asymptotic security (where the probability of error and information leakage vanish as block-length goes to ∞). Our techniques include the use of a data processing inequality for residual information (i.e., the gap between mutual information and Gács-Körner common information), a new information inequality for three-user protocols, and the idea of distribution switching by which lower bounds computed under certain worst case scenarios can be shown to apply for the general case. Our lower bounds are shown to be tight for various functions of interest. In particular, we show concrete functions which have communication-ideal protocols, i.e., which achieve the minimum communication simultaneously on all links in the network. Also, we obtain the first explicit example of a function that incurs a higher communication cost than the input length, in the secure computation model of Feige et al. (26th Annual ACM Symposium on Theory of Computing, 1994), who had shown that such functions exist. We also show that our communication bounds imply tight lower bounds on the amount of randomness required by MPC protocols for many interesting functions.

In information theoretically secure multiparty computation, several mutually distrusting users want to jointly compute a function of their private data such that users do not learn any additional information about other users' data other than what they can infer from their own data and the function value they compute. In this work we consider asymptotically secure computation - where vanishing probability of error and vanishing information leakage are allowed as block lengths become large - in a three user setting, where two users have inputs and third user securely computes the output of a function on these two inputs. We provide generic lower bounds on the amount of communication required among users and the total amount of private randomness needed to compute any function in this three-user model. We also consider some examples where our bounds are tight. Our lower bounds are derived for the honest-but-curious security model and hence also apply for the malicious model.

We study oblivious transfer (OT) between Alice and Bob in the presence of an eavesdropper Eve over a degraded wiretapped binary erasure channel from Alice to Bob and Eve. In addition to the privacy goals of oblivious transfer between Alice and Bob, we require privacy of Alice and Bob's private data from Eve. In previous work we derived the OT capacity (in the honest-but-curious model) of the wiretapped binary independent erasure channel where the erasure processes of Bob and Eve are independent. Here we derive a lower bound on the OT capacity in the same secrecy model when the wiretapped binary erasure channel is degraded in favour of Bob.

We study the following private data transfer problem: Alice has a database of files. Bob and Cathy want to access a file each from this database (which may or may not be the same file), but each of them wants to ensure that their choices of file do not get revealed even if Alice colludes with the other user. Alice, on the other hand, wants to make sure that each of Bob and Cathy does not learn any more information from the database than the files they demand (the identities of which will be unknown to her). Moreover, they should not learn any information about the other files even if they collude. It turns out that it is impossible to accomplish this if Alice, Bob, and Cathy have access only to private randomness and noiseless communication links. We consider this problem when a binary erasure broadcast channel with independent erasures is available from Alice to Bob and Cathy in addition to a noiseless public discussion channel. We study the file-length-per-broadcast-channel-use rate in the honest-but-curious model. We focus on the case when the database consists of two files, and obtain the optimal rate. We then extend to the case of larger databases, and give upper and lower bounds on the optimal rate.

It is well known that, in general, feedback may enlarge the capacity region of Gaussian broadcast channels. This has been demonstrated even when the feedback is noisy (or partial-but-perfect) and only from one of the receivers. The only case known where feedback has been shown not to enlarge the capacity region is when the channel is physically degraded. In this paper, we show that for a class of two-user Gaussian broadcast channels (not necessarily physically degraded), passively feeding back the stronger user's signal over a link corrupted by Gaussian noise does not enlarge the capacity region if the variance of feedback noise is above a certain threshold.

One of the most widely-known techniques for securing a message from eavesdropping, is the famous one-time pad. Although the one-time pad offers unconditional security, it has limited applicability today, because it requires that to communicate, two parties already share a key that is not known by the eavesdropper and has size equal to the message. In this review paper we present a line of work that explores how we can efficiently share keys securely from an eavesdropper, and thus communicate using a one-time pad like approach. The basic idea is to exploit new opportunities that wireless networks offer, such as the fact that we have multiple paths, the fact that we have packet losses, and the availability of ACK/NACK feedback.

Secure network coding assumes that the underlying network channels are error-free; thus, if our channels introduce errors, we need to first apply a channel code to correct them, and then build security on top of the resulting error-free network. In this paper, we develop achievability protocols and outer bounds for the secure network coding setting, where the edges are subject to packet erasures, and public feedback of the channel state is available to both Eve and the legitimate network nodes. We show that by leveraging erasures and feedback, we can achieve secrecy rates that are in some cases multiple times higher than the alternative of separate channel-error-correction followed by secure network coding; moreover, we develop outer bounds and prove optimality of our proposed schemes in some special cases.

We consider a 1-to-K communication scenario, where a source transmits private messages to K receivers through a broadcast erasure channel, and the receivers feedback strictly, causally, and publicly their channel states after each transmission. We explore the achievable rate region when we require that the message to each receiver remains secret-in the information theoretical sense-from all the other receivers. We characterize the capacity of secure communication in all the cases where the capacity of the 1-to-K communication scenario without the requirement of security is known. As a special case, we characterize the secret-message capacity of a single receiver point-to-point erasure channel with public state-feedback in the presence of a passive eavesdropper. We find that in all the cases where we have an exact characterization, we can achieve the capacity using linear complexity two-phase schemes: in the first phase, we create appropriate secret keys, and in the second phase, we use them to encrypt each message. We find that the amount of key we need is smaller than the size of the message, and equal to the amount of encrypted message the potential eavesdroppers jointly collect. Moreover, we prove that a dishonest receiver that provides deceptive feedback cannot diminish the rate experienced by the honest receivers. We also develop a converse proof which reflects the two-phase structure of our achievability scheme. As a side result, our technique leads to a new outer bound proof for the nonsecure communication problem.

In this paper, the problem of writing on a dirty paper in the presence of jamming is examined. We consider an AWGN channel with an additive white Gaussian state and an additive adversarial jammer. The state is assumed to be known non-causally to the encoder and the jammer but not to the decoder. The capacity of the channel in the presence of a jammer is determined. A surprising result that this capacity is equal to the capacity of a relaxed version of the problem, where the state is also known non-causally to the decoder, is proved.

We study correlated jamming in joint source-channel communication systems. An i.i.d. source is to be communicated over a memoryless channel in the presence of a correlated jammer with non-causal knowledge of user transmission. This user-jammer interaction is modeled as a zero sum game. A set of conditions on the source and the channel is provided for the existence of a Nash equilibrium for this game, where the user strategy is uncoded transmission and the jammer strategy is i.i.d jamming. This generalizes a well-known example of uncoded communication of Gaussian sources over Gaussian channels with additive jamming. Another example, of a Binary Symmetric source over a Binary Symmetric channel with jamming, is provided as a validation of this result.

We characterize the secret message capacity of the triangle network, that consists of a source, a relay and a destination connected through orthogonal erasure channels. A passive eavesdropper, Eve, wiretaps any one of the three channels. The source and the relay can each generate unlimited private randomness; the relay and the destination can publicly provide strictly causal channel state information. Our achievable scheme is expressed through a linear program (LP) with 11 inequalities that captures a minimal set of secret key generation methods and the use of them for message encryption. Our outer bound is expressed also through a linear program, in this case with 41 constraints, constructed from general information inequalities. We prove that the optimal value of the outer bound LP is no larger than that of the scheme LP, which implies that the solution of the achievable scheme LP is the capacity. We find that equipping the relay with private randomness increases the secrecy rate by more than 40% in some cases and that cut-set bounds, directly applied in the network, are not always tight. Because the derivation of the inner and outer bound are both lengthy, we describe in this paper the achievability scheme, outline the outer bound, and provide the full derivations online [1]. We also make available Matlab functions that take as input the erasure probabilities and evaluate the inner and outer bounds.

We consider oblivious transfer between Alice and Bob in the presence of an eavesdropper Eve when there is a broadcast channel from Alice to Bob and Eve. In addition to the secrecy constraints of Alice and Bob, Eve should not learn the private data of Alice and Bob. When the broadcast channel consists of two independent binary erasure channels, we derive the oblivious transfer capacity for both 2-privacy (where the eavesdropper may collude with either party) and 1-privacy (where there are no collusions).

In secure multiparty computation, mutually distrusting users in a network want to collaborate to compute functions of data which is distributed among the users. The users should not learn any additional information about the data of others than what they may infer from their own data and the functions they are computing. Previous works have mostly considered the worst case context (i.e., without assuming any distribution for the data); Lee and Abbe (2014) is a notable exception. Here, we study the average case (i.e., we work with a distribution on the data) where correctness and privacy is only desired asymptotically. For concreteness and simplicity, we consider a secure version of the function computation problem of Körner and Marton (1979) where two users observe a doubly symmetric binary source with parameter p and the third user wants to compute the XOR. We show that the amount of communication and randomness resources required depends on the level of correctness desired. When zero-error and perfect privacy are required, the results of Data et al. (2014) show that it can be achieved if and only if a total rate of 1 bit is communicated between every pair of users and private randomness at the rate of 1 is used up. In contrast, we show here that, if we only want the probability of error to vanish asymptotically in blocklength, it can be achieved by a lower rate (binary entropy of p) for all the links and for private randomness; this also guarantees perfect privacy. We also show that no smaller rates are possible even if privacy is only required asymptotically.

We study oblivious transfer (OT) using a binary erasure broadcast channel from Alice to Bob and Charlie. Alice wants to establish independent OTs with Bob and Charlie with 2-privacy, i.e., where secrecy needs to be maintained even against pairs of parties in addition to against parties working on their own. We give an achievable rate-region in the honest-but-curious setting and show its optimality for a range of erasure probabilities.

We derive a new upper bound on the string oblivious transfer capacity of discrete memoryless channels (DMCs). The main tool we use is the tension region of a pair of random variables introduced in Prabhakaran and Prabhakaran (2014) where it was used to derive upper bounds on rates of secure sampling in the source model. In this paper, we consider secure computation of string oblivious transfer in the channel model. Our bound is based on a monotonicity property of the tension region in the channel model. We show that our bound strictly improves upon the upper bound of Ahlswede and Csiszár (2013).

In multiterminal communication systems, signals carrying messages meant for different destinations are often observed together at any given destination receiver. Han and Kobayashi proposed a receiving strategy, which performs a joint unique decoding of messages of interest along with a subset of messages, which are not of interest. It is now well-known that this provides an achievable region, which is, in general, larger than if the receiver treats all messages not of interest as noise. Nair and El Gamal and Chong, Motani, Garg, and El Gamal independently proposed a generalization called indirect or nonunique decoding where the receiver uses the codebook structure of the messages to uniquely decode only its messages of interest. Nonunique decoding has since been used in various scenarios. The main result in this paper is to provide an interpretation and a systematic proof technique for why nonunique decoding, in all known cases where it has been employed, can be replaced by a particularly designed joint unique decoding strategy, without any penalty from a rate region viewpoint.

An important subclass of secure multiparty computation is secure sampling: two parties output samples of a pair of jointly distributed random variables such that neither party learns more about the other party's output than what its own output reveals. The parties make use of a setup - correlated random variables with a different distribution - as well as unlimited noiseless communication. An upperbound on the rate of producing samples of a desired distribution from a given setup is presented. The region of tension developed in this paper measures how well the dependence between a pair of random variables can be resolved by a piece of common information. The bounds on rate are a consequence of a monotonicity property; a protocol between two parties can only lower the tension between their views. Connections are drawn between the region of tension and the notion of common information. A generalization of the Gács-Körner common information, called the assisted common information, which takes into account almost common information ignored by Gács-Körner common information is defined. The region of tension is shown to be related to the rate regions of both the assisted common information and the Gray-Wyner systems (and, a fortiori, Wyner's common information).

The performance gain by allowing half-duplex source cooperation is studied for Gaussian interference channels. The source cooperation is in-band, meaning that each source can listen to the other source's transmission, but there is no independent (or orthogonal) channel between the sources. The half-duplex constraint supposes that at each time instant the sources can either transmit or listen, but not do both. Our main result is a characterization of the sum capacity when the cooperation is bidirectional and the channel gains are symmetric. With unidirectional cooperation, we essentially have a cognitive radio channel. By requiring the primary to achieve a rate close to its link capacity, the best possible rate for the secondary is characterized within a constant. Novel inner and outer bounds are derived as part of these characterizations.

The sampling, quantization, and estimation of a bounded dynamic-range bandlimited signal affected by additive independent Gaussian noise is studied in this work. Considering the desirability of cheap, low-precision sensors, the use of single-bit analog to digital convertors (ADCs) is considered. For bandlimited signals, the distortion due to additive independent Gaussian noise can be reduced by oversampling (statistical diversity). The pointwise expected mean-squared error is used as a distortion metric for signal estimate in this work. If N is the oversampling ratio with respect to the Nyquist rate, then we show that a distortion of O(1=N) can be achieved with single-bit ADCs that record the signs of the observed noisy signal. This improves the (best known) distortion result by Masry for quantizing bandlimited signals in noise, using signs of noisy signal samples, from O(1/N2/3). This improvement comes by exploiting the structure of bandlimited signals in the estimation of original signal from noisy quantized bits.

Encoding schemes for broadcasting two nested message sets are studied. We start with a simple class of deterministic broadcast channels for which (variants of) linear superposition coding are optimal in several cases [1], [2]. Such schemes are sub-optimal in general, and we propose a block Markov encoding scheme which achieves (for some deterministic channels) rates not achievable by the previous schemes in [1], [2]. We adapt this block Markov encoding scheme to general broadcast channels, and show that it achieves a rate-region which includes the previously known rate-regions1.

We study the problem of secure message multicasting over graphs in the presence of a passive (node) adversary who tries to eavesdrop in the network. We show that use of feedback, facilitated through the existence of cycles or undirected edges, enables higher rates than possible in directed acyclic graphs of the same mincut. We demonstrate this using code constructions for canonical combination networks (CCNs). We also provide general outer bounds as well as schemes for node adversaries over CCNs.

We study a distributed sampling scenario in which two agents observing components of a correlated source must each generate components of a second correlated source. The agents are aided by an “omniscient” third terminal which observes the two input sources and transmits rate-limited messages to assist the terminals in generating the required correlation in their outputs. We identify two sub-cases of this problem based on how the generated sources must depend on the input sources.

We investigate the problem of secure communication in a simple network with three communicating parties, two distributed sources who communicate over orthogonal channels to one destination node. The cooperation between the sources is restricted to a rate limited common random source they both observe. The communication channels are erasure channels with strictly causal channel state information of the destination available publicly. A passive adversary is present in the system eavesdropping on any one of the channels. We design a linear scheme that ensures secrecy against the eavesdropper. By deriving an outer bound for the problem we prove that the scheme is optimal in certain special cases.

In mutiterminal communication systems, signals carrying messages meant for different destinations are often observed together at any given destination receiver. Han and Kobayashi (1981) proposed a receiving strategy which performs a joint unique decoding of messages of interest along with a subset of messages which are not of interest. It is now well-known that this provides an achievable region which is, in general, larger than if the receiver treats all messages not of interest as noise. Nair and El Gamal (2009) and Chong, Motani, Garg, and El Gamal (2008) independently proposed a generalization called indirect or non-unique decoding where the receiver uses the codebook structure of the messages to only uniquely decode its messages of interest. Indirect (non-unique) decoding has since been used in various scenarios. The main result in this paper is to provide an interpretation and a systematic proof technique for why indirect decoding, in all known cases where it has been employed, can be replaced by a particularly designed joint unique decoding strategy, without any penalty from a rate region viewpoint1.

Consider a source, Alice, broadcasting private messages to multiple receivers through a broadcast erasure channel; users send back to Alice public feedback that she causally uses to decide the coding strategy for her following transmissions. Recently, the multiple unicast capacity region for this problem has been exactly characterized for a number of special cases; namely the 2-user, 3-user, symmetric K-user, and one-sidedly fair K-user [1], [2]. In this paper, we show that for all the cases where such characterizations exist, we can also optimally characterize the “secure” communication rates, where the message that Alice transmits to each user is information theoretically secure from the other users, even if these collude. We show that a simple, two-phase strategy, where appropriate amounts of secret keys are first generated and then consumed, matches a new outer bound we derive.

In this paper, we study delivery of two nested message sets over combination networks with an arbitrary number of receivers, where a subset of receivers (public receivers) demand only the lower priority message and a subset of receivers (private receivers) demand both the lower and the higher priority messages. We give a complete rate region characterization over combination networks with three public and any number of private receivers, where achievability is through linear coding. Our encoding scheme is general and characterizes an achievable region for arbitrary number of public and private receivers.

We investigate secure multi-party sampling problems involving more than two parties. In the public discussion model, we give a simple characterization of the distributions that can be sampled without any setup. In a model which allows private point-to-point communication, we reduce the problem of characterizing distributions that can be securely sampled using pairwise setups to the problem of characterizing distributions that can be sampled without any setups.

Alice and Bob want to share a secret key and to communicate an independent message, both of which they desire to be kept secret from an eavesdropper Eve. This problem of secret communication and secret-key generation when two resources are available-correlated sources at Alice, Bob, and Eve, and a noisy broadcast channel from Alice to Bob and Eve which is independent of the sources is studied. The goal is to characterize the fundamental tradeoff between the rates of the secret message and secret key. An achievable solution and proof of its optimality for the parallel channels and sources case when each subchannel and source component satisfies a degradation order (either in favor of the legitimate receiver or the eavesdropper) is presented. This includes the case of jointly Gaussian sources and an additive Gaussian channel, for which the secrecy region is evaluated.

We presented assisted common information as a generalization of Gacs-Korner (GK) common information at last year's ISIT. The motivation for our formulation was to improve upperbounds on the efficiency of protocols for secure two-party sampling (which is a form of secure multi-party computation). Our upperbound was based on a monotonicity property of a rate region (called the assisted residual information region) associated with the assisted common information formulation. In this note we present further results. We explore the connection of assisted common information with the Gray-Wyner system. We show that the assisted residual information region and the Gray-Wyner region are connected by a simple relationship: the assisted residual information region is the increasing hull of the Gray-Wyner region under an affine map. Several known relationships between GK common information and Gray-Wyner system fall out as consequences of this. Quantities which arise in other source coding contexts acquire new interpretations. In previous work we showed that assisted common information can be used to derive upperbounds on the rate at which a pair of parties can securely sample correlated random variables, given correlated random variables from another distribution. Here we present an example where the bound derived using assisted common information is much better than previously known bounds, and in fact is tight. This example considers correlated random variables defined in terms of standard variants of oblivious transfer, and is interesting on its own as it answers a natural question about these cryptographic primitives.

We characterize the secret message capacity of a wiretapped erasure channel where causal channel state information of the honest nodes is publicly available. In doing so, we establish an intimate connection between message secrecy and secret key generation for the same channel setup. We propose a linear coding scheme that has polynomial encoding/decoding complexity, and prove a converse that shows the optimality of our scheme. Our work also demonstrates the value of causal public feedback, which has previously been shown for the secret key generation problem.

The problem of broadcasting a parallel Gaussian source over an additive white Gaussian noise broadcast channel under the mean-squared error distortion criterion is studied. A hybrid digital-analog coding strategy which combines source coding with side information, channel coding with side information, layered source coding, and superposition broadcast channel coding is presented. When specialized to the open problem of broadcasting a white Gaussian source over an additive white Gaussian noise broadcast channel with bandwidth mismatch, which has been the subject of several previous investigations, this coding scheme strictly improves on the state of the art.

In this paper, the role of cooperation in managing interference-a fundamental feature of the wireless channel-is investigated by studying the two-user Gaussian interference channel where the source nodes can both transmit and receive in full duplex. The sum capacity of this channel is obtained within a gap of a constant number of bits. The coding scheme used builds up on the superposition scheme of Han and Kobayashi for the two-user interference channel without cooperation. New upperbounds on the sum capacity are also derived. The same coding scheme is shown to obtain the sum capacity of the symmetric two-user Gaussian interference channel with noiseless feedback within a constant gap.

Interference is a fundamental feature of the wireless channel. To better understand the role of cooperation in interference management, the two-user Gaussian interference channel where the destination nodes can cooperate by virtue of being able to both transmit and receive is studied. The sum capacity of this channel is characterized up to a constant number of bits. The coding scheme employed builds up on the superposition scheme of Han and Kobayashi for two-user interference channels without cooperation. New upperbounds to the sum capacity are also derived.

Secure multi-party computation is a central problem in modern cryptography. An important sub-class of this are problems of the following form: Alice and Bob desire to produce sample(s) of a pair of jointly distributed random variables. Each party must learn nothing more about the other party's output than what its own output reveals. To aid in this, they have available a set up - correlated random variables whose distribution is different from the desired distribution - as well as unlimited noiseless communication. In this paper we present an upperbound on how efficiently a given set up can be used to produce samples from a desired distribution. The key tool we develop is a generalization of the concept of common information of two dependent random variables [Gács-Körner, 1973]. Our generalization - a three-dimensional region - remedies some of the limitations of the original definition which captured only a limited form of dependence. It also includes as a special case Wyner's common information [Wyner, 1975]. To derive the cryptographic bounds, we rely on a monotonicity property of this region: the region of the “views” of Alice and Bob engaged in any protocol can only monotonically expand and not shrink. Thus, by comparing the regions for the target random variables and the given random variables, we obtain our upperbound.

We consider the problem of securing a distributed storage system with decentralized data, where some of the nodes are compromised by an eavesdropper. The system is formed of n storage nodes among which k nodes (k <; n) have information sources. The system is required to have the “MDS property”, i.e., to allow any user to recover all the sources by contacting any k nodes. To achieve this goal, the source nodes need to disseminate their data to the other nodes in the system while revealing no information to the eavesdropper. We investigate the role of interaction between the sources in reducing the total required bandwidth. When the sources are independent, we show that interaction does not help and that there always exists an optimal non-interactive scheme.

We study the two-user interference channel where the source nodes may transmit and receive in half-duplex while the destinations only receive as usual. Depending on the sources, the channel can be in one of three modes: A) both sources transmit, B) source 1 transmits while source 2 receives, and C) source 2 transmits and source 1 receives. This allows a limited form of cooperation between the sources. In this paper, we focus on the corresponding symmetric linear deterministic channel and derive its sum capacity. We consider a scheme which, by operating in modes B and C, transforms mode A into a virtual two-user interference channel with rate-limited bit pipes between the two source nodes and from each source node to the destination node it causes interference to. For the virtual channel so created, we propose a generalization of the superposition coding scheme of Han-Kobayashi to take advantage of the bit pipes. Finally, we derive matching upperbounds to show that the performance of the composite scheme is indeed optimal for the original channel.

Interference is a central feature of the wireless channel. However, in many cases, the interferer's activity can be bursty and it is overly pessimistic to assume that interference is always present. In this paper, we use a degraded message set formulation of the two-user interference channel to study the statistical gains that can be harnessed from bursty interference. We consider a linear deterministic model of the Gaussian interference channel and characterize the degraded message set capacity region.

In many low-power networks, the power cost for a node to remain ON to listen to transmissions from other nodes or to transmit to other nodes can constitute a significant part of the total power consumption by the radio. Thus, unlike the traditional relay channel model, under a low power constraint, the relay node cannot stay ON and listen to the entire duration of the transmission. We study the slope of the capacity-power function at zero power for relay channels where the power cost of remaining ON is explicitly taken into account. We show that in this low-power limit, information is conveyed primarily through the ON-OFF activity of the source. The relay node should have significantly more power compared to the source node in order to improve the slope at zero power. The rough intuition is that, in order for a relay node to be useful, it needs to stay ON and listen during a significant portion of the time during which the source node may transmit. This fact limits the utility of the relay to those cases where the it has much higher power than the source node it is trying to help.

We consider a two-user interference channel where the source/destination nodes can cooperate with each other by virtue of being able to both transmit and receive. For the full-duplex mode of operation, we characterize the sum capacity of a linear deterministic channel exactly, and that of the Gaussian channel up to a constant number of bits. This reveals a reciprocity between the cases where the sources cooperate and the destinations cooperate. The main contributions are novel strategies and new upper bounds.

Interference is a central feature of wireless communication. In many scenarios, interference is bursty: interfering wireless links come and go. Designing the system assuming interference to be always present is very conservative. In this paper, we take a fundamental information theoretic stand point and address the issue of statistical gain associated with bursty interference in the context of a pair of unicast interfering wireless links. Modeling the problem as a ldquodegraded message setrdquo two user Gaussian interference channel, we approximately characterize the symmetric capacity region. Our results demonstrate the fundamental existence of three regimes: one where treating interference as always there is without loss of optimality, another where one can harness as well as if interference was never there and a third where the performance is in between these two regimes.

The linear deterministic model has been used recently to get a first order understanding of many wireless communication network problems. In many of these cases, it has been pointed out that the capacity regions of the network and its reciprocal (where the communication links are reversed and the roles of the sources and the destinations are swapped) are the same. In this paper, we consider a linear deterministic communication network with multiple unicast information flows. For this model and under the restriction to the class of linear coding, we show that the rate regions for a network and its reciprocal are the same. This can be viewed as a generalization of the linear reversibility of wireline networks, already known in the network coding literature.

We introduce the two-user finite state compound interference channel. The main contributions involve both novel inner and outer bounds. For the Gaussian case, we characterize its capacity region to within one bit. The inner bound is multilevel superposition coding but the decoding of the levels is opportunistic, depending on the channel state. The genie aided outer bound is motivated by the typical error events of the achievable scheme.

The compound wiretap channel provides a general framework for studying secrecy communication under channel uncertainty. Characterizing the secrecy capacity of nondegraded compound wiretap channels is a challenging problem in information theory. This paper considers the class of parallel Gaussian compound wiretap channels with only one possible channel realization for the legitimate receiver and characterizes the secrecy capacity. (Such parallel Gaussian compound wiretap channels are generally nondegraded.) Moreover, it is shown that the proposed coding scheme strictly outperforms the best known single-letter scheme with Gaussian codebooks.

Alice and Bob want to share a secret key and to communicate an independent message, both of which they desire to be kept secret from an eavesdropper Eve. We study this problem of secret communication and secret key generation when two resources are available — correlated sources at Alice, Bob, and Eve, and a noisy broadcast channel from Alice to Bob and Eve. No other resource, in particular, no other channel is available. We are interested in characterizing the fundamental trade-off between the rates of the secret message and secret key. We present an achievable solution based on a separation architecture and prove its optimality under three settings: when Eve’s source and channel are degraded versions of Bob’s, and either Bob’s source or channel is by itself useless in generating a secret key.

We introduce the two user finite state compound Gaussian interference channel and characterize its capacity region to within one bit. The main contributions involve both novel inner and outer bounds. The inner bound is multilevel superposition coding but the decoding of the levels is opportunistic, depending on the channel state. The genie aided outer bound is motivated by the typical error events of the achievable scheme.

The problem of transmitting a Gaussian source with memory to a digital and a linear-analog receiver, over an arbitrarily colored, nondegraded Gaussian broadcast channel is studied. The main result of this work is a complete characterization of the set of achievable distortion pairs at the two receivers given a power constraint at the transmitter. Further, a constructive hybrid uncoded-coded scheme consisting of the cascade of source coding with side information and channel coding with side information systems is shown to achieve the entire power-mean squared error (MSE) distortion region associated with the problem. An interesting operating point in this region is one where the digital receiver obtains the classical point-to-point optimal quality and the analog receiver attains the best possible simultaneously achievable distortion. This problem is motivated by the practical application of the seamless ldquoin-bandrdquo digital upgrade of legacy analog transmission systems.

In this paper we study channels where a side-information sequence is available strictly causally at the transmitter, i.e., the channel input at time k may depend on the side-information sequence up to and including time k - 1. This is in contrast to Shannon's channel coding with causal side-information at the transmitter where the channel input at time k may depend on the side-information sequence up to and including time k. We consider side-information sequences with memory and study the Gaussian and modulo-additive channels.

We investigate the problem of constructing fountain codes for distributed storage in sensor networks. Specifically, we assume that there are n storage nodes with limited memory and k < n data nodes generating the data by sensing the environment. We want a data collector who can appear anywhere in the network, to query any k + epsi storage nodes and be able to retrieve almost all the data packets. We demonstrate how it is possible to solve this problem by using a specific kind of fountain code that requires only linear communication and decoding complexity. Further, for a grid topology, we propose a randomized algorithm that constructs the fountain code over a network using only geographical knowledge and local decisions. A key step in the analysis of our algorithm is a novel result concerning random walks on finite grids with traps

This paper addresses the problem of low-latency robust video delivery over packet networks characterized by a bursty loss process. We propose a joint source-channel coding based video codec which uses distributed source coding (DSC) principles. This codec can efficiently tune to both the source content as well as to the network loss characteristics while respecting stringent latency constraints. Simulation results show that the proposed system is both objectively (in PSNR) and subjectively (visual quality) superior to predictive video coding systems where the encoded bitstream is protected with forward error correction (FEC) codes.

In this paper, we address the case of a single remote sensing unit (encoder), a central processing unit (decoder), and a finite bitrate constraint as an abstraction of a bandwidth-limited channel between the encoder and decoder. The goal is to spend this bit budget in an optimal sense, in terms of classification or estimation performance (minimize the probability of classification error or minimize the probability that the parameter estimation error exceeds a desired tolerance) while ensuring the reconstruction of the raw data with maximum fidelity (in a rate-distortion sense)

In this correspondence, we consider the problem of constructing an erasure code for storage over a network when the data sources are distributed. Specifically, we assume that there are n storage nodes with limited memory and k

Consider a large-scale wireless sensor network of n nodes, where a fraction k out of n generate data packets of global interest. Assuming that the individual nodes have limited storage and computational capabilities, we address the problem of how to enable ubiquitous access to the distributed data packets. Specifically, we assume that each node can store at most one data packet, and study the problem of diffusing the data so that by querying any k nodes, it is possible to retrieve all the k data packets of interest (with high probability). We introduce a class of erasure codes and show how to solve this problem efficiently in a completely distributed and robust way. Specifically we show that we can efficiently diffuse the data by "pre-routing" only O(ln n) packets per data node to randomly selected storage nodes. By using the proposed scheme, the distributed data becomes available "at the fingertips" of a potential data collector located anywhere in the network.

When transmitting a source over an insecure and bandwidth-limited channel, compression (lossy/lossless) precedes encryption. We show that, through the use of side-information coding principles, the order of these operations can be reversed without loss of Wyner-sense perfect secrecy and often with a significant compression ratio. Further, when the source has to be recovered perfectly (with high probability) or is Gaussian (with the mean-squared error fidelity criterion), there is no loss of compression efficiency and the proposed system requires no more randomness in the encryption key compared to systems where compression precedes encryption.

In the so-called CEO problem, a hidden source random process is of interest to a central unit or the "CEO". But this process cannot be observed directly. L sensors or agents observe independently corrupted versions of the source. They encode their observations without cooperating with one another and send through rate constrained noiseless channels to the CEO. The problem was first studied by T. Berger et al. (1996) in the context of discrete memoryless sources. The quadratic Gaussian version of the problem was studied. The best result known to date is the characterization of the sum-rate when all the agents have the same quality of observations. Here we characterize the rate region for any number of agents without assuming that their quality of observations is the same. This is one of the few examples of multiterminal lossy source coding problems in which the rate region can be characterized completely.

This paper presents an information-theoretic study of video codecs that are based on the principle of source coding with side information at the decoder. In contrast to the classical Wyner-Ziv side-information source coding problem (1976), in this work we address the situation where the source and side-information are connected through a state of nature that is unknown to both the encoder and the decoder. We dub this framework as source encoding with side-information under ambiguous state of nature (SEASON). Our objective is to compare the achievable rate-distortion (R/D) performance of conventional video codecs designed under the motion-compensated predictive coding (MCPC) framework and video codecs designed under the SEASON framework. Our analysis shows that under appropriate motion models and for Gaussian displaced frame difference (DFD) statistics, the R/D performance of a classical MCPC-based video codec is matched by that of our proposed SEASON-based video codec, with the hitter being characterized by the novel concept of moving the motion compensation task from the encoder to the decoder.