6 ms·

How to Turn a Quantum Computer into the Ultimate Randomness Generator

39 points by headalgorithm 7y ago

sandworm101 7y ago
A source, but nowhere near the "ultimate" source of random data. For that, you have to think on different scales. "The researchers believe quasars could make an ideal cryptographic tool because the strength and frequency of the radio pulses they emit is impossible to predict. “Quasar-based cryptography is based on a physical fact that such a space signal is random and has a very broad frequency spectrum,” Umeno told New Scientist." https://www.newscientist.com/article/dn8913-your-secrets-are-safe-with-quasar-encryption/ https://www.newscientist.com/article/dn8913-your-secrets-are...
- mensetmanusman 7y ago
  I imagine future inter-galactic quadrillionaires collecting Quasar’s for their own satisfaction, so it might not be a safe bet to rely on them now :)
- manifestsilence 7y ago
  Interesting, but it seems like if an attacker could guess the target quasar and time (a much smaller search space perhaps than the general space of random strings), they could use their own database of quasar blips to crack the one-time pad. It's basically a public source of randomness, which seems like it makes it inherently not suitable for cryptography.
  - sandworm101 7y ago
    Well, it isn't as simple as light levels or color. The randomness would come from measuring aspects of individual photons, things that could not be shared between telescopes. If you want to measure something like entanglement, you want a source of randomness totally divorced from any local influence. Nobody can argue that photons formed in a star millions of years away could possibly have been influenced by local forces. Use two quasars separated by 180* (ie on opposite sides of sky) and you could definitively say that, given the speed of light, the incoming photons could not possibly have interacted with each other before being measured.
SilasX 7y ago
Wait, what? I think that's going the wrong direction. There are quantum(-specific) phenomena that contain true randomness -- i.e. no amount of knowledge will make the result more predictable. Those phenomena get harnessed to interact in a certain way to produce use computations. Such devices are quantum computers. But if you just want the randomness, you don't need the computer part. You just measure the quantum phenomena and don't bother to make the interactions happen in just the right way to do (other) computations. The "computer" part is irrelevant for that use case (random number generation). By analogy, this sounds like "how to turn a (classical) computer into a heater". Same issue: running a current through a wire creates heat. Certain setups of said wires also produce useful computations. But if you just want the heat, you just need a regular boring resistor; you don't need to make it into a computer as well, though you're free to use whatever heat it throws off as well. Edit: Okay, on further reading, that is what they mean by a quantum computer: one that just takes such measurements and where you can specify a distribution it samples from. But, just to clarify, this is not the kind of quantum computer you hear about generally, where it solves factorization or simulated annealing or something. As in the quote from Scott Aaronson, it's not the most interesting thing you can do with a QC.
- Retra 7y ago
  But what if you want your heater to send an email...
  - UI_at_80x24 7y ago
    I think I saw that at CES in 2001.
lisper 7y ago
> Pure, verifiable randomness is hard to come by. No, that's simply not true. Entropy is everywhere, and really easy to collect. The only thing that is even remotely challenging is estimating how much entropy a particular source provides, and even that is not really a problem because you can just add a few orders of magnitude of safety margin. You don't really need all that much entropy to be perfectly secure. 512 bits of actual entropy is ridiculous overkill for any application short of securing nuclear stockpiles (and might be adequate even for that).
- scottlocklin 7y ago
  Randomness has bias. Including the type of randomness mentioned in this article. Which in the physical world (something "quantum information theorists" forget about virtually always) has measurement bias at the very least.
  - lisper 7y ago
    Yes, and there are well established techniques for compensating for that. TL;DR: don't use the data from your entropy source directly, run it through a cryptographically secure hash first.
    - dchest 7y ago
      Practically, yes. But consider one-time pad or Shamir secret sharing: they stop being information-theoretically secure if you use such conditioning.
      - lisper 7y ago
        > they stop being information-theoretically secure if you use such conditioning No, that's not true. As long as you put more entropy in than you take out then you retain IT-security. But there is no rational reason to care about that.
        dchest 7y ago
nategri 7y ago
I mean, if you think generating a large amount of pure randomness from a quantum mechanical source is cool, you can do it with crap you can buy at Microcenter. Just amplify a reverse-biased diode. You'll get some entropy from quantum tunneling and (probably more) from avalanche breakdown. Then you can use a simple MC to digitize, and apply a simple algorithm to ensure an equal number of random 1's and 0'. This is a good write-up (RIP Make): https://makezine.com/projects/really-really-random-number-generator/ https://makezine.com/projects/really-really-random-number-ge...
- techslave 7y ago
  exactly. in fact there exist already other sources of “ultimate” randomness, available commercially without needing a quantum computer.
