Skip to main content
Top
Published in: Applicable Algebra in Engineering, Communication and Computing 1/2020

05-07-2019 | Original Paper

Multidimensional linear complexity analysis of periodic arrays

Authors: Rafael Arce-Nazario, Francis Castro, Domingo Gomez-Perez, Oscar Moreno, José Ortiz-Ubarri, Ivelisse Rubio, Andrew Tirkel

Published in: Applicable Algebra in Engineering, Communication and Computing | Issue 1/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The linear complexity of a sequence is an important parameter for many applications, especially those related to information security, and hardware implementation. It is desirable to develop a corresponding measure and theory for multidimensional arrays that are consistent with those of sequences. In this paper we use Gröbner bases to develop a theory for analyzing the multidimensional linear complexity of general periodic arrays. We also analyze arrays constructed using the method of composition and establish tight bounds for their multidimensional linear complexity.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Buchberger, B.: PhD thesis 1965: an algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. J. Symb. Comput. 41(3–4), 475–511 (2006)CrossRef Buchberger, B.: PhD thesis 1965: an algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. J. Symb. Comput. 41(3–4), 475–511 (2006)CrossRef
2.
go back to reference Cardell, S.D., Fúster-Sabater, A.: Linear models for the self-shrinking generator based on CA. J. Cellular Autom. 11(2–3), 195–211 (2016)MathSciNetMATH Cardell, S.D., Fúster-Sabater, A.: Linear models for the self-shrinking generator based on CA. J. Cellular Autom. 11(2–3), 195–211 (2016)MathSciNetMATH
3.
go back to reference Cardell, S.D., Fúster-Sabater, A.: Modelling the shrinking generator in terms of linear CA. Adv. Math. Commun. 10(4), 797–809 (2016)MathSciNetCrossRef Cardell, S.D., Fúster-Sabater, A.: Modelling the shrinking generator in terms of linear CA. Adv. Math. Commun. 10(4), 797–809 (2016)MathSciNetCrossRef
4.
go back to reference Cardell, S.D., Fúster-Sabater, A.: Discrete linear models for the generalized self-shrunken sequences. Finite Fields Appl. 47, 222–241 (2017)MathSciNetCrossRef Cardell, S.D., Fúster-Sabater, A.: Discrete linear models for the generalized self-shrunken sequences. Finite Fields Appl. 47, 222–241 (2017)MathSciNetCrossRef
5.
go back to reference Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms, 3rd edn. Springer, New York (2007). An introduction to computational algebraic geometry and commutative algebraCrossRef Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms, 3rd edn. Springer, New York (2007). An introduction to computational algebraic geometry and commutative algebraCrossRef
6.
go back to reference Cusick, T.W., Ding, C., Renvall, A.R.: Stream Ciphers and Number Theory, vol. 66. Elsevier, Amsterdam (2004)MATH Cusick, T.W., Ding, C., Renvall, A.R.: Stream Ciphers and Number Theory, vol. 66. Elsevier, Amsterdam (2004)MATH
7.
go back to reference Ding, C., Helleseth, T., Shan, W.: On the linear complexity of Legendre sequences. IEEE Trans. Inf. Theory 44(3), 1276–1278 (1998)MathSciNetCrossRef Ding, C., Helleseth, T., Shan, W.: On the linear complexity of Legendre sequences. IEEE Trans. Inf. Theory 44(3), 1276–1278 (1998)MathSciNetCrossRef
8.
go back to reference Ding, C., Xiao, G., Shan, W.: The Stability Theory of Stream Ciphers, vol. 561. Springer, Berlin (1991)CrossRef Ding, C., Xiao, G., Shan, W.: The Stability Theory of Stream Ciphers, vol. 561. Springer, Berlin (1991)CrossRef
9.
go back to reference Fang-Wei, F., Niederreiter, H., Özbudak, F.: Joint linear complexity of arbitrary multisequences consisting of linear recurring sequences. Finite Fields Appl. 15(4), 475–496 (2009)MathSciNetCrossRef Fang-Wei, F., Niederreiter, H., Özbudak, F.: Joint linear complexity of arbitrary multisequences consisting of linear recurring sequences. Finite Fields Appl. 15(4), 475–496 (2009)MathSciNetCrossRef
10.
go back to reference Gianni, P., Trager, B., Zacharias, G.: Gröbner bases and primary decomposition of polynomial ideals. J. Symb. Comput. 6(2–3), 149–167 (1988). Computational aspects of commutative algebraCrossRef Gianni, P., Trager, B., Zacharias, G.: Gröbner bases and primary decomposition of polynomial ideals. J. Symb. Comput. 6(2–3), 149–167 (1988). Computational aspects of commutative algebraCrossRef
11.
go back to reference Gomez-Perez, D., Moreno, O., Høholdt, T., 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., Moreno, O., Høholdt, T., Rubio, I.: Linear complexity for multidimensional arrays: a numerical invariant. In 2015 IEEE International Symposium on Information Theory (ISIT), pp. 2697–2701 (June 2015)
12.
go back to reference Gomez-Perez, D., Sha, M., Tirkel, A.: On the linear complexity for multidimensional sequences. J. Complex. 49, 46–55 (2018)MathSciNetCrossRef Gomez-Perez, D., Sha, M., Tirkel, A.: On the linear complexity for multidimensional sequences. J. Complex. 49, 46–55 (2018)MathSciNetCrossRef
13.
go back to reference Gyarmati, K., Mauduit, C., Sárközy, A.: Measures of pseudorandomness of finite binary lattices, I. The measures \( q\_k \), normality. Acta Arith. 144(3), 295–313 (2010)MathSciNetCrossRef Gyarmati, K., Mauduit, C., Sárközy, A.: Measures of pseudorandomness of finite binary lattices, I. The measures \( q\_k \), normality. Acta Arith. 144(3), 295–313 (2010)MathSciNetCrossRef
14.
go back to reference Gyarmati, K., Mauduit, C., Sárközy, A.: On the linear complexity of binary lattices. Ramanujan J. 32(2), 185–201 (2013)MathSciNetCrossRef Gyarmati, K., Mauduit, C., Sárközy, A.: On the linear complexity of binary lattices. Ramanujan J. 32(2), 185–201 (2013)MathSciNetCrossRef
15.
go back to reference Gyarmati, K., Mauduit, C., Sárközy, A.: On linear complexity of binary lattices, II. Ramanujan J. 34(2), 237–263 (2014)MathSciNetCrossRef Gyarmati, K., Mauduit, C., Sárközy, A.: On linear complexity of binary lattices, II. Ramanujan J. 34(2), 237–263 (2014)MathSciNetCrossRef
16.
go back to reference Gyarmati, K., Mauduit, C., Sárközy, A.: On finite pseudorandom binary lattices. Discrete Appl. Math. 216(part 3), 589–597 (2017)MathSciNetCrossRef Gyarmati, K., Mauduit, C., Sárközy, A.: On finite pseudorandom binary lattices. Discrete Appl. Math. 216(part 3), 589–597 (2017)MathSciNetCrossRef
17.
go back to reference Leukhin, A., Moreno, O., Tirkel, A.: Secure CDMA and frequency hop sequences. In: Wireless Communication Systems (ISWCS 2013), Proceedings of the Tenth International Symposium on Wireless Communication Systems, pp. 1–5. VDE (2013) Leukhin, A., Moreno, O., Tirkel, A.: Secure CDMA and frequency hop sequences. In: Wireless Communication Systems (ISWCS 2013), Proceedings of the Tenth International Symposium on Wireless Communication Systems, pp. 1–5. VDE (2013)
18.
19.
20.
go back to reference Massey, J.L.: Shift-register synthesis and \({\rm BCH}\) decoding. IEEE Trans. Inf. Theory IT–15, 122–127 (1969)MathSciNetCrossRef Massey, J.L.: Shift-register synthesis and \({\rm BCH}\) decoding. IEEE Trans. Inf. Theory IT–15, 122–127 (1969)MathSciNetCrossRef
21.
go back to reference Mauduit, C., Sárközy, A.: Construction of pseudorandom binary lattices by using the multiplicative inverse. Monatsh. Math. 153(3), 217–231 (2008)MathSciNetCrossRef Mauduit, C., Sárközy, A.: Construction of pseudorandom binary lattices by using the multiplicative inverse. Monatsh. Math. 153(3), 217–231 (2008)MathSciNetCrossRef
22.
go back to reference Meidl, W., Niederreiter, H.: The expected value of the joint linear complexity of periodic multisequences. J. Complex. 19(1), 61–72 (2003)MathSciNetCrossRef Meidl, W., Niederreiter, H.: The expected value of the joint linear complexity of periodic multisequences. J. Complex. 19(1), 61–72 (2003)MathSciNetCrossRef
23.
go back to reference Mérai, L.: Construction of pseudorandom binary lattices based on multiplicative characters. Period. Math. Hungar. 59(1), 43–51 (2009)MathSciNetCrossRef Mérai, L.: Construction of pseudorandom binary lattices based on multiplicative characters. Period. Math. Hungar. 59(1), 43–51 (2009)MathSciNetCrossRef
24.
go back to reference Mérai, L.: Construction of pseudorandom binary lattices using elliptic curves. Proc. Am. Math. Soc. 139(2), 407–420 (2011)MathSciNetCrossRef Mérai, L.: Construction of pseudorandom binary lattices using elliptic curves. Proc. Am. Math. Soc. 139(2), 407–420 (2011)MathSciNetCrossRef
25.
go back to reference Moreno, O., Høholdt, T., Rubio, I.: Security of multidimensional arrays. US provisional patent applications 62/131616 (March, 2015) and 62/174973 (June, 2015) Moreno, O., Høholdt, T., Rubio, I.: Security of multidimensional arrays. US provisional patent applications 62/131616 (March, 2015) and 62/174973 (June, 2015)
26.
go back to reference Moreno, O., Tirkel, A.: Multi-dimensional arrays for watermarking. In: Information Theory Proceedings (ISIT), pp. 2691–2695. IEEE, Washington, DC (2011) Moreno, O., Tirkel, A.: Multi-dimensional arrays for watermarking. In: Information Theory Proceedings (ISIT), pp. 2691–2695. IEEE, Washington, DC (2011)
27.
go back to reference Moreno, O., Tirkel, A.: New optimal low correlation sequences for wireless communications. In: Sequences and Their Applications—SETA 2012, Volume 7280 of Lecture Notes in Comput. Sci., pp. 212–223. Springer, Heidelberg (2012) Moreno, O., Tirkel, A.: New optimal low correlation sequences for wireless communications. In: Sequences and Their Applications—SETA 2012, Volume 7280 of Lecture Notes in Comput. Sci., pp. 212–223. Springer, Heidelberg (2012)
28.
go back to reference Mullen, G.L., Panario, D.: Handbook of Finite Fields. CRC Press, Boca Raton (2013)CrossRef Mullen, G.L., Panario, D.: Handbook of Finite Fields. CRC Press, Boca Raton (2013)CrossRef
29.
go back to reference Niederreiter, H.: The probabilistic theory of linear complexity. In: Workshop on the Theory and Application of Cryptographic Techniques, pp. 191–209. Springer, Berlin (1988) Niederreiter, H.: The probabilistic theory of linear complexity. In: Workshop on the Theory and Application of Cryptographic Techniques, pp. 191–209. Springer, Berlin (1988)
30.
go back to reference Niederreiter, H., Vielhaber, M., Wang, L.-P.: Improved results on the probabilistic theory of the joint linear complexity of multisequences. Sci. China Inf. Sci. 55(1), 165–170 (2012)MathSciNetCrossRef Niederreiter, H., Vielhaber, M., Wang, L.-P.: Improved results on the probabilistic theory of the joint linear complexity of multisequences. Sci. China Inf. Sci. 55(1), 165–170 (2012)MathSciNetCrossRef
31.
go back to reference Niederreiter, H., Wang, L.-P.: The asymptotic behavior of the joint linear complexity profile of multisequences. Monatsh. Math. 150(2), 141–155 (2007)MathSciNetCrossRef Niederreiter, H., Wang, L.-P.: The asymptotic behavior of the joint linear complexity profile of multisequences. Monatsh. Math. 150(2), 141–155 (2007)MathSciNetCrossRef
32.
go back to reference Rubio, I., Sweedler, M., Heegard, C.: Finding a Gröbner basis for the ideal of recurrence relations on m-dimensional periodic arrays. In: Canteaut, A., Effinger, G., Huczynska, S., Panario, D., Storme, L. (eds.) Contemporary Developments in Finite Fields and Applications, pp. 296–320. World Scientific, Singapore (2016) CrossRef Rubio, I., Sweedler, M., Heegard, C.: Finding a Gröbner basis for the ideal of recurrence relations on m-dimensional periodic arrays. In: Canteaut, A., Effinger, G., Huczynska, S., Panario, D., Storme, L. (eds.) Contemporary Developments in Finite Fields and Applications, pp. 296–320. World Scientific, Singapore (2016) CrossRef
33.
go back to reference Rubio, I.: PhD thesis: Gröbner bases for 0-dimensional ideals and applications to decoding. Cornell University (1998) Rubio, I.: PhD thesis: Gröbner bases for 0-dimensional ideals and applications to decoding. Cornell University (1998)
34.
go back to reference Sakata, S.: Finding a minimal set of linear recurring relations capable of generating a given finite two-dimensional array. J. Symb. Comput. 5(3), 321–337 (1988)MathSciNetCrossRef Sakata, S.: Finding a minimal set of linear recurring relations capable of generating a given finite two-dimensional array. J. Symb. Comput. 5(3), 321–337 (1988)MathSciNetCrossRef
35.
go back to reference Sakata, S.: Extension of the Berlekamp–Massey algorithm to \(N\) dimensions. Inf. Comput. 84(2), 207–239 (1990)MathSciNetCrossRef Sakata, S.: Extension of the Berlekamp–Massey algorithm to \(N\) dimensions. Inf. Comput. 84(2), 207–239 (1990)MathSciNetCrossRef
36.
go back to reference Tirkel, A., Hall, T.: New matrices with good auto and cross-correlation. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 89(9), 2315–2321 (2006)CrossRef Tirkel, A., Hall, T.: New matrices with good auto and cross-correlation. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 89(9), 2315–2321 (2006)CrossRef
37.
go back to reference Tirkel, A., Osborne, C.F., Hall, T.H.: Steganography—applications of coding theory. In: IEEE Information Theory Workshop, Svalbard, Norway, pp. 57–59 (1997) Tirkel, A., Osborne, C.F., Hall, T.H.: Steganography—applications of coding theory. In: IEEE Information Theory Workshop, Svalbard, Norway, pp. 57–59 (1997)
Metadata
Title
Multidimensional linear complexity analysis of periodic arrays
Authors
Rafael Arce-Nazario
Francis Castro
Domingo Gomez-Perez
Oscar Moreno
José Ortiz-Ubarri
Ivelisse Rubio
Andrew Tirkel
Publication date
05-07-2019
Publisher
Springer Berlin Heidelberg
Published in
Applicable Algebra in Engineering, Communication and Computing / Issue 1/2020
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-019-00393-z

Premium Partner