### On the Existence of Secure Keystream Generators

Journal of Cryptology ** 14 ** (2001) 1-15.
Author:

Andrew Klapper, 779A Anderson Hall, Dept. of Computer Science,
University of Kentucky, Lexington, KY, 40506-0046, klapper at cs.uky.edu.

**Abstract**
Designers of stream ciphers have generally used ad hoc methods to build
systems that are secure against known attacks. There is often a sense that
this is the best that can be done, that any system will eventually fall to a
practical attack. In this paper we show that there are families of keystream
generators that resist all possible attacks of a very general type in which a
small number of known bits of a keystream are used to synthesize a generator
of the keystream (called a synthesizing algorithm). Such attacks are
exemplified by the Berlekamp-Massey attack. We first formalize the notions of
a family of finite keystream generators and of a synthesizing algorithm. We
then show that for any function h(n) that is in O(2^{n/d}) for every d>0,
there is a secure family B of periodic sequences in the sense that any
efficient synthesizing algorithm outputs a generator of size h(log(per(B)))
given the required number of bits of a sequence B in B of large enough period.
This result is tight in the sense it fails for any faster growing function
h(n). We also consider several variations on this scenario.

**Index Terms --**
Binary sequences, nonlinear feedback registers, security, cryptography,
stream ciphers.