Paper 2016/1116

Evaluating Entropy for TRNGs: Efficient, Robust and Provably Secure

Maciej Skorski

Abstract

Estimating entropy of randomness sources is a task of crit- ical importance in the context of true random number generators, as feeding cryptographic applications with insufficient entropy is a serious real-world security risk. The challenge is to maximize accuracy and con- fidence under certain data models and resources constants. In this paper we analyze the performance of a simple collision-counting estimator, under the assumption that source outputs are independent but their distribution can change due to adversarial influences. For n samples and confidence 1 − we achieve the following features (a) Efficiency: reads the stream in one-pass and uses constant memory (forward-only mode) (b) Accuracy: estimates the amount of extractable bits with a relative 1 error O(n − 2 log(1/ε)), when the source outputs are i.i.d. (c) Robustness: keeps the same error when the source outputs are inde- 1 pendent but the distribution changes up to t = O(n^0.5) times during runtime We demonstrate that the estimator is accurate enough to adjust post- processing components dynamically, estimating entropy on the fly in- stead investigating it off-line. Our work thus continues the line of re- search on "testable random number generators" originated by Bucii and Luzzi at CHES'05.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. Inscrypt 2016
Keywords
online entropy estimatorstestable random number generators
Contact author(s)
maciej skorski @ gmail com
History
2016-12-01: received
Short URL
https://ia.cr/2016/1116
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1116,
      author = {Maciej Skorski},
      title = {Evaluating Entropy for TRNGs: Efficient, Robust and Provably Secure},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1116},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1116}},
      url = {https://eprint.iacr.org/2016/1116}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.