Paper 2015/591

How much randomness can be extracted from memoryless Shannon entropy sources?

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Contact author(s)
maciej skorski @ gmail com
History
2015-06-21: received
Short URL
https://ia.cr/2015/591
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/591,
      author = {Maciej Skorski},
      title = {How much randomness can be extracted from memoryless Shannon entropy sources?},
      howpublished = {Cryptology ePrint Archive, Paper 2015/591},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/591}},
      url = {https://eprint.iacr.org/2015/591}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.