Randomness Means Security
Credit: James Bowe
Random numbers are a necessity for computer security, but a leading contributor to problems with cybersecurity is how surprisingly hard it can be for computers to produce high quality random numbers. The numbers produced by many random number generators harbor subtle patterns that make it possible for hackers to crack encrypted messages based on them.
Now computer scientist David Zuckerman and alumnus Eshan Chattopadhyay have found a method for taking two low-quality random sources and combining them to get a high-quality random number — something previously theorized but that had proved too difficult for any algorithm before. With additional work, the breakthrough might eventually be used to improve data encryption in numerous ways, possibly helping to make electronic voting more secure and improve the ability of technology to accurately simulate complex systems such as Earth’s climate.
“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.”
The method first converts the two weakly random inputs into a series of what could be described as coin flips, where most of the coin flips are almost random. In the second part, a mathematical function divides up the flips into subgroups, and then redivides them in many different ways. By comparing the contents of these many different subgroups, it produces one highly random coin flip. Other researchers subsequently showed that if you modify the first part of the method, the second part can be greatly simplified.
Yael Kalai, a senior researcher working in cryptography at Microsoft Research New England called the research a masterpiece: “When I heard about it, I couldn’t sleep I was so excited.”