Random numbers are essential for cryptography and computer security. The problem is that algorithms don’t really generate totally random numbers. Depending on the seed value, these generated random numbers are fairly easy or very difficult to predict. Academics at University of Texas made a breakthrough in the field by generating high-quality random numbers by combining two low-quality sources.
Credit: Flickr
The work is still theoretical, but the two researchers, David Zuckerman, a computer science professor, and Eshan Chattopadhyay, a graduate student, say it could significantly improve cryptography, scientific polling, and even climate models. Already, some randomness extractors that create sequences of many more random numbers have been made using the University of Texas algorithms.
“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,” Zuckerman said.
Because computers just follow instructions, and random numbers are the opposite of following instructions, random numbers are theoretically predictable, although some easier or harder than others. Comic by XKCD
“You expect to see advances in steps, usually several intermediate phases,” Zuckerman said. “We sort of made several advances at once. That’s why people are excited.”
The new algorithm, detailed in the journal ECCC, will make hacking a lot more difficult as random numbers of higher quality can be generated for less computational power.
“This is a problem I’ve come back to over and over again for more than 20 years,” said Zuckerman. “I’m thrilled to have solved it.”
