On the existence of secure keystream generators

Designers of stream ciphers have generally used ad hoc methods to build sys tems that are secure against known attacks. There is often a sense that thi s is the best that can be done, that any system will eventually fall to a p ractical attack. In this paper we show that there are families of keystream generators that resist all possible attacks of a very general type in whic h a small number of known bits of a keystream are used to synthesize a gene rator 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 family a of periodic sequences such that any efficient synth esizing algorithm outputs a generator of size h (log(per(B))) given the req uired number of bits of a sequence B is an element of B of large enough per iod. This result is tight in the sense that it fails for any faster growing function h(n). We also consider several variations on this scenario.