And if it’s confident that it knows you, it won’t even ask you to check the box.
I’m mainly commenting here to remind myself to get back to this, but it should be noted that certified randomness generation isn’t just generating a random number, it’s generating randomness that you can be sure couldn’t be replicated by a classical device, and that’s secure against possible adversaries, like eavesdroppers. This leverages quantum tasks that are infeasible to implement using classical hardware, so it’s in that sense a bona fide useful (to the extent you need that kind of randomness) application of current quantum computing hardware.
Basically, the situation is that we have certain tasks where current quantum computers outperform any classical systems, but broadly speaking, these answer questions nobody’s ever asked. The certified randomness protocol is a way to get something useful out of that capacity, namely cryptographically secure random bits.
ETA: Or I could just use this space for the regular reminder that for every quantum computing claim out there, your best bet is to just check Scott Aaronson’s blog: Shtetl-Optimized » Blog Archive » On the JPMC/Quantinuum certified quantum randomness demo
Although as a notice, he’s one of the inventors of the original protocol.
Yes and no… The gold standard for true randomness is various sorts of devices based on quantum mechanics, but even a really good quantum RNG is still far simpler than anything that could be called a “quantum computer”.
Real true random numbers are a lot harder than often appreciated. Numerical random number generators aren’t random. That much is easy. Indeed deterministic behaviour is required in many uses.
Trying to get really good randomness out of physical processes is not trivial. The often overlooked problem is intrinsic auto correlated noise in your detector. A simple and efficient source can be a zener diode suitably biased feeding a comparator. The output can be sampled as ones and zeros as needed.
But even ignoring the underlying physics of the noise, how good is your comparator? How resistant to noise on the supply rails is it? Similar question about the level you compare against. And the simple clock. All the care in the world picking a stochastic noise source can be ruined by power supply or clock noise reaching the comparator. And you may not notice. But a suitable long term analysis of the random values generated can find correlations of that contamination.
So whenever I see claims made about new fabulous random value generators I am always sceptical.
You see claims about ridiculous performance that can be undone with levels of correlated noise contaminating the real life implementation that would otherwise be considered near perfect.
That wall of lava lamps? Anyone checked the illumination lights for flicker? Fabulous source of double mains frequency contamination. I would not be surprised if there is per-bit and cross bit correlation between samples with mains frequency related energy. Similar problems can come from the camera sensor. Claiming 64 bits of pure random is a very high bar.
(This relates to the oft misunderstood phenomenon of sampling information below the noise floor. Shannon places no lower limit on the amplitude from which you can extract information in a channel. You can trade off information rate to get as far under the noise as you like. The limit is the bandwidth signal to noise product. Getting down low does amusingly require good random noise and exactly the care in the detector as above. (My favourite real life example is GPS.))
Mostly these levels of entropy don’t actually matter for the real world. The leverage gained from finding such problems isn’t huge. But it exists, and reduces the actual entropy enough that claims about “perfect” randomness should always be called out.
The interesting part here isn’t really the mere fact of random number generation, but the certification of these random numbers as really just generated—i.e. not drawn, for instance, from some pre-generated list. Essentially, you come up with a classically hard problem (sampling a random quantum circuit), which you then execute on a quantum computer, and if you get an answer quickly, you know that there’s no classical way that this answer could’ve been generated, plus you can check whether it’s a valid answer to the problem you posed. The inherent randomness of quantum mechanics gives you the random bits, and the fact that they must match the problem you submitted that couldn’t have been spoofed classically in the available time ensures that it’s from a truly quantum source, and hence, genuinely random.
Another way to convert a biased d10 toss (b) to a uniform random d10 toss (u) :–
For each toss b of the biased d10, grab an unbiased d10 equivalent (c) from an ordinary PRNG. Now simply set u = 1 + ((b + c) mod 10)
That’s no good: If you care about the distinction between a PRNG and a true RNG, then you’re implicitly assuming that the output of the PRNG is predictable. In which case the moduloed sum is still exactly as biased as the original die roll (just biased to a different number).
Any true debiasing scheme must involve some cases where you throw out some rolls, and the more truly-biased your original roll is, the more common that will be. Like, in the coin debiasing technique @Dr.Strangelove described, if you were to try it with a double-headed coin, you’d end up throwing out all the rolls.
Notably, even that does still depend on the assumption that every roll is independent of all others (that is, the probabilities of different outcomes of a roll must not depend on the outcomes of prior rolls). This is not necessarily true in all cases: For instance, a sort of rigged die called a “tapper” would be biased to roll the same number again (unless you “set” the die to some other number by tapping it against the table).
The problem is easy if you consider the information. A true fair coin gives exactly 1 bit of Shannon entropy. A biased die gives less than 1. So you need to flip more than once, at the very least. And possibly many times if the coin is extremely biased. A two-headed coin has 0 bits of entropy.
The approximate scheme I described above basically turns a linear bias term into a quadratic one. So, a 1% bias becomes roughly 0.01%. A pretty nice improvement but it’s not truly unbiased.
Even the state lotteries have no true random number generators. I like to play keno and my sister had a job for the lottery. She wasn’t supposed to tell me, but she is gone now.
They have several programs attempting to emulate random numbers. These are large programs full of apparently randon numbers but the are not. These programs are changed several times at unknown intervals.
That is the best they can come up with.
That makes no sense to me. For generating lottery numbers, a commercial hardware RNG based on Zener noise or free running oscillators should be sufficient. Such devices are dirt cheap, and certainly better than hard-coded tables that could be stolen or leaked. And where does the table data come from?
I’m curious how this plays out as a practical matter. Maybe sampling the flicker of one lava lamp is doable but there are 100 there. (I am also not sure the flicker even matters from reading how they do it…another discussion.)
Put another way, could anyone (say NSA with all the money and computing power they can lay their hands on) have a reasonable chance at hacking lava lamp random numbers to defeat their encryption?
They just have a webcam pointed at the wall.
They say it’s a “secondary” source, which basically means it’s just a (fun) stunt.
Anyway, “whitening” (eliminating all of the various biases) is an easy process and can be combined with stretching (using a small number of bits to produce a large number of them).
I don’t think it’s quite as black and white as this, though.
Suppose you want to send people down a branching path (metaphorically or not). Each time they come to a junction, they flip a coin and go left or right. Suppose also that you want an even mix of left vs. right branches (to keep the wear on the paths even), but also make it hard to follow someone (i.e., they can’t predict the path in advance).
A somewhat biased coin xor PRNG is fine in this case. There’s enough true randomness to make path-following hard if there are many branches. But the whitening from the PRNG keeps the load even.
I’m not surprised. It occurred to me that a bad actor walking in with a hammer and smashing those lava lamps (they are in their lobby) would wreck their encryption in a minute. They certainly have a more robust system.
As you say, it is just a cool stunt.The real work is elsewhere.
Even smashing up the lava lamps wouldn’t matter. There’s enough shot noise in the camera sensor to provide enough randomness. They could even put a lens cap on the camera. Smashing the camera would be a problem, though.
The attack I’d worry about is someone walking into that public lobby and presenting something in the camera’s field of view that would cause it to generate particular numbers. Maybe a really bright light source, so all of the sensor elements in the camera saturate.
The issue is if your x bits of random has some cross sample or intro sample correlation, it reduces the actual entropy present. To make use of this you need a model of how this might manifest itself. If you can produce a model it might guide prioritisation of choices of parameters used to attack a cypher text.
Any sort of leverage that reduces the number of attempts needed to brute force encryption is a win. The whole defence against brute forcing is the compute time needed. If, rather than just starting with a key value of zero and trying every value onwards, you have a generator function that uses even quite small biases in the pattern of bits to search the slightly more likely keys first, you may bring brute force attack within practical bounds.
Much breaking of encryption depends on such tiny flaws. Maybe the 64 key only contains 60 bits of entropy. If you know why, that could result in 16 times less effort to break.
Famously Turing realised that because an Enigma machine couldn’t code a letter to itself, this provided leverage to decryption. It still needed a lot of effort and time to search the key space. But tiny gains like this brought brute force into tractability.
With the lava lamps you might be able to use knowledge of small biases in the system to find correlations. The manner in which the camera scans the field, flicker in the lighting, and slight differences in camera sensitivity might mean that some parts of the image field contain local biases and correlations. You might be able to model this if you had access to a good number of generated numbers, or maybe just from access to the physical setup for long enough to take some pictures and video.
It would be a really fun project to see what defects actually exist.
Would observing Brownian motion come up with unpredictable results? And thus be random?
The math on that link is beyond me, and I do not see a firm conclusion, aside from:
[Off topic]
I once had an idea for an art project to fly kites off various high points in my city, each equipped with a microphone, and use the ambient noise recorded to change colours in a series of large glass tubes by adding ink and slowly moving the water through a filter, so colour change would be gradual. Obvious some predictable events like rush hour traffic would mean this project would not be random - but that was part of the point. It never got off the ground, so to speak.
Ya beat me to it. I think that’s very cool. And it’s just fun.
While the particles are considered suspended in the fluid, they might be denser than the fluid and gradually sink down over time. That’s a problem. Another issue is the resolution of the detector to motion. There has to be cut off for detecting a particle’s motion which affects the distribution. If this isn’t taken into account in doing the stats, that might skew things.
(I am slogging thru the Xarchive paper linked above. I am noticing some things that I consider abuse of language and over generalization. There seems to be ways to inefficiently generate random strings that pass the quantum program’s test. Something that may not be made clear here. Worse, I have doubts about doing the same but efficiently.)