Chinese Journal of Computers   Full Text
Title	Joint k-Error 2-Adic Complexity for Binary Periodic Multi-Sequences
Authors	DONG Li-Hua HU Yu-Pu ZENG Yong
Address	(Key Laboratory of Computer Networks and Information Security of Ministry of Education, Xidian University, Xi’an 710071)
Year	2009
Issue	No.6(1134—1139)
Abstract &   Background	Abstract Cryptographically strong sequences should have a large 2-adic complexity to thwart the known feedback with carry shift register synthesis algorithms. At the same time the change of a few terms should not cause a significant decrease of the 2-adic complexity, that is, the k-error 2-adic complexity should also be large. Recent developments in stream ciphers point towards an interest in word-based stream ciphers, which require the study of the complexity of multi-sequences. This paper introduces joint k-error 2-adic complexity measures for multi-sequences. Several results on the existence and lower bounds on the number of multi-sequences with maximal joint 2-adic complexity and large joint k-error 2-adic complexity are proved. The existence of many such sequences thwarts attacks against the keystreams by exhaustive search. Keywords cryptography; stream cipher; FCSR; joint 2-adic complexity; k-error 2-adic complexity Background This work is supported by a grant from the Major State Basic Research Development Program(973 Program) of China (No.2007CB311201), by the National Natural Science Foundation of China (Nos.60473029, 60673072), and by the National Science Fund for Distinguished Young Scholars (No.60503010). The projects mainly focus on the theory of stream cipher. This research group has published a lot of papers. In the study of the theory of stream cipher, much attention has been paid on the stability theory of stream cipher. This theory suggests that good keystream sequences must not only have a large linear complexity, but also a change of a few terms must not cause a significant drop of the linear complexity. This requirement leads to the theory of the k-error linear complexity of keystream sequences of Niederreiter’s ［2003］. In the study of the Klapper’s FCSR sequences, the following fact has also been found. Let S=(1,0,…,0)∞ or (0,1,1,…,1)∞with period N. Then the 2-adic complexity is log2(2N-1). However, after changing 1 bit within every period, the 2-adic complexity becomes 0. For this case, knowledge of the first few bits can allow the efficient generation of a sequence, which closely approximates the original sequence. This observation motivates the study of the k-error 2-adic complexity of sequences. The area of k-error 2-adic complexity was first formally studied by Wang Lei ［2000］. Then a lower bound of the k-error 2-adic complexity was given by Hu Hong-Gang ［2005］. To respond efficiently considerations, recent developments in stream ciphers point towards an interest in word-based stream ciphers (e.g., RC4, SNOW and the ECRYPT stream cipher project, etc). The theory of such stream ciphers requires a study of the complexity of multi-sequences, i.e., of parallel streams of finitely many sequences. In 2007 Meidl and Niederreiter develop a theory of the k-error linear complexity for multi-sequences. And in 2008 Niederreiter and Venkateswarlu discussed the existence and lower bounds on the number of multi-sequences with large k-error linear complexity. while in 2006, Hu determined the expected value of the joint 2-adic complexity of periodic binary multi-sequences and gave a nontrivial lower bound for the expected value of the joint symmetric 2-adic complexity of periodic binary multi-sequences. In this paper, the authors introduce joint k-error 2-adic complexity measures for multi-sequences. Several results on the existence and lower bounds on the number of multi-sequences with maximal joint 2-adic complexity and large joint k-error 2-adic complexity are proved. The existence of many such sequences thwarts attacks against the keystreams by exhaustive search.