Publication

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

Škorić, B., Obi, C., Verbitskiy, E. & Schoenmakers, B., 2011, In : Information and Computation. 209, 8, p. 1184-1196 13 p.

Research output: Contribution to journalArticleAcademic

APA

Škorić, B., Obi, C., Verbitskiy, E., & Schoenmakers, B. (2011). Sharp lower bounds on the extractable randomness from non-uniform sources. Information and Computation, 209(8), 1184-1196. https://doi.org/10.1016/j.ic.2011.06.001

Author

Škorić, Boris ; Obi, Chibuzo ; Verbitskiy, Evgeny ; Schoenmakers, Berry. / Sharp lower bounds on the extractable randomness from non-uniform sources. In: Information and Computation. 2011 ; Vol. 209, No. 8. pp. 1184-1196.

Harvard

Škorić, B, Obi, C, Verbitskiy, E & Schoenmakers, B 2011, 'Sharp lower bounds on the extractable randomness from non-uniform sources', Information and Computation, vol. 209, no. 8, pp. 1184-1196. https://doi.org/10.1016/j.ic.2011.06.001

Standard

Sharp lower bounds on the extractable randomness from non-uniform sources. / Škorić, Boris; Obi, Chibuzo; Verbitskiy, Evgeny; Schoenmakers, Berry.

In: Information and Computation, Vol. 209, No. 8, 2011, p. 1184-1196.

Research output: Contribution to journalArticleAcademic

Vancouver

Škorić B, Obi C, Verbitskiy E, Schoenmakers B. Sharp lower bounds on the extractable randomness from non-uniform sources. Information and Computation. 2011;209(8):1184-1196. https://doi.org/10.1016/j.ic.2011.06.001


BibTeX

@article{705de124c2aa40839b070fdd38ba1d8f,
title = "Sharp lower bounds on the extractable randomness from non-uniform sources",
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 resources in devices. We show that using them has negligible effect on the extractable randomness.",
keywords = "Randomness extraction, Universal hash function, Leftover Hash Lemma",
author = "Boris Škorić and Chibuzo Obi and Evgeny Verbitskiy and Berry Schoenmakers",
note = "Relation: https://www.rug.nl/informatica/onderzoek/bernoulli Rights: University of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science",
year = "2011",
doi = "10.1016/j.ic.2011.06.001",
language = "English",
volume = "209",
pages = "1184--1196",
journal = "Information and Computation",
issn = "0890-5401",
publisher = "ACADEMIC PRESS INC ELSEVIER SCIENCE",
number = "8",

}

RIS

TY - JOUR

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

AU - Škorić, Boris

AU - Obi, Chibuzo

AU - Verbitskiy, Evgeny

AU - Schoenmakers, Berry

N1 - Relation: https://www.rug.nl/informatica/onderzoek/bernoulli Rights: University of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science

PY - 2011

Y1 - 2011

N2 - 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 resources in devices. We show that using them has negligible effect on the extractable randomness.

AB - 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 resources in devices. We show that using them has negligible effect on the extractable randomness.

KW - Randomness extraction

KW - Universal hash function

KW - Leftover Hash Lemma

U2 - 10.1016/j.ic.2011.06.001

DO - 10.1016/j.ic.2011.06.001

M3 - Article

VL - 209

SP - 1184

EP - 1196

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

IS - 8

ER -

ID: 14401521