- gaze 7y ago
  Yeah but if you do that there's a bunch of thermally driven noise mixed in which might be conspiring to generate a predictable key to secure your porn stash... so there's a chance you might get compromised. All this true random number generator stuff strikes me as a bit dippy.
  - contravariant 7y ago
    Well, it prevents Laplace and Maxwell's demon from predicting and interfering with your random numbers. Although it wouldn't prevent either of them from breaking any encryption you could care to throw at them, and most realistic threats are bound by the laws of physics, but hey it's something.
- abdullahkhalids 7y ago
  You are oversimplifying the issue and solving a "strawman problem. From the abstract of one of the discussed papers [1], > We give a protocol for producing certifiable randomness from a single _untrusted_ quantum device that is _polynomial-time bounded_. The randomness is certified to be statistically close to uniform from the point of view of any _computationally unbounded quantum adversary_, that may _share entanglement_ with the quantum device. where I have highlighted the important terms. Your goal is to generate a random string that you trust that your adversary does not have any statistical information about. * untrusted: the device that you are using to generate the random string is untrusted. You bought it from the market but have not tested it or can't test it with resources on hand. * polynomial-time bounded: to get a random string of size $n$, you don't want to run the untrusted device for longer than poly($n$) * computationally unbounded quantum adversary: the adversary is computationally unbounded. If the adversary was more limited computationally, it might be possible to use a simpler protocol to generate your random string. * share entanglement: this is important. If the adversary is the one who sold you your diode, he might have entangled it in some way with the devices in his own lab, allowing him to get the same measurement results as you did. Clearly, this is a very difficult problem, but is relevant to when your random number generator comes installed in your laptop from the manufacturer. This problem is also important for understanding the information processing powers of quantum mechanics. [1] https://arxiv.org/abs/1804.00640 https://arxiv.org/abs/1804.00640 To add some argument from authority, the authors of this Vazirani and Vidick are two of the giants of the field and know what they are talking about.
foxyv 7y ago
Too complicated, replaced with lava lamp: https://en.wikipedia.org/wiki/Lavarand https://en.wikipedia.org/wiki/Lavarand

39 points by headalgorithm 7y ago

A source, but nowhere near the "ultimate" source of random data. For that, you have to think on different scales. "The researchers believe quasars could make an ideal cryptographic tool because the strength and frequency of the radio pulses they emit is impossible to predict. “Quasar-based cryptography is based on a physical fact that such a space signal is random and has a very broad frequency spectrum,” Umeno told New Scientist." https://www.newscientist.com/article/dn8913-your-secrets-are-safe-with-quasar-encryption/ https://www.newscientist.com/article/dn8913-your-secrets-are...

mensetmanusman 7y ago
I imagine future inter-galactic quadrillionaires collecting Quasar’s for their own satisfaction, so it might not be a safe bet to rely on them now :)
manifestsilence 7y ago
Interesting, but it seems like if an attacker could guess the target quasar and time (a much smaller search space perhaps than the general space of random strings), they could use their own database of quasar blips to crack the one-time pad. It's basically a public source of randomness, which seems like it makes it inherently not suitable for cryptography.
- sandworm101 7y ago
  Well, it isn't as simple as light levels or color. The randomness would come from measuring aspects of individual photons, things that could not be shared between telescopes. If you want to measure something like entanglement, you want a source of randomness totally divorced from any local influence. Nobody can argue that photons formed in a star millions of years away could possibly have been influenced by local forces. Use two quasars separated by 180* (ie on opposite sides of sky) and you could definitively say that, given the speed of light, the incoming photons could not possibly have interacted with each other before being measured.

SilasX 7y ago

Wait, what? I think that's going the wrong direction. There are quantum(-specific) phenomena that contain true randomness -- i.e. no amount of knowledge will make the result more predictable. Those phenomena get harnessed to interact in a certain way to produce use computations. Such devices are quantum computers. But if you just want the randomness, you don't need the computer part. You just measure the quantum phenomena and don't bother to make the interactions happen in just the right way to do (other) computations. The "computer" part is irrelevant for that use case (random number generation). By analogy, this sounds like "how to turn a (classical) computer into a heater". Same issue: running a current through a wire creates heat. Certain setups of said wires also produce useful computations. But if you just want the heat, you just need a regular boring resistor; you don't need to make it into a computer as well, though you're free to use whatever heat it throws off as well. Edit: Okay, on further reading, that is what they mean by a quantum computer: one that just takes such measurements and where you can specify a distribution it samples from. But, just to clarify, this is not the kind of quantum computer you hear about generally, where it solves factorization or simulated annealing or something. As in the quote from Scott Aaronson, it's not the most interesting thing you can do with a QC.

