[Cryptography] RNG Breakthrough: Explicit Two-Source Extractors and Resilient Functions

grarpamp grarpamp at gmail.com
Wed May 18 02:38:42 EDT 2016


Let's do another 100 post round on the favorite subject shall we...
because serious RNG is serious.

Academics Make Theoretical Breakthrough in Random Number Generation
https://news.ycombinator.com/item?id=11719543
https://threatpost.com/academics-make-theoretical-breakthrough-in-random-number-generation/118150/
Explicit Two-Source Extractors and Resilient Functions.
http://eccc.hpi-web.de/report/2015/119/

We explicitly construct an extractor for two independent sources on n
bits, each with min-entropy at least logCn for a large enough
constant~C. Our extractor outputs one bit and has error n−(1). The
best previous extractor, by Bourgain, required each source to have
min-entropy 499n.

A key ingredient in our construction is an explicit construction of a
monotone, almost-balanced boolean function on n bits that is resilient
to coalitions of size n1−, for any 0. In fact, our construction is
stronger in that it gives an explicit extractor for a generalization
of non-oblivious bit-fixing sources on n bits, where some unknown n−q
bits are chosen almost \polylog(n)-wise independently, and the
remaining q=n1− bits are chosen by an adversary as an arbitrary
function of the n−q bits. The best previous construction, by Viola,
achieved q=n12− .

Our explicit two-source extractor directly implies an explicit
construction of a 2(loglogN)O(1)-Ramsey graph over N vertices,
improving bounds obtained by Barak et al. and matching independent
work by Cohen.


More information about the cryptography mailing list