Extracting Randomness from a Poisson Distribution

Question

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.

Answer 1

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.

Answer 2

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.