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)
4
-
$\begingroup$ Duplicate of: cs.stackexchange.com/questions/67766/achieving-randomness cs.stackexchange.com/questions/13893/… $\endgroup$– Pseudonym ♦Mar 23, 2021 at 5:00
-
$\begingroup$ The answer, by the way, is a qualified "yes", if you start with a truly stochastic process (e.g. atomic decay). $\endgroup$– Pseudonym ♦Mar 23, 2021 at 5:08
-
2$\begingroup$ Does this answer your question? Achieving Randomness $\endgroup$– Andrej BauerMar 23, 2021 at 7:43
-
$\begingroup$ @Pseudonym I do not think this is strictly a duplicate since the other question concerns composing PRNGs while this question asks a broader question of whether true randomness is mechanically possible at all. $\endgroup$– user4577Mar 23, 2021 at 16:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Mar 23, 2021 at 9:03