Some exciting progress to pure mathematics is due to Bourgain

Springer - Multilinear Exponential Sums in Prime Fields Under Optimal Entropy Condition on the Sources

with applications to randomness extractors and gave the first two source extractor with min entropy rate <0.5

Since this paper there’s been other innovations and simplifications of Bourgains work, such as

An explicit two-source extractor with min-entropy rate near 4/9

This is all exciting for mathematics. Is the same true from an applied crypto perspective? For example, would it help in any way with the issues discussed here

The GCD strikes back to RSA in 2019 - Good randomness is the only solution?

Other applications/places where these theoretical breakthroughs have already been applied?


1 Answer 1


...would it help in any way with the issues discussed here?

No, not really. There's always been a gap between myriad theoretical mathematical extractor constructs and those used in commercial validated TRNGs. I honestly don't know why as that seems like an unlikely dichotomy, yet it demonstrably exists. The two should ideally converge to a common output entropy rate, but they don't :-(

Most creditable TRGNs are based on min. entropy extraction via the Left Over Hash Lemma: $ \epsilon = 2^{-(sn-k)/2} $ where $s=H_{\infty}$per bit input to the extractor. This lemma is unaffected by Bourgain.

So no.

  • $\begingroup$ what is the $s$ in your equation? $\endgroup$
    – kodlu
    Commented May 6, 2020 at 21:53
  • $\begingroup$ Thank you for the answer. Am I right in thinking ciphers are a popular choice for randomness since implementation, entropy issues have already been studied? $\endgroup$
    – user79425
    Commented May 7, 2020 at 7:15
  • $\begingroup$ @zz7948 Not sure I quite understand your comment question. Ciphers can only extract true randomness equivalent to that of their keys. Ciphers per se aren't really considered randomness extractors, and in many cases are just a crutch for weak entropy generation/measurement techniques. It seems that from looking at Bourgain's abstract, he's focusing on extractors specifically, rather than ciphers more generally. $\endgroup$
    – Fred
    Commented May 7, 2020 at 10:40
  • $\begingroup$ @Fred, Thanks for clarifying. Yes, I think I was confusing some technical points about random number generation in general. Anyway, I'm coming at this from a pure math background and finding some very nice ideas in crypto. $\endgroup$
    – user79425
    Commented May 7, 2020 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.