New method creates real randomness: 'extractor' removes bias from computer-generated numbers.
The method improves on previous randomness extractors because it requires only two sources of randomness, and those sources can be very weak. "It's a big breakthrough on a fundamental problem," says computer scientist Dana Moshkovitz of MIT.
Eshan Chattopadhyay and David Zuckerman, computer scientists at the University of Texas at Austin, were scheduled to present the new randomness extractor June 20 in Cambridge, Mass., at the Symposium on the Theory of Computing.
For computers, random numbers are a precious resource, essential for encrypting sensitive information such as credit card numbers, for instance. But computers typically fail at generating truly random numbers. Many computer applications instead rely on "pseudorandom" numbers. These are generated in a reproducible way, relying on an algorithm, and therefore aren't really random.
Deviations from true randomness can create security holes. "A common way for hackers to break into systems is to exploit the fact that people don't use high-quality randomness," says Zuckerman.
To sidestep computers' predictable natures, computer scientists have devised ways of harvesting randomness from the environment, using input from the mouse or the keyboard, for example. The computer might sample the mouse's coordinates at several points in time and convert these values into a string of numbers. But this still falls short of being truly random. If the mouse is on the left of the screen one moment, it's less likely to be all the way on the right in the following instant. So successive numbers could be correlated or biased toward certain values, making them only weakly random.
Randomness extractors excavate the randomness from these weak sources, throwing away the predictable junk to create a truly random number. "Randomness is a resource--it's just like gold that you mine," says Moshkovitz. "You take the sources that you have and you just purify the gold out of them."
The new randomness extractor combines two independent sources of weakly random numbers into one set that is nearly random, with only minor deviations. Then the researchers use a "resilient function," a method of combining information, to turn the string of numbers into one truly random bit--a 1 or 0.
Resilient functions combine information in a way that can withstand a certain amount of bias. For example, in an election, some number of malicious voters might collude to sway it in one direction. A resilient function can protect honest voters. Rather than taking the majority vote, election officials could group voters into threes and take the majority of each group, then group those results into threes and take the majority and so on. This method allows the election to tolerate a larger number of bad apples--or, in random number generation, it can filter out the effect of the biased numbers.
Compared with previous state-of-the-art randomness extractors, which required input that was already very close to random, the new method can mine sources that are "much, much, much, much weaker," says computer scientist Avi Wigderson of the Institute for Advanced Study in Princeton, N. J. The new extractor is a "substantial improvement over the previous results, and it's very close to the best you can hope for."
|Printer friendly Cite/link Email Feedback|
|Title Annotation:||MATH & TECHNOLOGY|
|Date:||Jun 25, 2016|
|Previous Article:||Schrodinger's cat in 2 boxes at once: entangled microwaves offer benefits for quantum computing.|
|Next Article:||Insect-sized both is first to both fly and land.|