The exact composition of mechanisms for which two differential privacy (DP) constraints hold simultaneously is studied. The resulting privacy region admits an exact representation as a mixture over compositions of mechanisms of heterogeneous DP guarantees, yielding a framework that naturally generalizes to the composition of mechanisms for which any number of DP constraints hold. This result is shown through a structural lemma for mixtures of binary hypothesis tests. Lastly, the developed methodology is applied to approximate $f$-DP composition.

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

We consider two privacy measures, local differential privacy and binary maximal leakage, simultaneously. We study the subsequent utility-privacy trade-off for two utility problems: information preservation and$f$-divergence maximization. We present new achievability results for both problems over all mechanisms that satisfy the combined privacy measure and compare this with the optimal utility over all$\epsilon$-LDP mechanisms. In particular, we study the binary mechanism with erasure and the randomized response mechanism with erasure. Finally, we show that singular mechanisms are dominating for binary maximal leakage.

Given two random variables$X$and$Y$, the maximal leakage$\mathcal{L}(X\rightarrow Y)$from$X$to$Y$was recently proposed as an operational privacy measure. Maximal leakage quantifies the multiplicative increase of the probability of correctly guessing any randomized function of$X$- after observing$\mathrm{Y}$-. This work investigates the properties of maximal leakage in the situation where only certain functions of$X$- are assumed to be of interest to the adversary; specifically, the focus is on measuring maximal leakage with respect to all binary functions of$X$. A definition for binary leakage$\mathcal{L}_{2}^{\ast }(X\rightarrow Y)$is proposed and a characterization theorem for this new measure is derived. The new privacy measure is shown to satisfy standard properties, such as composition theorems and the data processing inequalities. Many of the stated results naturally extend to$C_{k}^{\ast }(X\rightarrow Y)$which assumes the function of interest is$k$-valued. Finally, a relation between the binary leakage and the Dobrushin coefficient is established, and possible applications of this relation are explored.

We study communication-constrained secret key generation, where two legitimate parties would like to generate a secret key using communication subject to a rate constraint. The problem is studied in the finite-blocklength regime. In this regime, the use of auxiliary random variables subject to Markov chain conditions in the corresponding asymptotic bounds has proven to make most existing proof techniques insufficient. However, two recently proposed proof techniques – one for the achievability side based on Poisson matching, and another for the converse side based on reverse hypercontractivity – allow us to overcome these issues to some extent. Based on these techniques, novel one-shot and second-order achievability and converse bounds are derived for the problem. While the second-order bounds do not coincide, leaving a precise second-order characterization of the problem an open issue, they improve upon the previously known tightest bounds. The second-order bounds are demonstrated for two simple sources: the binary symmetric source and the Gaussian symmetric source. For the binary source, we find that the gap between the two bounds is mainly due to an unwanted constant in the converse bound, and the non-convexity of the achievability bound.

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

We consider a remote source coding problem subject to a distortion function. Contrary to the use of the classical separable distortion criterion, herein we consider the more general, f-separable distortion measure and study its implications on the characterization of the minimum achievable rates (also called f-separable indirect rate distortion function (iRDF)) under both excess and average distortion constraints. First, we provide a single-letter characterization of the optimal rates subject to an excess distortion using properties of the f-separable distortion. Our main result is a single-letter characterization of the f-separable iRDF subject to an average distortion constraint. As a consequence of the previous results, we also show a series of equalities that hold using either indirect or classical RDF under f-separable excess or average distortions. We corroborate our results with two application examples in which new closed-form solutions are derived, and based on these, we also recover known special cases.

As the applications of biometric recognition systems are increasing rapidly, there is a growing need to secure the sensitive data used within these systems. Considering privacy challenges in such systems, different biometric template protection (BTP) schemes were proposed in the literature, and the ISO/IEC 24745 standard defined a number of requirements for protecting biometric templates. While there are several studies on evaluating different requirements of the ISO/IEC 24745 standard, there have been few studies on how to measure the linkability of biometric templates. In this paper, we propose a new method for measuring linkability of protected biometric templates. The proposed method is based on maximal leakage, which is a well-studied measure in information-theoretic literature. We show that the resulting linkability measure has a number of important theoretical properties and an operational interpretation in terms of statistical hypothesis testing. We compare the proposed measure to two other linkability measures: one previously introduced in the literature, and a similar measure based on differential privacy. In our experiments, we use the proposed measure to evaluate the linkability of biometric templates from different biometric characteristics (face, voice, and finger vein), which are protected with different BTP schemes. The source codes of our proposed measure and all experiments are publicly available.

