How to Turn a Quantum Computer into the Ultimate Randomness Generator
quantamagazine.org
quantamagazine.org
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-ge...
All this true random number generator stuff strikes me as a bit dippy.
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.
> 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 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.
lol
In other words, in the statement "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", the adversary is actually the physical laws of the universe, and we are testing what those laws allow as far as generating randomness goes.
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.
"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...
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.
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).
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.
That is the definition of a cryptographically secure hash.
One can quibble over whether or not any available hash function is in fact a CSH. But if you believe that any of the algorithms that are widely considered to be CSHs are in fact CSHs then the rest is easy.
It is not! None of the cryptographically secure hashes are proven to produce truly random output. They only strive to achieve indistinguishability from randomness, bounded by computational complexity of attacks.
Anyway, what you're talking about, in general, is called a randomness extractor. The protocol described in the article, apart from verification, uses "a strong quantum-proof randomness extractor to extract Ω(N) bits of randomness from the recorded string". So yeah, "pure, verifiable randomness is hard to come by".
> It is not!
You're right, it's the definition of a secure psuedo-random function (PRF).
https://en.wikipedia.org/wiki/Pseudorandom_function_family
However, all cryptographic hashes are PRFs. Any deviation from being a PRF would be an attackable weakness.
2) That isn't what the article said. The article asserted "quantum computers" were uniquely and inherently excellent random number generators. I assert you can only say this if you never in your life interacted with matter, which is generally accurate when discussion "quantum information theorists" who come up with gorp like this.
Because your adversary could "come across" those same strings. Your entropy source has to be private (obviously).
> That isn't what the article said
The first sentence, is, quite literally, "Pure, verifiable randomness is hard to come by." And that is both false and unimportant.