Follow Slashdot stories on Twitter

 



Forgot your password?
typodupeerror
×
Encryption Science

Researchers Devise a Way To Generate Provably Random Numbers Using Quantum Mechanics (newatlas.com) 139

No random number generator you've ever used is truly, provably random. Until now, that is. Researchers have used an experiment developed to test quantum mechanics to generate demonstrably random numbers, which could come in handy for encryption. From a report: The method uses photons to generate a string of random ones and zeros, and leans on the laws of physics to prove that these strings are truly random, rather than merely posing as random. The researchers say their work could improve digital security and cryptography. The challenge for existing random number generators is not only creating truly random numbers, but proving that those numbers are random. "It's hard to guarantee that a given classical source is really unpredictable," says Peter Bierhorst, a mathematician at the National Institute of Standards and Technology (NIST), where this research took place. "Our quantum source and protocol is like a fail-safe. We're sure that no one can predict our numbers." For example, random number algorithms often rely on a source of data which may ultimately prove predictable, such as atmospheric noise. And however complex the algorithm, it's still applying consistent rules. Despite these potential imperfections, these methods are relied on in the day-to-day encryption of data. This team's method, however, makes use of the properties of quantum mechanics, or what Einstein described as "spooky action at a distance." Further reading: Wired, LiveScience, and CNET.
This discussion has been archived. No new comments can be posted.

Researchers Devise a Way To Generate Provably Random Numbers Using Quantum Mechanics

