Score:1

Randomness extraction on correlated data in TRNG

us flag

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.

Score:1
cn flag

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.

DurandA avatar
us flag
"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.
DurandA avatar
us flag
I was not aware that you were the author of this awesome website. Thank you for your interesting answer.
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.