Live random digits

The above is 0 bits of free, independent and identically distributed true randomness with an absolutely ridiculous yet world class bias of $\epsilon \approx 2^{-10,000} $. Each 512 bit block is brought to you today by a single pass of 512 bit SHA-2 across single unique frames from the Photonic Instrument.

Standard caveats apply: don’t use it for your bank’s password (we’ve seen it!). And of course we might be keeping a record of it too. And how do you know it’s random anyway? It may have come from a kiddie’s linear congruential generator like RANDU or java.util.Random. This is just intended to be an example of a working, gold standard DIY TRNG. And it’s really really random. Best build your own though!

Randomness extractors are generally applied to a biased entropy source $(X)$ with only $(1-\epsilon)s$ bits of entropy, where $\epsilon$ is a bias away from perfectly random. And the Photonic Instrument is oh so biased. All of the excessive zeros lead to a raw signal bias $\epsilon = 0.0114 $ or $ 2^{-6.45} $. The basic idea of such an extractor is to compute $k$ output bits with high randomness from $n > k$ input bits with less randomness. This is known as the Left Over Hash Lemma.

Given that each bit of the input sequence has entropy $s$ ($s = 1$ for perfect randomness), the probability that the extractor output will deviate from a perfectly uniform $k$-bit string is in accordance[1] with $$ \epsilon = 2^{-(sn-k)/2} $$ NIST generally accepts that $ \epsilon \leq 2^{-64} $ is a sufficiently negligible bias for any cryptographic strength random sequence. As the entropy from the Photonic Instrument arrives in batches of approximately 21.2 kbits, when we use the entire frame, our $ \epsilon \approx 2^{-10,000} $! We don’t know whether contemporary pseudo random functions like SHA-2 can output blocks with so little bias as it’s impossible to generate the requisite massive data sample for analysis. It should offer comfort though that such a simple extraction technique can easily achieve the recommended negligible bias.

In order to not waste scarce entropy, we could recompute $sn$ to achieve a more sane yet still world class target of $\epsilon = 2^{-128} $. The 0.9875 value their-in arises from $H_{\infty} = 7.9$ bits/byte converted to the entropy per singular bit. We also allow for NISTs’ recommendation that approved hash functions can utilise their full minimum internal width, thus not needing to reduce our raw entropy rate to $0.85 \times s$. So based on a raw IID entropy rate of 7.9 bits/byte, we could hash every $n=778$ bits (98 bytes) of the Photonic Instrument’s frames to achieve a world beating bias of $\epsilon = 2^{-128} $, when they are post-processed via a method detailed here.

We only use the above method for bulk randomness extraction on the desktop. This page sticks with hash passes over entire frames, just for simplicity.

References:-

[1] M. Troyer and R. Renner, A randomness extractor for the Quantis device. ID Quantique Technical Paper on Randomness Extractor, September 19, 2012. Available here.