On the Existence of Secure Feedback Registers (Extended Abstract).
Andrew Klapper · Theory and Application of Cryptographic Techniques · 1996
Designcrs of stream ciphers have generally used ad hoc meth- ods to build systems that are secxre against known attacks. There is often a sense that this is the best that can be done, that any system will even- tually fall to a practical attack. In this paper we show that thcrc nrc families of keystream generators that resist all possible attacks of a very general t,ype in which a small number of known bits of a keystream are used t,o synthesize a generator of the keystream (called a synthesizing algorithm). Such attacks are exemplified by the Berlekamp-Massey at- tack. We first formalize the notions of a family of feedback registers and of a synthesizing algorithm. We then show that for any function h(n) that is in U(2nld) for every d > 0, there is a secure family B of periodic sequences in thc sense that any efficient synthesizing algorithm outputs a register of size h(log(period(l3))) given the required number of bits of a sequence B E I3 of large enough period. This result is tight in the sense it fails for any faster growing function h(n). UJe also consider several variations on this scenario.