Characterization of 2 n -periodic binary sequences with fixed 2-error or 3-error linear complexity
Tóm tắt
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
n
-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
n
-periodic binary sequences in a more general setting using a combination of algebraic, combinatorial, and algorithmic methods. This approach allows us to characterize 2
n
-periodic binary sequences with fixed 2- or 3-error linear complexity. Using this characterization we obtain the counting function for the number of 2
n
-periodic binary sequences with fixed k-error linear complexity for k = 2 and 3.
Tài liệu tham khảo
Cusick T.W., Ding C., Renvall A.: Stream Ciphers and Number Theory. North-Holland (1998).
Ding C., Xiao G., Shan W.: The Stability Theory of Stream Ciphers. Springer (1991).
Fu F.-W., Niederreiter H., Su M.: The characterization of 2n-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 (2006).
Games R.A., Chan A.H.: A fast algorithm for determining the complexity of a pseudo-random sequence with period 2n. IEEE Trans. Inform. Theory 29(1), 144–146 (1983)
Kavuluru R.: 2n-periodic binary sequences with fixed 2-error or 3-error linear complexity. In: Golomb S., Parker M., Pott A., Winterhof A. (eds.) SETA 2008. LNCS, vol. 5203, pp. 252–265. Springer (2008).
Kurosawa K., Sato F., Sakata T., Kishimoto W.: A relationship between linear complexity and k-error linear complexity. IEEE Trans. Inform. Theory 46(2), 694–698 (2000)
Massey J.L.: Shift register synthesis and BCH decoding. IEEE Trans. Inform. Theory 15(1), 122–127 (1969)
Meidl W.: On the stability of 2n-periodic binary sequences. IEEE Trans. Inform. Theory 51(3), 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(1), 87–103 (2002)
Meidl W., Niederreiter H.: On the expected value of linear complexity and the k-error linear complexity of periodic sequences. IEEE Trans. Inform. Theory 48(11), 2817–2825 (2002)
Meidl W., Venkateswarlu A.: Remarks on the k-error linear complexity of p n-periodic sequences. Des. Codes Cryptogr. 42(2), 181–193 (2007)
Rueppel R.A.: Analysis and Design of Stream Ciphers. Springer (1986).
Stamp M., Martin C.F.: An algorithm for the k-error linear complexity of binary sequences with period 2n. IEEE Trans. Inform. Theory 39(4), 1398–1401 (1993)