zbMATH — the first resource for mathematics

Analysis and design of stream ciphers. (English) Zbl 0618.94001
Communications and Control Engineering Series. Berlin etc.: Springer- Verlag. XII, 244 p. DM 98.00 (1986).
This book is concerned with stream ciphers. The introduction gives a survey on cryptographic systems and an outline of the rest of the book. Chapter 2 defines the notion of stream cipher system. Moreover the main problem (i.e. to find suitable key stream generators) is stated. In chapter 3 basic concepts of algebra (e.g. finite fields) are discussed. This provides us with the tools needed to tackle the problem mentioned in chapter 2. Also Linear Feedback Shift Registers (LFSRs) are introduced. Chapter 4 treats the notion of random sequences and linear complexity (profile). It appears that the randomness postulates of Solomon Golomb do not give the right criteria; the linear complexity profile turns out to be a more useful concept (cf. p. 53).
Chapter 5 is devoted to the analysis of nonlinear functions which when applied to one or more LFSR-sequences may produce new sequences satisfying the criteria obtained in the previous chapter. In particular, in section 5.1 the author analyses what happens when distinct stages of one LFSR are combined in a nonlinear way and in section 5.2 he describes what happens when sequences of distinct LFSRs are combined in a nonlinear way. Furthermore, the concept of correlation immunity is introduced. It appears that the involved nonlinear functions must satisfy conflicting conditions in order to produce a ”wanted” new sequence. By allowing memory in the nonlinear combining functions these conflicts can be avoided (cf. p. 140). This idea is exploited in chapter 9. In chapter 6 the effects of multiple clocking are studied. The remaining two chapters (7 and 8) discuss ways to apply the classical knapsack problem in the connexion with stream cipher systems.
I think this book is basically a good book for two reasons. Firstly, since there are not so many publications handling the subject of nonlinear combinations of LFSRs, and secondly because the devices and concepts are described in a very transparant way. However, sometimes the proofs are too long and detailed. The concept of quintessential element is non-standard and one should consider twice the introduction of a new notion in a well developed area as field theory. The Berlekamp-Massey algorithm is important enough to be included in this book. I was disappointed that it was not presented.
Typographically I do not like the presentation. The reason for this is that sometimes two formulas interfere because of lines being too close to each other. Sometimes indices are not appended in the right place. Formula (6.28) is not in accordance with the text (cf. p. 157 line eight from top).
The conclusion must be that we can learn a lot from this book, it is nicely and transparently written, but there could be improved a lot when typing errors and typographical flaws are corrected.

94A60 Cryptography
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
94-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory
94-02 Research exposition (monographs, survey articles) pertaining to information and communication theory