3
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

...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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ what is the $s$ in your equation? $\endgroup$
    – kodlu
    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$
    – zz7948
    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
    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$
    – zz7948
    May 7, 2020 at 13:42

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.