International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 21 June 2015

Maciej Skorski
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.