We study the trade-off between secret message (SM) and secret key (SK) rates, simultaneously achievable over a state-dependent (SD) wiretap channel (WTC) with non-causal channel state information (CSI) at the encoder. This model subsumes other instances of CSI availability as special cases, and calls for efficient utilization of the state sequence for both reliability and security purposes. An inner bound on the semantic-security (SS) SM-SK capacity region is derived based on a superposition coding scheme inspired by a past work of the authors. The region is shown to attain capacity for a certain class of SD-WTCs. SS is established by virtue of two versions of the strong soft-covering lemma. The derived region yields an improvement upon the previously best known SM-SK trade-off result reported by Prabhakaran et al., and, to the best of our knowledge, upon all other existing lower bounds for either SM or SK for this setup, even if the semantic security requirement is relaxed to weak secrecy. It is demonstrated that our region can be strictly larger than those reported in the preceding works.

The Brascamp-Lieb inequality in functional analysis can be viewed as a measure of the “uncorrelatedness” of a joint probability distribution. We define the smooth Brascamp-Lieb (BL) divergence as the infimum of the best constant in the Brascamp-Lieb inequality under a perturbation of the joint probability distribution. An information spectrum upper bound on the smooth BL divergence is proved, using properties of the subgradient of a certain convex functional. In particular, in the i.i.d. setting, such an infimum converges to the best constant in a certain mutual information inequality. We then derive new single-shot converse bounds for the omniscient helper common randomness generation problem and the Gray-Wyner source coding problem in terms of the smooth BL divergence, where the proof relies on the functional formulation of the Brascamp-Lieb inequality. Exact second-order rates are thus obtained in the stationary memoryless and nonvanishing error setting. These offer rare instances of strong converses/second-order converses for continuous sources when the rate region involves auxiliary random variables.

This paper establishes the exact exponents for the soft-covering phenomenon of a memoryless channel under the total variation metric when random (i.i.d. and constant-composition) channel codes are used. The exponents, established herein, are strict improvements in both directions on bounds found in the literature. This complements the recent literature establishing the exact exponents under the relative entropy metric; however, the proof techniques have significant differences, and thus, neither result trivially implies the other. The found exponents imply new and improved bounds for various problems that use soft-covering as their achievability argument, including new lower bounds for the resolvability exponent and the secrecy exponent in the wiretap channel.

The state-dependent (SD) wiretap channel (WTC) with non-causal channel state information (CSI) available at the encoder is considered. An inner bound on the trade-off region between admissible secret key (SK) and secret message (SM) rates is provided. The result is derived under the stringent semantic-security metric. Our inner bound recovers the best-known achievability results for either SK generation, SM transmission, or simultaneous execution of both. Since some of these past benchmarks were derived under weaker security metrics, our results imply that an upgrade to semantic-security is possible without inflicting any rate loss. It is shown that for certain instances of the considered SD-WTC, the derived region is strictly larger than the previously best-known SK-SM trade-off region reported by Prabhakaran et al., and that a recently reported SK rate for this setup cannot be achieved.

This work establishes the exact exponent for the soft-covering phenomenon of a memoryless channel under the total variation metric. The exponent, established herein, is a strict improvement (in both directions) on bounds found in the literature. This complements the recent literature establishing the exact exponent under the relative entropy metric; however, the proof techniques have significant differences, neither bound trivially implies the other. This result implies new and improved bounds for various problems that use soft-covering as their achievability argument, including new lower bounds for the resolvability exponent and the secrecy exponent in the wiretap channel.

Abstract In this work, we investigate if statistical privacy can enhance the performance of ORAM mechanisms while providing rigorous privacy guarantees. We propose a formal and rigorous framework for developing ORAM protocols with statistical security viz., a differentially private ORAM (DP-ORAM). We present Root ORAM, a family of DP-ORAMs that provide a tunable, multi-dimensional trade-off between the desired bandwidth overhead, local storage and system security. We theoretically analyze Root ORAM to quantify both its security and performance. We experimentally demonstrate the benefits of Root ORAM and find that (1) Root ORAM can reduce local storage overhead by about 2× for a reasonable values of privacy budget, significantly enhancing performance in memory limited platforms such as trusted execution environments, and (2) Root ORAM allows tunable trade-offs between bandwidth, storage, and privacy, reducing bandwidth overheads by up to 2×-10× (at the cost of increased storage/statistical privacy), enabling significant reductions in ORAM access latencies for cloud environments. We also analyze the privacy guarantees of DP-ORAMs through the lens of information theoretic metrics of Shannon entropy and Min-entropy [16]. Finally, Root ORAM is ideally suited for applications which have a similar access pattern, and we showcase its utility via the application of Private Information Retrieval.

