[JoGu]

Cryptology

IV.4 Perfect Pseudorandom Generators

a7Hzq .#5r<
k\as TK$
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]
Appendix:

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:

The first concrete approaches to the construction of perfect pseudorandom generators yielded algorithms that were too slow for most practical uses (given the then current CPUs), the best known being the BBS generator (for Lenore BLUM, Manuel BLUM, Michael SHUB). But modified approaches soon provided pseudorandom generators that are passably fast und nevertheless (presumably) cryptographically secure.

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 as intersection]

Pseudorandom sequences

For some more theoretical framework see the book by GOLDREICH (Modern Cryptography, Probabilistic Proofs and Pseudorandomness) in the Reference and Book List.

In the literature we find many tests for randomness:

By definition a perfect pseudorandom generator will pass all these tests. However in practice, since perfectness is an »asymptotic property« only, applying these tests can't harm.


Author: Klaus Pommerening, 2000-Nov-27; last change: 2021-Apr-13