Theoretical Breakthrough Made In Random Number Generation (threatpost.com)

msm1267 quotes a report from Threatpost: Two University of Texas academics have made what some experts believe is a breakthrough in random number generation that could have longstanding implications for cryptography and computer security. David Zuckerman, a computer science professor, and Eshan Chattopadhyay, a graduate student, published a paper in March that will be presented in June at the Symposium on Theory of Computing. The paper describes how the academics devised a method for the generation of high quality random numbers. The work is theoretical, but Zuckerman said down the road it could lead to a number of practical advances in cryptography, scientific polling, and the study of other complex environments such as the climate. "We show that if you have two low-quality random sources -- lower quality sources are much easier to come by -- two sources that are independent and have no correlations between them, you can combine them in a way to produce a high-quality random number," Zuckerman said. "People have been trying to do this for quite some time. Previous methods required the low-quality sources to be not that low, but more moderately high quality. We improved it dramatically." The technical details are described in the academics' paper "Explicit Two-Source Extractors and Resilient Functions."

Comments

Re:FP

[JanneM]

For large-scale simulations you need them to be pseudo-random, as in repeatable. If you are running a parallel simulation across hundreds or thousands of nodes, you can't send random data to all the nodes. You'd spend all your time sending that, not getting anywhere with your simulation.

Instead, what you do is that each node runs its own random generator, but seeded with the same state. That way they all have the same random source, with no need to flood the interconnect with (literally) random data.

Another reason is repeatability of course. You may often want to run the exact same simulation many times when you're developing and debugging your code.

Re:FP

[TechyImmigrant]

I read it too, and I fail to see the breakthrough. There are plenty of pseudo random number generators, such as the Mersenne Twister, with very long periods, so just occassionally XORing even a poor quality random number into the feedback loop, is enough to make it completely unpredictable.

This proof is about proving mathematically that an algorithm is a good entropy extractor. MT has no such proof. It doesn't even meet the definition of an entropy extractor and isn't cryptographically secure. For algorithms in the same class, PCGs are currently top of the pile, but they still aren't secure.

They claim to have an algorithm for a secure two input extractor (where the two inputs are independent) which can extract from low entropy source. 'low' means less than 0.5. Single input extractors suffer from an absence of proofs that they can extract from sources with min-entropy less than 0.5.

I fail to see it as new because the Barack, Impagliazzo, Wigdersen extractor from 2007 did the same trick using three sources (A*B)+C where values from A,B and C are treated as elements in a GF(2^P) field and can operate with low min-entropy inputs. This is so cheap that the extractor is smaller than the smallest entropy sources. Intel published this paper using the BIW extractor for what is probably the most efficient (bits/s/unit_area and bits/s/W) to date.

I fail to see that it is useful, because real world sources have min-entropy much higher that 0.5. Low entropy inputs is a problem mathematicians think we have, but we don't. We engineer these things to be in the 0.9..0.999 range.

On top of it, these two papers are as clear as mud. I tried and failed to identify an explicit construct and ether I'm too dumb to find it or they hid it well. I did find an implication that the first result uses a depth-4 monotone circuit that takes long bit strings and compresses them to 1 bit and the second paper extends this with a matrix multiply. That sounds both inefficient and more expensive than an additional small source needed to use the cheaper 3-input BIW extractor.

My take is that there have been two breakthroughs in extractor theory in recent years. Dodis's papers on randomness classes and extraction with cbc-mac and hmac for single input extractors and the BIW paper for three input extractors. Both useful in real world RNGs.

I may be wrong though. I've asked a real mathematician to decode the claims.