# Extracting Randomness from a Poisson Distribution

I'm working on a quantum random number generator based on the shot noise of CMOS camera sensor. Shot noise in an image is caused by the variance of the number of photons hitting the sensor per unit of time. The distribution follows the Poisson distribution. To collect shot noise, I have to illuminate the sensor with a diffused light source.

A lot of papers discussing how to extract randomness from shot noise usually use equal frequency binning method. The following image is an illustration of randomness extraction using two bins. If the current sample is greater than average, output 1, if the current sample is less than average, output 0.

The problem with this method is it's not easy to determine the cut points, or in this case, the average. I tried to use moving average but the voltage of the light source sometimes drops for a few seconds caused by the other electronics in my room and it makes the output generated by my RNG sometimes biased for a few seconds. I tested the generated data using NIST Statistical Test Suite and it only passed 5/15 tests.

Although it passed 14/15 tests when I applied von Neumann debiasing method, the fact that the quality of the raw data is really bad still bugs me. So I experimented with a different extraction method. Here's how it works using one pixel

Let Brightness(t) be a function that returns the brightness of the pixel at time t

if Brightness(0) < Brightness(1) then
output 1
if Brightness(0) > Brightness(1) then
output 0
else
don't output anything


Basically, take two non-overlapping samples, if the second sample is brighter than the first one, output 1, if the second sample is darker than the first sample, output 0.

The data generated using this method passed 15/15 NIST tests. But since I've never seen any paper discussing a method like this, I need confirmation if this method really as good as it looks, and maybe some explanation why it's good. Thank you.

• If you're still at this, I suggest your biggest problem is not extraction but stabilisation. "voltage of the light source sometimes drops for a few seconds" should be the focus. All else will fall into place. The good folks over at Electrical Engineering can help with the wonky volts. Or get a good UPS. – Paul Uszak Jan 10 at 14:28
• Also see this answer for a real world VN example, and how good it can be. – Paul Uszak Jan 10 at 14:41

The question's method is not secure absent a model of the source. In particular, applied to a source evolving in time as this sawtooth

assumed of period several times the sampling time between Brightness(0) and Brightness(1), the output will be terribly biased towards 0, because the function is decreasing most of the time (this effect will decrease with added Gaussian noise, spacing the samplings).

Another issue is that multiple pixels can output correlated bits.

Both effects might well occur in practice, for a variety of reasons: switching regulator of the power supply of the gizmo, or of the LED source of the ambient lighting. In a cryptographic context, adversaries often have some level of access to a RNG, and might induce that effect on purpose (e.g. varying the power supply, or a light source). And by a corollary of Murphy's law often verified in this very context, such things will happen without explicit adversaries (e.g. as the effect of aging of power supply capacitors) and at the worst time.

The data generated using this method passed 15/15 NIST tests

If a source fails any statistical test¹, this conclusively proves that the source is bad from a cryptographic perspective. But if the source passes all tests, it can still be horribly bad from a cryptographic perspective; the best that can be reasonably be said is that the source, as tested, was free from the particular defects that the tests are designed to detect.

My though experiment with the sawtooth shows that the source could fail under different, realistic conditions. And it is trivial to design a bit source that passes all tests, yet is terribly weak cryptographically.

¹ significantly more often that predicted by the test's $$p$$-value, with the test correctly designed, implemented and applied.

• Thanks a lot for pointing out the possible bias caused by sawtooth pattern and for your advice – Andika Wasisto May 22 '20 at 8:07

If anyone else comes upon this question, there's a commonly cited 2007 paper describing random number generation in the exact same manner described by OP here: https://arxiv.org/abs/quant-ph/0609043

Important quote:

Basic idea of the method for extracting random bits is to consider a pair of non overlapping random time intervals (t1, t2) which are defined with subsequent random events, as shown in Fig. 2a, and generate either binary value ”0” if t1 < t2, or ”1” if t1 > t2. Next two intervals will be considered to generate the next random bit. Since the events which determine time intervals are by definition independent of each other it is not possible that t1 < t2 would appear with any different probability than t1 > t2, consequently the probability to generate ”0” is exactly equal to the probability to generate ”1”. In other words, the distribution of t2i − t2i−1, i = 1, 2, 3, . . . is symmetric. Furthermore, the bits are mutually independent (i.e. uncorrelated) since independent pairs of events are used to generate different bits.

Anyone building a DIY TRNG is to be commended, but you really need to establish a constant entropy rate. It's the first of the three golden rules of TRNG design. If the entropy rate is in flux, there is no reliable way to extract entropy in an information theoretic manner. 'For a few seconds' is almost an infinite time @ 16 Mhz for kiddie Arduino kit, and even longer for cleverer ESP32 devices. You have to fix this.

Just because you've not seen any papers mentioning this technique is pretty irrelevant. You will find that there is an arms race to develop ever faster TRNGs given that one time pads are so common these days. We're up to about 1 Tbit/s, and that just gets you more funding. Faster is better, Shannon–Hartley limits not withstanding. There is no funding for CMOS cameras as current research is around spontaneous laser emission, chaos or zero point quantum fluctuation. All these ignore tactical uses of one time pads but require a £100k photonics table. Although I did find Practical True Random Number Generator using CMOS Image Sensor Dark Noise and Quantum Random Number Generation on a Mobile Phone. Nevertheless, the principle focus of research is laser based as the entropy rates are massively higher.

If your technique passes the standard randomness tests, it's random. That's it.

• "there is an arms race to develop ever faster TRNGs given that one time pads are so common these days". Uh? Can you cite actual uses of the OTP for sizable amount of data, that would make the speed of the TRNG relevant? Also "If your technique passes the standard randomness tests, it's random" is to be taken with a truckload of salt (drop that in the void where the hypothesized nature of what's tested should be). – fgrieu May 22 '20 at 5:48
• @fgrieu Whilst it's fascinating to learn what a sawtooth waveform is, it's pretty much a null argument. You can't really build an entropy source in good faith that isn't truly random once it passes randomness tests. This question is about randomness extraction and CMOS camera research, not how to defeat NIST. – Jacob May 22 '20 at 12:56