We employ a recent technique based on a semigroup application of the method of types to improve on a second-order converse for the common randomness (CR) generation problem. The previously known bound lead to a correct second-order asymptotic rate, but incorrect sign on the second-order term for error rates below 1/2. The new bound has both the correct scaling and sign of the second-order term for small enough error rates.

This paper investigates the problem of secret key generation from correlated Gaussian random variables in the short block-length regime. Inspired by the state-of-the-art performance provided by polar codes in the short blocklength regime for channel coding, we propose an explicit protocol based on polar codes for generating the secret keys. This protocol differs from previously proposed key generation protocols based on polar coding in two main ways: (i) we consider a Gaussian source for the key generation; (ii) we focus on the short block-length regime. Simulation results show that the proposed protocol performs well even for very short blocklengths, especially if one can relax the BER requirements for the generated keys. They also demonstrate that the polar code based protocol outperforms a similar one using LDPC codes in place of polar codes, and that this advantage grows the shorter the blocklength becomes.

Secrecy by design is examined as an approach to information-theoretic secrecy. The main idea behind this approach is to design an information processing system from the ground up to be perfectly secure with respect to an explicit secrecy constraint. The principal technical contributions are decomposition bounds that allow the representation of a random variable$X$as a deterministic function of$({S},{Z})$, where$S$is a given fixed random variable and$Z$is constructed to be independent of$S$. Using the problems of privacy and lossless compression as examples, the utility cost of applying secrecy by design is investigated. Privacy is studied in the setting of the privacy funnel function previously introduced in the literature and new bounds for the regime of zero information leakage are derived. For the problem of lossless compression, it is shown that strong information-theoretic guarantees can be achieved using a reduced secret key size and a quantifiable penalty on the compression rate. The fundamental limits for both problems are characterized with matching lower and upper bounds when the secret$S$is a deterministic function of the information source$X$.

We consider the problem of secret key generation from correlated Gaussian random variables in the finite blocklength regime. Such keys could be used to encrypt communication in IoT networks, and have provable secrecy guarantees in contrast to classic cryptographic approaches. We investigate the performance of polar coding schemes for generating the secret key over short blocklengths. Our simulation results show that the proposed scheme achieves close to theoretical upper bounds at short blocklengths.

The relationship between secrecy, compression rate, and shared secret key rate is surveyed under perfect secrecy, equivocation, maximal leakage, local differential privacy, and secrecy by design. It is emphasized that the utility cost of jointly compressing and securing data is very sensitive to (a) the adopted secrecy metric and (b) the specifics of the compression setting. That is, although it is well-known that the fundamental limits of traditional lossless variable-length compression and almost-lossless fixed-length compression are intimately related, this relationship collapses for many secrecy measures. The asymptotic fundamental limit of almost-lossless fixed length compression remains entropy for all secrecy measures studied. However, the fundamental limits of lossless variable-length compression are no longer entropy under perfect secrecy, secrecy by design, and sometimes under local differential privacy. Moreover, there are significant differences in secret key/secrecy tradeoffs between lossless and almost-lossless compression under perfect secrecy, secrecy by design, maximal leakage, and local differential privacy.

Providing massive connectivity is one of the key challenges for the next generation of wireless communication networks, and hence the capacity limits of massive connectivity need to be thoroughly studied. The uplink in the regime of massive connectivity is captured by the many-access channel (MnAC) model, assuming the number of users to be extremely large and comparable to the blocklength. This work investigates a generalized MnAC, in which the transmitters and/or the receiver can be equipped with multiple antennas, and the channel gain of each user is allowed to be different. This work characterizes the sum-message-length capacity of the multiple-input and multiple-output Gaussian MnAC in the regime where the number of users increases sub-linearly in the blocklength (i.e., Kn= o(n)).

The framework of secrecy by design is introduced and the fundamental limits of lossless data compression are characterized for this setting. The main idea behind secrecy by design is to begin with an operational secrecy constraint, which is modeled by a secrecy function fs, and then to derive fundamental limits for the performance of the resulting secrecy system. In the setting of lossless compression, it is shown that strong information-theoretic secrecy guarantees can be achieved using a reduced secret key size and a modular two-part coding strategy. Focusing on the non-asymptotic fundamental limits of lossless compression, variable-length lossless compression is studied. It is noted that completely lossless compression is not possible when perfect secrecy is required; however, it becomes meaningful under partial secrecy constraints. Moreover, although it is well known that the traditional fundamental limits of variable-length and almost lossless fixed-length compression are intimately related, this relationship collapses once the secrecy constraint is incorporated.

