"When I heard about it, I couldn't sleep. It’s really a masterpiece.”
Computer scientists are raving about a new cybersecurity method developed by scientists at the University of Texas at Austin, with one cryptography expert even calling it a “masterpiece.”
The new method for producing truly random numbers could be used to encrypt data, make electronic voting more secure, conduct statistically significant polls, and create more accurate simulations of complex systems like Earth’s climate.
"When I heard about it, I couldn't sleep," said Yael Kalai, a senior cryptography researcher at Microsoft Research New England who has also worked on randomness extraction but was not involved in the study. "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 new method is the brainchild of science professor David Zuckerman and graduate student Eshan Chattopadhyay, and the pair is set to present their research at the annual Symposium on Theory of Computing (STOC) in June. Receiving an invitation to present at the conference is preceded by a rigorous peer review process to evaluate the accuracy and significance of the work — and Zuckerman and Chattopadhyay’s paper will be one of three receiving the STOC Best Paper Award.
Examples of weakly random sequences are air temperatures and stock market prices sampled over time — they harbor predictable patterns. On the contrary, truly random sequences have nothing predictable about them, like a coin toss.
The new method takes two weakly random sequences of numbers and turns them into one sequence of truly random numbers. It creates truly random numbers with less computational effort than other methods, which could lead to significantly higher levels of security for anything from credit card purchases and bank transactions to shielding military communications from enemies.
"One common way that encryption is misused is by not using high-quality randomness," says Zuckerman, explaining how other methods require much more computational effort than his. "So in that sense, by making it easier to get high-quality randomness, our methods could improve security."
The problem with previous versions of randomness extractors was that they either required one of the two source sequences to be truly random (which presents a chicken-or-the-egg problem, the press release notes) or both source sequences to be truly random. The new method allows for two sequences that are only weakly random — a more practical approach.
Last summer, Zuckerman and Chattopadhyay posted a draft of their method to a website called the Electronic Colloquium on Computational Complexity. The site allows researchers to receive feedback on their work before publishing final versions in journals or at conferences, and computer scientists have been carefully reviewing the article and providing suggestions to make the method more powerful.
"This is a problem I've come back to over and over again for more than 20 years," Zuckerman says. "I'm thrilled to have solved it."
You might also like: Illegal Numbers: Can Sharing a Number Be Against the Law?