On The Three Kinds Of Vector Depths

In this paper, we study the properties about the depths of the pseudo-random sequences, which are used as key streams in stream cipher cryptosystems. The security of stream cipher is determined by the randomness properties of the key stream sequences. The linear complexity of a sequence is an important index for assessing its randomness properties. Some authors investigated the linear complexity in terms of the linear recursion relation among many items of a sequence (e.g. LFSR). Etzion thought otherwise. He studied the linear complexity from the point of view of the relation between two items of a sequence (e.g. the first-order difference sequence). He, Bar-Yehuda and Moran initially introduced the notion of vector depth for studying the rotating-table games in computer science. Etzion thought that the depth of a binary vector with length 2r is equal to the linear complexity of the corresponding periodic sequence. Roth also studied the linear complexity in terms of factors in the generation polynomial of a binary vector, and proposed a notion that was identical with Etzion's vector depth. Soon afterwards, Mitchell showed that the set of infinite binary sequences of finite depth is equal to the set of binary sequences of period 2i for some i≥0, and gave the depth distributions for all linear cyclic codes. In this paper we propose to induce the vector depth defined by Etzion and Roth to three categories, and to study the properties of a vector with any length by matrix representations as the major tools.The first five chapters focus on the model of stream cipher and some basic theories of key stream sequences. Especially, in Chapter 3, a comparison is made to tell the subtle differences between character polynomial, feedback polynomial, connect polynomial and minimum polynomial in many essays related to LFSR. Furthermore, we discuss the Massey's Algorithm in detail, which is usually used to compute the linear complexity of a sequence, to lay solid foundation for further study of LFSR.Chapter 6 presents the properties of the three kinds of vector depths over F₂. First, the definitions of five kinds of vector operations and their matrix representations are given, and the definitions of the three kinds of vector depths based on the information above are given too; second, we briefly prove that for n=2^r the three kinds of vector depths are equal to the linear complexity of correspondence sequence, where n is the length of the vector; third, we give the third depth distribution of n-dimensional vector space over F₂. Particularly, for the first time we study the ultimate period of sequence{( E-1)^m ( s )}_m≥0, when the third depth of the vector s is∞. Then, some explicit and interesting period formulas are derived. In addition, we discuss the application scope of the definition of the second depth, and give the third depth distribution of n-dimensional vector space over F₂. Finally, for n=2^r-1 we study the relationship between the first depth and the linear complexity of a sequence, and present a newalgorithm for determining the first depth of vector of length 2^r-1. The last chapter is the description about the properties of the three kinds of vector depths over Fq. Furthermore, similar topics over F2 as mentioned above are partly extended over Fq in this chapter.