1
$\begingroup$

I know that for most programs pseudo-random numbers are sufficient, but there are ways that machines can generate truly random numbers! There are devices that generate unpredictable processes. However, they tend to be biased somehow. So, is it possible to make devices that can generate unpredictable processes and also unbiased (truly random)? (Please note that I am not asking whether true randomness can be achieved by composing PRNG)

$\endgroup$
4
2
$\begingroup$

What is true randomness, and is it necessary? Algorithms cannot distinguish truly random bits from pseudorandom bits (by definition!), and so in practice we are only interested in generating strongly pseudorandom bits. As indicated above, true randomness ensures that even if we run the same algorithm twice, we get different results.

True randomness is required only in highly classified cryptographic applications, such as one-time pads, used for strategic communication. Although pseudorandom bits are still enough, now the bar is a lot higher, due to the importance of the data being encoded. Nevertheless, by crunching more pseudorandom and truly random (but biased and correlated) bits together, we can create highly secure one-time pads. High-quality randomness is generated by combining physical noise and "bit crushers"; stated differently, by injecting "true" randomness into a pseudorandom number generator.

The idea is to start with a high-quality pseudorandom generator, and stick a "pipe" of low-quality true noise into it. The low-quality true noise is truly random, but not iid: it could be highly biased, there could be significant correlations, and so on. By combining it with a good "bit cruncher", the resulting stream of random bits combines the advantages of both sources: it is more unpredictable than the already highly unpredictable pseudorandom generator, and it does not suffer from the bias and correlations of the actual physical source of noise.

Is this "true randomness"? No. But computers won't be able to distinguish the difference. This is already true for high-quality pseudorandom generators, so what did we gain? Two things. First, we may think that the pseudorandom generator is strong, but perhaps it's weak; by injecting true randomness, we strengthen it. Second, even a high-quality stream of pseudorandom bits can be predicted if you know the initial seed. For this reason, when reproducibility is not required, pseudorandom generators are initialized with a seed produced from actual (although low-quality) physical randomness.

The pseudorandom generator used in Unix systems employs this methodology. It keeps an "entropy pool" — a source of true, low-quality randomness — and mixes it into a pseudorandom generator. In practice, it works quite well, although it's not completely bullet-proof. Using a dedicated physical random noise generator would result in a much enhanced stream of random bits which should be difficult to attack.

$\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.