The fastest random-number generator ever built

https://www.nature.com/articles/d41586-021-00562-6

by gmays • 5 years ago

51 23 5 years ago

nemo16183• 5 years ago

This article doesn't go into much detail about the actual source of randomness -- can anyone explain why the photon emissions are random?

Green_man• 5 years ago

many properties of photons are quantum in nature, relying on an underlying continuous wave function, that when "measured", will output some discrete value. The wave function determines the likelihood of each possible measurement value, with the relationship amplitude^2 = probability.

I was similarly confused about which property of the photons they were measuring, it seemed they might be measuring the number of photons over specific periods of time. Because the position of each individual photon is uncertain until it is destructively measured, randomness will be generated by the "collapse" of the wave function, where one of the possible outputs is generated. Before measuring, photons can be in a "superposition" of bouncing inside the bow tie shaped chamber, or escaping out of the laser to be measured. After measuring, a photon can either be inside the laser, or outside the laser, but not the "both" of a previous superposition. Arguably, superposition isn't really a "both", but there aren't great words in English for this unfortunately. The fundamental uncertainty of measuring a superposed quantum state has been convincingly demonstrated in experimentation, but nobody really knows _why_ it happens this way. The "measurement problem" has inspired many interpretations of quantum mechanics, but many of them are unfalsifiable.

https://en.wikipedia.org/wiki/Measurement_problem

dakr• 5 years ago

From reading the article it seems likes they're using the fact that photons are Poisson distributed. Just like raindrops or particles emitted by radioactive decay, you can determine an average rate of flux and the probability distribution of where particles will hit your detector, but for any given moment, you don't know if a particle will hit at that instant, and you don't know where. With a super fast camera, they're recording many instantaneous snapshots to see if and where a photon has been detected.

RcouF1uZ4gsC• 5 years ago

Bruce Schneier had a section on recognizing snake oil encryption. One of the things that gave it away was a ridiculous key length. “Standard AES uses 256 but keys, but ours uses 10,000 bit keys, so ours is much better.”

In terms of using randomness is crypto, you actually don’t need that much. If you have 256 bits, or 512 bits for an crazy amount of safety factor, you should be good to go. A lot of the secure PRNG’s are built in the same principles as our encryption algorithms. If we don’t trust those, we likely have much bigger issues with the foundations of cryptography.

chairmanwow1• 5 years ago

I absolutely agree with you that the amount of randomness you need is incredibly small for modern cryptography relies on an objectively small amount of random values.

Although, I wonder if an invention like this allows for some new developments in crypto protocols that are extremely "random hungry" in the same way that modern innovation in NNs was made possible by scaled up processors (GPUs / accelerated NN chips).

ie just XOR your plaintext with a random "key" the length of your plaintext

nemo16183• 5 years ago

ie just XOR your plaintext with a random "key" the length of your plaintext

This is essentially what a modern cipher does, except that the key is a keystream and is generated deterministically from the actual key. This is objectively better than just using a really big key -- it means your shared secret only needs to be e.g. 32 bytes, rather than len(plaintext) bytes!

I do still think there's an important use case for high-volume "good" entropy, though: it should replace essentially all uses of "bad" entropy (generated by weak pseudo-random generators, maybe seeded with a few dozen bits of entropy). Programmers should have to go out of their way to get weak entropy, rather than the other way around. Historically programmers have reached for weak RNGs because they tend to be much faster and more convenient to use than the strong RNGs. We should flip that equation. We don't necessarily need a device like this one to do that, but it might help.

nemo16183• 5 years ago

Yep. As djb pointed out, PGP is predicated on the idea that you generate a small amount of secure entropy once, and then keep that entropy safe indefinitely. And a good CSPRNG can be seeded with 32 bytes of entropy and generate essentially infinite secure output.

Still, it would be nice to remove the CSPRNG from the equation entirely, and just read from the stream of "pure"/"true" randomness directly. On the other hand, there are obvious downsides to getting your entropy from a single source... I guess it comes down to a simple question: which do you trust more, your hardware or your software?

xyzzyz• 5 years ago

Yeah, I’d rather trust well understood, deterministic CSPRNGs than opaque hardware that might just have a non-obvious defect.

ackbar03• 5 years ago

I dunno man, it ain't got nothing on my man over in accounting

https://dilbert.com/strip/2001-10-25

jacobolus• 5 years ago

Cf. https://xkcd.com/221/

squid_demon• 5 years ago

Reminds me of the dice used in Greg Egan's Quarantine.

MertsA• 5 years ago

Am I wrong to assume that this will forever be expensive and impractical compared to e.g. Intel's RDRAND implementation where the RNG is built using the same process as the rest of the processor? It seems like you couldn't easily integrate this on the same die as a processor and if it's a completely separate chip, how in the world are you ever going to make it economically advantageous compared to a silicon RNG feeding a CSPRNG? The CSPRNG could be outputting as much random data as you could ever want and it's simple enough to guard your seed data to that CSPRNG, not to mention reseeding it just to make side channels that much more cumbersome to exploit, such that the output of the CSPRNG is for all practical purposes just as secure as whatever output this thing is putting out.

tus89• 5 years ago

Well integrating a diverse range of cores into a CPU is all the rage these days...if Intel doesn't do it Apple would.

ncmncm• 5 years ago

A common problem is the microcontroller that powers up and needs randomness immediately, before it can initialize its peripherals and establish communication links. There, a billion or even a million bits per second may be enough.

Now that we have packaged chiplets, we should be open to stuff on a different semiconductor process than our CPU cores.

Where we need random bits as fast as they can be had is when running Monte Carlo processes on GPUs. There, the sources need to be on-chip because interconnect would be too expensive; we need a separate bit source integrated into each functional unit, and producing a whole machine word's worth each cycle, so a word is always ready immediately when it could be used. Sometime we need more than one before starting a computation.

fulafel• 5 years ago

There have boon some major problems with rdrand, on amd side at least (first the bulldozer/jaguar incident, and now the ryzen one).

marshmallow_12• 5 years ago

there's that thing called ERNIE that the guys who run Premium Bonds use. I find it strange that they use so much energy for such a straightforward task

ycnews• 5 years ago

Previous HN link https://news.ycombinator.com/item?id=26287811

bob1029• 5 years ago

Presumably, less secure applications could derive random data very quickly via existing means by dropping the cryptographically-secure constraint.

As noted in other comments, if you seed a reasonable cryptographic scheme with enough entropy up-front (and protect it well), you shouldn't constantly need to produce more.

So, what practical application would this have?

hansvm• 5 years ago

It could have practical application when any of those constraints are violated:

- Most crypto schemes haven't been proven secure in any absolute sense, only relative to other problems we think are hard.

- Protecting that entropy can be hard.

- Crypto is expensive. If you need a high bit-rate (another comment mentioned GPU Monte Carlo) then integrating these on-chip could be cheaper than mangling the same entropy source over and over.

- Adding to the above, using the same entropy source in multiple places can be prone to non-obvious bugs and race conditions where you use identical or correlated random bits.

Also, less secure applications often cannot get by with dropping the cryptographic constraint, and it might not be obvious when it can be safely dropped (even ignoring the arguments that usually crop up in these kinds of discussions like how for an online poker match you probably do need secure RNG) -- e.g., non-crypto RNG is prone to linear dependences and other problems which can significantly and qualitatively change the nature of all but the most trivial simulations.

The fastest random-number generator ever built

Related Stories