Shannon Entropy Versus Renyi Entropy from a Cryptographic Viewpoint

摘要

We provide a new inequality that links two important entropy notions: Shannon Entropy H_1 and collision entropy H_2. Our formula gives the worst possible amount of collision entropy in a probability distribution, when its Shannon Entropy is fixed. While in practice it is easier to evaluate Shannon entropy than other entropy notions, it is well known in folklore that it does not provide a good estimate of randomness quality from a cryptographic viewpoint, except very special settings. Our results and techniques put this in a quantitative form, allowing us to precisely answer the following questions: (a) How accurately does Shannon entropy estimate uniformity? Concretely, if the Shannon entropy of an n-bit source X is n - ε, where ε is a small number, can we conclude that X is close to uniform? This question is motivated by uniformity tests based on entropy estimators, like Maurer's Universal Test. (b) How much randomness can we extract having high Shannon entropy? That is, if the Shannon entropy of an n-bit source X is n - O(1), how many almost uniform bits can we retrieve, at least? This question is motivated by the folklore upper bound O(log(n)). (c) Can we use high Shannon entropy for key derivation? More precisely, if we have an n-bit source X of Shannon entropy n - O(1), can we use it as a secure key for some applications, such as square-secure applications? This is motivated by recent improvements in key derivation obtained by Barak et al. (CRYPTO'11) and Dodis et al. (TCC'14), which consider keys with some entropy deficiency. Our approach involves convex optimization techniques, which yield the shape of the "worst" distribution, and the use of the Lambert W function, by which we resolve equations coming from Shannon Entropy constraints. We believe that it may be useful and of independent interests elsewhere, particularly for studying Shannon Entropy with constraints.