A novel definition of the conditional smooth Rényi entropy, which is different from that of Renner and Wolf, is introduced. It is shown that our definition of the conditional smooth Rényi entropy is appropriate for providing lower and upper bounds on the optimal guessing moment in a guessing problem where the guesser is allowed to stop guessing and declare an error. Further a general formula for the optimal guessing exponent is presented. In particular, a single-letterized formula for a mixture of i.i.d. sources is obtained. It is also shown that our definition is appropriate to characterize the optimal exponential moment of the codeword length in the problem of source coding with common side-information available at the encoder and decoder under a constraint on the probability of a decoding error.
A novel definition of the conditional smooth Rényi entropy, which is different from that of Renner and Wolf, is introduced. It is shown that our definition of the conditional smooth Rényi entropy is appropriate for providing lower and upper bounds on the optimal guessing moment in a guessing problem where the guesser is allowed to stop guessing and declare an error. Further a general formula for the optimal guessing exponent is presented. In particular, a single-letterized formula for a mixture of i.i.d. sources is obtained. It is also shown that our definition is appropriate to characterize the optimal exponential moment of the codeword length in the problem of source coding with common side-information available at the encoder and decoder under a constraint on the probability of a decoding error.
A novel definition of the conditional smooth Rényi entropy, which is different from that of Renner and Wolf, is introduced. It is shown that our definition of the conditional smooth Rényi entropy is appropriate to give lower and upper bounds on the optimal guessing moment in a guessing problem where the guesser is allowed to stop guessing and declare an error. Further a general formula for the optimal guessing exponent is given. In particular, a single-letterized formula for mixture of i.i.d. sources is obtained.
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.
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.
One-shot achievable rate region for source coding when coded side information is available at the decoder (source coding with a helper) is proposed. The achievable region proposed is in terms of conditional smooth max Rényi entropy and smooth max Rényi divergence. Asymptotically (in the limit of large block lengths) this region is quantified in terms of spectral-sup conditional entropy rate and spectral-sup mutual information rate. In particular, it coincides with the rate region derived in the limit of unlimited arbitrarily distributed copies of the sources.
Abstract. In this paper, information theoretic cryptography is discussed based on conditional Rényi entropies. Our discussion focuses not only on cryptography but also on the definitions of conditional Rényi entropies and the related information theoretic inequalities. First, we revisit conditional Rényi entropies, and clarify what kind of properties are required and actually satisfied. Then, we propose security criteria based on Rényi entropies, which suggests us deep relations between (conditional) Rényi entropies and error probabilities by using several guessing strategies. Based on these results, unified proof of impossibility, namely, the lower bounds of key sizes is derived based on conditional Rényi entropies. Our model and lower bounds include the Shannon’s perfect secrecy, and the minentropy based encryption presented by Dodis, and Alimomeni and Safavi-Naini. Finally, new optimal symmetric key cryptography and almost optimal secret sharing schemes are proposed which achieve our lower bounds.
Users of a quantum cryptographic system face a problem of deciding on the ignorance of a maximally adroit eavesdropper concerning their key material. It is known that there can be no sure, positive, lower bound on any plausible measure of ignorance, and for this reason we characterize the problem as the making of an informed guess, meaning a guess that employs a rule that can be shown to work except in unlikely cases. As the measure of an eavesdropper's ignorance concerning n bits of sifted key material less some number k of bits found in error and discarded, we analyze Renyi entropy of arbitrary order R, for 1 ≤ R ≤ 2. We offer a rule for deciding on Renyi entropy based on a tighter bound on the relevant probability distributions than has been available. To this end, we employ a recently derived approximation to the cumulative binomial distribution which is uniformly accurate over a larger domain than previously available approximations. This results in a longer distilled key than that obtained from looser bounds, as well as generalizing the order R. Some numerical examples are presented.