0
$\begingroup$

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.

equal frequency binning

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.

$\endgroup$
0
$\begingroup$

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
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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot for pointing out the possible bias caused by sawtooth pattern and for your advice $\endgroup$ – Andika Wasisto May 22 at 8:07
-1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ "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). $\endgroup$ – fgrieu May 22 at 5:48
  • $\begingroup$ @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. $\endgroup$ – Jacob May 22 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.