Perfect Randomness Realized For the First Time (phys.org) 138
ETH Zurich researchers say they have generated certified "perfect randomness" for the first time by using a quantum Bell-test setup with two entangled superconducting chips connected by a 30-meter cooled link. "In the long term, this work could play a similar role in digital security as atomic clocks do for timekeeping: a physically certified source of randomness that other systems can rely on," reports Phys.org. "Possible applications range from the encryption of sensitive communications and digital identities to public randomness services for lotteries and blockchain applications." From the report: They call their method randomness amplification. "This was made possible by an improved so-called Bell-Test with simultaneously high quality and high data rate," says [Renato Renner and Andreas Wallraff]. He and his coworkers use a complex setup that consists of two superconducting chips, which they cool down to very low temperatures close to absolute zero. Each chip represents a quantum bit or qubit, which can take on the states "0" or "1" or any arbitrary superposition of these states. A 30-meter-long tube, which is also cooled down, connects the two chips.
Microwave photons can fly back and forth between them, thus creating quantum mechanical entanglement. This means that a quantum measurement on one qubit, which randomly yields the values "0" or "1," influences automatically and at a distance whether "0" or "1" is measured on the second qubit. The separation of 30 meters ensures that, during the measurement, even at the speed of light, no information can be exchanged between the qubits. This would disturb the perfect randomness.
Wallraff and his team made the choice of the exact type of measurement (or "measurement basis" in technical jargon) on the two qubits depending on an imperfect random number generator. Renner's coworkers could then amplify the randomness of the measurement results further using a special algorithm. "The resulting sequence of zeros and ones is now really perfectly random, and we can even certify that," says Renner. He likens this result to crossing a ridge: "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." The findings have been published in the journal Nature.
Microwave photons can fly back and forth between them, thus creating quantum mechanical entanglement. This means that a quantum measurement on one qubit, which randomly yields the values "0" or "1," influences automatically and at a distance whether "0" or "1" is measured on the second qubit. The separation of 30 meters ensures that, during the measurement, even at the speed of light, no information can be exchanged between the qubits. This would disturb the perfect randomness.
Wallraff and his team made the choice of the exact type of measurement (or "measurement basis" in technical jargon) on the two qubits depending on an imperfect random number generator. Renner's coworkers could then amplify the randomness of the measurement results further using a special algorithm. "The resulting sequence of zeros and ones is now really perfectly random, and we can even certify that," says Renner. He likens this result to crossing a ridge: "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." The findings have been published in the journal Nature.
Wow, Random ! (Score:4, Funny)
Re: (Score:2)
Totally !
Typical Slashdot first post comment with regards to an article about generating reliable randomness.
Re: (Score:3)
I know! It's so random!
Re: (Score:2)
I know! It's so random!
I can recollect a video of a machine built for a casino as I recall, but I might be wrong. Its purpose was to constantly generate truly random numbers.
Essentially a very large number of quality dice was automatically rolled and finally fell into a row, a horizontal tray actually, to define the result of the dice. The tray itself was part of a conveyor belt and the the dice traveled vertically upward, and each row of dice was captured with an OCR camera to convert into a random number. But I can't find the v
Re: (Score:2)
... each row of dice was captured with an OCR camera to convert into a random number ...
I hope they were using base 6 :-)
Re: (Score:2)
... each row of dice was captured with an OCR camera to convert into a random number ...
I hope they were using base 6 :-)
Solid point, but wouldn't that somehow make the entire exercise moot? Because that wouldn't result in a truly random and acceptable number? I suppose you can add a computer to translate, somehow, between Base 6 and Base 10, but I don't think so, (and I'm way out of my league here. A man's got to know his limitations [youtube.com]).
Re: (Score:2)
... each row of dice was captured with an OCR camera to convert into a random number ...
I hope they were using base 6 :-)
Solid point, but wouldn't that somehow make the entire exercise moot? Because that wouldn't result in a truly random and acceptable number? I suppose you can add a computer to translate, somehow, between Base 6 and Base 10, but I don't think so, (and I'm way out of my league here. A man's got to know his limitations).
Let's assume the dice faces are random. We have six possible faces. Numbers in a base 6 representation (0-5) conveniently match perfectly. For the given number of dice, the number of digits, all possible numbers in the range are represented. How are they not random? Yes they would need to be converted to decimal, binary, etc depending on the use.
If we interpret the digits as base 10, we are only using 6 out of 10 possible digits. We have gaps in the range. That doesn't seem random. Some values having a z
Re: (Score:2)
You don't interpret the number of dots on the dice faces as digits in base 10, you convert the dot patterns to whatever base you want.
Re: (Score:2)
I hope not. That would have been a problem, as zero isn't represented on a die.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
When is a one not a one?
When it's warm, because according the Property of Ones [hrwiki.org], a one that is not cold is scarcely a one at all.
Re: (Score:2)
>I hope they were using base 6 :-)
I hope not. That would have been a problem, as zero isn't represented on a die.
>I hope they were using base 6 :-)
I hope not. That would have been a problem, as zero isn't represented on a die.
There are 6 faces on the dice. What symbol is on the faces are irrelevant, all that matters is that they are unique so they can be mapped to 0-5 in some manner.
Re: Wow, Random ! (Score:3, Funny)
Re: (Score:3)
There are dozens of us!
You mean there are 10s of us
Re: (Score:2)
Re: (Score:2)
Probably Dice-O-Matic: https://www.youtube.com/watch?... [youtube.com]
Enjoy!
That was so long ago as evidenced by the timestamp! No way! Am I that old already?! I think its awesome you managed that citation! 17 years? No way!
BTW: Serious question because someone seriously wise and learned long ago replied to a comment I once made with EXCELLENT advise about LED's for home lighting, but I can longer find the comments, and I'm certain it was in the last 6 years or so, but slashdot seems to have comment retention limits -- and I trusted slashdot, and I was stupid and lazy for doing so.
Re: (Score:2)
I told the person that replied to me they were a God, if that keyword helps. Muchos gracias to anyone in advance that even considers making an effort to assist me. Nerd.
Re: (Score:2)
Re: (Score:2)
Re: (Score:3)
Sounds like an interesting device. However, ALL dice are imperfect, no matter how much is spent on their quality. They will always be biased in favor of some faces and against others (though it is different what gets favored from one die to the next). Humans don't have the technological capacity to machine a perfectly balanced die, and even if we did, after a little use the natural wear and tear would bias it.
So this machine may have generated "pretty good" random numbers, they were not truly random.
Predictable (Score:2)
Totally !
Typical Slashdot first post comment with regards to an article about generating reliable randomness.
So its predictable :-)
Re: (Score:2)
Totally !
Typical Slashdot first post comment with regards to an article about generating reliable randomness.
So its predictable :-)
I'll opine even more so. Its typical.
Can someone help explain "perfect" randomness? (Score:5, Interesting)
I'm curious as to how this is more random than previous sources of randomness we use, specifically the development and recording of electrical shot-noise, or using a source that exhibits completely chaotic interaction with environments - pointing a camera at a lava lamp.
How were they not random enough to be considered perfect?
And I guess while we're at it, do we really truly need an even more perfect random number for cryptography? I'm not aware of any attacks that have broken cryptography by attacking hardware random number systems (though there are those who have exploited poorly implemented software pseudo-RNG)
Re: (Score:2)
Im wondering the same thing.
In Bhuddism a central philosophy is everything is dependent on conditions. So whatever number comes out of this clever thing is dependent on the conditions the clever thing was subject to. Those conditions are sufficiently complex that it is unpredictable when they would occur again.
Maybe that's what perfect random is, sufficiently unpredictable?
We need a Math guy or gal, they'll know.
Re: Can someone help explain "perfect" randomness? (Score:2)
Re: (Score:2)
It wouldn't. Bell's inequality has several assumptions. People are still writing papers about what exactly they are. Bell himself spent decades writing papers on the topic.
The big three are realism, locality and independence. Roughly, realism is hidden variables, locality is no faster than light communication and independence is the magical ability of two things to never be influenced by each other or any common cause. At least one of these assumptions cannot be true if Bell's inequality is not satisfied.
Yo
Re: (Score:2)
Humans have a hard time accepting true randomness as even being possible. A famous example being Einstein's criticism of the emerging claims about random behavior at the quantum level "God does not play dice with the universe." Many people really, really want the universe to be this ordered, deterministic, machine. It sounds like the same goes for whatever old Buddhists cooked up this doctrine that everything is dependent on conditions.
I observe that this statement is true, at a practical level, most of
Re: (Score:2, Interesting)
It is not even known to be unpredictable. That is just what the theoretical model claims, not any observation about actual physical reality. If you want quantum-randomness, you can get that for about $10 in hardware, with claims exactly as valid as those from this non-story.
Re: (Score:2)
Re: (Score:2)
Even anciently, some Buddhists believed in the supernatural and others didn't.
Re: (Score:2)
Let's consider the definition of religion -
an organized system of religious attitudes, beliefs, and practices. Check
the religious be
Re: (Score:3)
Re: (Score:2)
https://en.wikipedia.org/wiki/Buddhist_deities
Re: (Score:3, Insightful)
Listen to almost any Trump speech. :-)
[Totally perfect, only the best randomness - like no one has ever seen. ]
Re:Can someone help explain "perfect" randomness? (Score:5, Interesting)
Probably because true randomness is different than "too many parameters to account for".
The physical interactions you described follow precise laws, it's just that there are way too many interactions to be realistically predictable in real time... for now.
The randomness described in the article derives directly from the statistical nature of quantum physics, so it's non-deterministic by design.
Now to be fair, all deterministic "traditional" physics is an emergent phenomenon of non-deterministic quantum physics, but that would be ahuge digression I don't have the time and energy for right now...
Re: (Score:2)
Well your reply focuses on chaos from the lava lamp, but shot noise is also truly random in nature and that randomness... it actually a form of "quantum noise". So why does measuring that not produce perfect randomness and haven't we already done that in the past?
Re: (Score:2, Informative)
My ten seconds of research on the topic turned up this: [wikipedia.org]
Which sounds like the 'deterministic traditional physics as an emergent phenomenon of non-deterministic quantum physics' that the OP described.
IOW, although shot noise results from quantum interactions, it comes after the wave functions have collapsed, and we could theoretically predic
Re: (Score:2)
My ten seconds of research on the topic turned up this:
You didn't look at CCDs
All of this is a guess, of course, to the point where I'm not even going to sign my name to this post ...
Look at CCDs and you can sign the next one
Re: (Score:2)
There's nothing deterministic about the noise produced in CCDs. On your previous link it specifically discusses the implications of noise when QE 1
Re: (Score:2)
You are heading down the right path.
A book that made things more clear for me is "Non uniform random variate generation" by Luc Devroye (https://www.cs.fsu.edu/~mascagni/Devroye.pdf).
The generation of different distributions can be done algorithmically, but the algorithms get to the core of the processes making the noise. E.G. 1/f noise can be made from summing many exponential decaying functions. Electrons falling in holes in silicon - same thing. So we have 1/f noise in silicon. The type of process determ
Re: (Score:3)
Re:Can someone help explain "perfect" randomness? (Score:4, Interesting)
Quantum mechanics is very well understood. Every particle in a configuration has an associated wave function. When squared that wave function now represents a probability distribution of where the particle will be when you collapse the wave function. You can set up configurations that create particles with a wave function with two distinct equal peaks. Collapse it like in a Stern-Gerlach experiment, and you get a completely random bit stream.
Nuclear decay is also completely random and driven by quantum effects. The time between decays in a sample is completely random and we know what the probability distribution curve is for most isotopes. That allows us to normalize it into the 50:50 random bit stream with some math.
Now getting enough throughput of random bits is an engineering issue and for virtually every case the $/ random bit per second has far exceeded cheaper methods that get you 99% of the way to true randomness.
Re: (Score:2)
The physical interactions you described follow precise laws, it's just that there are way too many interactions to be realistically predictable in real time... for now.
No.
Diode shot-noise output is demonstrably based in large part upon quantum effects. There is also some determinism in there, but mixed in with a lot of true randomness.
As a practical matter, getting enough output from a noisy diode and then compressing it with a cryptographic hash function is equivalent to perfect true randomness. This work is a cool achievement, but it has no practical benefit over the systems we use today... systems that are built into most modern CPUs.
Re: (Score:3)
It's not that. Junction noise is believed to be truly random, governed by quantum physics, and impossible to predict.
The question is, can you prove it? That's what they have done here - created a system that is provably random, not just strongly suspected to be by our current understanding of quantum physics, and a review of the measurement hardware.
Re:Can someone help explain "perfect" randomness? (Score:5, Interesting)
Regarding hardware RNGs: Theodore Ts'o (of Linux fame) begs to differ. https://daniel-lange.com/docum... [daniel-lange.com]
Re: (Score:2)
Regarding hardware RNGs: Theodore Ts'o (of Linux fame) begs to differ. https://daniel-lange.com/docum... [daniel-lange.com]
I don't think he does beg to differ. Nothing on that page discusses and attack on the randomness produced by random number generators, it explicitly postulates a backdoor which can exist in any implementation including the one described in TFS.
Re: (Score:3)
Ah, no. That is about a HW randomness generator that may not actually be one and about Intel using a compromised design that makes it very hard to find out. And then lying about that.
Re: (Score:2)
Re: (Score:2)
From a hardware point of view are you suggesting that while shot noise may be truly random in nature, the act of recording it introduces a bias?
Re: (Score:2)
Truly random doesn't necessarily imply a uniform distribution.
Re: (Score:2)
Doesn't the law of large numbers account for this? If something is truly random by the law of large numbers doesn't it by definition have a uniform distribution?
Re: (Score:3)
The problem is for crypto, you need high per-bit entropy (or rather high per-bit unpredictability under reasonable conditions). But all this means is that you gather, say, 10kBit from your generator and then make a 256 bit key from that using a mixing process. Crypto-hashes are perfect for that. A CPRNG already does something like that for you and you just put in the 10kBit (or more) as seed.
Re: (Score:2)
No, the law of large numbers says that if you take lots of samples then the sample average will be very close to the underlying expected value, but it doesn't say that the underlying expected value of a binary valued random variable must be 0.5. To take a simple, albeit obviously pessimising, example, if we take two truly random uniform bit generators then we can combine them with bitwise AND to get a truly random bit generator with expected value 0.25.
Re: (Score:2)
Bias is not a problem. You just gather more and hash it together.
Re: (Score:2)
Famouly, Cloudflare has a lava lamp random generator in a wall in its HQ, but they don't use it anymore.
Re: (Score:3)
and waves in Lisbon HQ
https://blog.cloudflare.com/ch... [cloudflare.com]
London have double pendulums and Austin, Texas have translucent rainbow mobiles
https://blog.cloudflare.com/ha... [cloudflare.com]
radioactive decay of a uranium pellet via a Geiger counter in its Singapore (no official post about it, it should not be as pretty, you actually may not be even allowed to be next to it! )
It is not the main source of randomness anymore, now it use hardware RND in cpus, much faster... but they are STILL used as a secondary source to inj
Re: (Score:2)
Which always was a stunt. Most of the randomness in there came from the noise in the camera sensors, not the lava-lamps. Pretty nice stunt though.
Re: (Score:3)
Lava lamps (like Cloudflare actually use as part of their RNG, IIRC) might
Re: (Score:2)
I'm assuming that when they do one of those distribution plots of the output values (the ones that show clear patterns for pseudo random generators when run for long enough) they can prove that the distribution is totally uniform, and with time as a further axis, every attempt achieves that even distribution in a different sequence. That implies they can account for, or negate the impact of, every potential variable in the system.
Ah, no. That is totally worthless for this purpose. For example, the Mersenne Twister MT19997 passes this test perfectly, but with a few KB of its output you can predict all further output. Incidentally, only really bad and outdated PRNGs show such patterns. These days, statistical measurements are essentially useless to prove randomness. But these are Physicists, so they may not understand that. What you need is mathematical proof. Obviously, you can never get that for a physical system because that would
Re: (Score:2)
Simple: This is not better. The whole thing is hot air and lies.
Re: (Score:2)
Re: (Score:2)
I don't understand how they did it, but that is what they are claiming.
Re: (Score:2)
Indeed, but other elements of random number generation don't rely on imperfections creating bias. I come back to shot noise which itself is a subset of sources of "quantum noise". Maybe the answer is we have no way of measuring shot noise without introducing a bias? But the fundamental principles seem to be truly random already.
Re:Can someone help explain "perfect" randomness? (Score:5, Informative)
I skimmed a few of the referenced papers back to something in 1986.
It turns out that the practical implementation of a theoretical perfect (quantum) random bit generator (the example given in one paper was a zener diode[1]) always has some skew. This might vary over time but, for example, a random bit stream that is biased to more ones than zeros over the last 10s is more likely than not suffering from some temporary bias that an attacker can at least theoretically use.
Using classical physics it's possible to remove this bias so that you have a pseudo-random stream that is, for all practical purposes perfect however it's (apparently[2]) provable that doing this in the classical domain is theoretically open to attack due to the original bias.
What this has done is allowed a quantum process to do that post filtering so that even the theoretical attack on the pseudo-random stream driven from an almost perfect RNG is gone.
[1] example here - different paper:
https://www.researchgate.net/f... [researchgate.net]
[2] I took it on trust - one paper said it was proved in another referenced paper, I didn't try to check if it really did say that and I certainly didn't even try to follow a proof...
Re: (Score:2)
It isn't clear what "perfectly random" means in any way that brings utility to the workflows, processes, and measurements that are implemented by products and systems in the "real world".
What's been good enough for a long time, and likely for a long time to come, is sufficiently random to meet some criteria in a risk/consequence trade. The quest for "better randomness" or maybe "perfect randomness" is just a means of saying I can completely retire one risk that is part of a number of risks in a risk assess
Re: Can someone help explain "perfect" randomness? (Score:2)
I'm wondering the same. If you can TELL that it's perfectly random, doesn't that imply that it's not so?
I'd expect more and more comprehensive calculations of the source's entropy, approaching a limit of infinity, but how can one know it's perfect?
Is it that monkeys with typewritten Shakespeare keep flying out of it?
Re: (Score:3)
The big thing is that it's certifiably random. Shot noise can be influenced by environmental factors, so can lava lamps.
Shot noise also has potential issues, depending on the application, that it is Poisson distributed so the variance is determined by the mean. It can also carry correlations if you're using charged particles because they repel each other.
Unnecessary expense (Score:2)
Re:Unnecessary expense (Score:5, Funny)
I think my wife's conversational topics might also work.
Re: (Score:2)
So is this a legal marriage or one of those common law things? Maybe the expenses you avoided involved the expensive wedding and so forth?
Trying to bridge to the "state of sin" joke that I was expecting on this story. Yours was the best of the jokes on offer, but I had much higher hopes for the story.
Me? If an AI certified the system as random, then I have my doubts.
Oh yeah, I suppose I better complete my citation of the ancient joke, hadn't I?
"Anyone who considers arithmetical methods of producing random d
I'm thinking of a number between 0 and 1 (Score:2)
Re: (Score:2)
Re: I'm thinking of a number between 0 and 1 (Score:2)
Mod parent up. That is awesome.
Re: (Score:2)
Simple: Your head is empty. There is no integer number between 0 and 1. Alternatively, you would have needed to say between 0.0 and 1.0 and you just made a rather gross type error. (Sorry, could not resist. My apologies.)
Re: (Score:2)
Can you guess it?
I have a fear of numbers that can’t be expressed as a fraction, though I realize it’s irrational.
Knuth wonâ(TM)t stand for it (Score:3)
Next edition of TAOCP will show why this random algorithm also didnâ(TM)t hold up.
"I achieved perfet randomness before anyone (Score:2)
What's the difference? (Score:2)
What's the difference between this RNG and the next-best RNG? How can you tell? What will this RNG be able to enable that the next-best RNG can't? Can this RNG be used to attack other RNGs?
give it a name (Score:4, Funny)
Whatever
NIST CMVP (Score:2)
Hard to believe there isn't a single QRNG or Physical TRNG in this list that isn't (for all practical purposes) just as high quality a source of Entropy as what ETH Zurich designed:
https://csrc.nist.gov/projects/cryptographic-module-validation-program/validated-modules/search/all
Re: NIST CMVP (Score:2)
https://csrc.nist.gov/projects/cryptographic-module-validation-program/entropy-validations/search?ipp=250
No, based on the summary (Score:2)
> depending on an imperfect random number generator. Renner's coworkers could then amplify the randomness of the measurement results further using a special algorithm.
You can't take a non-random source and make it random with an algorithm. Either there is true randomness in the input or there isn't. The algorithm is deterministic.
Re: No, based on the summary (Score:4, Interesting)
It sounds to me like the input to the algorithm is truly random, but not unbiased, and the algorithm perfectly unbiases output from the particular source they are using. The rest of the article goes into the type of flaw they're addressing, and talks about very slightly unfair dice, which you could correct, but you'd need to know exactly how unfair they are, and you're always going to be very slightly wrong and end up correcting not quite perfectly. The obvious quantum RNG is to generate polarized light and measure it perpendicular to the polarization, but you'd still need to get it perfectly perpendicular. It sounds like they've built something that doesn't rely on precise alignment to give a known distribution, which they can then use to unbias the output perfectly.
I thought was first! (Score:2)
*nt*
Obviously, this is nonsense (Score:2)
First, a reverse PN diode delivers about 50% quantum-tunneling avalanche noise at 5.6V. That is quantum noise. Combine a few samples the right way (crypto-hash), and you have "perfect" randomness. Second, that quantum-noise is "true" noise is the theoretical (!) model. It just means "we have no clue how it works". It does not prove or imply perfection. And third, there is zero need for this. Security and cryptography just needs unpredictable data, not random data. A competently seeded CPRNG delivers that.
tl
Re: (Score:2)
Maaaaybe research is not always about products. Nobody said you need this for your next PGP key. They achieved an interesting physics result, and did not create a new random generator for your PC.
Re: (Score:2)
The point is that this is in no way a "first" and that it is in no way "perfect" either.
Prior art (Score:2)
Much more simple: https://xkcd.com/221/ [xkcd.com]
Nonsense (Score:2)
This is nothing new, Slashdot comments have been perfectly random for years
And what is the result? (Score:2)
So what random number did they get?
Re: (Score:3)
Not True (Score:3)
Claims of perfect randomness from quantum physicists are always wrong.
1) The claims rely on some detector being 50/50 (they never are), always detecting individual events (they often see multiple or none) .
2) Randomness amplification is a subfield of entropy extraction and it cannot give you full entropy (aka perfect randomness).
Certified? (Score:2)
Re: (Score:2)
In a truly random sequence, every number has the same probability of being next.
In a less random sequence, some numbers are more likely than others. For example, in a binary sequence the next number could have a 10% chance of being 1, and 90% chance of being 0.
In a random sequence, there is a higher probability of getting a 1, and a lower probability o
Re: (Score:2)
What you're describing is "a truly random number generator with a uniform distribution of outcomes"
Apparently it's also called perfect randomness.
Re: (Score:2)
No. It is also called "source without memory". No predictions possible.