Abstract
The linear complexity and k-error linear complexity of sequences are important measures of the strength of key-streams generated by stream ciphers. Fu et al. studied the distribution of \(2^n\)-periodic binary sequences with 1-error linear complexity in their SETA 2006 paper. Recently, people have strenuously promoted the solving of this problem from \(k=2\) to \(k=4\) step by step. Unfortunately, it still remains difficult to obtain the solutions for larger k. In this paper, we propose a new sieve method to solve this problem. We first define an equivalence relationship on error sequences and build a relation between the number of sequences with given k-error linear complexity and the number of pairwise non-equivalent error sequences. We introduce the concept of cube fragment and build specific equivalence relation based on the concept of the cube classes to figure out the number of pairwise non-equivalent error sequences. By establishing counting functions for several base cases and building recurrence relations for different cases of k and L, it is easy to manually get the complete counting function when k is not too large. And an efficient algorithm can be derived from this method to solve the problem using a computer when k is large.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ding, C., Xiao, G., Shan, W.: The Stability Theory of Stream Ciphers. Lecture Notes in Computer Science, vol. 561. Springer, Heidelberg (1991)
Fu, F.-W., Niederreiter, H., Su, M.: The characterization of \(2^k\)-periodic binary sequences with fixed 1-error linear complexity. In: Gong, G., Helleseth, T., Song, H.-Y., Yang, K. (eds.) SETA 2006. LNCS, vol. 4086, pp. 88–103. Springer, Heidelberg (2006). doi:10.1007/11863854_8
Kavuluru, R.: \(2^n\)-periodic binary sequences with fixed k-error linear complexity for \(k\) 2 or 3. In: Golomb, S.W., Parker, M.G., Pott, A., Winterhof, A. (eds.) SETA 2008. LNCS, vol. 5203, pp. 252–265. Springer, Heidelberg (2008). doi:10.1007/978-3-540-85912-3_23
Kavuluru, R.: Characterization of \(2^n\)-periodic binary sequences with fixed 2-error or 3-error linear complexity. Des. Codes Crypt. 53(2), 75–97 (2009)
Kurosawa, K., Sato, F., Sakata, T., Kishimoto, W.: A relationship between linear complexity and \(k\)-error linear complexity. IEEE Trans. Inf. Theory 46(2), 694–698 (2000)
Massey, J.L.: Shift-register synthesis and bch decoding. IEEE Trans. Inf. Theory 15(1), 122–127 (1969)
Meidl, W.: On the stability of \(2^n\)-periodic binary sequences. IEEE Trans. Inf. Theory 51(3), 1151–1155 (2005)
Ming, S.: Decomposing approach for error vectors of k-error linear complexity of certain periodic sequences. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E97–A(7), 1542–1555 (2014)
Rueppel, A.R.: Analysis and Design of Stream Ciphers. Communications and Control Engineering Series. Springer, Heidelberg (1986)
Stamp, M., Martin, C.F.: An algorithm for the \(k\)-error linear complexity of binary sequences with period \(2^n\). IEEE Trans. Inf. Theory 39(4), 1398–1401 (1993)
Zhou, J.: A counterexample concerning the 3-error linear complexity of \(2^n\)-periodic binary sequences. Des. Codes Crypt. 64(3), 285–286 (2012)
Zhou, J., Liu, J., Liu, W.: The 4-error linear complexity distribution for \(2^n\)-periodic binary sequences. CoRR abs/1310.0132 (2013)
Zhou, J., Liu, W.: The \(k\)-error linear complexity distribution for \(2^n\)-periodic binary sequences. Des. Codes Crypt. 73(1), 55–75 (2014)
Zhou, J., Liu, W., Zhou, G.: Cube theory and stable \(k\)-error linear complexity for periodic sequences. In: Lin, D., Xu, S., Yung, M. (eds.) Inscrypt 2013. LNCS, vol. 8567, pp. 70–85. Springer, Heidelberg (2014). doi:10.1007/978-3-319-12087-4_5
Acknowledgments
Many thanks go to the anonymous reviewers for their detailed comments and suggestions. This work was supported by the National Key R&D Program of China with No. 2016YFB0800100, CAS Strategic Priority Research Program with No. XDA06010701, National Key Basic Research Project of China with No. 2011CB302400 and National Natural Science Foundation of China with No. 61671448, No. 61379139.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Pan, W., Bao, Z., Lin, D., Liu, F. (2016). The Distribution of \(2^n\)-Periodic Binary Sequences with Fixed k-Error Linear Complexity. In: Bao, F., Chen, L., Deng, R., Wang, G. (eds) Information Security Practice and Experience. ISPEC 2016. Lecture Notes in Computer Science(), vol 10060. Springer, Cham. https://doi.org/10.1007/978-3-319-49151-6_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-49151-6_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-49150-9
Online ISBN: 978-3-319-49151-6
eBook Packages: Computer ScienceComputer Science (R0)