Retra 7y ago
But what if you want your heater to send an email...
- UI_at_80x24 7y ago
  I think I saw that at CES in 2001.

lisper 7y ago

> Pure, verifiable randomness is hard to come by. No, that's simply not true. Entropy is everywhere, and really easy to collect. The only thing that is even remotely challenging is estimating how much entropy a particular source provides, and even that is not really a problem because you can just add a few orders of magnitude of safety margin. You don't really need all that much entropy to be perfectly secure. 512 bits of actual entropy is ridiculous overkill for any application short of securing nuclear stockpiles (and might be adequate even for that).

scottlocklin 7y ago
Randomness has bias. Including the type of randomness mentioned in this article. Which in the physical world (something "quantum information theorists" forget about virtually always) has measurement bias at the very least.
- lisper 7y ago
  Yes, and there are well established techniques for compensating for that. TL;DR: don't use the data from your entropy source directly, run it through a cryptographically secure hash first.
  - dchest 7y ago
    Practically, yes. But consider one-time pad or Shamir secret sharing: they stop being information-theoretically secure if you use such conditioning.
    - lisper 7y ago
      > they stop being information-theoretically secure if you use such conditioning No, that's not true. As long as you put more entropy in than you take out then you retain IT-security. But there is no rational reason to care about that.
      - dchest 7y ago

nategri 7y ago

I mean, if you think generating a large amount of pure randomness from a quantum mechanical source is cool, you can do it with crap you can buy at Microcenter. Just amplify a reverse-biased diode. You'll get some entropy from quantum tunneling and (probably more) from avalanche breakdown. Then you can use a simple MC to digitize, and apply a simple algorithm to ensure an equal number of random 1's and 0'. This is a good write-up (RIP Make): https://makezine.com/projects/really-really-random-number-generator/ https://makezine.com/projects/really-really-random-number-ge...

techslave 7y ago
exactly. in fact there exist already other sources of “ultimate” randomness, available commercially without needing a quantum computer.
gaze 7y ago
Yeah but if you do that there's a bunch of thermally driven noise mixed in which might be conspiring to generate a predictable key to secure your porn stash... so there's a chance you might get compromised. All this true random number generator stuff strikes me as a bit dippy.
- contravariant 7y ago
  Well, it prevents Laplace and Maxwell's demon from predicting and interfering with your random numbers. Although it wouldn't prevent either of them from breaking any encryption you could care to throw at them, and most realistic threats are bound by the laws of physics, but hey it's something.
abdullahkhalids 7y ago
You are oversimplifying the issue and solving a "strawman problem. From the abstract of one of the discussed papers [1], > We give a protocol for producing certifiable randomness from a single _untrusted_ quantum device that is _polynomial-time bounded_. The randomness is certified to be statistically close to uniform from the point of view of any _computationally unbounded quantum adversary_, that may _share entanglement_ with the quantum device. where I have highlighted the important terms. Your goal is to generate a random string that you trust that your adversary does not have any statistical information about. * untrusted: the device that you are using to generate the random string is untrusted. You bought it from the market but have not tested it or can't test it with resources on hand. * polynomial-time bounded: to get a random string of size $n$, you don't want to run the untrusted device for longer than poly($n$) * computationally unbounded quantum adversary: the adversary is computationally unbounded. If the adversary was more limited computationally, it might be possible to use a simpler protocol to generate your random string. * share entanglement: this is important. If the adversary is the one who sold you your diode, he might have entangled it in some way with the devices in his own lab, allowing him to get the same measurement results as you did. Clearly, this is a very difficult problem, but is relevant to when your random number generator comes installed in your laptop from the manufacturer. This problem is also important for understanding the information processing powers of quantum mechanics. [1] https://arxiv.org/abs/1804.00640 https://arxiv.org/abs/1804.00640 To add some argument from authority, the authors of this Vazirani and Vidick are two of the giants of the field and know what they are talking about.

foxyv 7y ago

Too complicated, replaced with lava lamp: https://en.wikipedia.org/wiki/Lavarand https://en.wikipedia.org/wiki/Lavarand