We give 12 mathematical puzzles (and their solutions) that were presented at a special session in honor of Sol Golomb at the 2017 ITA meeting in San Diego. Some are “well known,” and the very first one is a famous result due to Golomb.

We study the state-dependent (SD) wiretap channel (WTC) with non-causal channel state information (CSI) at the encoder. This model subsumes all other instances of CSI availability as special cases, and calls for an efficient utilization of the state sequence both for reliability and security purposes. A lower bound on the secrecy-capacity, that improves upon the previously best known result by Chen and Han Vinck, is derived based on a novel superposition coding scheme. The improvement over the Chen and Han Vinck result is strict for some SD-WTCs. Specializing the lower bound to the case where CSI is also available to the decoder reveals that it is at least as good as the achievable formula by Chia and El-Gamal, which is already known to outperform the adaptation of the Chen and Han Vinck code to the encoder and decoder CSI scenario. The results are derived under the strict semantic-security metric that requires negligible information leakage for all message distributions. The proof of achievability relies on a stronger version of the soft-covering lemma for superposition codes.

We consider a Shannon cipher system in which distortion is allowed at the legitimate receiver. The secrecy metric used is the exponent of the probability that the reconstruction of the source sequence by the eavesdropper is within a distortion level. A single-letter characterization is provided when the message rate is large enough. Under the optimal code, the eavesdropper can do no better than either making a reconstruction blindly or guessing the key first and then reconstructing based on the sequence reconstructed by the legitimate receiver.

A broadcast channel (BC) where the decoders cooperate via a one-sided link is considered. One common and two private messages are transmitted and the private message to the cooperative user should be kept secret from the cooperation-aided user. The secrecy level is measured in terms of strong secrecy, i.e., a vanishing information leakage. An inner bound on the capacity region is derived by using a channel-resolvability-based code that double-bins the codebook of the secret message, and by using a likelihood encoder to choose the transmitted codeword. The inner bound is shown to be tight for semideterministic and physically degraded BCs, and the results are compared with those of the corresponding BCs without a secrecy constraint. Black well and Gaussian BC examples illustrate the impact of secrecy on the rate regions. Unlike the case without secrecy, where sharing information about both private messages via the cooperative link is optimal, our protocol conveys parts of the common and non-confidential messages only. This restriction reduces the transmission rates more than the usual rate loss due to secrecy requirements. An example that illustrates this loss is provided.

The conventional channel resolvability refers to the minimum rate needed for an input process to approximate the channel output distribution in total variation distance. In this paper, we study Eγ-resolvability, in which total variation is replaced by the more general Eγdistance. A general one-shot achievability bound for the precision of such an approximation is developed. Let QX|Ube a random transformation, n be an integer, and E ∈ (0, +∞). We show that in the asymptotic setting where γ = exp(nE), a (nonnegative) randomness rate above inf QU:D(QXIIπX)≤E{D(QXIIπX) + I(QU, QX|U) - E} is sufficient to approximate the output distribution πX⊗nusing the channel QX|U⊗n, where QU→ QX|U→ QX, and is also necessary in the case of finite U and X . In particular, a randomness rate of inf QUI(QU, QX|U) - E is always sufficient. We also study the convergence of the approximation error under the high-probability criteria in the case of random codebooks. Moreover, by developing simple bounds relating Eγand other distance measures, we are able to determine the exact linear growth rate of the approximation errors measured in relative entropy and smooth Rényi divergences for a fixed-input randomness rate. The new resolvability result is then used to derive: 1) a one-shot upper bound on the probability of excess distortion in lossy compression, which is exponentially tight in the i.i.d. setting; 2) a one-shot version of the mutual covering lemma; and 3) a lower bound on the size of the eavesdropper list to include the actual message and a lower bound on the eavesdropper false-alarm probability in the wiretap channel problem, which is (asymptotically) ensemble-tight.

A basic two-terminal secret key generation model is considered, where the interactive communication rate between the terminals may be limited, and in particular may not be enough to achieve the maximum key rate. We first prove a multi-letter characterization of the key-communication rate region (where the number of auxiliary random variables depends on the number of rounds of the communication), and then provide an equivalent but simpler characterization in terms of concave envelopes in the case of unlimited number of rounds. Two extreme cases are given special attention. First, in the regime of very low communication rates, the key bits per interaction bit (KBIB) is expressed with a new “symmetric strong data processing constant”, which has a concave envelope characterization analogous to that of the conventional strong data processing constant. The symmetric strong data processing constant can be upper bounded by the supremum of the maximal correlation coefficient over a set of distributions, which allows us to determine the KBIB for binary symmetric sources, and conclude, in particular, that the interactive scheme is not more efficient than the one-way scheme at least in the low communication-rate regime. Second, a new characterization of the minimum interaction rate needed for achieving the maximum key rate (MIMK) is given, and we resolve a conjecture by Tyagi regarding the MIMK for (possibly nonsymmetric) binary sources. We also propose a new conjecture for binary symmetric sources that the interactive scheme is not more efficient than the one-way scheme at any communication rate.

