Stream ciphers and linear complexity

Abstract

The thesis mainly reviews the mathematical analysis of the security of stream ciphers. Firstly, we will introduce the background ofstream ciphers with their design principles and theoretical security from the information theory viewpoint. Then we will introduce thealgebraic tools for the analysis of linear recurring sequences followed by discussions on the two kinds of basic nonlinear filters.Also, we will discuss the randomness of the sequences over $\mathbb{F}_{q}$ and justify the use of linear complexity profiles to measure the randomness of the key streams generated by linear feedback shift registers. An exploration of the probabilistic properties of sequences over $\mathbb{F}_{q}$ is included too. Finally, we define an important parameter $k$-error linear complexity to measure the security of the key streams and discuss the lower bounds for this parameter of periodic sequences over $\mathbb{F}_{q}$.