[JoGu]

Cryptology

IV.4 Perfect Random 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
  2. The BBS generator and quadratic residuosity [PDF]
  3. Perfect (pseudo-) random generators [PDF]
  4. Examples and practical considerations [PDF]
  5. The MICALI-SCHNORR generator [PDF]
  6. The IMPAGLIAZZO-NAOR generator [PDF]

The complete chapter as PDF file.


Introduction

As we saw the essential cryptologic criterion for random 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 or discrete logarithm. This idea established a new quality standard for random generators, much stronger than statistical tests, but eventually building on unproven mathematical hypotheses. Thus the situation with respect to the security of random 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 random generators. In particular there is no efficient statistical test that is able to distinguish the output of a perfect random generator from a true random sequence. Thus, on the theoretical side, we have a very appropriate model for random generators that are absolutely strong from a statistical viewpoint, and invulnerable from a cryptological viewpoint. In other words:

Perfect random generators are cryptographically secure and statistically undistinguishable from true random sources.
Presumably perfect random generators exist, but there is no com plete mathematical proof ot their existence.
The first concrete approaches to the construction of perfect random generators, the best known being the BBS generator (for Lenore BLUM, Manuel BLUM, Michael SHUB) yielded algorithms that were too slow for most practical uses (given the then current CPUs). But modified approaches soon provided random generators that are passably fast und nevertheless (presumably) cryptographically secure.


Author: Klaus Pommerening, 2000-Nov-27; last change: 2016-Jan-12