Differential privacy is a precise mathematical constraint meant to ensure privacy of individual pieces of information in a database even while queries are being answered about the aggregate. Intuitively, one must come to terms with what differential privacy does and does not guarantee. For example, the definition prevents a strong adversary who knows all but one entry in the database from further inferring about the last one. This strong adversary assumption can be overlooked, resulting in misinterpretation of the privacy guarantee of differential privacy. Herein we give an equivalent definition of privacy using mutual information that makes plain some of the subtleties of differential privacy. The mutual-information differential privacy is in fact sandwiched between ε-differential privacy and (ε,δ)-differential privacy in terms of its strength. In contrast to previous works using unconditional mutual information, differential privacy is fundamentally related to conditional mutual information, accompanied by a maximization over the database distribution. The conceptual advantage of using mutual information, aside from yielding a simpler and more intuitive definition of differential privacy, is that its properties are well understood. Several properties of differential privacy are easily verified for the mutual information alternative, such as composition theorems.

Wyner's soft-covering lemma is the central analysis step for achievability proofs of information theoretic security, resolvability, and channel synthesis. It can also be used for simple achievability proofs in lossy source coding. This work sharpens the claim of soft-covering by moving away from an expected value analysis. Instead, a random codebook is shown to achieve the soft-covering phenomenon with high probability. The probability of failure is super-exponentially small in the block-length, enabling many applications through the union bound. This work gives bounds for both the exponential decay rate of total variation and the second-order codebook rate for soft covering.

The secrecy capacity of the type II wiretap channel (WTC II) with a noisy main channel is currently an open problem. Herein its secrecy-capacity is derived and shown to be equal to its semantic-security (SS) capacity. In this setting, the legitimate users communicate via a discrete-memoryless (DM) channel in the presence of an eavesdropper that has perfect access to a subset of its choosing of the transmitted symbols, constrained to a fixed fraction of the blocklength. The secrecy criterion is achieved simultaneously for all possible eavesdropper subset choices. On top of that, SS requires negligible mutual information between the message and the eavesdropper's observations even when maximized over all message distributions. A key tool for the achievability proof is a novel and stronger version of Wyner's soft covering lemma. Specifically, the lemma shows that a random codebook achieves the soft-covering phenomenon with high probability. The probability of failure is doubly-exponentially small in the blocklength. Since the combined number of messages and subsets grows only exponentially with the blocklength, SS for the WTC II is established by using the union bound and invoking the stronger soft-covering lemma. The direct proof shows that rates up to the weak-secrecy capacity of the classic WTC with a DM erasure channel (EC) to the eavesdropper are achievable. The converse follows by establishing the capacity of this DM wiretap EC as an upper bound for the WTC II.

We study the infimum of the best constant in a functional inequality, the Brascamp-Lieb-like inequality, over auxiliary measures within a neighborhood of a product distribution. In the finite alphabet and the Gaussian cases, such an infimum converges to the best constant in a mutual information inequality. Implications for strong converse properties of two common randomness (CR) generation problems are discussed. In particular, we prove the strong converse property of the rate region for the omniscient helper CR generation problem in the discrete and the Gaussian cases. The latter case is a rare instance of a strong converse for a continuous source when the rate region involves auxiliary random variables.

We generalize a result by Carlen and Cordero-Erausquin on the equivalence between the Brascamp-Lieb inequality and the subadditivity of relative entropy by allowing for random transformations (a broadcast channel). This leads to a unified perspective on several functional inequalities that have been gaining popularity in the context of proving impossibility results. We demonstrate that the information theoretic dual of the Brascamp-Lieb inequality is a convenient setting for proving properties such as data processing, tensorization, convexity and Gaussian optimality. Consequences of the latter include an extension of the Brascamp-Lieb inequality allowing for Gaussian random transformations, the determination of the multivariate Wyner common information for Gaussian sources, and a multivariate version of Nelson's hypercontractivity theorem. Finally we present an information theoretic characterization of a reverse Brascamp-Lieb inequality involving a random transformation (a multiple access channel).

