Cryptology IV.4 Perfect Pseudorandom Generators

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Contents

1. The BBS generator [PDF]
   Mathematica programm as text and as notebook
   For SageMath code the the Appendix.
2. The BBS generator and quadratic residuosity [PDF]
3. Perfect pseudorandom generators [PDF]
4. YAO's criterion [PDF]
5. The prediction test [PDF]
6. Examples and practical considerations [PDF]
7. The MICALI-SCHNORR generator (outline) [PDF]
8. The IMPAGLIAZZO-NAOR generator (outline) [PDF]

• Statistical distinguishers [PDF]

The complete chapter as PDF file.

Introduction

As we saw the essential cryptologic criterion for pseudorandom generators is unpredictability. In the 1980s cryptographers, guided by an analogy with asymmetric cryptography, found a way of modelling this property in terms of complexity theory: Prediction should boil down to a known »hard« algorithmic problem such as factoring integers or discrete logarithm. This idea established a new quality standard for pseudorandom generators, much stronger than statistical tests, but eventually building on unproven mathematical hypotheses. Thus the situation with respect to the security of pseudorandom generators is comparable to asymmetric encryption.

As an interesting twist it soon turned out that in a certain sense unpredictability is a universal property: For an unpredictable sequence there is no efficient algorithm at all that distinguishes it from a true random sequence, a seemingly much stronger requirement (YAO's theorem). This universality justifies the denomination »perfect« for the corresponding pseudorandom generators. In particular there is no efficient statistical test that is able to distinguish the output of a perfect pseudorandom generator from a true random sequence. Thus, on the theoretical side, we have a very appropriate model for pseudorandom generators that are absolutely strong from a statistical viewpoint, and invulnerable from a cryptological viewpoint. In other words:

• Perfect pseudorandom generators are cryptographically secure and statistically undistinguishable from true random sources—and are fit for any efficient application that needs random input..
  
  
• Presumably perfect pseudorandom generators exist, but there is no complete mathematical proof ot their existence.

Looking back at Section 3.6 we might stumble over the apparent contradiction with the general »rule«: »If a sequence has a short description (as the BBS sequence obviously has!), then it can't be random and even has a short description by a linear feedback shift register.« In particular this would yield an efficient algorithm that distinguishes it from a random sequence. However as already stated in 3.6 this rule leaves a small loophole—small small in relative terms but maybe wide enough in absolute terms. The notion of pseudorandomness tries to slip through this loophole, see the figure (where the size of the areas is by far not to scale):

Pseudorandom sequences

• are not random because they have a short description,
• can't nevertheless be efficiently predicted, or distinguished from random sequences.

In the literature we find many tests for randomness:

• MARSAGLIA's diehard test suite, a collection of statistical tests that check the fitness of a sequence for statistical, but not cryptological applications,
• GOLOMB's postulates, see Section 1.10 above,
• the linear complexity profile, see Chapter 3 above,
• MAURER's universal test, see Section 5.4.5 of the Handbook of Applied Cryptography,
• and several more.