Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
It is well known that a true random generator exploits the randomness occurs in some physical phenomena. Also, the output of a true random generators can be either biased or correlated. Therefore, de-skewing techniques are required.
My question is that if we have two true random bit generators whose outputs are not passing the test-suite of NIST, can we combine these outputs to obtain a random bit generator that passes the statistical randomness testing suites?
If some conditions are true, it is possible to combine two TRNGs into one and get better output from them.
I'll call the two original generators TRNG-1 and TRNG-2, and their combination TRNG-3.
There are multiple ways to combine TRNG-1 and TRNG-2. Below are some examples.
If the TRNGs are good on their own and do not have meaningful correlation, you might be able to get away with a simple XOR. But the methods above are not too complex or expensive, so I'd recommend to stay on the safe side and implement one of them.
This is actually done pretty frequently in circuitry. Consider a generic all digital TRNG based on ring oscillators:-
The above is an even more extreme example than yours, where many (perhaps 32) individual ring oscillators are used. They are all identical, all spectacularly fail any randomness test yet produce entropy by themselves. If 32 ring oscillators are required to produce 1 bit/tick of entropy, you can imagine that each must produce much much less. Their biases must also be very high (which is a characteristic of such oscillators). Combining them greatly improves the entropy rate and therefore reduces the output bias.
Another example is the generation of $m \times n$ randomness extractor matrices used in TRNGs. From ID Quantique, Technical Paper on Randomness Extractor, Version 1.0, September 2012:-
Ideally, the r individual sources used in the described procedure to generate the matrix m should be obtained from different sources.
This anecdotally illustrates the concept. Mathematically the appropriate paradigm is the Piling Up Lemma (Mitsuru Matsui, Linear Cryptanalysis Method for DES Cipher) :-
For $n$ independent, random binary variables, $X_1, X_2, \ldots X_n$,
$$ Pr(X_1 \oplus \ldots \oplus X_n = 0) = \frac{1}{2} + 2^{n-1} \prod_{i=1}^n \epsilon_i $$
Rearranging, so that if $ \epsilon_{1,2, \ldots, n} $ represents the bias of $ X_1 \oplus \ldots \oplus X_n = 0 $, we get the final bias of $n$ combined independent sources as:-
$$ \epsilon_{1,2, \ldots, n} = 2^{n-1} \prod_{i=1}^n \epsilon_i $$
In short, as you combine more and more independent RNGs, the overall output bias tends asymptotically towards zero. So creating a new, better one.
Yes. We can combine two PRNGs and make a better one. The simplest form would be to XOR the two values. If at least one of them is random, so will be the output. This doesn't fix everything, but it has nice provable properties. Essentially it's at least as good as either (Assuming they weren't correlated to begin with).
However, if we have very biased sources with some real entropy, we probably want to apply a cryptographic hash. This is good even with a single RNG source.
Secure random generators typically collect entropy from multiple weak sources and mix them cryptographically (Essentially a hash). Then this entropy pool is a seed for a cryptographically secure PRNG. Suppose we are worried about adversaries with unbounded computation. In that case, we try to estimate how much actual entropy we collected and only output a smaller amount of random bits until we collect more entropy.