The basic two-terminal key generation model is considered, where the communication between the terminals is limited. We introduce a preorder relation on the set of joint distributions called XY-absolute continuity, and we reduce the multi-letter characterization of the key-communication tradeoff to the evaluation of the XY-concave envelope of a functional. For small communication rates, the key bits per interaction bit is expressed with a “symmetrical strong data processing constant”. Using hypercontractivity and Rényi divergence, we also prove a computationally friendly strong converse bound for the common randomness bits per interaction bit in terms of the supremum of the maximal correlation coefficient over a set of distributions, which is tight for binary symmetric sources. Regarding the other extreme case, a new characterization of the minimum interaction for achieving the maximum key rate (MIMK) is given, and is used to resolve a conjecture by Tyagi [1] about the MIMK for binary sources.

The secrecy capacity of the type II wiretap channel (WTC II) with a noisy main channel is currently an open problem. Herein its secrecy-capacity is derived and shown to be equal to its semantic-security (SS) capacity. In this setting, the legitimate users communicate via a discrete-memoryless (DM) channel in the presence of an eavesdropper that has perfect access to a subset of its choosing of the transmitted symbols, constrained to a fixed fraction of the blocklength. The secrecy criterion is achieved simultaneously for all possible eavesdropper subset choices. The SS criterion demands negligible mutual information between the message and the eavesdropper's observations even when maximized over all message distributions. A key tool for the achievability proof is a novel and stronger version of Wyner's soft covering lemma. Specifically, a random codebook is shown to achieve the soft-covering phenomenon with high probability. The probability of failure is doubly exponentially small in the blocklength. Since the combined number of messages and subsets grows only exponentially with the blocklength, SS for the WTC II is established by using the union bound and invoking the stronger soft-covering lemma. The direct proof shows that rates up to the weak-secrecy capacity of the classic WTC with a DM erasure channel (EC) to the eavesdropper are achievable. The converse follows by establishing the capacity of this DM wiretap EC as an upper bound for the WTC II. From a broader perspective, the stronger soft-covering lemma constitutes a tool for showing the existence of codebooks that satisfy exponentially many constraints, a beneficial ability for many other applications in information theoretic security.

We show that for product sources, rate splitting is optimal for secret key agreement using limited one-way communication between two terminals. This yields an alternative proof of the tensorization property of a strong data processing inequality originally studied by Erkip and Cover and amended recently by Anantharam et al. We derive a water-filling solution of the communication-rate-key-rate tradeoff for a wide class of discrete memoryless vector Gaussian sources which subsumes the case without an eavesdropper. Moreover, we derive an explicit formula for the maximum secret key per bit of communication for all discrete memoryless vector Gaussian sources using a tensorization property and a variation on the enhanced channel technique of Weingarten et al. Finally, a one-shot information spectrum achievability bound for key generation is proved from which we characterize the communication-rate-key-rate tradeoff for stationary Gaussian processes.

A likelihood encoder is studied in the context of lossy source compression. The analysis of the likelihood encoder is based on the soft-covering lemma. It is demonstrated that the use of a likelihood encoder together with the soft-covering lemma yields simple achievability proofs for classical source coding problems. The cases of the point-to-point rate-distortion function, the rate-distortion function with side information at the decoder (i.e., the Wyner-Ziv problem), and the multi-terminal source coding inner bound (i.e., the Berger-Tung problem) are examined in this paper. Furthermore, a non-asymptotic analysis is used for the point-to-point case to examine the upper bound on the excess distortion provided by this method. The likelihood encoder is also related to a recent alternative technique using the properties of random binning.

A new model of multi-party secret key agreement is proposed, in which one terminal called the communicator can transmit public messages to other terminals before all terminals agree on a secret key. A single-letter characterization of the achievable region is derived in the stationary memoryless case. The new model generalizes some other (old and new) models of key agreement. In particular, key generation with an omniscient helper is the special case where the communicator knows all sources, for which we derive a zero-rate one-shot converse for the secret key per bit of communication.

We study the amount of randomness needed for an input process to approximate a given output distribution of a channel in the Eγ distance. A general one-shot achievability bound for the precision of such an approximation is developed. In the i.i.d. setting where γ = exp(nE), a (nonnegative) randomness rate above infQU:D(QX||πX)≤E{D(QX||πX) + I(QU, QX|U) - E} is necessary and sufficient to asymptotically approximate the output distribution πX⊗nusing the channel QX|U⊗n, where QU→ QX|U→ QX. The new resolvability result is then used to derive a oneshot upper bound on the error probability in the rate distortion problem; and a lower bound on the size of the eavesdropper list to include the actual message in the wiretap channel problem. Both bounds are asymptotically tight in i.i.d. settings.

