Study On Measure Indexes Of Stream Cipher Stability

This dissertation mainly investigates some important measure indexes of stream cipher stability, such as linear complexity and k-error linear complexity. Integrating the notions of linear complexity, k-error linear complexity, k-error linear complexity profile and minerror(S), a new measure index of stream cipher stability, tight error linear complexity, is proposed. The m-tight error linear complexity is a two tuple denoted by (km, LCm). The m-tight error linear complexity of sequence S is the value of km and the km error linear complexity LCm of the mth jump point on the k error linear complexity profile. The algorithms for determining the k-error linear complexity of some periodic sequences are improved, and several fast algorithms for determining the tight linear complexity of periodic sequences are designed. The main results are as follows:1. Based on Wang-Zhang-Xiao algorithm, a new algorithm is invented for determining the k-error linear complexity of a binary sequence with period p~n by utilizing two-dimension vector of cost, where p is a prime and 2 is a primitive root modulo p~2.2. The minimum value of k is investigated for which the k-error linear complexity is strictly less than the linear complexity of sequences with period p~n over GF(q). The upper and lower bounds of the minimum value are derived, where p is a prime and q is a primitive root modulo p~2.3. An efficient algorithm is presented to determine the tight error linear complexity of binary sequences with period 2~n.4. An efficient algorithm is obtained for computing the tight error linear complexity of binary sequences with period p~n, where p is a prime and 2 is a primitive root modulo p~2.5. A fast algorithm is derived for determining the tight error linear complexity of sequences with period 2p~n over GF(q), where p and q are odd primes and q is a primitive root modulo p~2.