nach oben

Designs, Codes and Cryptography

Erschienen in:

01.08.2023

Analysis and computation of multidimensional linear complexity of periodic arrays

verfasst von: Rafael Arce, Carlos Hernández, José Ortiz, Ivelisse Rubio, Jaziel Torres

Erschienen in: Designs, Codes and Cryptography | Ausgabe 3/2024

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Linear complexity is an important parameter for arrays that are used in applications related to information security. In this work we survey constructions of two and three dimensional arrays, and present new results on the multidimensional linear complexity of periodic arrays obtained using the definition and method proposed in Arce-Nazario et al. (Appl. Algebra Eng Commun Comput 31(1):43–63, 2020), Gomez-Perez et al. (2015 IEEE International Symposium on Information Theory, pp 2697–2701, 2015) and Moreno et al. (US Provisional Patent Applications, 2015). The results include a generalization of a bound for the linear complexity, a comparison with the measure of complexity for multisequences, and computations of the complexity of arrays with periods that are not relatively prime for which the “unfolding method” does not work. Conjectures for exact formulas and the asymptotic behavior of the complexity of some array constructions are formulated. We also present open source software for constructing multidimensional arrays and for computing their multidimensional linear complexity.

Vorheriger Artikel Constructing irreducible polynomials recursively with a reverse composition method

Nächster Artikel Quantum impossible differential attacks: applications to AES and SKINNY

Although the hypothesis of the theorem cited in these papers is not completely correct (for example, consider \(x^2+x+6 \in \mathbb {F}_{11}[x]\) and note that the sequence obtained does not have length 12), it is true that sequences of length \(q+1\) can be constructed using certain rational functions over \(\mathbb {F}_q\).

Alderson T.L.: n-dimensional optical orthogonal codes, bounds and optimal constructions. Appl. Algebra Eng. Commun. Comput. 30(5), 373–386 (2019).MathSciNetCrossRef

Arce-Nazario R., Castro F., Gomez-Perez D., Moreno O., Ortiz-Ubarri J., Rubio I., Tirkel A.: Multidimensional linear complexity analysis of periodic arrays. Appl. Algebra Eng. Commun. Comput. 31(1), 43–63 (2020).MathSciNetCrossRef

Bömer L., Antweiler M., Schotten H.: Quadratic residue arrays. Frequenz 47(7–8), 190–196 (1993).

Ding C., Helleseth T., Shan W.: On the linear complexity of Legendre sequences. IEEE Trans. Inform. Theory 44(3), 1276–1278 (1998).MathSciNetCrossRef

Gomez-Perez D., Hoholdt T., Moreno O., Rubio I.: Linear complexity for multidimensional arrays—a numerical invariant. In 2015 IEEE International Symposium on Information Theory (ISIT), pp. 2697–2701, June 2015.

Gomez-Perez D., Gomez A.-I., Tirkel A.: Arrays composed from the extended rational cycle. Adv. Math. Commun. 11(2), 313 (2017).MathSciNetCrossRef

Gómez-Pérez D., Gómez Ana I., Tirkel A.: Large families of sequences for CDMA, frequency hopping, and UWB. Cryptogr. Commun. 1, 1–15 (2019).

Leukhin A., Moreno O., Tirkel A.: Secure CDMA and frequency hop sequences. In Proceedings of the Tenth International Symposium on Wireless Communication Systems (ISWCS 2013), pp. 1–5. VDE (2013).

MacWilliams F.J., Sloane N.J.A.: Pseudo-random sequences and arrays. Proc. IEEE 64(12), 1715–1729 (1976).MathSciNetCrossRef

10.

Massey J.L.: Shift-register synthesis and \({\rm BCH}\) decoding. IEEE Trans. Inf. Theory 15, 122–127 (1969).MathSciNetCrossRef

11.

Meidl W., Niederreiter H.: The expected value of the joint linear complexity of periodic multisequences. J. Complex. 19(1), 61–72 (2003).MathSciNetCrossRef

12.

Moreno O., Maric S.V.: A new family of frequency-hop codes. IEEE Trans. Commun. 48(8), 1241–1244 (2000).CrossRef

13.

Moreno O., Tirkel A.: Multi-dimensional arrays for watermarking. In 2011 IEEE International Symposium on Information Theory Proceedings (ISIT), pp. 2691–2695 (2011).

14.

Moreno O., Tirkel A.: New optimal low correlation sequences for wireless communications. In Sequences and Their Applications—SETA 2012. Lecture Notes in Computer Science, vol. 7280, pp. 212–223 (2012).

15.

Moreno O., Høholdt T., Rubio I.: Security of multidimensional arrays. US Provisional Patent Applications, 62/131616 (March, 2015) and 62/174973 (June, 2015).

16.

Ortiz-Ubarri J.: New asymptotically optimal three-dimensional wave-length/space/time optical orthogonal codes for OCDMA systems. Cryptogr. Commun. 12, 785–794 (2020).MathSciNetCrossRef

17.

Rubio I.M., Sweedler M., Heegard C.: Finding a Gröbner basis for the ideal of recurrence relations on m-dimensional periodic arrays. In Contemporary Developments in Finite Fields and Applications, pp. 296–320. World Scientific, Singapore (2016).

18.

Sakata S.: Extension of the Berlekamp-Massey algorithm to \(N\) dimensions. Inf. Comput. 84(2), 207–239 (1990).MathSciNetCrossRef

19.

Tirkel A., Hall T.: New matrices with good auto and cross-correlation. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 89(9), 2315–2321 (2006).

20.

Tirkel A.Z., Osborne C.F., Hall T.H.: Steganography-applications of coding theory, pp. 57–59. In IEEE Information Theory Workshop, Svalbard, Norway (1997).

21.

Torres J.: RST\_Complexity (2019). https://github.com/jazieltorres/RST_Complexity.git.

22.

Yao J., Jiang R., Heng W.: Algebraic construction of optimal frequency hopping patterns based on Welch Costas arrays. IEEE Trans. Veh. Technol. 69(2), 1841–1854 (2019).CrossRef

Titel: Analysis and computation of multidimensional linear complexity of periodic arrays
verfasst von: Rafael Arce
Carlos Hernández
José Ortiz
Ivelisse Rubio
Jaziel Torres
Publikationsdatum: 01.08.2023
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 3/2024
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-023-01274-w

Springer Professional

Analysis and computation of multidimensional linear complexity of periodic arrays

Abstract

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 3/2024

Densities of codes of various linearity degrees in translation-invariant metric spaces

Editorial Note: Coding and Cryptography 2022

Antipodal two-weight rank metric codes

Constructing irreducible polynomials recursively with a reverse composition method

Quantum impossible differential attacks: applications to AES and SKINNY

Modified Patterson–Wiedemann construction

Premium Partner