Periodic multisequences with large error linear complexity

Generalizing the theory of k-error linear complexity for single sequences over a finite field, Meidl et al. (J. Complexity 23(2), 169–192 (2007)) introduced three possibilities of defining error linear complexity measures for multisequences. A good keystream sequence must possess a large linear complexity and a large k-error linear complexity simultaneously for suitable values of k. In this direction several results on the existence, and lower bounds on the number, of single sequences with large k-error linear complexity were proved in Meidl and Niederreiter (Appl. Algebra Eng. Commun. Comput. 14(4), 273–286 (2003)), Niederreiter (IEEE Trans. Inform. Theory 49(2), 501–505 (2003)) and Niederreiter and Shparlinski (In: Paterson (ed.) 9th IMA International Conference on Cryptography and Coding (2003)). In this paper we discuss analogous results for the case of multisequences. We also present improved bounds on the error linear complexity and on the number of sequences satisfying such bounds for the case of single sequences.     

Error linear complexity measures for multisequences

Complexity measures for sequences over finite fields, such as the linear complexity and the k-error linear complexity, play an important role in cryptology. Recent developments in stream ciphers point towards an interest in word-based stream ciphers, which require the study of the complexity of multisequences. We introduce various options for error linear complexity measures for multisequences. For finite multisequences as well as for periodic multisequences with prime period, we present formulas for the number of multisequences with given error linear complexity for several cases, and we present lower bounds for the expected error linear complexity.     

The Asymptotic Behavior of the Joint Linear Complexity Profile of Multisequences

We prove a conjecture on the asymptotic behavior of the joint linear complexity profile of random multisequences over a finite field. This conjecture was previously shown only in the special cases of single sequences and pairs of sequences. We also establish an asymptotic formula for the expected value of the nth joint linear complexity of random multisequences over a finite field. Some more precise results are shown for triples of sequences.     

Remarks on the <Emphasis Type="Italic">k</Emphasis>-error linear complexity of <Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>-periodic sequences

Recently the first author presented exact formulas for the number of 2 ⁿ -periodic binary sequences with given 1-error linear complexity, and an exact formula for the expected 1-error linear complexity and upper and lower bounds for the expected k-error linear complexity, k ≥ 2, of a random 2 ⁿ -periodic binary sequence. A crucial role for the analysis played the Chan–Games algorithm. We use a more sophisticated generalization of the Chan–Games algorithm by Ding et al. to obtain exact formulas for the counting function and the expected value for the 1-error linear complexity for p ⁿ -periodic sequences over prime. Additionally we discuss the calculation of lower and upper bounds on the k-error linear complexity of p ⁿ -periodic sequences over .      

基于代数曲线上具有高广义联合线性复杂度的多重序列

多重序列的联合线性复杂度是衡量基于字的流密码体系安全的一个重要指标. 由元素取自F_q上的m 重序列和元素取自F_q^m 上的单个序列之间的一一对应, Meidl 和Özbudak 定义多重序列的广义联合线性复杂度为对应的单个序列的线性复杂度. 在本文中, 我们利用代数曲线的常数域扩张, 研究两类多重序列的广义联合线性复杂度. 更进一步, 我们指出这两类多重序列同时具有高联合线性复杂度和高广义联合线性复杂度.     

On the joint linear complexity profile of explicit inversive multisequences

We prove lower bounds on the joint linear complexity profile of multisequences obtained by explicit inversive methods and show that for some suitable choices of parameters these joint linear complexity profiles are close to be perfect.     

Characterization of 2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>-periodic binary sequences with fixed 2-error or 3-error linear complexity

The linear complexity of sequences is an important measure of the cryptographic strength of key streams used in stream ciphers. The instability of linear complexity caused by changing a few symbols of sequences can be measured using k-error linear complexity. In their SETA 2006 paper, Fu et al. (SETA, pp. 88–103, 2006) studied the linear complexity and the 1-error linear complexity of 2 ⁿ -periodic binary sequences to characterize such sequences with fixed 1-error linear complexity. In this paper we study the linear complexity and the k-error linear complexity of 2 ⁿ -periodic binary sequences in a more general setting using a combination of algebraic, combinatorial, and algorithmic methods. This approach allows us to characterize 2 ⁿ -periodic binary sequences with fixed 2- or 3-error linear complexity. Using this characterization we obtain the counting function for the number of 2 ⁿ -periodic binary sequences with fixed k-error linear complexity for k = 2 and 3.     

Linear Complexity,k-Error Linear Complexity,and the Discrete Fourier Transform

Complexity measures for sequences of elements of a finite field play an important role in cryptology. We focus first on the linear complexity of periodic sequences. By means of the discrete Fourier transform, we determine the number of periodic sequences S with given prime period length N and linear complexity L_N, 0(S)=c as well as the expected value of the linear complexity of N-periodic sequences. Cryptographically strong sequences should not only have a large linear complexity, but also the change of a few terms should not cause a significant decrease of the linear complexity. This requirement leads to the concept of the k-error linear complexity L_N, k(S) of sequences S with period length N. For some k and c we determine the number of periodic sequences S with given period length N and L_N, k(S)=c. For prime N we establish a lower bound on the expected value of the k-error linear complexity.     

Global optima results for the Kauffman NK model

The Kauffman NK model has been used in theoretical biology, physics and business organizations to model complex systems with interacting components. Recent NK model results have focused on local optima. This paper analyzes global optima of the NK model. The resulting global optimization problem is transformed into a stochastic network model that is closely related to two well-studied problems in operations research. This leads to applicable strategies for explicit computation of bounds on the global optima particularly with K either small or close to N. A general lower bound, which is sharp for K = 0, is obtained for the expected value of the global optimum of the NK model. A detailed analysis is provided for the expectation and variance of the global optimum when K = N−1. The lower and upper bounds on the expectation obtained for this case show that there is a wide gap between the values of the local and the global optima. They also indicate that the complexity catastrophe that occurs with the local optima does not arise for the global optima.