Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Shannon Entropy Versus Renyi Entropy from a Cryptographic Viewpoint
verfasst von : Maciej Skórski
Erschienen in: Cryptography and Coding
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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-\epsilon \), where \(\epsilon \) 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.