Why are countries creating public random number generators?
In Chile, politicians resent the Comptroller General, which audits government officials to prevent corruption. The audits are supposed to be random—but scrutinized officials sometimes complain about unfair targeting. "The auditors have to convince the public they're doing their work honestly," says Alejandro Hevia, a computer scientist at the University of Chile in Santiago. Along with researchers around the world, he is developing technology that could persuade critics that audits are truly random: public random number generators.
On 10 July, Hevia's team will unveil an online random number service. Later in July, the U.S. National Institute of Standards and Technology (NIST) will launch its Randomness Beacon as a permanent service, upgrading a pilot program that began in 2013. Brazil, too, is planning a beacon, by the end of 2019. All aim to improve on commercial random number generators, not only by being free, but by generating the random numbers through transparent protocols and permanently archiving them. The services could benefit everyday applications such as cryptography and lotteries—and also research. Some scientific simulation methods rely on random numbers, and clinicians could use them in drug trials to fairly assign who gets a treatment or placebo.
"We want to put randomness on the internet for people to use in whatever way they can find," says Rene Peralta, a computer scientist at NIST in Gaithersburg, Maryland, who leads the U.S. effort. "I think of it as digital infrastructure."
A sequence of truly random numbers exhibits no patterns or predictability. Knowing the sequence one day should not provide any hints to the sequence published a minute or a day later. But that ideal is not easy to attain. Some online random number generators rely on algorithms, which means their output is, in principle, predictable; others depend on random physical phenomena. The NIST beacon, which generates a string of 512 0s and 1s, or bits, every 60 seconds, combines the two approaches. It starts with output from two commercial random number generators that rely on electronic noise in circuits, then increases the numbers' unpredictability by combining them in a mathematical operation that reduces underlying bias. Chile's beacon combines circuit noise with other disorderly data such as real-time earthquake measurements, online Twitter posts, radio streams, and cryptocurrency transactions.
Readily available, trustworthy random numbers could be used to deliver public services more fairly, computer scientists say. Besides trying to help the Comptroller General maintain its credibility, Hevia is pushing to use Chile's beacon to assign students to schools through a lottery. In the United States, the government could use public random numbers to assign visas. "If you're an applicant and you were not chosen, you would like to know that it was because you weren't lucky enough, and not because you are Muslim," Peralta says. Brazil wants to use its service to assign court cases to judges, says Raphael Machado, a computer scientist at Brazil's National Institute of Metrology Standardization and Industrial Quality in Rio de Janeiro.
Taking one's chances
Several countries are set to unveil public random number generators, or beacons.
Country | Beacon start | Randomness source |
---|---|---|
United States | July | Circuit noise |
Chile | July | Circuit noise, earthquakes, crypto-currency, Twitter, radio streams |
Brazil | End of 2019 | Circuit noise, radioactive decay statistics |
The numbers could also boost security by serving as timestamps to authenticate digital documents. The idea resembles the classic kidnapper's protocol: To prove a hostage is alive, a kidnapper photographs the hostage with that day's newspaper. Similarly, a random number linked to a digital document proves the document was not modified any earlier than the number was generated.
An early motivation for public randomness was to help develop elegant cryptographic techniques called zero-knowledge protocols, which require each party to have access to the same random numbers. "I can prove to a server that I know what the password is but never actually have to tell it," says Carlisle Adams, a computer scientist at the University of Ottawa. "The security would go up a million-fold." However, the protocols are currently too slow, so beacon developers have pursued other applications, Machado says.
A beacon can only be useful for security applications if people believe it's random. Some cryptologists have a lingering distrust of NIST, says Bryan Ford, a computer scientist at the Swiss Federal Institute of Technology in Lausanne. In 2007, one of NIST's encryption standards contained a security vulnerability, and news reports implied the U.S. National Security Agency had intentionally inserted it. "In general, I trust NIST just fine," Ford says. He says the beacons are "probably fine for applications where you need some randomness, but security isn't critical."
Peralta is aware of NIST's image problem, and his team is trying to boost its beacon's trustworthiness. For example, they log the time-stamped random numbers by pairing each one with two other numbers: one called a hash that is calculated from the current number, and the previous entry's hash. This logging method creates a self-referencing chain, so if a hacker changed a number in the sequence, the subsequent number would refer to an incorrect hash, and it would be obvious that someone altered the log. In addition, the U.S., Chilean, and Brazilian beacons all use the same format, so users can mix and match as they please. "People don't have to trust the randomness from NIST because they can combine it with the ones from Chile and Brazil," Hevia says.
Eventually, the computer scientists want to move to a hack-proof, gold standard of randomness: quantum-generated random numbers. Quantum objects don't have a defined state until you measure them, which means that a random outcome is guaranteed by the laws of nature. In April, NIST said it had developed a quantum random number generator based on single photons, which it plans to integrate with the public beacon in the future.
NIST is planning to hold workshops in the next year to brainstorm new uses for its Randomness Beacon. Peralta expects some creative ideas. During the Randomness Beacon's prototype years, one man thought God spoke to him through the beacon. He chose Bible passages based on its output—and when the scripture sequences didn't make sense, he wrote to Peralta complaining about it. "I get funny mail like that," Peralta says. He is expecting better ideas.