homehome Home chatchat Notifications


Computer science breakthrough in random number generation

Random numbers are essential for cryptography and computer security. The problem is that algorithms don't really generate totally random numbers.

Tibi Puiu
May 19, 2016 @ 2:19 pm

share Share

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.

dice random numbers

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

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.”

 

share Share

China Resurrected an Abandoned Soviet 'Sea Monster' That's Part Airplane, Part Hovercraft

The Soviet Union's wildest aircraft just got a second life in China.

A Rocket Carried Cannabis Seeds and 166 Human Remains into Space But Their Capsule Never Made It Back

The spacecraft crashed into the Pacific Ocean after a parachute failure, ending a bold experiment in space biology and memorial spaceflight.

Ancient ‘Zombie’ Fungus Trapped in Amber Shows Mind Control Began in the Age of the Dinosaurs

The zombie fungus from the age of the dinosaurs.

Your browser lets websites track you even without cookies

Most users don't even know this type of surveillance exists.

What's Seasonal Body Image Dissatisfaction and How Not to Fall into Its Trap

This season doesn’t have to be about comparison or self-criticism.

Why a 20-Minute Nap Could Be Key to Unlocking 'Eureka!' Moments Like Salvador Dalí

A 20-minute nap can boost your chances of a creative breakthrough, according to new research.

The world's oldest boomerang is even older than we thought, but it's not Australian

The story of the boomerang goes back in time even more.

Swarms of tiny robots could go up your nose, melt the mucus and clean your sinuses

The "search-and-destroy” microrobot system can chemically shred the resident bacterial biofilm.

What if Every Roadkill Had a Memorial?

Road ecology, the scientific study of how road networks impact ecosystems, presents a perfect opportunity for community science projects.

Fireball Passes Over Southeastern United States

It’s a bird! It’s a plane! It’s… a bolide!