Paper 2003/132

Guaranteeing the diversity of number generators

Adi Shamir and Boaz Tsaban

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.

Metadata
Available format(s)
PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Information and Computation 171 (2001), 350--363.
Keywords
pseudorandomnesscycle lengthcryptography
Contact author(s)
tsaban @ math huji ac il
History
2003-07-16: received
Short URL
https://ia.cr/2003/132
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2003/132,
      author = {Adi Shamir and Boaz Tsaban},
      title = {Guaranteeing the diversity of number generators},
      howpublished = {Cryptology ePrint Archive, Paper 2003/132},
      year = {2003},
      note = {\url{https://eprint.iacr.org/2003/132}},
      url = {https://eprint.iacr.org/2003/132}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.