17
$\begingroup$

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".

$\endgroup$
  • 3
    $\begingroup$ There's even a Universal PRG - it's secure if secure PRGs exist. $\:$ $\endgroup$ – user6973 May 14 '12 at 22:27
  • $\begingroup$ Do you mean cryptographic PRGs? If so, then don't we know that (cryptographic) PRGs are equivalent to OWFs? $\endgroup$ – Henry Yuen May 15 '12 at 0:33
  • 2
    $\begingroup$ Yes. $\;\;$ Split the $k$-bit seed into approximately $\sqrt{k}$ blocks of approximately $\sqrt{k}$ bits each, run $\hspace{.2 in}$ the first [number of blocks] Turing machines on the corresponding blocks for up to $k^2$ steps, $\hspace{.15 in}$ pad the outputs to $\:k+1\:$ bits, and output the xor of those TM's outputs. $\;\;$ (Just like Levin's universal search, this can't be used in practice.) $\;\;\;\;$ $\endgroup$ – user6973 May 15 '12 at 2:33
  • 1
    $\begingroup$ maybe more relevant to practice are results related to randomness required for hashing: from the classical bounded independence families to more recent results like Mitzenmacher-Vadhan (pairwise independence + some entropy in the input gives pseudorandomness sufficient for linear probing and bloom filters) or the Patrascu-Thorup results on tabulation hashing. $\endgroup$ – Sasho Nikolov May 18 '12 at 17:51
  • 1
    $\begingroup$ "Yet these methods are used indiscriminately in all sorts of applications, ranging from cryptographic protocols...". I hope not. Mersenne Twisters should not be used for cryptography since they are not cryptographically strong though there are variants that may be. $\endgroup$ – Mike Samuel May 18 '12 at 22:07
13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I guess you wanted to link to one of Jonathan Katz's papers in place to his webpage. Btw, would you like us to merge this with your other account? $\endgroup$ – Kaveh May 18 '12 at 16:11
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer, Yuval. However, I don't fully believe that pseudorandom generator constructions from cryptography are impractically inefficient. As far as I can see, nobody has done a study of this. $\endgroup$ – Henry Yuen May 17 '12 at 2:33
  • 2
    $\begingroup$ I also disagree with the blanket statement that standard pseudorandom generators suffice for "everyday purposes". As the recent "Ron was wrong, Whit was right" paper showed, defective pseudorandom generation has led to embarrassing vulnerabilities for a non-negligible amount of people. That particular analysis was simple enough; how many "real world" applications may suffer more subtle vulnerabilities because LSFRs aren't adequate? If the added computational overhead needed for theoretically sound PRGs aren't that much, why not use them? $\endgroup$ – Henry Yuen May 17 '12 at 2:34
  • 1
    $\begingroup$ @HenryYuen LSFRs are not used for cryptographic applications in any decent, modern system. (Of course, there are badly designed systems out there, such as GSM which is taught in introductory courses as how not to do it.) The problems found in the “Ron was wrong, Whit is right” paper weren't with the quality of PRNG themselves, but with the quality of entropy gathering. $\endgroup$ – Gilles 'SO- stop being evil' May 19 '12 at 10:20

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.