I'm trying to understand the nature of true randomness. I'm building an RNG using a radioactive source. Basically, I'm measuring the time between consecutive decays which in theory should be unpredictable. The distribution of these time measurements shows a Gaussian-like distribution as I predicted. Now my understanding of true randomness requires a uniform distribution of variables, which is all variables are equally likely. How can I transform a Gaussian Distribution to uniform distribution and is it really necessary to have uniformly distributed random bits to have a good generator?
$\begingroup$
$\endgroup$
1
-
7$\begingroup$ The distinction between true randomness and pseudo-randomness has nothing whatever to do with distribution, and in particular, most true random processes do not generate uniformly distributed results. Uniformity comes in as an application requirement, such as for cryptography, so the trick, then, is to derive a uniformly-distributed output from a differently-distributed true random input. Such an output does not fail to be true random on account of there being an intermediary function by which that transformation is achieved. $\endgroup$– John BollingerJan 7, 2021 at 18:34
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
4
You can just follow the instructions on HotBits, which is exactly what you're trying to build. It's been running for years and is the only radioactive TRNG on the internet. It goes into great depth regarding underlying nuclear physics, sample distributions and extractor mechanism.
Although not really within the realms of strict cryptography, there is also a good counting analysis here from Caltech. In a nutshell, at low count rates the click rate follows a Poisson distribution. But as the mean click rate $(\mu$) increases, it morphs into a nice symmetrical Gaussian shape which is typical behaviour of Poisson if $\mu > \approx 20$.
If you can get a good tube and a decent/safe source, it'll be pretty simple if you follow the instructions. Don't worry about the tick distribution. Simply detect the ticks and follow the de-biasing procedure in the sections featuring this:-
It's a reversing von Neumann extractor. It's written up so I won't repeat the details. If tube dead times and saturation levels are met (so that there is no autocorrelation), you'll get uniformly distributed random bits popping out of the de-biasing algorithm. So that we can see HotBits' quality, I downloaded their 91 Mbit data set and ran ent over it:-
Entropy = 1.000000 bits per bit.
Optimum compression would reduce the size
of this 91750400 bit file by 0 percent.
Chi square distribution for 91750400 samples is 0.05, and randomly
would exceed this value 81.93 percent of the times.
Arithmetic mean value of data bits is 0.5000 (0.5 = random).
Monte Carlo value for Pi is 3.141486168 (error 0.00 percent).
Serial correlation coefficient is -0.000773 (totally uncorrelated = 0.0).
They have other more stringent testing on their site, but it's a clean pass at this level. Chi square also answers your "is it really necessary to have uniformly distributed random bits to have good generator?" mini question. Yes, they do have to be uniformly random for cryptographic use.
So do what HotBits does.
Please note this though:-
the increased sensitivity of the RM-80 and its immunity from saturation increased the rate of HotBits generation from about 30 bytes per second to more than 100.
It's not fast. And there's all that high voltage stuff.
answered Jan 5, 2021 at 22:48
-
1$\begingroup$ Thanks for the link. One question, is the only only unbiasing performed the fact that a one bit is emitted if $T_{i+1}>T_i$ followed by emitting a one bit if $T_{i+2}<T_{i+1},$ i.e., reversing the sense of the comparison. $\endgroup$– kodluJan 6, 2021 at 0:22
-
2$\begingroup$ @kodlu Yes I think so. " In practice, to avoid any residual bias resulting from non-random systematic errors in the apparatus or measuring process consistently favouring one state, the sense of the comparison between T1 and T2 is reversed for consecutive bits." I think that it's also meant to nullify any doubts about long term source decay effects. Although I've never seen two von Neumanns back to back, the test results speak for themselves. $\endgroup$ Jan 6, 2021 at 1:00
-
$\begingroup$ Any reason to measure $T_2$ between the third and fourth pulse, rather than second and third? $\endgroup$– fgrieu ♦Apr 30, 2021 at 21:11
-
$\begingroup$ @fgrieu With some speculation, I think that it's to reduce auto-correlation for the extractor. You could make the case that if we measure $T_2$ between $PK_2$ and $PK_3$, we could then write $\text{duration}(PK_1 \to PK_3) = T_1 + T_2$. The addition sign seems like a form of correlation between $T_1$ and $T_2$. No such formula can be written if we go the HotBits way as there's that unknown interval $PK_2 \to PK_3$. Perhaps... $\endgroup$ Apr 30, 2021 at 23:00
$\begingroup$
$\endgroup$
4
Radioactive decay is normally measured by an exponential process assuming environment parameters are constant. This means that the average time between decays assuming stationarity is an exponential random variable, with $$ Pr[T_i>t]=\exp(-\lambda t) $$ for a constant $\lambda.$
If you know $\lambda$ you can divide time into intervals of length $T_0$ such that $$\exp(-\lambda T_0)=1/2$$ and output a one if there is a decay zero otherwise.
There are many reasons this is probably too simplistic, plus the issue of the environmental interference (natural or malicious) with the source statistics.
So just treat $\lambda$ as unknown pick some $T_0$ by observing the source decay rate, and apply an unbiasing algorithm and then pass blocks of long enough output strings through a secure hash function to be sure.
If the source decay rate changes significantly you can adjust $T_0.$
-
$\begingroup$ Thanks for the answer, could you suggest a debiasing algorithm? I used von Neumann Debiaser, which sometimes causes problems. $\endgroup$– rdkylpJan 5, 2021 at 20:30
-
1$\begingroup$ There is also the multi level method of Mitzenmacher. $\endgroup$– kodluJan 5, 2021 at 20:46
-
2$\begingroup$ Is the unbiasing algorithm really needed if passing data through a secure hash function? Taking a conservative estimate of how much entropy is in a sample, then making sure you pass enough samples into the hashing algorithm that the input entropy is larger than the number of bits in the output, is a common approach. $\endgroup$ Jan 6, 2021 at 9:58
-
1$\begingroup$ @James_pic Sorry to jump in. No it's not, but as you implied (100% - common) still leaves a lot of TRNGs that do. VN is just as common in the literature, but that is predicated (bold in my answer) that you measure the correlation to see if it's low enough (typically $R < 10^{-3}$) but there are formal IID tests. My
enttest proves that it is for the HotBits sample. $\endgroup$ Jan 6, 2021 at 12:59
$\begingroup$
$\endgroup$
2
Radio active decay is a Poisson process. I'm a bit puzzled how you got a Gaussian-like distribution of the time between decays, since the time should have an exponential distribution.
In general, if you have a random variable X with a known distribution having a distribution function F, you get a uniform random variable Y in [0,1] by applying the distribution function to the random variable. I.e. Y = F(X).
The distribution function of an exponential distribution is $ F(t) = 1 -e^{-\lambda t} $. So you should be able to get a uniform distribution by plugging the time between decays t into that. The parameter $\lambda$ is the average number of decays in unit time, which you can measure, e.g. by counting the number of decays in one hour (then the unit of time for t is also one hour).
If the OP calculated the average of multiple delays, it will indeed tend towards a Normal (Gaussian) distribution due to the central limit theorem.
-
$\begingroup$ The total number of decay events in a given time period is Poisson, but the OP is asking about elapsed time between decays. $\endgroup$ Jan 7, 2021 at 2:57
-
$\begingroup$ You are conflating Poisson process with Poisson distribution. $\endgroup$– TrayManJan 8, 2021 at 5:49
$\begingroup$
$\endgroup$
1
Any distribution can be transformed to a uniform distribution by simply taking the cumulative distribution. That is, if for each measurement, you calculate the cumulative distribution up the the value that you observed, then the results of those calculations will, for a continuous distribution, be uniformly distributed in the interval the unit interval.
-
$\begingroup$ Absolutely. And there papers that feature exactly this technique. $\endgroup$ Jan 23, 2021 at 22:02
$\begingroup$
$\endgroup$
3
Use a Zenner diode as noise generator, take sample of the noise voltage on the diode (through a capacitor), amplify it and measure the voltage with a ADC. After this process, extract the square root of this value and keep only the mantisa (numeric part after decimal point). It should deliver absolute true random numbers.
-
1$\begingroup$ should't this be Zener diode instead of Zenner diode? $\endgroup$– gelonidaApr 29, 2021 at 9:54
-
1$\begingroup$ That last sentence... There's quite a lot of work/analysis/verification before we get IID "true" random numbers suitable for cryptography though. $\endgroup$ Apr 29, 2021 at 12:17
-
$\begingroup$ I think is a lot faster than using a radioactive decay anaysis.. which is gaussian btw $\endgroup$ Apr 29, 2021 at 12:35