Abstract
The linear complexity of sequences is one of the important security measures for stream cipher systems. Recently, using fast algorithms for computing the linear complexity and the k-error linear complexity of 2n-periodic binary sequences, Meidl determined the counting function and expected value for the 1-error linear complexity of 2n-periodic binary sequences. In this paper, we study the linear complexity and the 1-error linear complexity of 2n-periodic binary sequences. Some interesting properties of the linear complexity and the 1-error linear complexity of 2n-periodic binary sequences are obtained. Using these properties, we characterize the 2n-periodic binary sequences with fixed 1-error linear complexity. Along the way, we obtain a new approach to derive the counting function for the 1-error linear complexity of 2n-periodic binary sequences. Finally, we give new fast algorithms for computing the 1-error linear complexity and locating the error positions for 2n-periodic binary sequences.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cusick, T.W., Ding, C., Renvall, A.: Stream Ciphers and Number Theory. North-Holland Mathematical Library, vol. 55. Elsevier, Amsterdam (1998)
Ding, C., Shan, W., Xiao, G.: The Stability Theory of Stream Ciphers. LNCS, vol. 561. Springer, Heidelberg (1991)
Games, R.A., Chan, A.H.: A fast algorithm for determining the complexity of a binary sequence with period 2n. IEEE Trans. Inform. Theory 29, 144–146 (1983)
Kaida, T., Uehara, S., Imamura, K.: Computation of the k-error linear complexity of binary sequences with period 2n. In: Jaffar, J., Yap, R.H.C. (eds.) ASIAN 1996. LNCS, vol. 1179, pp. 182–191. Springer, Heidelberg (1996)
Kaida, T., Uehara, S., Imamura, K.: An algorithm for the k-error linear complexity of sequences over GF(p m) with period p n, p a prime. Inform. Comput. 151, 134–147 (1999)
Kurosawa, K., Sato, F., Sakata, T., Kishimoto, W.: A relationship between linear complexity and k-error linear complexity. IEEE Trans. Inform. Theory 46, 694–698 (2000)
Lauder, A.G.B., Paterson, K.G.: Computing the error linear complexity spectrum of a binary sequence of period 2n. IEEE Trans. Inform. Theory 49, 273–280 (2003)
Lidl, R., Niederreiter, H.: Finite Fields. Cambridge University Press, Cambridge (1997)
Meidl, W.: How many bits have to be changed to decrease the linear complexity? Des. Codes Cryptogr. 33, 109–122 (2004)
Meidl, W.: On the stability of 2n-periodic binary sequences. IEEE Trans. Inform. Theory 51, 1151–1155 (2005)
Meidl, W., Niederreiter, H.: Counting functions and expected values for the k-error linear complexity. Finite Fields Appl. 8, 142–154 (2002)
Meidl, W., Niederreiter, H.: Linear complexity, k-error linear complexity, and the discrete Fourier transform. J. Complexity 18, 87–103 (2002)
Meidl, W., Niederreiter, H.: On the expected value of the linear complexity and the k-error linear complexity of periodic sequences. IEEE Trans. Inform. Theory 48, 2817–2825 (2002)
Meidl, W., Niederreiter, H.: Periodic sequences with maximal linear complexity and large k-error linear complexity. Appl. Algebra Engrg. Comm. Comput. 14, 273–286 (2003)
Meidl, W., Venkateswarlu, A.: Remarks on the k-error linear complexity of p n-periodic sequences (submitted for publication)
Niederreiter, H.: Some computable complexity measures for binary sequences. In: Ding, C., Helleseth, T., Niederreiter, H. (eds.) Sequences and Their Applications, pp. 67–78. Springer, London (1999)
Niederreiter, H.: Periodic sequences with large k-error linear complexity. IEEE Trans. Inform. Theory 49, 501–505 (2003)
Niederreiter, H.: Linear complexity and related complexity measures for sequences. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 1–17. Springer, Heidelberg (2003)
Niederreiter, H., Paschinger, H.: Counting functions and expected values in the stability theory of stream ciphers. In: Ding, C., Helleseth, T., Niederreiter, H. (eds.) Sequences and Their Applications, pp. 318–329. Springer, London (1999)
Niederreiter, H., Shparlinski, I.E.: Periodic sequences with maximal linear complexity and almost maximal k-error linear complexity. In: Paterson, K.G. (ed.) Cryptography and Coding 2003. LNCS, vol. 2898, pp. 183–189. Springer, Heidelberg (2003)
Rueppel, R.A.: Analysis and Design of Stream Ciphers. Springer, Berlin (1986)
Sălăgean, A.: On the computation of the linear complexity and the k-error linear complexity of binary sequences with period a power of two. IEEE Trans. Inform. Theory 51, 1145–1150 (2005)
Stamp, M., Martin, C.F.: An algorithm for the k-error linear complexity of binary sequences with period 2n. IEEE Trans. Inform. Theory 39, 1398–1401 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fu, FW., Niederreiter, H., Su, M. (2006). The Characterization of 2n-Periodic Binary Sequences with Fixed 1-Error Linear Complexity. In: Gong, G., Helleseth, T., Song, HY., Yang, K. (eds) Sequences and Their Applications – SETA 2006. SETA 2006. Lecture Notes in Computer Science, vol 4086. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11863854_8
Download citation
DOI: https://doi.org/10.1007/11863854_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44523-4
Online ISBN: 978-3-540-44524-1
eBook Packages: Computer ScienceComputer Science (R0)