There’s no cheating this random number generator

If your name gets picked for jury duty, it’s because a computer used a random number generator to select it. The same goes for tax audits or when you opt for a quick pick lottery ticket. But how can you trust that the draw was truly fair? A new cheat-proof protocol for generating random numbers could provide that confidence — preventing hidden tampering or rigged outcomes, researchers report June 11 in Nature.

“Having a public source of randomness that everyone trusts is important because the higher the stakes of an application or the more people involved, the more incentive there is to change or hack a random number generator,” says Gautam Kavuri, a physicist at the National Institute of Standards and Technology in Boulder, Colo. “This protocol verifies that random number generation is not being compromised.”

Most classical methods of generating random numbers aren’t truly random: Anything with a pattern can be predicted. Computers can generate pseudorandom numbers, but anyone who cracks the algorithm can also guess its output. Even monkeys banging on keyboards would create guessable sequences based on their finger length and the keyboard layout.

Genuine unpredictability can be found only in the quantum realm, where the tiniest particles exist in indefinite states until measured. Scientists can harness this natural randomness through loophole-free Bell tests, experiments that use entangled particles and measurement settings chosen at random and in real time. These tests offer a way to certify that the results are truly random, even if individual devices themselves can’t be fully trusted — a strategy known as device-independent randomness.

But how can you verify that the entire system isn’t being manipulated behind the scenes? This is an especially important question for public randomness beacons, which broadcast fresh, random numbers online at regular intervals. “The worst thing that can happen if you’re claiming to have a randomness beacon is for someone to be able to guess your random numbers in advance,” says Roger Colbeck, an applied mathematician at the University of York in England, who was not involved in the study. 

To guard against that, Kavuri and his colleagues designed a system that doesn’t rely on a single point of trust. Instead, it distributes trust across institutions by creating several points of measurement and building data structures called hash chains — where each hash is like a cryptographic fingerprint that can’t be altered without detection. By weaving together five hash chains, operated by three independent institutions, into a single system, the team can create something like a tamper-proof receipt.

The number generation process starts at the National Institute of Standards and Technology in Colorado when a laser zaps a crystal, knocking off a pair of entangled particles of light, or photons, that share mysteriously linked properties. The entangled photons whiz over optic fibers to two measurement stations spaced 110 meters apart at the University of Colorado Boulder. While the photons are traveling, each station randomly chooses how to measure the incoming photon’s polarization, the orientation of its electromagnetic field. Once measured, the detectors convert the result into a bit: either a 0 or a 1.

The entire process is “a really paranoid way to make sure things are really random,” Kavuri says. “You would need to communicate faster than the speed of light to be able to spoof this.”

This process repeats 15 million times in about a minute, creating a massive stream of raw random bits. After quality control tests, computers at the university combine the stream with the next random number sample from a third institution, another public beacon. Everything is processed through an algorithm that filters out any patterns. The result is 512 binary digits of certified pure randomness.

Those 512 bits are equivalent to 10¹⁵⁴ possible strings of bits, which each translate to a different number. That’s a pool of possibilities so massive that it dwarfs the number of atoms in the observable universe.

Over a 40-day trial, as the protocol ran more than 7,000 times, each run came with less than a 1-in-18-quintillion chance of the numbers not being perfectly random. “The protocol is extremely secure at that error rate,” Colbeck says.

More than three institutions can join the network to distribute tasks and increase trust. Some may play an active role in generating the random numbers. Others might serve as observers, impartially recording and verifying events in the hash chain, with the random numbers ultimately appearing on public beacons like NIST’s.

“The more parties that are involved,” Kavuri says, “the more the trust spreads out.”