Welcome to the resource topic for 2015/591
Title:
How much randomness can be extracted from memoryless Shannon entropy sources?
Authors: Maciej Skorski
Abstract:We revisit the classical problem: given a memoryless source having a certain amount of Shannon Entropy, how many random bits can be extracted? This question appears in works studying random number generators built from physical entropy sources. Some authors use a heuristic estimate obtained from the Asymptotic Equipartition Property, which yields roughly n extractable bits, where n is the total Shannon entropy amount. However the best known precise form gives only n-O(\sqrt{\log(1/\epsilon) n}), where \epsilon is the distance of the extracted bits from uniform. In this paper we show a matching n-\Omega(\sqrt{\log(1/\epsilon) n}) upper bound. Therefore, the loss of \Theta(\sqrt{\log(1/\epsilon) n}) bits is necessary. As we show, this theoretical bound is of practical relevance. Namely, applying the imprecise AEP heuristic to a mobile phone accelerometer one might overestimate extractable entropy even by 100\%, no matter what the extractor is. Thus, the ``AEP extracting heuristic’’ should not be used without taking the precise error into account.
ePrint: https://eprint.iacr.org/2015/591
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .