2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Simply concatenating or even XOR-ing bits from the PRNG may is very likely to show bias, so I think the answer is a simple no. Or a maybe as "combine" is not described. I guess it would have to contain de-skewing techniques similar to having to deal with one TRNG. Actually, I think you can prove this is the case by simply splitting up the one TRNG stream into two by taking every other bit. $\endgroup$
    – Maarten Bodewes
    Jul 16 at 9:10
  • $\begingroup$ A lot more about this here... $\endgroup$
    – Paul Uszak
    Jul 16 at 12:54
1
$\begingroup$

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.

  1. If TRNG-1 is generating $k$ bits of output per second, and TRNG-2 is generating $l$ bits of output per second, their combination (TRNG-3) needs to produce less than $k+l$ bits of output per second. The actual output rate needs to be determined carefully by considering the estimated entropy of both generators, and how much correlation there is between them.
  2. TRNG-1 and TRNG-2 needs to be not completely correlated. As long as there is a small, independent variance between them, a better output can be generated by combining than using either of them on their own.

There are multiple ways to combine TRNG-1 and TRNG-2. Below are some examples.

  1. Cryptographic hash functions
  2. Sponge functions such as Keccak or the Gimli sponge
  3. Multiplication with a randomly-filled matrix
  4. Even simple methods such as Pearson hashing.

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.

$\endgroup$
3
$\begingroup$

This is actually done pretty frequently in circuitry. Consider a generic all digital TRNG based on ring oscillators:-

ros

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.

$\endgroup$
1
  • 1
    $\begingroup$ Lemma 4 is also known as the piling up Lemma of Matsui. $\endgroup$
    – kodlu
    Jul 17 at 10:44
2
$\begingroup$

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.

$\endgroup$

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.