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 nO(log(1/ϵ)n), where ϵ is the distance of the extracted bits from uniform. In this paper we show a matching upper bound. Therefore, the loss of 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 , 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},
      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.