Aspects of local linear complexity

Abstract

The concept of linear complexity is important in cryptography, and in particular in the study of stream ciphers. There are two varieties of linear complexity; global linear complexity, which applies to infinite periodic binary sequences, and local linear complexity, which applies to binary sequences of finite length.This thesis is concerned primarily with the latter.The local linear complexity of a finite binary sequence can be computed using the Berlekamp-Massey algorithm. Chapter 2 deals with a number of aspects of this algorithm.The Berlekamp-Massey algorithm also yields the linear complexity profile of a binary sequence. Linear complexity profiles are discussed in Chapter 3, and a number of associated enumeration results are obtained.In Chapter 4 it is shown that if the bits of a binary sequence satisfy certain conditions, expressible as a set of linear equations, then the linear complexity profile of the sequence will be restricted in some way. These restrictions take the form of conditions on the heights of the jumps in the profile.The final chapter deals with the randomness testing of binary sequences. Statistical tests for randomness based on linear complexity profiles are derived, and it is demonstrated how these tests can identify the non-randomness in the sequences discussed in the preceding chapter.