Skip to main content

Researchers Discover Breakthrough Method To Generate True Random Numbers From Weak Randomness Sources

Computer science professor David Zuckerman and graduate student Eshan Chattopadhyay from the University of Texas (Austin) developed a new method of generating truly random numbers by combining two “weak randomness” sources such as the stock market and weather temperatures. The method is considered a breakthrough because it could have a significant positive impact on all types of encryption, making systems, communications, and data more secure.

Random numbers are important for encryption because without them, encryption keys could be easily “guessed.” Because encryption is used for everything from securing private communications to protecting credit card numbers both in transit over the internet but also on the companies’ servers, having a good random number generator is important to protect all of that data.

Current methods of obtaining truly random numbers are either not high quality, or it’s difficult to obtain a source of true randomness such as a measurement of background radiation or variations in atmospheric noise for most devices. The latter methods are also computationally demanding, which means they can’t be implemented in all types of devices for either performance or cost reasons.

Dr. Zuckerman said that he has been working on this problem for over 20 years and is now “thrilled” to have finally solved it. Other computer science academics are just as ecstatic about the discovery.  

Oded Goldreich, a professor of computer science at the Weizmann Institute of Science in Israel, said that even if this was a moderate improvement over what currently exists, it would’ve still been worthy of a “night-long party.” However, this goes much further than just a moderate improvement.

"When I heard about it, I couldn't sleep," said Yael Kalai, a senior researcher working in cryptography at Microsoft Research New England who has also worked on randomness extraction. "I was so excited. I couldn't believe it. I ran to the (online) archive to look at the paper. It's really a masterpiece."

Zuckerman and Chattopadhyay's research paper currently shows how to create only one random number at a time, such as flipping a coin, but Xin Li, one of Zuckerman's former students, has already expanded the method to generate a series of random numbers. Other researchers can also review his draft and suggest improvements before publication of the final version of the paper in the coming months. The two researchers will also present the paper at the annual Symposium on Theory of Computing in June.

Lucian Armasu is a Contributing Writer for Tom's Hardware. You can follow him at @lucian_armasu. 

Follow us on FacebookGoogle+, RSS, Twitter and YouTube.

  • falchard
    Yea that's cool, but would it be as fast as my: ranX = % range + 1;
    Reply
  • anathema_forever
    Think this might have more than just ramifications for encryption this could be a breakthrough in math as well unless math already knew how to do this of course.
    Reply
  • tom10167
    Not to discredit all this, but how big will this be for encryption, isn't aes256 already by far the strongest link in the chain?
    Reply
  • heffeque
    Not to discredit all this, but how big will this be for encryption, isn't aes256 already by far the strongest link in the chain?
    You know nothing, John Snow. The creation of random numbers has nothing to do with AES256.
    Reply
  • tom10167
    Thanks, I'll take your word for it, though some explanation of real world applications would be nice.
    Reply
  • heffeque
    17986460 said:
    Thanks, I'll take your word for it, though some explanation of real world applications would be nice.

    I guess I didn't make things easy.
    This might help you understand how AES works: http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html

    Interestingly enough, it's actually possible to use AES to get a random number... but then again... what "is" random? http://postimg.org/image/kzn9ljuyp/
    :)
    Reply
  • turkey3_scratch
    This is incredible and groundbreaking! It's also very weird, because I was thinking yesterday of ways in my head on how to create a random number better. One of my methods had to actually do with the wind, or weather. Basically, if you have some device which can measure airflow to the trillionths place, for instance, and take that last digit, it should be very random because obviously the airflow speed would easily change in the trillionths place constantly; there is no way it will be that constant.

    Just my idea, though. I know there are some atomic things, perhaps radiation, that I have researched have some randomness to them. There are also add-on PCI cards for PCs that can generate more accurate random numbers that traditional methods.
    Reply
  • mavikt
    @turkey: What is an accurate random number...? I guess that if you could measure the growth rate of your beard to to the trillionth place, that would also be random, perhaps affected by your diet...

    Anyways, from the article I understand that Oded Goldreich is gonna have to party like it's 1999 instead!
    Reply
  • turkey3_scratch
    That's the thing I question myself, what makes him so sure that his algorithm is truly random? Well, he never said truly random, only that it's more random than the current ones. And I'm not going to question somebody who has been researching this sole problem for 20 years straight.
    Reply
  • ComputerSecurityGuy
    Traditionally you just read from a psuedorandomly chosen RAM bit. There was a bad SSL incident when someone "patched" it.
    Reply