×

Linear complexity profile and correlation measure of interleaved sequences. (English) Zbl 1343.94033

Summary: Let \(m\) be a positive integer. We study the linear complexity profile and correlation measure of two interleaved \(m\)-ary sequences of length \(s\) and \(t\), respectively. In the case that \(s \geq 2t\) or \(s = t\) and \(m\) is prime we estimate the correlation measure in terms of the correlation measure of the first base sequence and the length of the second base sequence. In this case a relation by N. Brandstätter and A. Winterhof [Period. Math. Hung. 52, No. 2, 1–8 (2006; Zbl 1127.11050)] immediately implies a lower bound on the linear complexity profile of the interleaved sequence. If \(m\) is not a prime, under the same restrictions on \(s\) and \(t\), the power correlation measure introduced by Z. Chen and A. Winterhof [Indag. Math., New Ser. 20, No. 4, 631–640 (2009; Zbl 1237.11034)] takes the role of the correlation measure to obtain lower bounds on the linear complexity profile. Moreover, we show that these restrictions on \(s\) and \(t\) are necessary, and otherwise the (power) correlation measure can be close to \(st\). However, introducing and estimating the (power) correlation measure with bounded lags we are able to get a lower bound on the linear complexity profile of the interleaved sequence.

MSC:

94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
94A60 Cryptography
11K36 Well-distributed sequences and other variations
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brandstätter, N., Winterhof, A.: Linear complexity profile of binary sequences with small correlation measure. Period. Math. Hung. 52, 1-8 (2006) · Zbl 1127.11050 · doi:10.1007/s10998-006-0008-1
[2] Golomb, S.W., Gong, G.: Signal Design for Good Correlation. Cambridge University Press, Cambridge (2005) · Zbl 1097.94015 · doi:10.1017/CBO9780511546907
[3] Chen, Z., Winterhof, A.: Linear complexity profile of m-ary pseudorandom sequences with small correlation measure. Indag. Mathem. 20, 631-640 (2011) · Zbl 1237.11034 · doi:10.1016/S0019-3577(09)80030-X
[4] Gong, G.: Theory and applications of q-ary interleaved sequences. IEEE Trans. Inform. Theory 41, 400-411 (1995) · Zbl 0943.94509 · doi:10.1109/18.370141
[5] Gong, G.: New design for signal sets with low cross-correlation, balance property, and large linear span: GF(p) case. IEEE Trans. Inform. Theory 48, 2847-2867 (2002) · Zbl 1062.94026 · doi:10.1109/TIT.2002.804044
[6] Gyarmati, K.: Measures of pseudorandomness. In: Charpin, P., Pott, A., Winterhof A. (eds.) Finite fields and their applications, 43-64, Radon Ser. Comput. Appl. Math., vol. 11. De Gruyter, Berlin (2013) · Zbl 1304.11077
[7] He, J.J., Panario, D., Wang, Q.: A family of binary sequences from interleaved construction and their cryptographic properties. Contemp. Math. 518, 209-223 (2010) · Zbl 1206.94035 · doi:10.1090/conm/518/10207
[8] Hu, H., Gong, G.: New sequence families with zero or low correlation zone via interleaving techniques. ISIT 2009, Korea, 124-128 (2009) · Zbl 1127.11050
[9] Mauduit, C., Sárközy, A.: On finite pseudorandom binary sequences, I: Measures of pseudorandomness, the Legendre symbol. Acta Arith 82, 365-377 (1997) · Zbl 0886.11048
[10] Mauduit, C., Sárközy, A.: On finite pseudorandom sequences of k symbols. Indag. Mathem. 13, 89-101 (2002) · Zbl 1049.11090 · doi:10.1016/S0019-3577(02)90008-X
[11] Shparlinski, I.E.: Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness. Progress in Computer Science and Applied Logic, vol. 22. Birkhäuser Verlag, Basel (2003) · Zbl 1036.94001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.