Comments Filter:
  • by Anonymous Coward

    Mostly just for the random entertainment value: https://www.random.org/

  • First post (Score:2, Funny)

    by Anonymous Coward

    int getRandomNumber()
    {
        return 1; // chosen from random post number
    }

    • by Anonymous Coward

      What is "provably random"?

      Can you really "prove" that a number is random?

      • Re:First post (Score:4, Interesting)

        by alvinrod ( 889928 ) on Thursday April 12, 2018 @01:45PM (#56426001)
        In this case TFS seems to define provably random as that which cannot be predicted in advance given sufficient knowledge of how the number is generated and some initial conditions. Supposedly they have proven that this is the case, though I have not verified the correctness of their proof. However, this is really no different than other mathematical proofs. Either the proof is correct or it is not, but a lack of understanding of the proof does not change its correctness.
        • by Roger W Moore ( 538166 ) on Thursday April 12, 2018 @03:03PM (#56426525) Journal

          However, this is really no different than other mathematical proofs.

          No, it is very different from a mathematical proof. This proof relies on our understanding of quantum mechanics and photons. Mathematical proofs are far more fundamental in that they are true regardless of the properties of the universe you happen to be in at the time. That being said QM is one of the most accurately tested scientific laws there has ever been but, nevertheless, if an experiment tomorrow shows that it is wrong this "proof" might come crashing down.

          • Is this actually new? My understanding was that 'hidden variables' were ruled out, so randomness is required, as any theory that predicted outcomes would be tantamount to hidden variables. So we already have quantum randomness generators:
            https://qrng.anu.edu.au/ [anu.edu.au]

            • by HiThere ( 15173 )

              No, only local hidden variables were ruled out. But non-local hidden variables are so weird that almost nobody believes in them. (They've got to be non-local in time as well as in space.)

              I've got to admit I don't understand what that means. Ask David Bohm, though you'll need a medium. Or you could try to read his book "Wholeness and the Implicate Order". Good luck.

          • by swillden ( 191260 ) <shawn-ds@willden.org> on Thursday April 12, 2018 @08:44PM (#56428189) Journal

            Mathematical proofs are far more fundamental in that they are true regardless of the properties of the universe you happen to be in at the time.

            This is deeply wrong.

            Mathematical proofs are true if and only if the assumptions (axioms) on which they're based are true. When you apply mathematics to real things, you're making a critical unproven and unprovable assumption: That the mathematical structure maps perfectly onto the real-world structure. That this works quite well isn't surprising, because we work hard to craft mathematical structures that map as closely as we can, and because the universe appears to have consistent structure. That said, the fact that it has always worked well in no way proves that the mapping will always hold, and it says nothing about the "truth" of reality other than we observe that it consistently appears to behave according to a certain pattern.

            The map is not the terrain. And when you posit a universe with a different properties (different terrain!) then there is no reason to expect the map even to be useful.

            • This is deeply wrong.

              No, it's correct and indeed you say as much in your reply! As you say maths is based on certain axioms which are held to be true and as long as you hold those axioms to be true mathematical proofs based on them are absolute. Whether those proofs are useful for describing the real world is a different question.

              In this way maths is not a map to the real world it is a language we can use to describe it. A map is always required to describe accurately the world it is associated with but with a language we c

        • by novakyu ( 636495 )

          So, if it's provably random but you do not understand the proof, does it matter to you that it was provably random, rather than pseudorandom?

        • at least there's finally an application for quantum mechanics lol, roll the dice ! no more cheating by turning your computer clock to the same minute as yesterday
      • Chi-squared test comes close.

        • Chi-squared test comes close.

          Not nearly as close as the Markov-Renye min entropy test or the least common value test.

          In fact tests of randomness fill the largest two chapters in my book on random number generators.
          https://www.degruyter.com/view... [degruyter.com]

          Available at all good internet portals sometime later this year.

    • Re:First post (Score:5, Informative)

      by darkain ( 749283 ) on Thursday April 12, 2018 @01:41PM (#56425969) Homepage

      Obligatory XKCD reference for those that didn't get it: https://xkcd.com/221/ [xkcd.com]

      • by Anonymous Coward on Thursday April 12, 2018 @02:56PM (#56426461)

        Obligatory Dilbert: http://dilbert.com/strip/2001-... [dilbert.com]

        • by Anonymous Coward

          The Dilbert brings a bit more insight.

          Most pseudo-random number generators aren't capable of generating a long sequence of the same number, and for most applications that would be undesirable and probably reported as a bug.

          A true random number is capable of generating an infinite sequence of the same number. That particular outcome is just a likely as any other specific sequence.

          When we use randomness in programming we often want a controlled "randomness" that gives us a fairly even distribution.
          The one in

  • by CajunArson ( 465943 ) on Thursday April 12, 2018 @01:36PM (#56425921) Journal

    You're not fooling me. It's well known that the NSA incorporated backdoors into the fabric of the universe when they subverted the big bang.

  • by Kenja ( 541830 ) on Thursday April 12, 2018 @01:38PM (#56425937)
    int getRandom() {
    return 4; // generated by dice roll
    }
    • by Jeremi ( 14640 )

      We have new technology to optimize that code now. Here's the modern implementation:

      int getRandom() {
            return 4; // generated by "spooky action at a distance"
      }

  • See Lava Rand [wikipedia.org]
    • See Lava Rand [wikipedia.org]

      Thank you. An RNG that uses external sources (values inherent to QM) to generate said value isn't using a strict mathematical proof. This is just reality sampling.

  • by lurcher ( 88082 ) on Thursday April 12, 2018 @01:40PM (#56425955) Homepage

    I would have thought thermal noise in a resistor or semiconductor (which is in itself generated by subatomic so quantum, events) would be just as random.

    • What about small tritium gas vial, size used in wristwatch numbers (like a Trigalight) coupled with a detector? Couple that with some high speed flip-flops or as stated above, noise in a NP junction, and that should produce cryptographically secure random numbers, especially if the CPU had a built in pool with a "stirring" mechanism so anything periodic would be dispersed among the bits fairly quickly.

    • by Baloroth ( 2370816 ) on Thursday April 12, 2018 @02:59PM (#56426489)

      It is, and that's exactly how Intel's hardware-based random number generator in their CPUs works (so, yes, we have used a truly provably random source of RNGs... that is, if Intel is telling the truth about how it works). Another source of RNG is radioactive decay, though that's not terribly commonly used thanks to the hardware requirements. In this case, the article doesn't describe the source of randomess (aside from "correlations in superpositions", which could be anything from completely random to completely unrandom). It might not even be as random as they think it is (just being quantum is very much not enough), especially because they "improved their data" by only looking at sequences where the bits were almost perfectly uniformly 50/50 1 and 0, which is precisely not the right way to ensure good randomness: true random sequences usually don't obey uniformity, except in the limit as the length of the sequence goes to infinity, and requiring uniformity (or near-uniformity) in a "random" sequence reduces the entropy. That tells me they don't really understand randomness, which does not bode well for their claims.

      • by TechyImmigrant ( 175943 ) on Thursday April 12, 2018 @03:47PM (#56426811) Homepage Journal

        >It is, and that's exactly how Intel's hardware-based random number generator in their CPUs works

        Indeed, it is. I happen to know this well because I'm one of the designers of it.

        Quantum proven randomness is proven by showing a violation of Bell's theorem, showing a correlation that exceeds whats could be achieved by unentangled particles and therefore showing that they were a part of a random quantum process.

        The form of every mathematical proof is of the form "If this is true, then [blah blah blah], so that it true".
        The form of this particular proof is "If the rules of quantum physics are true, then [blah blah blah] so 'the output is random' is true".

      • Another source of RNG is radioactive decay, though that's not terribly commonly used thanks to the hardware requirements.

        Radioactive decay is fundamentally a quantum effect, which is why we cannot predict individual decays, only the macroscale statistics. So the article might have a new method per se, but simply using quantum effects wouldn't be new.

        they "improved their data" by only looking at sequences where the bits were almost perfectly uniformly 50/50 1 and 0, which is precisely not the right way to ensure good randomness: true random sequences usually don't obey uniformity, except in the limit as the length of the sequence goes to infinity, and requiring uniformity (or near-uniformity) in a "random" sequence reduces the entropy. That tells me they don't really understand randomness, which does not bode well for their claims.

        I've written a HWRNG for FPGAs, and it was frustrating to test and tweak it to pass the tests in rng-tools based on FIPS 140-2. One of the tests fails upon too long stretches of 0s or 1s [dilbert.com], for example. I guess for practical purposes you want something like short-term randomness;

      • by jezwel ( 2451108 )

        I would have thought thermal noise in a resistor or semiconductor (which is in itself generated by subatomic so quantum, events) would be just as random.

        It is, and that's exactly how Intel's hardware-based random number generator in their CPUs works (so, yes, we have used a truly provably random source of RNGs... that is, if Intel is telling the truth about how it works)

        If you run the same code on the same CPU under the same conditions, how similar is the thermal noise generated? Is it completely different or will there be any similarities at all?
        TIA, just curious.

    • I would have thought thermal noise in a resistor or semiconductor (which is in itself generated by subatomic so quantum, events) would be just as random.

      Via the central limit theorem, the addition of multiple binary random events will combine into a gaussian distribution. It will be random, with the min-entropy determined by the distribution - H_inf(X) = -log_2(max(Pr(X_i)).

      So there will be some entropy loss. But that's fine. There's plenty of entropy about us to sample and turn into random bits.

  • So we do have free will after all.

    • by Anonymous Coward

      No, photons have free will. We can prove it.

      You are entirely predictable. Advertisers can prove it.

    • Re: (Score:2, Offtopic)

      by mark-t ( 151149 )

      Consider that we appear, by most standards of observation, to have at least some measure of what we imagine free will to be, and we generally live our lives as if we were free willed. In fact, if we were not, the expression "free will" would not even mean anything, since it is the very term that we regularly use to describe the appearance of freely made choices. By extension, therefore, if free will did not exist, then it seems apparent that we should not be capable of imagining what we think that actu

      • if free will did not exist, then it seems apparent that we should not be capable of imagining what we think that actual free

        Seems apparent, is not a proof, may things that seem apparent are not true, if you have a rope are around the circumference of the earth and the you increase the diameter by 1m can you fit a cat under it. The answer is you increase the distance above the earth by 1/(2pi)m everywhere which is about 16cm. Or add 15% then take off 15% you do not end up with the same number.

        There is no way to prove we have free will. Take for example I can control your every thought and action therefore you have no free will. I

        • by mark-t ( 151149 )
          My point is that to assert that we don't have free will is meaningless, because we still have some notion of what free will is, and if that doesn't actually exist, then the term doesn't mean anything that corresponds to reality.

          Essentially any illusion of free will that cannot be distinguished from a hypothetical real free will may as well be just called free will, and arguing that it's not because it doesn't live up to some hypothetical standard is meaningless, particularly since it's impossible to prov

    • So we do have free will after all.

      Nope, the multiverse is most likely correct. The big bang never stopped, it just went interdimensional and time itself is an illusion caused by the patterns which emerge when tracing a path along one of all potential possibilities. The interference pattern and statistical interpretation of it is just the probability that a particle you observe on your worldline goes in a particular direction at a particular velocity, but all of those possibilities are traced out on different worldlines. There's a reality

      • by Anonymous Coward

        I have a Quantum Multiverse-Locked Hammer (QMLH). When my QMLH is used on an object, 50% of the time it drives the object like a regular hammer, and 50% of the time it bounces back and does not impact the object. But fortunately, my hammer has a multiverse lock, which means it selects the quantum universe in which the probability was the 50% success of driving an object, so my hammer ALWAYS behaves like a non-quantum hammer to observers.

        Multiverse theory and applications to topics like quantum computing are

        • Difference between your description and reality is that the multiverse explanation removes all paradoxes from the quantum and relativistic worlds at all scales, while every other potential resolution fails to do so and usually create additional ones. That fact alone makes the multiverse interpretation the only plausible solution at this point in time.
    • So we do have free will after all.

      With determinism, everything is on its set path, so we don't have free will.

      But if everything is truly random at a fundamental level, it doesn't get any better. If the outcome of every decision is truly random, you're not actually making the choice.

      So IMHO, free will isn't a question of determinism vs. randomness. At least not a binary question.

  • I'm missing the proof that there are no non-local hidden-variables or super-deterministic local hidden variables at play.

  • by MrKevvy ( 85565 ) on Thursday April 12, 2018 @01:50PM (#56426029)

    It has already been established that thermal/shot component noise (most commonly from reversed diodes) is demonstrably statistically random and is based on quantum electrodynamic events.

    TRNGs (True Random Number Generators) using this principle have been around for a while embedded in some hardware such as the Intel 82802 firmware hub found on some Intel mainboards

    • by gweihir ( 88907 )

      They are also really cheap to do. And, from physical principles, part of the noise generated is tunneling ("true random" if Quantum Theory is exact, which it most likely is not) and part is thermal (good enough for even hardcore cryptography). Hence this "story" is a mixture of lies and things that are irrelevant.

  • by Anonymous Coward

    Observe time between a decay and the next one. Do this twice. Next bit is comparison between the two times. This method is as old as quantum mechanics itself.

    • If we're talking about radioactive decay, we'll find that, statistically, intervals between decay get larger over time. This isn't completely unbiased. There is a way to make biased random bits unbiased, if you don't mind slower generation (a minimum of eight times slower, assuming an unbiased source). Divide the stream into pairs. Throw away all "11" and "00". Take "01" to be 0 and "10" to be 1.

  • Is 1 less random than 29840972.58792384 ?

    Perhaps they mean "randomly generate numbers"?

    • by rossdee ( 243626 )

      >Perhaps they mean "randomly generate numbers"?

      And my conjecture is that you can never prove that "a set of presumably random numbers" is trully random, you can only prove that it is not random (by running it long enough that you can find a pattern)

      [monkeys, typewriters, complete works of Shakespeare]

      • by gweihir ( 88907 )

        It is in fact trivial that any given set of numbers is not random. You can only say that a source of data produces data that is not predictable before it has produced the data. That property does not transfer to the data produced once it has been produced. All you have there is that it is not possible to infer the data from an accurate description of the source that produced it. But that is quite enough. In fact, for all relevant applications you do not even need "random". "Not predictable" is quite enough

    • "What's a provably random number? "

      Perhaps they mean they can generate a number they can prove is more random than the best attempts of others.

      From the article:

      "The researchers call this proximity to fifty-fifty perfection "uniformity." From the more than 100 million bits generated, the researchers found 1,024 certified to be uniform to a trillionth of a percent. "A perfect coin toss would be uniform, and we made 1,024 bits almost perfectly uniform, each extremely close to equally likely to be 0 or 1," Bier

      • by gweihir ( 88907 )

        Maybe. In that case they have no clue what they are talking about, though. Bias is not a factor (unless total) in whether something is random or not. In actual reality, just use an entropy pool, a cryptographic whitener and put in 1000 bits or so of entropy you are good. This "discovery" is irrelevant nonsense.

    • Is 1 less random than 29840972.58792384 ?

      Perhaps they mean "randomly generate numbers"?

      Not any more.

      I can predict them both because you told me their values. Entropy is in the eye of the beholder.

    • by gweihir ( 88907 )

      No. They are the same. "Randomness" is not a property of data. It is a property of a data-source, just as you say. But since they do not even know that quantum process based RNGs have been around for very long and are cheap to do in addition, anything said by them is likely nonsense.

  • by sinij ( 911942 ) on Thursday April 12, 2018 @02:11PM (#56426193)
    Nice, I can finally upgrade my lava lamp [wikipedia.org] entropy source to a quantum source that uses laser light on a crystal. Why? Because /dev/urandom is for peasants.
    • Nice, I can finally upgrade my lava lamp [wikipedia.org] entropy source to a quantum source that uses laser light on a crystal. Why? Because /dev/urandom is for peasants.

      And quickrdrand [github.com] is for kings and queens.

  • all the Three Letter Agencies around the world decided to scramble resources to determine if they could identify any form of structure underlying the quantum nature of the universe being leveraged to support this [P]RNG technique - and in so doing discovered a layer of structure or order that underpins the quantum realm.

    Let's face it, when you consider the budgets these TLAs get to play with, they must be orders of magnitude more than theoretical physicists and mathematicians - and we already know that t
    • The bogeyman / bullshit justification of fighting inanimate object such as the War on Terrorism (TM) is more profitable though. /cynical

    • by Jeremi ( 14640 )

      Let's face it, when you consider the budgets these TLAs get to play with, they must be orders of magnitude more than theoretical physicists and mathematicians - and we already know that the NSA has more PhD mathematicians than anywhere else...

      On the other hand, one thing a lot of brilliant people really want to do is become famous for answering a question or solving a problem that nobody else could -- a situation that is unlikely to happen for anyone who is working under triple-dog-secret-no-disclosure-ever-and-we-mean-it-or-else conditions at the NSA.

      Any reasonably brilliant person can find a way make plenty of money, if making money is what motivates them. But the desire for money is not usually what drives brilliant people; OTOH figuring out

  • Can we use this result to prove that our reality is not a computer simulation (e.g. that we live in reality prime)?
    • by gweihir ( 88907 )

      No. And if you have to ask, you have not understood the question you asked.

      • Thanks for being so polite on the internet.
        • by gweihir ( 88907 )

          I am just stating a fact. Please read up on theories before you ask for obvious characteristics.

          • by gweihir ( 88907 )

            Amplifying from that (and I realize I was rude, my apologies), the thing is it is not actually possible to determine you are or you are not in a simulation, unless some very specific conditions are met. First, and most important, a proof is only possible if the human mind is at least somewhat independent of the simulation. Otherwise, the simulation would (if at least somewhat intelligently designed) determine what is going on and simply modify the minds attempting to prove anything to make them fail. So, un

  • What about the giant wall of lava lamps that is used to generate random numbers..?

  • "We do not understand how it works" is not the same as "provable random numbers". Any proof here comes with "if quantum theory is exact". Now, it is known that Quantum Theory and Relativity are inconsistent, yet both are exceptionally well verified. It is therefore exceptionally likely that Quantum Theory is not an exact model of reality. Incidentally, it is not possible to prove that any specific bit of data is "random" either, Mathematics does not allow that and Physics even less so.

    Also, just use a stand

  • That you won't know its random till you look at it.

  • by david_thornley ( 598059 ) on Thursday April 12, 2018 @07:11PM (#56427771)

    Wikipedia [wikipedia.org] has a list of available hardware random number generators from $7 on up. The ones that use direct quantum randomness seem to start at about a thousand euros, the cheaper ones using forms of noise. There isn't any way to predict atmospheric noise, since we're talking about a chaotic system that deals with interactions small enough that the uncertainty principle isn't completely swamped.

  • True randomness is there for sure, but making it unbiased is another matter. Real systems interact with their environments, and those environments can change the results in subtle ways. Small imperfections in the apparatus can create correlations between the photons, for example (simple example: magnetic fields cause photon polarizations to rotate). And correlations between random values are really nasty for random number generation. I'd be really reluctant to trust the output of such a random number ge

  • I am a physicist who worked on this project at NIST, so I am sorry to be late to this conversation. A lot of the comments here express doubt or uncertainty about what is new or different in our quantum random number generator compared to others like thermal-electronic noise, lava lamps, random.org, and others. This a great question, because the news article linked at the top of the thread does not explain this well. Maybe I can help.

    The key idea is that our randomness is "device independent", meanin

  • There is no such thing as a truly random number.

    ALL outcomes of any algorithm will be reliant of the state of the constituent components;
    actual states and those relative to their environment and (neighbors).

    If you can duplicate those exact states and circumstances, you will get the same number.

An Ada exception is when a routine gets in trouble and says 'Beam me up, Scotty'.

Working...