Published in News

High-quality random numbers can now be computed with much less effort

by on26 May 2016

A big win for encryption, more efficient complex simulations

Last week, computer scientist researchers at the University of Texas at Austin published a draft paper describing a new, more efficient way of generating truly random numbers that can be used everyday encryption situations like mobile banking, statistics, electronic voting and complex simulations, among other applications.

At the university, computer science professor David Zuckerman and graduate student Eshan Chattopadhyay developed a method of taking two weakly random numbers and combining them into a single sequence of truly random numbers. In the past, the task of generating truly random numbers for encryption and simulation purposes required very large amounts of computational power to produce higher-quality randomness results. Previous randomness extractors also had difficult requirements – at least one of the two source random sequences had to be “truly random,” or both sequences had to be “close to truly random.”

The new method effectively removes both of these requirements and allows for two source sequences that are only weakly random.

random number generation new method explicit two source extractors

Random number generation using explicit two-source extractors and resilient functions (via University of Texas at Austin)

Over the past several decades, the computer science field of study has generally been accustomed to gradual improvements in the “quality-per-watt” performance needed for high-quality random number generation. Zuckerman and Chattopadhyay’s breakthrough method is now described by some as “light years ahead” of previous methods, as it produces higher randomization with lower computational effort.

quantis true random number generator pci e card

Quantis True Random Number Generator (TRNG) PCI-Express card (specifications here)

"When I heard about it, I couldn't sleep," says 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."

The researchers claim that any truly random numbers required by everyday usage situations like online mobile banking, two-factor authentication and statistically significant poll results can now be computed with fractions of the compute power that was previously demanded. High-quality randomness needed for secure credit card purchases, medical data and military communications can now be produced with significantly higher quality-per-watt performance.

"This is a problem I've come back to over and over again for more than 20 years," says Zuckerman. "I'm thrilled to have solved it."

A draft paper of the new method was released in July 2015 describing the new method, titled “Explicit Two-Source Extractors and Resilient Functions.” It has been revised twice, with the most recent version dated March 20th.

The University of Texas at Austin researchers present their discovery next month at the Symposium on Theory of Computing (STOC) hosted by the Association of Computing Machinery (ACM). The paper is also expected to receive one of three STOC Best Paper Awards.

Last modified on 26 May 2016
Rate this item
(13 votes)