New Quantum Method Generates Really Random Numbers
Researchers at the National Institute of Standards and Technology (NIST) have developed a method for generating numbers guaranteed to be random by quantum mechanics. Generating truly random numbers is one of the major challenges for quantum-based encryption and could mark a major leap in cybersecurity.
The research is part of an ongoing effort to enhance NIST’s randomness beacon, which uses two independent commercially available sources to broadcast random bits for applications such as secure multiparty computation. Technically, the new method is already usable, but it will take some time before it can be used for the beacon. “Currently our system is a prototype so that if something comes out of alignment, it may take a long time to put it back in alignment before we can get it running again. Addressing this is an engineering challenge,” says NIST mathematician Peter Bierhorst.
The speed of bit generation also is an issue. “We also need to increase the rate at which we can generate randomness,” says Scott Glancy, a NIST physicist. He adds that the current rate is “significantly slower” than the 512 bits per minute required to keep up with the beacon generator. In addition, the commercial methods currently used for the beacon are less expensive, easier to deploy and more dependable than the prototypical method.
Random numbers are used hundreds of billions of times a day to encrypt data in electronic networks. The numbers cannot be certified random in an absolute sense, however, because the software or physical devices generating the bits can be undermined by outside factors such as predictable sources of noise. Running statistical tests can help, but no statistical test alone can absolutely guarantee that the output was unpredictable, especially if an adversary has tampered with the device, NIST officials explain in an announcement released today.
The new method generates digital bits—1s and 0s—with photons, or particles of light, using data generated in an improved version of a landmark 2015 NIST physics experiment. In the new work, researchers certify and quantify the randomness available in the data and generate a string of much more random bits.
“It’s hard to guarantee that a given classical source is really unpredictable. Our quantum source and protocol is like a fail-safe. We’re sure that no one can predict our numbers,” Bierhorst says.
Researchers can measure a quantum system, but it’s hard to prove that measurements are being made of a quantum system and not a classical system in disguise. In NIST’s experiment, that proof comes from observing the quantum correlations between pairs of distant photons while closing the loopholes that might otherwise allow non-random bits to appear to be random. For example, the two measurement stations could be positioned too far apart to allow hidden communications between them; by the laws of physics any such exchanges would be limited to the speed of light.
Random numbers are generated in two steps. First, a long string of bits is generated through a Bell test, a process in which researchers measure correlations between the properties of the pairs of photons. The timing of the measurements ensures the correlations cannot be explained by classical processes such as pre-existing conditions or exchanges of information at, or slower than, the speed of light.
Other researchers have used Bell tests to generate random numbers, but the NIST method is the first to use a loophole-free Bell test and to process the resulting data through extraction. Extractors and seeds are already used in classical random number generators. In fact, random seeds are essential in computer security and can be used as encryption keys.
“The loophole-free Bell experiments show that the randomness is essential, if sending signals faster than the speed of light is prohibited, which is of course believed to be true. Our current work exploits this phenomenon to generate random numbers that are certifiably unpredictable under a minimal set assumptions,” Bierhorst explains.
Statistical tests of the correlations demonstrate that quantum mechanics is at work, and these data allow the researchers to quantify the amount of randomness present in the long string of bits.
That randomness may be spread very thin throughout the long string of bits. For example, nearly every bit might be 0 with only a few being 1. To obtain a short, uniform string with concentrated randomness such that each bit has a 50 percent chance of being 0 or 1, a second step called extraction is performed. NIST researchers developed software to process the Bell test data into a shorter string of bits that are nearly uniform with 0s and 1s equally likely. The full process requires the input of two independent strings of random bits to select measurement settings for the Bell tests and to seed the software to help extract the randomness from the original data.
NIST researchers used a conventional random number generator to create the input strings. From 55,110,210 trials of the Bell test, each of which produces two bits, researchers extracted 1,024 bits certified to be uniform to within one trillionth of 1 percent.
In the new NIST method, the final numbers are certified to be random even if the measurement settings and seed are publicly known; the only requirement is that the Bell test experiment be physically isolated from customers and hackers.
The research is described in the April 12 issue of Nature.