We’ve finally cracked how to make truly random numbers
SOURCE:New Scientist
From machine learning to voting, the workings of the world demand randomisation, but true sources of randomness are surprisingly hard to find. Now quantum mechanics has supplied the answer
Phillip Harris
Eeny, meeny, miny, mo, catch a tiger by the toe – so the rhyme goes. But even children know that counting-out rhymes like this are no help at making a truly random choice. Perhaps you remember when you first realised you could game the outcome by carefully choosing the starting point?
Flipping a coin, or rolling a dice, might be better, but try to prove that the outcome of your flip or roll is random and you will be stymied. That’s because these things aren’t truly random: if you knew the precise position of the dice or coin in your hand, the trajectory of the throw, the strength of gravity and subtle factors like air resistance or the friction of the landing surface, you could predict the result. True randomness is hard to come by.
The thing is, we now know that randomness is real, baked into the very fabric of the universe in the form of quantum mechanics. Given a choice of two paths, a quantum entity – like an electron or a photon of light – will take one entirely at random: there is no predictable cause behind a quantum effect. The Colorado University Randomness Beacon, affectionately nicknamed CURBy, takes advantage of this phenomenon. It came online this year as the world’s first publicly accessible source of traceable, verifiable, truly random numbers.
You might wonder who needs such radical randomness. After all, people have been happily throwing dice and flipping coins for millennia. But there are applications where it is essential to generate as much randomness as possible. “People don’t realise it, but without randomness, digital life wouldn’t be secure or fair,” says Nemitari Ajienka, a computer scientist with an interest in verifiable randomness at Nottingham Trent University in the UK. Every time you connect to a secure web page or generate a secure password, there is a level of randomness at play, he says. And machine learning has randomness built into the training.
Another use is supporting democracy. In Chile, for instance, politicians and public servants are subjected to random tax audits, and those chosen tend to object that the system is targeting them for a nefarious reason. “Everybody complains that it’s a witch hunt,” says Krister Shalm, one of CURBy’s creators at the US National Institute of Standards and Technology (NIST). Those claims are much harder to make if the system employs a randomness beacon whose numbers are derived from truly random sources.
At the moment, the Chilean government gets its randomness from analysing, among other things, and the output of the University of Chile’s radio station. But it still isn’t fully random: seismic activity happens for a reason, after all, and someone is deciding the radio station’s playlist. Nor is it fully traceable, given that people can’t routinely access seismic data. CURBy, though, is both.
Ten years ago, the system was “held together by duct tape and prayers”, according to Shalm. That was when the researchers behind it first made their painstaking proof of principle for CURBy. In the intervening time, they have been working to make the system fast, automated and ready for use – at any time – by anyone with access to the internet.
Now CURBy is a cutting-edge facility dealing with thousands of user requests every day. It could help shore up democracy, improve trust in judicial systems and even bring harmony to a family game night. “CURBy represents a working, publicly-accessible quantum technology. For me, this is an exciting development,” says Peter Brown, a physicist at the Polytechnic Institute of Paris.
“ People don’t realise it, but without randomness, digital life wouldn’t be secure “
Creating truly random numbers is tough. Very little in the universe operates by true randomness because, unless you are dealing with quantum stuff, there is always a mechanism behind the number generation. Even computers that produce “pseudo-random” numbers to create secure passwords can be gamed. The passwords are generated from a “seed” number, and if you know the seed and the algorithm, there is nothing random about them at all.
You could go further and use “high entropy” sources of randomness such as the unpredictable timing of a radioactive decay from a lump of material – cobalt-60 or strontium-90, perhaps. This is a random, quantum event, but one that is hard to make user-friendly. And unless someone is in the room with you, you can’t always prove that you didn’t just make up the numbers.
Physicists (left to right) Jasper Palfree, Gautam Kavuri and Krister Shalm entangling photons for random number generation
Rebecca Jacobson/NIST
It also makes for a rather dangerous game of Yahtzee – and with CURBy now available, there’s just no need to expose family members to radiation. Instead, CURBy relies on pairs of photons connected by a quantum phenomenon called quantum entanglement.
When two entities are entangled, they behave as if they are, in some respect, a single thing. This weird situation shows up when you perform a measurement on one of the entities, then carry out a similar measurement on the other. In certain circumstances, the first measurement affects the outcome of the second, even if the quantum objects have been moved to opposite sides of the universe and cannot possibly have exchanged any information. It is like rolling two dice and finding that if one turns up as a 6, the other always settles as a 1.
The entanglement between quantum objects, famously dubbed “spooky action at a distance” by Albert Einstein, defies common sense: it occurs without any signal being sent between the two. No one has ever come up with a physical mechanism for how it happens.
Inside CURBy, the entanglement shows up in measurements of a property called polarisation. Pairs of entangled photons are separated and sent through optical fibres to two destinations 100 metres apart. At each location, the apparatus measures the polarisation, with only a very short time elapsing between the two measurements.
Next, the results of the measurements are “correlated”: there is a subtle relationship between the outcomes, whose extent CURBy can analyse. Under “classical” conditions, there is an upper limit to this extent, but if the behaviour is truly quantum, and therefore random, the limit is exceeded and can be used to produce random numbers. This is done by “purifying” the inherent randomness using a technique called Trevisan extraction. CURBy can make around 250,000 polarisation measurements per second, and it takes around 15 million measurements to produce its end product: a string of 512 truly random binary digits, or bits, that people can use however they wish.
Rolling dice is never truly random
RLBPhotography / Alamy Stock Pho
If you want to know exactly how random those bits are, there’s an algorithm for that. Given that there are 512 bits in a string, and each bit can be 0 or 1, that means there are 2512 possible combinations. “It’s a massive number of possibilities,” says Shalm.
All of them should be equally likely to crop up, and Shalm and his colleagues have been able to measure the likelihood of a particular string of bits appearing. It isn’t perfectly even, but it might as well be. Think of it as wanting a road that’s completely flat. If the gradient is 1 in 10, that’s a steep hill. Even 1 in 100 – 1 metre of rise in 100 metres of road – is noticeable. The gradient equivalent to CURBy’s randomness is 1 in more than 184 quintillion: as random as anyone needs.
Proving randomness
The randomness isn’t CURBy’s only selling point – in fact, the main thing is that anyone can trace the numbers back to where they came from and prove they are random, says Shalm. “There isn’t currently a good way to do that with any kind of random number generator,” he says.
To make their randomness traceable, the CURBy researchers have borrowed from the blockchain mathematics used to guarantee the security of digital assets like NFTs and cryptocurrency. It is essentially a way of verifying what was done when and by whom – in a scenario where nobody trusts anyone – and everything can be traced right back to the original output from the experiment.
The other factor that makes it hard for anyone to game the system is that the whole process is distributed among a range of institutions. NIST passes the quantum data to apparatus at the University of Colorado Boulder for processing, and then an independent cryptographic service known as the Distributed Randomness Beacon Daemon adds its own set of ingredients to extract the true randomness contained in the measurement data and convert it into the final, uniform binary string.
“It’s almost like a spider’s web of connected, time-ordered things,” says Shalm. “No one party has complete control over what the random bits are, and you can go back and see if anybody cheated or tried to change things around.”
The integration of all the necessary physics with high-level security analyses is “quite remarkable”, says Brown. Quantum technologies are generally still very much in a developmental stage, he points out, with few complete products available. But will CURBy be useful? Undoubtedly, says Brown – although there are applications where you definitely shouldn’t use traceable randomness. “You don’t want to choose your passwords based on a public source of randomness,” he says.
But the selection of jurors and judges for cases, the generation of lottery results and randomised sampling in clinical trials are some examples of where traceable randomness would be a boon. University of Oxford mathematician Artur Ekert is also impressed. The way the CURBy team has blended quantum and classical physics to create a cutting-edge but accessible technology is a sign of things to come, he says.
In fact, says Shalm, CURBy is itself explicitly designed to be compatible with other technologies coming down the line. In other words, true randomness is going to be built into all our futures, making the world a fairer and safer place. It sure beats a coin flip.
