International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Guaranteeing the diversity of number generators

Authors:
Adi Shamir
Boaz Tsaban
Download:
URL: http://eprint.iacr.org/2003/132
Search ePrint
Search Google
Abstract: A major problem in using iterative number generators of the form $x_i=f(x_{i-1})$ is that they can enter unexpectedly short cycles. This is hard to analyze when the generator is designed, hard to detect in real time when the generator is used, and can have devastating cryptanalytic implications. In this paper we define a measure of security, called \emph{sequence diversity}, which generalizes the notion of cycle-length for non-iterative generators. We then introduce the class of counter assisted generators, and show how to turn any iterative generator (even a bad one designed or seeded by an adversary) into a counter assisted generator with a provably high diversity, without reducing the quality of generators which are already cryptographically strong.
BibTeX
@misc{eprint-2003-11847,
  title={Guaranteeing the diversity of number generators},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / pseudorandomness, cycle length, cryptography},
  url={http://eprint.iacr.org/2003/132},
  note={Information and Computation 171 (2001), 350--363. tsaban@math.huji.ac.il 12248 received 15 Jul 2003},
  author={Adi Shamir and Boaz Tsaban},
  year=2003
}