We evaluate the asymptotics of equivocations, their exponents as well as their second-order coding rates under various Rényi information measures. Specifically, we consider the effect of applying a hash function on a source and we quantify the level of non-uniformity and dependence of the compressed source from another correlated source when the number of copies of the sources is large. Unlike previous works that use Shannon information measures to quantify randomness, information, or uniformity, we define our security measures in terms of a more general class of information measures-the Rényi information measures and their Gallager-type counterparts. A special case of these Rényi information measure is the class of Shannon information measures. We prove tight asymptotic results for the security measures and their exponential rates of decay. We also prove bounds on the second-order asymptotics and show that these bounds match when the magnitudes of the second-order coding rates are large. We do so by establishing new classes non-asymptotic bounds on the equivocation and evaluating these bounds using various probabilistic limit theorems asymptotically.
We evaluate the asymptotics of equivocations, their exponents as well as their second-order coding rates under various Rényi information measures. Specifically, we consider the effect of applying a hash function on a source and we quantify the level of non-uniformity and dependence of the compressed source from another correlated source when the number of copies of the sources is large. Unlike previous works that use Shannon information measures to quantify randomness, information, or uniformity, we define our security measures in terms of a more general class of information measures-the Rényi information measures and their Gallager-type counterparts. A special case of these Rényi information measure is the class of Shannon information measures. We prove tight asymptotic results for the security measures and their exponential rates of decay. We also prove bounds on the second-order asymptotics and show that these bounds match when the magnitudes of the second-order coding rates are large. We do so by establishing new classes non-asymptotic bounds on the equivocation and evaluating these bounds using various probabilistic limit theorems asymptotically.
This dissertation investigates relative entropies, also called generalized divergences, and how they can be used to characterize information-theoretic tasks in quantum information theory. The main goal is to further refine characterizations of the optimal rates for quantum source coding, state redistribution, and measurement compression with quantum side information via second order asymptotic expansions and strong converse theorems. The dissertation consists of a mathematical and an information-theoretic part. In the mathematical part, we focus on the α-sandwiched Rényi divergence (α-SRD). We first investigate the limit α→0 to determine whether this recovers the well-known 0-Rényi relative divergence. We then prove various new results for entropic quantities derived from the α-SRD, including dimension bounds and useful bounds in terms of the fidelity between two quantum states. Furthermore, we derive a necessary and sufficient algebraic condition for equality in the data processing inequality (viz. monotonicity under quantum operations) for the α-SRD, and give applications to entropic bounds. In the information-theoretic part, we first derive the second order asymptotics of visible quantum source coding using a mixed source. For the achievability part, we develop universal quantum source codes achieving a given second order rate for a memoryless source. As a corollary of the main result, we obtain the second order asymptotics of quantum source coding using a single memoryless source. We then prove strong converse theorems for state redistribution (with or without feedback) and measurement compression with quantum side information. The key ingredients in proving these theorems are the aforementioned fidelity bounds on Rényi entropic quantities derived from the α-SRD.
Abstract — We derive a new upper bound for Eve’s information in secret key generation from a common random number without communication. This bound improves on Bennett[7]’s bound based on the Rényi entropy of order 2 because the bound obtained here uses the Rényi entropy of order 1+s for s ∈ [0, 1]. This bound is applied to a wire-tap channel. Then, we derive an exponential upper bound for Eve’s information. Our exponent is compared with Hayashi[8]’s exponent. For the additive case, the bound obtained here is better. The result is applied to secret key agreement by public discussion. Index Terms — exponential rate, non-asymptotic setting, secret key agreement, universal hash function, wire-tap channel I.
This study considers the unconditional smooth Rényi entropy proposed by Renner and Wolf [ASIACRYPT, 2005], the smooth conditional Rényi entropy proposed by Kuzuoka [IEEE Trans. Inf. Th., 66(3), 1674–1690, 2020], and a novel quantity which we term theconditional smooth-⋆entropy.The latter two quantities can be specialized to the first in the absence of side-information. We explore the operational roles of these smooth Rényi entropies by establishing one-shot coding theorems for several information-theoretic problems, including Campbell’s source coding problem, the Arıkan–Massey guessing problem, and the Bunte–Lapidoth task encoding problem. We consider these problems in cases where the errors are non-vanishing and for each problem, we consider two error formalisms: the average and maximum error criteria, where the averaging and maximization are taken with respect to the side-information. Using the one-shot coding theorems, we conclude that Kuzuoka’s smooth conditional Rényi entropy and the conditional smooth-⋆ entropy are the solutions to the problems involving the average and maximum error criteria, respectively. Furthermore, we examine asymptotic expansions of these entropies when the underlying source with its side-information is stationary and memoryless. Applying our asymptotic expansions to the one-shot coding theorems, we derive various fundamental limits for these problems. We show that, under non-degenerate settings, the first-order fundamental limits differ under the average and maximum error criteria. This is in contrast to a different but related setting considered by the present authors [IEEE Trans. Inf. Th., 66(12), 7565–7587, 2020], for variable-length conditional source coding allowing errors, in which the first-order terms are identical but the second-order terms are different under these error criteria.
This study considers the unconditional smooth Rényi entropy, the smooth conditional Rényi entropy proposed by Kuzuoka [\emph{IEEE Trans.\ Inf.\ Theory}, vol.~66, no.~3, pp.~1674--1690, 2020], and a new quantity which we term the conditional smooth Rényi entropy. In particular, we examine asymptotic expansions of these entropies when the underlying source with its side-information is stationary and memoryless. Using these smooth Rényi entropies, we establish one-shot coding theorems of several information-theoretic problems: Campbell's source coding, guessing problems, and task encoding problems, all allowing errors. In each problem, we consider two error formalisms: the average and maximum error criteria, where the averaging and maximization are taken with respect to the side-information of the source. Applying our asymptotic expansions to the derived one-shot coding theorems, we derive various asymptotic fundamental limits for these problems when their error probabilities are allowed to be non-vanishing. We show that, in non-degenerate settings, the first-order fundamental limits differ under the average and maximum error criteria. This is in contrast to a different but related setting considered by the present authors (for variable-length conditional source coding allowing errors) in which the first-order terms are identical but the second-order terms are different under these criteria.
The weak law of large numbers implies that, under mild assumptions on the source, the Renyi entropy per produced symbol converges (in probability) towards the Shannon entropy rate. This paper quantifies the speed of this convergence for sources with independent (but not iid) outputs, generalizing and improving the result of Holenstein and Renner (IEEE Trans. Inform. Theory, 2011). (a) we characterize sources with \emph{slowest convergence} (for given entropy): their outputs are mixtures of a uniform distribution and a unit mass. (b) based on the above characterization, we establish faster convergences in \emph{high-entropy} regimes. We discuss how these improved bounds may be used to better quantify security of outputs of random number generators. In turn, the characterization of "worst" distributions can be used to derive sharp "extremal" inequalities between Renyi and Shannon entropy. The main technique is \emph{non-convex programming}, used to characterize distributions of possibly large exponential moments under certain entropy.
We consider the problem of simulating a noisy channel using noiseless channels with unlimited shared randomness. This can be interpreted as the reverse problem of Shannon’s noisy channel coding theorem. In contrast to previous works, we employ Rényi divergence (with the parameter α ∈ [0,∞]) to measure the level of approximation, and we obtain the reverse Shannon theorem under this measure, which characterizes the Rényi simulation rate, the minimum communication rate required for the Rényi divergence vanishing asymptotically. Our derivation is done by a precise large-deviation analysis. When the communication rate is above the Rényi simulation rate, we provide a complete characterization of the convergence exponent for the Rényi divergence, called the reliability function. When the communication rate is below the Rényi simulation rate, we determine the linear increasing rate for the Rényi divergence, which implies the strong converse exponent for the order-α fidelity.