1
$\begingroup$

True random number generator (TRNG) designs I read about mostly consist of two digital stages:

  • Low-frequency sampling (of a physical noise source)
  • Randomness extractor

The noise signal is sampled at a low frequency to avoid correlation. Functionally, this is equivalent to the following three stages:

  1. High-frequency sampling
  2. Decimator
  3. Randomness extractor

In this design, (1) produces a correlated and biased source, (2) decorrelates the source and (3) extracts the entropy to produce an uniformly distributed output.

Now imagine that we swap the stage (2) and (3) such that the extractor feeds the decimator input. What are the implications for the TRNG?

I know that some extractor (such as the von Neumann extractor) only work for independant (not correlated) sources. What about other extractors or the use of a PRNG before decimation? My intuition is that a PRNG—since it does not change the amount of entropy—will "trade" the bias for more correlation.

$\endgroup$
1
$\begingroup$

Now imagine that we swap the stage (2) and (3) such that the extractor feeds the decimator input. What are the implications for the TRNG?

You'll be hit hard with NIST's 800-90B min.entropy calculation for correlated entropy sources. I'm assuming that you're concerned with kosher TRNG's not hybrid models like NIST's DRBG from 800-90A. Those tip out shed loads of pseudo-random bits in-between reseeds (also like \dev\urandom).

That means you need to extract unbiased bits (bias < $2^{-64}$, correlation <$10^{-3}$) from the raw possibly correlated source. Yet you will be aware of the issues concerning NIST's ea_non_iid assessment tool. And there is no other that I'm aware of. So you can't with any authoritative certainty. But you can ascertain whether a source is IID with a high degree of certainty. That's why it is common to either decimate the raw source samples, or adjust the resolution/frequency $(\epsilon, \tau^{-1})$ of the sampling regime instead till IID samples are obtained.

...since it does not change the amount of entropy...

But you have to reduce (so change) the amount of entropy coming from the TRNG's raw source. Otherwise you'll create a hybrid TRNG which produces a large (but pretty much immeasurable) amount of pseudo-randomness in the output stream.

What about other extractors or the use of a PRNG before decimation?

A PRNG cannot compress the samples, so it a PRNG cannot act as an extractor without massive and very inefficient reseeding. And decimation cannot significantly increase the entropy rate, all it can do is convert non-IID samples to IID ones.

You can see this type of conditioning here, where I decorrelate ~21 KB JPEG files to 5.8 KB via some quirky mix of entropy reduction and sampling regime change. In my linked example, I use SHA-512 as an extractor to compress 778 bits to 512 in order to achieve $\epsilon = 2^{-128}$ in accordance with the Left Over Hash Lemma.

$\endgroup$
2
  • $\begingroup$ "But you have to reduce the amount of entropy coming from the TRNG's raw source." I implied swapping (2) and (3) with the same decimation factor and not hybrid RNG. I think the implications very much depend on the particular extractor/RNG that is used. $\endgroup$
    – DurandA
    Jul 26 at 23:57
  • $\begingroup$ I was not aware that you were the author of this awesome website. Thank you for your interesting answer. $\endgroup$
    – DurandA
    Jul 26 at 23:58

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.