Are theoretically sound pseudorandom generators used in practice?

Question

As far as I'm aware, most implementations of pseudorandom number generation in practice use methods such as linear shift feedback registers (LSFRs), or these "Mersenne Twister" algorithms. While they pass lots of (heuristic) statistical tests, there are no theoretical guarantees that they look pseudorandom to, say, all efficiently computable statistical tests. Yet these methods are used indiscriminately in all sorts of applications, ranging from cryptographic protocols to scientific computing to banking (probably). I find it somewhat worrisome that we have little to no guarantee about whether these applications work as intended (because any sort of analysis would likely have assumed true randomness as input).

On the other hand, complexity theory and cryptography provide a very rich theory of pseudorandomness, and we even have candidate constructions of pseudorandom generators that would fool ANY efficient statistical test you could come up with, using candidate one way functions.

My question is: has this theory made its way into practice? I would hope that for important uses of randomness, such as cryptography or scientific computing, theoretically sound PRGs are used.

As an aside, I could find some limited analysis of how well popular algorithms such as quicksort work when using LSFRs as a source of randomness, and apparently they work well. See Karloff and Raghavan's "Randomized algorithms and pseudorandom numbers".

Answer 1

The notion of "theoretically sound" pseudorandom generators is not really well defined. After all, no pseudorandom generator has a proof of security. I don't know that we can say that a pseudorandom generator based on the hardness of factoring large integers is "more secure" than, say, using AES as a pseudorandom generator. (In fact, there is a sense that it is less secure, since we know of quantum factoring algorithms but not quantum algorithms to break AES.)

What we do have mathematical proofs for are various composition results, saying that if you compose block-ciphers or hash functions in certain ways you can get pseudorandom generators or pseudorandom function. Some such results are widely used in practice, e.g., HMAC. But it's true that the results that achieve a PRG and start with just assuming that the basic component is a plain one-way function are not efficient enough to use for applications (and this is at least partly inherent). So, typically we need to assume a PRG/stream cipher/block-cipher/hash function as a basic primitive, and start building other things from it. The issue is not really about asymptotic analysis since essentially all cryptographic reductions (except perhaps for Levin's universal PRG) can be made concrete and so give concrete guarantees under concrete assumptions.

But even though they are not based on one-way functions, there is a sense in which constructions such as AES are "theoretically sound" because: (1) There are formal conjectures about their security. (2) There is work to try to refute these conjectures, and also derive implications from them.

And indeed, people are aware that for many applications, it would not be smart to use PRG's such as LSFR that do not satisfy (1) and (2) above.

Answer 2

You seem to be confusing theory with practice. A theoretically sound pseudorandom generator is a bad fit for practical use for several reasons:

• It's probably very inefficient.
• The security proof is only asymptotic, and so for the particular security parameter used, the pseudorandom generator may be easy to break.
• All security proofs are conditional, so in some sense it doesn't even satisfy the notion of theoretical security.

In contrast to this, actual pseudorandom generators are fast, and come in different flavors depending on their use. For non-cryptographic use, almost anything other than a plain LFSR will do the job - not provably, but in practice (which is more important for people using stuff in reality).

For cryptographic use, people try to be more clever. At this point your criticism makes sense: we can't know that a particular pseudorandom generator used is "safe", and indeed some old ones have been broken, for example RC4 as used in WEP. However, for the reasons stated above, using a theoretically (conditionally) sound pseudorandom generator is unfortunately not a realistic solution. Instead, the cryptological community relies on "peer review" - other researchers that try to "break" the system (their definition of when a cipher is broken is very wide).

Finally, in applications when the money can be invested and security is important enough - say nuclear codes - people use physically generated noise (passed through a randomness extractor), though even that is not beyond theoretical criticism.

---

When researchers write grant proposals or introductions to papers, they often claim that their research pertains and informs practice. Whether they believe in it or it's just lip service I don't know (and it may depend on the researcher), but you should be aware that the connection is greatly exaggerated in academic circles, for obvious reasons.

One thing that limits us as mathematical researchers is our dogmatic attachment to formal proof. You mention analysis of randomized algorithms fed by simple pseudorandom generators. This kind of analysis cannot be extended to real-world problems, since they are simply too complicated. And yet, in practice people solve even NP-hard problems all the time, with informed methods.

Real-world problems are better understood with a more scientific and experimental eye. They are better solved from an engineering perspective. They inspire theoretical research, and occasionally are informed by it. As Dijsktra said, (theoretical) computer science is not really about computers, not any more.