Breakthrough in Random Number Generation Could Boost Data Encryption

The generation of random numbers has been an interesting problem for mathematicians for thousands of years. Old methods of random number generation include rolling dice, flipping coins and shuffling playing cards, but using these techniques for producing large numbers of sufficiently random numbers is extremely time-consuming.

Of course, there are now computer programs that can generate random numbers that meet the statistical definition of randomness. But many of these are inadequate in producing truly random numbers, as they use mathematical formulas or pre-calculated lists. After all, if a number can be computationally produced in such a way, then it can be predictably reproduced again, making these numbers pseudo-random rather than truly random.

Now, two University of Texas at Austin computer scientists have made what many experts are calling a breakthrough in the production of truly random numbers, which are vital in areas such as cryptography, cybersecurity and data encryption. Best of all, the new method requires less computational resources to produce numbers that have a higher quality of randomness.

Computer science professor David Zuckerman and graduate student Eshan Chattopadhyay published their findings in a paper titled ‘Explicit Two-Source Extractors and Resilient Functions‘ back in March, and which will be presented next month during the annual Symposium on Theory of Computing (STOC). So far, the response from the academic community has been enthusiastic, with some hailing the development as a “masterpiece.”

The new method works by taking two weakly random sequences of numbers and turning them into one sequence of truly random numbers. Examples of weakly random sequences — populated with “low-quality” random numbers — include stock market prices and air temperatures. Though these numbers may seem random at first, they will eventually present some predictable patterns over time, unlike other truly random number generation methods, such as rolling dice.

“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,” said Zuckerman on Threatpost. “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 [the method] dramatically.”

The pursuit of true randomness

The recent finding is a continuation of Zuckerman’s decades-long pioneering work on some of these previous methods, known as randomness extractors. To generate numbers that almost truly random, these mathematical functions rely on at least of one of the original sequences to be truly random, or that both sequences be close to truly random.

The new method, however, is a major leap forward from these predecessors. It overcomes these limitations by taking two weakly random number sequences and transforming them into truly unpredictable and random numbers. Moreover, this new method is much more efficient at what it does, as comparable methods for producing high-quality random numbers require exponentially more computational power.

Truly random numbers will help improve data security, where they are used to generate keys in the encryption of data. The more random a key, the more difficult it is for hackers to crack. Encryption helps to keep sensitive information like military intelligence from prying eyes, as well as ensuring that personal data, bank and credit card transactions stay private.

“One common way that encryption is misused is by not using high-quality randomness,” said Zuckerman in a press release. “So in that sense, by making it easier to get high-quality randomness, our methods could improve security.”

Besides data encryption and information security, higher-quality random numbers could also have a big impact on seemingly unrelated areas, such as modeling complex things like Earth’s interacting climate systems. The team’s findings could also potentially increase the security of electronic voting, or help to improve polling methods. For now, the team is working on refining their method by lowering the margins of error.

More over at Threatpost and University of Texas at Austin.

Image: Tom Conder (CC BY-ND 2.0)