Most digital security relies today on random numbers to generate cryptographic keys. Think of a cryptographic key like a long, complex password. If that password is truly random, an attacker has to guess every possible combination. But if the ‘random’ process used to make that password has a pattern, the attacker can use that pattern to skip billions of guesses.
Digital security has an Achilles’s heel: the numbers it uses for encryption are rarely as random as they seem. But in a study published in Nature, researchers at ETH Zürich have demonstrated a new solution called randomness amplification, where they used quantum physics to turn predictable bits of data into certifiably perfect randomness.
A note from the university said the researchers had effectively “generated certified perfect randomness for the first time”.
Creating true randomness is actually really difficult. Most random number generators (RNGs) produce bits with a small bias. Say you’re flipping a coin that lands on ‘heads’ 51% of the time instead of 50%. That 1% difference is a bias.
Santha-Vazirani limit
In 1986, computer science researchers Miklós Santha and Umesh Vazirani showed that a classical computer cannot upgrade a weakly random source into a perfectly random one. Put another way, if a source of random numbers is predictable even in a small way, classical post-processing alone could never eliminate it. So if you give a classical computer a biased coin, any data it produces based on that coil will remain just as biased and predictable, no matter how much the computer tries to improve on the input. This is why even high-end random number generators suffer from experimental imperfections — like heat or electronic noise — that make their outcomes slightly biased, and thus predictable to an advanced attacker.
“Even modern random number generators, which are based on quantum mechanical effects like the reflection of photons from beam splitters, are not entirely immune to such a systematic error or bias,” Andreas Wallraff, one of the study’s lead investigators and and Laboratory for Solid-State Physics professor, said in the note.
Over the last two decades, theoretical work has suggested that quantum physics may provide a workaround. In fact, in 2012, Roger Colbeck and Renato Renner — who is one of the authors of the new study — showed in theory that quantum physics could do it.
The ETH Zürich team achieved it using a Bell test, a physics experiment designed to prove a phenomenon called quantum entanglement. Entanglement is a state where two quantum particles — like atoms or photons — become linked such that a measurement performed on one particle instantly affects the other, no matter how far apart they are.
In a Bell test, two entangled particles are separated and measured. If the particles answer in a particular highly correlated way, it will show that the answers were not secretly decided in advance. In other words, the test will prove the universe itself did not know the answer until the moment the measurement happened.
Now, in quantum physics, the act of measuring something creates new information that wasn’t there before. For example, each of the two particles will be in a superposition of multiple states. When you measure one, it will collapse into one particular state — and so will the other entangled particle. This ‘final’ state is the new information.
Because this information is born at the exact instant of measurement, it is impossible for anyone to have known the outcome in advance. In the work, the team used this information as an additional source of randomness.
Quantum advantage
In their experiment, the team members entangled two particles, then placed them 30 m apart. This distance made sure the particles could not ‘cheat’ by communicating their ‘final’ states to each other at the speed of light.
Next, they used random biased bits to decide how to measure each particle. Then, with the measurement outcomes, they calculated the Bell violation score — a measure of how strongly the particles were entangled, and thus how clueless the universe might have been about the measurement outcomes. The score was 2.271.
This was above the classical limit of 2, meaning quantum physics rather than classical physics was in play. (Entanglement is a purely quantum phenomenon.)
“It is a clean instance of quantum advantage: a task quantum physics performs that classical physics provably cannot,” Marin Ivezic, founder of research-driven consulting firm Applied Quantum, wrote on his site.
However, the highest score quantum physics allows is 2.82. And the closer an experiment gets to this value, the stronger the evidence that the particles are behaving according to quantum physics alone rather than also being influenced by bias. In a lab, stray heat, microscopic timing errors, and other subtle factors can create noise that biases the particles in small ways. And an attacker who understands the specific noise in a setup might notice that when the system glitches, it tends to produce a ‘1’ more often than a ‘0’, and use that to their advantage.
The researchers now had two resources: the original random biased bits and the new outcomes from the Bell test. They combined both using a mathematical tool called a two-source extractor. Its purpose is to blend two independent strings of data. Independent means knowing anything about String 1 must reveal nothing about String 2, and vice versa.
The extractor is designed so that if an attacker has a slight advantage in predicting String 1 and a slight advantage in predicting String 2, they have zero advantage in predicting the combination. The extractor achieves this by cancelling the strings’ individual biases out as long as they are independent.
In their tests, the researchers worked with 5.3 billion random biased bits and 2.6 billion bits of information from the measurements. They combined them in 1.3 billion trials, which they ran at 50,000 times per second over nine hours. At the end of each trial, the extractor output was 45 million bits — all purely random. The rest got pruned away because they were biased information or noise.
“The resulting sequence of zeros and ones is now really perfectly random, and we can even certify that,” Prof. Renner, a professor at the Institute for Theoretical Physics at ETH Zürich, said in the note. The certificate is the Bell test score.
“The technical improvements allowed us, for the first time, to create random numbers that will remain perfectly random for all eternity — no matter what analytical methods are used to assess their randomness,” Prof. Renner added.
One in a trillion
The team also said their protocol to generate purely random numbers is device-independent — a gold standard in security that means even if you don’t trust the person who built the hardware, even if you don’t fully understand how the machine works, you can trust the output to be random.
In physics, it is mathematically impossible for a classical theory to score higher than 2 on a Bell test. By scoring 2.271 on the test, then, the researchers’ setup proved it was producing random quantum information.
That said, according to the team’s security analysis, the protocol has a failure probability of one in a trillion, similar to flipping a coin and getting ‘heads’ 40 times in a row. This is because of the number of tests, 1.3 billion. If they had conducted several billion more, the researchers may have reduced the failure rate to one in a quadrillion or quintillion. It is mathematically impossible to reach 100%.
In fact, the researchers had chosen one in a trillion as their finish line. And to reach that level of certainty with a score of 2.271, they had to discard a large amount of data in the end. If their score had been higher, they could have reached the same failure rate while keeping much more of the data.
While one in a trillion suffices for practical applications, the experiment’s apparatus can’t yet replace conventional random-number generators. First, it is complex and resource-intensive. Its randomness output is modest compared to commercial systems: around 1,400 bits per second versus 1 billion bits per second. It is also information-wise inefficient in that for every 119 “almost perfectly random” bits it consumed, it produced 1 “certified random” bit — whereas commercial generators produce a very large number of “almost perfectly random” bits from just one “somewhat random” bit.
But while the new protocol is slower and less efficient, it can produce randomness of a higher quality. That is, the work establishes that randomness can be amplified in lab conditions, that too in a device-independent way. It also proves the Santha-Wazirani limit can be broken by quantum physics.
Beacon of randomness
“My understanding is that the main advance here is not device-independent random-number generation per se. That has already been demonstrated using … Bell tests,” Urbasi Sinha, head of the Quantum Information and Computing lab at the Raman Research Institute, Bengaluru, told The Hindu. “The new element is the experimental demonstration of device-independent randomness amplification: starting with a weak, imperfect source of randomness and using quantum correlations to certify output bits that are unbiased under the stated model.”
“This is significant because practical quantum random-number generators are never ideal, and in our own work on QRNGs and semi-device-independent certification, we have also emphasised that the real issue is not whether a bit string passes statistical tests but whether its unpredictability can be certified from clearly stated physical assumptions,” she added.
“The important caveat is that the guarantee here is conditional on the Santha-Vazirani weak-source model, the claimed bias bound on the input randomness, the … Bell-test implementation, and the validity of the extractor/security analysis.”
The researchers proposed one application: a public randomness beacon — a service that broadcasts certified random bits for uses ranging from financial transactions and blockchain protocols to military encryption. The U.S. National Institute of Standards and Technology already runs a service where it releases 512 random bits every 60 seconds on its website. They are used in lotteries, to assign juries, to sample voting machines, and for research.
That said, Mr. Ivezic cautioned in his write-up that while certifiable randomness could help security today, it will not help protect encrypted information against attacks by future quantum computers.
“Better randomness was never the answer to that problem,” he wrote; “migrating to post-quantum algorithms is.” India recently took its very first steps on this front.
mukunth.v@thehindu.co.in
