1
$\begingroup$

The Wikipedia article on randomness extraction states that they are different to pseudo random number generators but the distinction is very hazy. Both seem to take in some input quasi-randomness and produce a uniformly random output.

I'm interested in the security aspect of the generated output. I want my final randomness to be private. For PRGs, knowing the seed completely compromises the generated output. Is this also the case for extractors i.e. they are only as secure as the privacy of the input randomness?

More generally, if I have no control over the privacy of my source of randomness, is there any way I can generate (assuming a public protocol that I follow) a private and random string?

$\endgroup$
1
$\begingroup$

Yes, a true random number generator (TRNG) is only as secure as the privacy of the input randomness. We call the input randomness entropy. You're conflating a TRNG and a pseudo random number generator (PRNG) with a randomness extractor.

A randomness extractor is simply a statistical combobulation and transmogrification of an arbitrary input distribution to a uniform distribution. And to reduce inevitable correlation to negligible amounts. It's a component downstream of an entropy source or state. That's it. So an extractor might convert a correlated and normally distributed set of physical samples to an uncorrelated and uniformly distributed set.

There's no strict cryptographic security involved other than (input entropy) > (output). The security of the TRNG comes from the fact that since less entropy is output than input, it is mathematically impossible to discover the original entropy. Some people like to use cryptographic functions as the basis of randomness extractors, but that's not really necessary. However since this is a crypto forum...

Two examples:-

  1. Have a 128 bit counter as a state. Repetitively increment that state. Then encrypt that state with a keyed cipher like AES. You could argue that the encryption part forms a randomness extractor in a PRNG. However, this is not a common paradigm.

  2. Have some physical process generating a truly random digital signal with a wonky distribution. Use some matrix multiplication or cryptographic hashing to produce a uniform distribution with an output bias < $2^{-64}$. This multiplication /hashing component is the randomness extractor part of a TRNG.

Now of course if someone knew the original state /entropy, the output sequence would be predictable. Unless you encrypted it with another cipher using a private key, or hashed it with a concatenated private IV. But what would the advantage be over a common PRNG in that case? It would be tantamount to example 1, but worse in that you'd have no idea of prejudice in the public sequence.

$\endgroup$
  • $\begingroup$ Great answer! After I asked the question, I came across en.wikipedia.org/wiki/Leftover_hash_lemma. Perhaps I misunderstand something but is this not the answer to my question where I can use privacy amplification to eliminate the adversary's partial knowledge of the original random string and obtain a random and private string? $\endgroup$ – user1936752 Nov 26 '18 at 21:59
  • $\begingroup$ @user1936752 Er, I'm not sure how that lemma might help you. If everyone knows all $t$ bits of input entropy $n$, $t-n=0$ meaning there is nothing left over for you to use directly without injecting more entropy via a key or IV. And in that case, why not just use your new entropy to construct a PRNG? $\endgroup$ – Paul Uszak Nov 26 '18 at 22:10
  • $\begingroup$ Is there some particular scheme you're looking at constructing, or is this theoretical stuff? $\endgroup$ – Paul Uszak Nov 26 '18 at 22:12
  • $\begingroup$ No, I was just doing some general reading. Thank you for the clarifications! I just wanted to check the case where the adversary gains partial knowledge of the random string - I see that in this case I can use privacy amplification, else if he learns the whole random string I cannot. $\endgroup$ – user1936752 Nov 26 '18 at 22:21

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.