Local Randomness in Pseudo-Random Sequences

Ueli Maurer and James L. Massey

Journal of Cryptology, vol. 4, no. 2, pp. 135–149, 1991, Preliminary version: [MauMas89].

The concept of provable cryptographic security for pseudo-random number generators that was introduced by Schnorr is investigated and extended. The cryptanalyst is assumed to have infinite computational resources and hence the security of the generators does not rely on any unproved hypothesis about the difficulty of solving a certain problem, but rather relies on the assumption that the number of bits of the generated sequence the enemy can access is limited. The concept of perfect local randomness of a sequence generator is introduced and investigated using some results from coding theory. The theoretical and practical cryptographic implications of this concept are discussed. Possible extensions of the concept of local randomness as well as some applications are proposed.

Keywords: pseudo-random number generator, provable security, local randomness.

BibTeX Citation

@article{MauMas91a,
    author       = {Ueli Maurer and James L. Massey},
    title        = {Local Randomness in Pseudo-Random Sequences},
    journal      = {Journal of Cryptology},
    pages        = 135--149,
    number       = 2,
    volume       = 4,
    year         = 1991,
    note         = {Preliminary version: \cite{MauMas89}},
}