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

Kevin kevinsisco61784 at gmail.com
Wed May 18 18:44:18 EDT 2016

```Is this using a source of true randomness or just another breakable
algorithm?

On 5/18/2016 2:38 AM, grarpamp wrote:
> 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
> 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.
> _______________________________________________
> cryptography mailing list
> cryptography at randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography

---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus

```