Quantum Mechanics Could Solve Cryptography’s Random Number Problem

A perfectly provable random number generator is the bedrock of good cryptography. This scientist wants to make one.

Peter Bierhorst’s machine is no pinnacle of design. Nestled in the Rocky Mountains inside a facility for the National Institute of Standards and Technology, the photon-generating behemoth spans an entire building. Its lasers, mirrors, and lenses are split among three laboratories, two of them at opposite ends of the L-shaped building. The whole thing is strung together with almost 900 feet of optical fiber. “It’s a prototype system,” the mathematician explains. “Something might drift out of alignment, and the whole thing stops working. It might take a few days to figure out what went wrong.”

On a good day, the machine produces 1,024 bits of data every 10 minutes, equivalent to typing 13 letters per minute. But it promises what even monkeys on typewriters can’t: completely random text.

Which is much more important than you might think. Cryptography protocols, like the ones that secure your credit card info online and your encrypted e-mails, rely on long strings of random numbers. The less guessable the number, the higher the security.

But the numbers often aren’t as random as you’d hope. “There are a number of papers that show weaknesses in cryptography because keys don’t have enough randomness,” says Grégoire Ribordy, the CEO of ID Quantique, a Swiss company that makes commercial random number generators. Some devices actually encrypt information using algorithm-generated numbers—which means that if you guess the algorithm, the numbers are entirely predictable. Other random number generators might convert electrical noise, like small fluctuations in voltage, into strings of numbers. But over time, these generators deteriorate and end up producing numbers that exhibit patterns. (Typing monkeys would exhibit patterns too, dictated by the relative lengths of their fingers and the layout of the QWERTY keyboard.) Any discernible pattern is a security risk.

Which is why, a couple years ago, Bierhorst’s team decided to develop a number generator that was perfectly, provably random. In the cryptography world, that means “numbers that cannot be predicted,” says Ribordy. And what’s random? Quantum mechanics.

It’s like this: Even if you repeat a quantum experiment by preparing a quantum particle in exactly the same initial state, subjecting it to the exact same conditions, measuring its orientation after the same amount of time, you can still end up with totally different results. This is unlike flipping a quarter, where its initial conditions—the force of your thumb, the direction of the winds—determine the outcome before it lands. The outcome of “flipping” a tiny quantum particle only exists as probabilities until the moment it “lands.” Electrons, photons, and atoms are really, actually random.

For several years now, companies like Ribordy’s have sold quantum random number generators based on photons. The encoding scheme can get complicated, but more or less, photons oriented in one direction represent 1, while ones oriented in another direction represent 0. However, these products still have a potential vulnerability. Someone—or something, like environmental noise—could have infiltrated the machine and inserted bias into the photons’ states, a blemish on their perfect randomness. A user can’t prove that these generators are random, says Ribordy.

So Bierhorst’s team set out to design a machine that could prove its own randomness. This involved a lot of math. Using a quantum mechanics theorem known as Bell’s inequality, Bierhorst designed a test that could show whether anything could have tampered with the photons to introduce patterns or bias. You can apply this test every time you generate a number, and it spits out a number that tells you, for sure, whether anyone has messed with its representative photon.

They added an extra feature to ultra-certify the number generator’s randomness: In order to for someone to mess with output numbers, they’d also have to tamper with a detector in one lab while simultaneously signaling to someone else at another detector what they’d done.

That’s why they built the machine to be so huge. A hacker would have to send a message faster than the speed of light to signal opposite ends of the machine. Which is, according to the laws of physics, impossible. Their machine produces random signals encoded in photons, and nothing can alter the photons unless it can travel faster than light. QED.

It’s not clear whether this machine could eventually be marketable, says Ribordy. It’s too expensive right now, requiring a pricey cooling system—and it’s very large. For encryption, they’d also need to generate random numbers faster. Eventually, it would be great if they shrank the setup to fit on a chip, says Bierhorst: a random number generator in every laptop, so that nobody ever uses those algorithm-based numbers for encryption again.

But at NIST, he’s not worrying about commercializing the technology. Instead, they want to turn it into a public service: an online, government-run, reliably random number generator.

Beginning in 2013, they’ve actually offered a beta version of this service, called the NIST Randomness Beacon. It produces a 512-bit random number every minute and is currently based on commercial random number generators, but they want to incorporate Bierhorst’s machine into the system soon.

Since these numbers are public, they can’t be used for encryption. But Rene Peralta, a NIST computer scientist in charge of the service, says that governments are interested in using the random number generators to prevent corruption. For example, Peralta is working with the government of Chile to potentially use the Randomness Beacon for running government audits. They’d like to use random numbers to fairly choose which officials to audit, which will also help them avoid accusations of collusion. Brazil’s government, too, is interested in using random numbers to assign court cases to judges, in an effort to show the citizens that the judicial system is fair.

But for Bierhorst, the random number generator isn’t just a practical tool. His tests are further evidence that quantum mechanics particles really do exist in weird probabilities and can’t be predetermined. “It’s exciting to be able to say that randomness exists in the universe,” he says. And now, maybe—we can use that randomness to secure our digital destinies.

Quantum Cryptography