Score:2

Can we combine two true random generators to obtain a new one?

co flag

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?

Maarten Bodewes avatar
in flag
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.
Paul Uszak avatar
cn flag
A lot more about this [here](https://cs.stackexchange.com/q/57648/31167)...
Score:3
cn flag

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.

kodlu avatar
sa flag
Lemma 4 is also known as the piling up Lemma of Matsui.
Score:2
in flag

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.

Score:1
cn flag
Leo

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.