Providing massive connectivity is one of the key challenges for the next generation of wireless communication networks, and hence the capacity limits of massive connectivity need to be thoroughly studied. The uplink in the regime of massive connectivity is captured by the many-access channel (MnAC) model, assuming the number of users to be extremely large and comparable to the blocklength. This work investigates a generalized MnAC, in which the transmitters and/or the receiver can be equipped with multiple antennas, and the channel gain of each user is allowed to be different. This model is referred to as the multiple-input and multiple-output (MIMO) MnAC model. In the MnAC paradigm, the message length (i.e., the number of bits communicated) is not necessarily linear in the blocklength. Therefore, instead of the conventional code rate, the message length is studied and defined as a function of the blocklength. This work characterizes the sum-message-length capacity (SMC) of the MIMO Gaussian MnAC in the regime where the number of users increases sub-linearly in the blocklength (i.e., Kn= o(n)). The SMC is numerically compared to lower bounds on achievable rate at finite blocklengths and is shown to be a good approximation for system performance. The impact of the number of antennas per user on SMC is also investigated. While in the single antenna MnAC model the conventional code rate is always zero, it is shown that in the MIMO MnAC it is possible to achieve positive rate by increasing the number of antennas per user. Furthermore, the antenna-user index is defined and the SMC is characterized for different antenna-user joint regimes. This provides useful insights for future MIMO MnAC system design.

We study the problem of sequential prediction with coded side information under logarithmic loss (log-loss). We show an operational equivalence between this setup and lossy compression with log-loss distortion. Using this insight, together with recent work on lossy compression with log-loss, we connect prediction strategies with distributions in a certain subset of the probability simplex. This allows us to derive a Shtarkov-like bound for regret and to evaluate the regret for several illustrative classes of experts. In the present work, we mainly focus on the “batch” side information setting with sequential prediction.

Universal lossy source coding under the logarithmic loss (log-loss) criterion is studied. Bounds on the rate-redundancy of variable-length universal codes with respect to a family of distributions are derived. These bounds correspond to previously derived bounds on distortion-redundancy of fixed-length coding. The asymptotic behavior of the resulting optimization problem is studied for a family of i.i.d. sources with a finite alphabet size. As is the case with distortion-redundancy, rate-redundancy of memoryless sources is lower bounded by [k/2] logn, wherenis the blocklength andkis the number of degrees of freedom in the parameter space. The impact of the distortion constraint is on the constant term: higher allowed distortion effectively reduces the volume of the parameter uncertainty set. In view of previously established connections between lossy variable-length coding under log-loss and compression with list decoding, the bounds derived in this work also apply to variable-length coding with list decoding.

This paper considers the problem of lossy source coding with a specific distortion measure: logarithmic loss. The focus of this paper is on the single-shot approach, which exposes crisply the connection between lossless source coding with list decoding and lossy source coding with log-loss. Fixed-length and variable-length bounds are presented. Fixed-length bounds include the single-shot fundamental limit for average as well as excess distortion. Variable-length bounds include the single-shot fundamental limit for average as well as excess length. Two multi-terminal problems are addressed: coding with side information (Wyner-Ziv) and multiple descriptions coding. In both the cases, the application of the Shannon-McMillan theorem to the single-shot bounds yields the rate-distortion function and the rate distortion-region for stationary ergodic sources.

Universal lossy source coding with the logarithmic loss distortion criterion is studied. Bounds on the non-asymptotic fundamental limit of fixed-length universal coding with respect to a family of distributions are derived. These bounds generalize the well-known minimax bounds for universal lossless source coding. The asymptotic behavior of the resulting optimization problem is studied for a family of i.i.d. sources with a finite alphabet size, and is characterized up to a constant. The redundancy of memoryless sources behaves like k/2 log n, where n is the blocklength and k is the number of degrees of freedom in the parameter space. The impact of the coding rate is on the constant term: higher compression rate effectively reduces the volume of the parameter uncertainty set.

