Paper 2008/484

Sharp lower bounds on the extractable randomness from non-uniform sources

Boris Skoric, Chibuzo Obi, Evgeny Verbitskiy, and Berry Schoenmakers

Abstract

Extraction of uniform randomness from (noisy) non-uniform sources is an important primitive in many security applications, e.g. (pseudo-)random number generators, privacy-preserving biometrics, and key storage based on Physical Unclonable Functions. Generic extraction methods exist, using universal hash functions. There is a trade-off between the length of the extracted bit string and the uniformity of the string. In the literature there are proven lower bounds on this length as a function of the desired uniformity. The best known bound involves a quantity known as smooth min-entropy. Unfortunately, there exist at least three definitions of smooth entropy. In this paper we compare three of these definitions, and we derive improved lower bounds on the extractable randomness. We also investigate the use of almost universal hash functions, which are slightly worse at extracting randomness than universal hash functions, but are preferable in practice because they require far less nonvolatile memory. We show that using them has negligible effect on the extractable randomness.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
extractorfuzzyinformation theoryuniversal hashPUF
Contact author(s)
b skoric @ tue nl
History
2008-11-19: received
Short URL
https://ia.cr/2008/484
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/484,
      author = {Boris Skoric and Chibuzo Obi and Evgeny Verbitskiy and Berry Schoenmakers},
      title = {Sharp lower bounds on the extractable randomness from non-uniform sources},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/484},
      year = {2008},
      url = {https://eprint.iacr.org/2008/484}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.