By developing one-shot mutual covering lemmas, we derive a one-shot achievability bound for broadcast with a common message which recovers Marton's inner bound (with three auxiliary random variables) in the i.i.d. case. The encoder employed is deterministic. Relationship between the mutual covering lemma and a new type of channel resolvability problem is discussed.

We study secure source-coding with causal disclosure, under the Gaussian distribution. The optimality of Gaussian auxiliary random variables is shown in various scenarios. We explicitly characterize the tradeoff between the rates of communication and secret key. This tradeoff is the result of a mutual information optimization under Markov constraints. As a corollary, we deduce a general formula for Wyner's Common Information in the Gaussian setting.

The secrecy performance of a source-channel model is studied in the context of lossy source compression over a noisy broadcast channel. The source is causally revealed to the eavesdropper during decoding. The fidelity of the transmission to the legitimate receiver and the secrecy performance at the eavesdropper are both measured by a distortion metric. Two achievability schemes using the technique of hybrid coding are analyzed and compared with an operationally separate source-channel coding scheme. A numerical example is provided and the comparison results show that the hybrid coding schemes outperform the operationally separate scheme.

We show that for product sources, rate splitting is optimal for secret key agreement using limited one-way communication at two terminals. This yields an alternative proof of the tensorization property of a strong data processing inequality originally studied by Erkip and Cover and amended recently by Anantharam et al. We derive a `water-filling' solution of the communication rate-key rate tradeoff for two arbitrarily correlated vector Gaussian sources, for the case with an eavesdropper, and for stationary Gaussian processes.

We investigate the problem of secure source coding with a two-sided helper in a game-theoretic framework. Alice (A) and Helen (H) view iid correlated information sequences Xnand Ynrespectively. Alice communicates to Bob (B) at rate R, while H broadcasts a message to both A and B at rate RH. Additionally, A and B share secret key K at rate R0that is independent of (Xn, Yn). An active adversary, Eve (E) sees all communication links while having access to a (possibly degraded) version of the past information. We characterize the rate-payoff region for this problem. We also solve the problem when the link from A to B is private. Our work recovers previous results of Schieler-Cuff and Kittichokechai et al.

We introduce a new measure of information-theoretic secrecy based on rate-distortion theory and study it in the context of the Shannon cipher system. Whereas rate-distortion theory is traditionally concerned with a single reconstruction sequence, in this paper, we suppose that an eavesdropper produces a list of 2(nRL) reconstruction sequences and measure secrecy by the minimum distortion over the entire list. We show that this setting is equivalent to one in which an eavesdropper must reconstruct a single sequence, but also receives side information about the source sequence and public message from a rate-limited henchman (a helper for an adversary). We characterize the optimal tradeoff of secret key rate, list rate, and eavesdropper distortion. The solution hinges on a problem of independent interest: lossy compression of a codeword uniformly drawn from a random codebook. We also characterize the solution to the lossy communication version of the problem in which distortion is allowed at the legitimate receiver. The analysis in both the settings is greatly aided by a recent technique for proving source coding results with the use of a likelihood encoder.

In this work, a likelihood encoder is studied in the context of lossy source compression. The analysis of the likelihood encoder is based on a soft-covering lemma. It is demonstrated that the use of a likelihood encoder together with the soft-covering lemma gives alternative achievability proofs for classical source coding problems. The case of the rate-distortion function with side information at the decoder (i.e. the Wyner-Ziv problem) is carefully examined and an application of the likelihood encoder to the multi-terminal source coding inner bound (i.e. the Berger-Tung region) is outlined.

Optical networks are vulnerable to physical layer attacks; wiretappers can improperly receive messages intended for legitimate recipients. Multimode fiber (MMF) transmission can be modeled via a broadcast channel in which both the legitimate receiver's and wiretapper's channels are multiple-input-multiple-output complex Gaussian channels. This work considers the theoretical aspects of this security problem in the domain of a broadcast channel. Source-channel coding analyses based on the use of distortion as the metric for secrecy are developed. Alice has a source sequence to be encoded and transmitted over this broadcast channel so that the legitimate user Bob can reliably decode it while forcing the distortion of the wiretapper, or eavesdropper, Eve's estimate to be as high as possible. Tradeoffs between transmission rate and distortion under two extreme scenarios are examined: the best case where Eve has only her channel output and the worst case where she also knows the past realization of the source. It is shown that under the best case, an operationally separate source-channel coding scheme guarantees maximum distortion at the same rate as needed for reliable transmission. Theoretical bounds are given, and particularized for MMF. Numerical results showing the rate distortion tradeoff are presented and compared with corresponding results for the perfect secrecy case.

Secrecy in communication systems is measured herein by the distortion that an adversary incurs. The transmitter and receiver share secret key, which they use to encrypt communication and ensure distortion at an adversary. A model is considered in which an adversary not only intercepts the communication from the transmitter to the receiver, but also potentially has side information. In particular, the adversary may have causal or noncausal access to a signal that is correlated with the source sequence or the receiver's reconstruction sequence. The main contribution is the characterization of the optimal tradeoff among communication rate, secret key rate, distortion at the adversary, and distortion at the legitimate receiver. It is demonstrated that causal side information at the adversary plays a pivotal role in this tradeoff. It is also shown that measures of secrecy based on normalized equivocation are a special case of the framework.

We analyze a class of distributed quantized consensus algorithms for arbitrary networks. In the initial setting, each node in the network has an integer value. Nodes exchange their current estimate of the mean value in the network, and then update their estimate by communicating with their neighbors in a limited capacity channel in an asynchronous clock setting. Eventually, all nodes reach consensus with quantized precision. We start the analysis with a special case of a distributed binary voting algorithm, then proceed to the expected convergence time for the general quantized consensus algorithm proposed by Kashyap et al. We use the theory of electric networks, random walks, and couplings of Markov chains to derive an O(N3log N) upper bound for the expected convergence time on an arbitrary graph of size N, improving on the state of art bound of O(N4log N) for binary consensus and O(N5) for quantized consensus algorithms. Our result is not dependent on the graph topology. Simulations are performed to validate the analysis.

We consider the problem of generating correlated random variables in a distributed fashion, where communication is constrained to a cascade network. The first node in the cascade observes an i.i.d. sequence$X^{n}$locally before initiating communication along the cascade. All nodes share bits of common randomness that are independent of$X^{n}$. We consider secure synthesis—random variables produced by the system appear to be appropriately correlated and i.i.d. even to an eavesdropper who is cognizant of the communication transmissions. We characterize the optimal tradeoff between the amount of common randomness used and the required rates of communication. We find that not only does common randomness help, its usage exceeds the communication rate requirements. The most efficient scheme is based on a superposition codebook, with the first node selecting messages for all downstream nodes. We also provide a fleeting view of related problems, demonstrating how the optimal rate region may shrink or expand.

In this work, secrecy in communication systems is measured by the distortion incurred by the worst-case adversary. The transmitter and receiver share secret key, which they use to encrypt communication and cause distortion at an adversary. In our model, we assume that an adversary not only intercepts the communication between the transmitter and receiver, but also may have access to noisy observations of the system. For example, the adversary may have causal access to a signal that is correlated with the source sequence or with the output of the receiver. Our main contribution is the solution of the optimal tradeoff among communication rate, secret key rate, distortion at the adversary, and distortion at the legitimate receiver. We demonstrate that side information at the adversary plays a pivotal role, and provide a number of examples that motivate and give insight into our results.

In this paper, the compression of an independent and identically distributed Gaussian source sequence is studied in an unsecure network. Within a game theoretic setting for a three-party noiseless communication network (sender Alice, legitimate receiver Bob, and eavesdropper Eve), the problem of how to efficiently compress a Gaussian source with limited secret key in order to guarantee that Bob can reconstruct with high fidelity while preventing Eve from estimating an accurate reconstruction is investigated. It is assumed that Alice and Bob share a secret key with limited rate. Three scenarios are studied, in which the eavesdropper ranges from weak to strong in terms of the causal side information she has. It is shown that one bit of secret key per source symbol is enough to achieve perfect secrecy performance in the Gaussian squared error setting, and the information theoretic region is not optimized by joint Gaussian random variables.

We consider a cascade network where a sequence of nodes each send a message to their downstream neighbor to enable coordination, the first node having access to an information signal. An adversary also receives all the communication as well as additional side-information. The performance of the system is measured by a payoff function over all actions produced by the nodes as well as the adversary. The challenge is to maintain secrecy from the adversary in order thwart his attempt to reduce the payoff. We obtain inner and outer bounds on performance, and give examples where they are tight. From these bounds, we also derive the optimal equivocation that can be achieved in this setting, as a special case.

The likelihood encoder with a random codebook is demonstrated as an effective tool for source coding. Coupled with a soft covering lemma (associated with channel resolvability), likelihood encoders yield simple achievability proofs for known results, such as rate-distortion theory. They also produce a tractable analysis for secure rate-distortion theory and strong coordination.

Let Xnϵ Xnbe a sequence drawn from a discrete memoryless source, and let Ynϵ ynbe the corresponding reconstruction sequence that is output by a good rate-distortion code. This paper establishes a property of the joint distribution of (Xn, Yn). It is shown that for D > 0, the input-output statistics of a R(D)-achieving rate-distortion code converge (in normalized relative entropy) to the output-input statistics of a discrete memoryless channel (dmc). The dmc is “backward” in that it is a channel from the reconstruction space ynto source space Xn. It is also shown that the property does not necessarily hold when normalized relative entropy is replaced by variational distance.

Two familiar notions of correlation are rediscovered as the extreme operating points for distributed synthesis of a discrete memoryless channel, in which a stochastic channel output is generated based on a compressed description of the channel input. Wyner's common information is the minimum description rate needed. However, when common randomness independent of the input is available, the necessary description rate reduces to Shannon's mutual information. This paper characterizes the optimal tradeoff between the amount of common randomness used and the required rate of description. We also include a number of related derivations, including the effect of limited local randomness, rate requirements for secrecy, applications to game theory, and new insights into common information duality. Our proof makes use of a soft covering lemma, known in the literature for its role in quantifying the resolvability of a channel. The direct proof (achievability) constructs a feasible joint distribution over all parts of the system using a soft covering, from which the behavior of the encoder and decoder is inferred, with no explicit reference to joint typicality or binning. Of auxiliary interest, this paper also generalizes and strengthens this soft covering tool.

A secret key can be used to conceal information from an eavesdropper during communication, as in Shannon's cipher system. Most theoretical guarantees of secrecy require the secret key space to grow exponentially with the length of communication. Here we show that when an eavesdropper attempts to reconstruct an information sequence, as posed in the literature by Yamamoto, very little secret key is required to effect unconditionally maximal distortion; specifically, we only need the secret key space to increase unboundedly, growing arbitrarily slowly with the blocklength. As a corollary, even with a secret key of constant size we can still cause the adversary arbitrarily close to maximal distortion, regardless of the length of the information sequence.

Recommendation systems have received considerable attention recently. However, most research has been focused on improving the performance of collaborative filtering (CF) techniques. Social networks, indispensably, provide us extra information on people's preferences, and should be considered and deployed to improve the quality of recommendations. In this paper, we propose two recommendation models, for individuals and for groups respectively, based on social contagion and social influence network theory. In the recommendation model for individuals, we improve the result of collaborative filtering prediction with social contagion outcome, which simulates the result of information cascade in the decision-making process. In the recommendation model for groups, we apply social influence network theory to take interpersonal influence into account to form a settled pattern of disagreement, and then aggregate opinions of group members. By introducing the concept of susceptibility and interpersonal influence, the settled rating results are flexible, and inclined to members whose ratings are "essential".

A gambler walks into a hypothetical fair casino with a very real dollar bill, but by the time he leaves he's exchanged that for a random amount of money. What is lost in the process? It may be that the gambler walks out at the end of the day, after a roller-coaster ride of winning and losing, with his dollar still intact-or maybe even with two dollars. But what the gambler loses the moment he places his first bet is position. He exchanges one distribution of money for a distribution of lesser value, and he can't get back to the original distribution. Our first discussion in this work connects known results of economic inequality and majorization to the probability theory of gambling and Martingales. We provide a simple proof that fair gambles cannot increase the Lorenz curve, and we also constructively demonstrate that any sequence of non-increasing Lorenz curves corresponds to at least one Martingale. We next consider the efficiency of gambles. If any fair gamble is available then one can move down the lattice of distributions with respect to the Lorenz ordering. The step from one distribution to the next is not unique. Is there a sense of efficiency with which one can move down the Lorenz stream? One approach would be to minimize the average total volume of money placed on the table. In this case, it turns out that implementing part of the strategy using private randomness can help reduce the need for the casino's randomness, resulting in less money on the table that the casino can get its hands on.

We explore a basic noise-free signaling scenario where coordination and communication are naturally merged. A random signal X1, ..., Xnis processed to produce a control signal or action sequence A1, ..., An, which is observed and further processed (without access to X1, ..., Xn) to produce a third sequence B1, ..., Bn. The object of interest is the set of empirical joint distributions p(x, a, b) that can be achieved in this setting. We show that H(A) ≥ I(X;A,B) is the necessary and sufficient condition for achieving p(x, a, b) when no causality constraints are enforced on the encoders. We also give results for various causality constraints. This setting sheds light on the embedding of digital information in analog signals, a concept that is exploited in digital watermarking, steganography, cooperative communication, and strategic play in team games such as bridge.

We clarify the relationship among several existing achievable multiple description rate-distortion regions by investigating the role of refinement layer in multiple description coding. Specifically, we show that the refinement layer in the El Gamal-Cover (EGC) scheme and the Venkataramani-Kramer-Goyal (VKG) scheme can be removed; as a consequence, the EGC region is equivalent to the EGC* region (an antecedent version of the EGC region) while the VKG region (when specialized to the 2-description case) is equivalent to the Zhang-Berger (ZB) region. Moreover, we prove that for multiple description coding with individual and hierarchical distortion constraints, the number of layers in the VKG scheme can be significantly reduced when only certain weighted sum rates are concerned. The role of refinement layer in scalable coding (a special case of multiple description coding) is also studied.

We consider theoretical limits of partial secrecy in a setting where an eavesdropper attempts to causally reconstruct an information sequence with low distortion based on an intercepted transmission and the past of the sequence. The transmitter and receiver have limited secret key at their disposal but not enough to establish perfect secrecy with a one-time pad. From another viewpoint, the eavesdropper is acting as an adversary, competing in a zero-sum repeated game against the sender and receiver of the secrecy system. In this case, the information sequence represents a sequence of actions, and the distortion function captures the payoff of the game. We give an information theoretic region expressing the tradeoff between secret key rate and max-min distortion for the eavesdropper. We also simplify this characterization to a linear program. As an example, we discuss how to optimally use secret key to hide Bernoulli-p bits from an eavesdropper so that they incur maximal Hamming distortion.

We develop elements of a theory of cooperation and coordination in networks. Rather than considering a communication network as a means of distributing information, or of reconstructing random processes at remote nodes, we ask what dependence can be established among the nodes given the communication constraints. Specifically, in a network with communication rates$\{R_{i,j}\}$between the nodes, we ask what is the set of all achievable joint distributions$p(x_{1},\ldots ,x_{m})$of actions at the nodes of the network. Several networks are solved, including arbitrarily large cascade networks. Distributed cooperation can be the solution to many problems such as distributed games, distributed control, and establishing mutual information bounds on the influence of one part of a physical system on another.

We investigate distributed source coding of two correlated sources X and Y where messages are passed to a decoder in a cascade fashion. The encoder of X sends a message at rate R1 to the encoder of Y. The encoder of Y then sends a message to the decoder at rate R2based both on Y and on the message it received about X. The decoder's task is to estimate a function of X and Y. For example, we consider the minimum mean squared-error distortion when encoding the sum of jointly Gaussian random variables under these constraints. We also characterize the rates needed to reconstruct a function of X and Y losslessly. Our general contribution toward understanding the limits of the cascade multiterminal source coding network is in the form of inner and outer bounds on the achievable rate region for satisfying a distortion constraint for an arbitrary distortion function d(x, y, z). The inner bound makes use of a balance between two encoding tactics—relaying the information about X and recompressing the information about X jointly with Y. In the Gaussian case, a threshold is discovered for identifying which of the two extreme strategies optimizes the inner bound. Relaying outperforms recompressing the sum at the relay for some rate pairs if the variance of X is greater than the variance of Y.

In this paper, some existing inner bounds of multiple description problem are investigated. We prove that the El Gamal-Cover region is a subset of the Zhang-Berger (ZB) region. Furthermore, the Venkataramani-Kramer-Goyal region is equivalent to the Zhang-Berger region.

Two familiar notions of correlation are re-discovered as extreme operating points for simulating a discrete memoryless channel, in which a channel output is generated based only on a description of the channel input. Wynerpsilas ldquocommon informationrdquo coincides with the minimum description rate needed. However, when common randomness independent of the input is available, the necessary description rate reduces to Shannonpsilas mutual information. This work characterizes the optimal tradeoff between the amount of common randomness used and the required rate of description.

We establish that the feedback capacity of the trapdoor channel is the logarithm of the golden ratio and provide a simple communication scheme that achieves capacity. As part of the analysis, we formulate a class of dynamic programs that characterize capacities of unifilar finite-state channels. The trapdoor channel is an instance that admits a simple closed-form solution.

We consider a family of channels, collectively referred to as the 'chemical channel', which generalizes the trapdoor channel. We show that the feedback capacity of the chemical channel can be cast as the solution to a dynamic programming (DP) problem. We obtain numerical values for the feedback capacity of the chemical channel by approximating the solution of the DP problem using value iteration. For the special case of the trapdoor channel, by solving the DP problem analytically, we prove that the feedback capacity of the trapdoor channel is the logarithm of the golden ratio. Further, we describe a simple scheme that achieves the capacity of the trapdoor channel. The scheme has zero probability of error, which allows us to conclude that the logarithm of the golden ratio is also the zero error capacity of the chemical channel.