This paper studies the problem of lossy source coding with a specific distortion measure: logarithmic loss. The focus of this paper is on the single-shot approach which exposes the connection between lossy source coding with log-loss and lossless source coding. Point-to-point bounds, including the single-shot fundamental limit for average as well as excess distortion, are presented. Two multi-terminal problems are addressed: coding with side information (Wyner-Ziv), and multiple descriptions coding. In both cases, the application of the Shannon-McMillan Theorem to the single-shot bounds immediately yields the rate-distortion function and the rate distortion-region for stationary and ergodic sources.

We study a form of unequal error protection that we term unequal message protection (UMP). The message set of a UMP code is a union of m disjoint message classes. Each class has its own error protection requirement, with some classes needing better error protection than others. We analyze the tradeoff between rates of message classes and the levels of error protection; our analysis reveals new tradeoffs, which were not captured by prior works on UMP codes. To obtain our results, we generalize finite block length achievability and converse bounds due to Polyanskiy-Poor-Verdú. We evaluate our bounds for the binary symmetric and binary erasure channels, and analyze the asymptotic characteristic of the bounds in the fixed error and moderate deviations regimes. In addition, we consider two questions related to the practical construction of UMP codes. First, we study a header construction that prefixes the message class into a header followed by data protection using a standard homogeneous (classical) code. We show that, in general, this construction is not optimal at finite block lengths. We further demonstrate that our main UMP achievability bound can be obtained using coset codes, which suggests a path to implementation of tractable UMP codes.

We study the problem of lossless joint source-channel coding (JSCC) in the finite block length regime from an unequal message protection (UMP) perspective. We demonstrate that the problem of lossless JSCC can be cast in terms of UMP codes previously studied. We show that an optimal JSCC can be constructed from a matched UMP code. We further derive a finite block length bound that characterizes the performance of a JSCC constructed from a UMP code not perfectly matched to the source. This bound is evaluated for a binary memoryless source transmitted over a binary symmetric channel. Two-class schemes previously studied in literature are compared with the proposed scheme. Empirically the JSCCs based on UMP codes approach the performance of the optimal matched code quite fast in number of classes used.

We study achievability bounds for a class of unequal error protection codebooks with m > 1 different classes of codewords called unequal message protection (UMP) codes. We extend the dependence testing bound due to Polyanskiy-Poor-Verdú to be applicable to UMP codes and use this extension to obtain refined asymptotic expansions for the performance of such codes over discrete memoryless channels. In addition, we consider two questions related to the practical construction of UMP codes. First, we study a “header” construction that prefixes the message class into a header followed by data protection using a standard homogeneous (classical) code. We show that, in general, this construction is not optimal at finite block lengths. We further demonstrate that our main UMP achievability bound can be obtained using coset codes, which suggests a path to tractable implementation of UMP codes.

We study converse bounds for unequal error protection codebooks with k > 1 different classes of codewords. We dub these unequal error protection codes “assorted codes”. We extend a finite blocklength converse bound due to Polyanskiy-Poor-Verdú to apply to assorted codes and use this extension to obtain a refined asymptotic expansion for the performance of assorted codes over a discrete memoryless channel. Our main contribution is to demonstrate that there is indeed a loss in the rates of an assorted code compared to equivalent homogeneous (classical) codes. Notably, when the number of codeword classes is polynomial in blocklength n the loss is apparent in the third order O(log n) term of the asymptotic expansion of the logarithm of the maximum number of codewords. This is in sharp contrast to the previous literature which only considers this problem within regimes where no such loss could be observed.

Consider the following unequal error protection scenario. One special message, dubbed the “red alert” message, is required to have an extremely small probability of missed detection. The remainder of the messages must keep their average probability of error and probability of false alarm below a certain threshold. The goal then is to design a codebook that maximizes the error exponent of the red alert message while ensuring that the average probability of error and probability of false alarm go to zero as the blocklength goes to infinity. This red alert exponent has previously been characterized for discrete memoryless channels. This paper completely characterizes the optimal red alert exponent for additive white Gaussian noise channels with block power constraints.

In this paper we bound the reliability function of decoding with errors and erasures for a streaming multiple-access channel with feedback. We show that, subject to an arbitrarily small bound on the probability of erasure, the best known lower bound on the reliability function (i.e., achievable error exponent) for the single-user version of our problem can also be achieved in the multi-user setting for high sum-rates. In other words, at high rates the interference of another user need not decrease the achievable error exponent of either.