[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Enumeration of maximal cycles generated by orthogonal cellular automata

  • Published:
Natural Computing Aims and scope Submit manuscript

Abstract

Cellular automata (CA) are an interesting computational model for designing pseudorandom number generators (PRNG), due to the complex dynamical behavior they can exhibit depending on the underlying local rule. Most of the CA-based PRNGs proposed in the literature, however, suffer from poor diffusion since a change in a single cell can propagate only within its neighborhood during a single time step. This might pose a problem especially when such PRNGs are used for cryptographic purposes. In this paper, we consider an alternative approach to generate pseudorandom sequences through orthogonal CA (OCA), which guarantees a better amount of diffusion. After defining the related PRNG, we perform an empirical investigation of the maximal cycles in OCA pairs up to diameter \(d=8\). Next, we focus on OCA induced by linear rules, giving a characterization of their cycle structure based on the rational canonical form of the associated Sylvester matrix. Finally, we devise an algorithm to enumerate all linear OCA pairs characterized by a single maximal cycle, and apply it up to diameter \(d=16\) and \(d=13\) for OCA respectively over the binary and ternary alphabets.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Availability of data and materials

The experimental data are available at https://github.com/rymoah/hip-to-be-latin-square.

Code availability

The source code is available at https://github.com/rymoah/hip-to-be-latin-square.

Notes

  1. Usually, the general definition of a dynamical system also requires that A is a metric space and that f is continuous with respect to the topology induced by the distance over A (K\(\mathop {{\rm u}}\limits ^{\circ }\)rka 2003). However, since we deal only with the case where the phase space is finite, every update function is trivially continuous with respect to the discrete topology.

  2. Substitution-Permutation Network.

References

  • Bassham III LE, Rukhin AL, Soto J, Nechvatal JR, Smid ME, Barker EB, Leigh SD, Levenson M, Vangel M, Banks DL et al (2010) Sp 800-22 rev. 1a. a statistical test suite for random and pseudorandom number generators for cryptographic applications. National Institute of Standards & Technology

  • Brent R, Zimmermann P (2008) A multi-level blocking distinct degree factorization algorithm. Contemp Math 461:47–58

    Article  MathSciNet  MATH  Google Scholar 

  • Carlet C (2021) Boolean functions for cryptography and coding theory. Cambridge University Press, Cambridge

    MATH  Google Scholar 

  • Daemen J, Govaerts R, Vandewalle J (1994) An efficient nonlinear shift-invariant transformation. In: 15th Symp. on information theory in the Benelux, Louvain-la-Neuve (B), pp 30–31

  • del Rey ÁM, Mateus JP, Sánchez GR (2005) A secret sharing scheme based on cellular automata. Appl Math Comput 170(2):1356–1364

    MathSciNet  MATH  Google Scholar 

  • Eloranta K (1993) Partially permutive cellular automata. Nonlinearity 6(6):1009

    Article  MathSciNet  MATH  Google Scholar 

  • Formenti E, Imai K, Martin B, Yunès J (2014) Advances on random sequence generation by uniform cellular automata. In: Calude CS, Freivalds R, Iwama K (eds) Computing with new resources, vol 8808. Lecture notes in computer science. Springer, Berlin, pp 56–70

    Chapter  Google Scholar 

  • Gallian J (2012) Contemporary abstract algebra. Nelson Education, Scarborough

    MATH  Google Scholar 

  • Gelfand IM, Kapranov M, Zelevinsky A (2008) Discriminants, resultants, and multidimensional determinants. Springer, Berlin

    MATH  Google Scholar 

  • Ghorpade SR, Hasan SU, Kumari M (2011) Primitive polynomials, singer cycles and word-oriented linear feedback shift registers. Des Codes Cryptogr 58(2):123–134

    Article  MathSciNet  MATH  Google Scholar 

  • Ghoshal A, Sadhukhan R, Patranabis S, Datta N, Picek S, Mukhopadhyay D (2018) Lightweight and side-channel secure 4 \({\times }\) 4 S-boxes from cellular automata rules. IACR Trans Symmetric Cryptol 2018(3):311–334

    Article  Google Scholar 

  • Hedlund GA (1969) Endomorphisms and automorphisms of the shift dynamical systems. Math Syst Theory 3(4):320–375

    Article  MathSciNet  MATH  Google Scholar 

  • Herranz J, Sáez G (2018) Secret sharing schemes for (k, n)-consecutive access structures. In: Camenisch J, Papadimitratos P (eds) CANS 2018, Proceedings. Lecture notes in computer science, vol 11124. Springer, Berlin, pp 463–480

  • Jacobson N (1985) Basic Algebra, I. W.H. Freeman and Company

    MATH  Google Scholar 

  • Kari J (2005) Theory of cellular automata: a survey. Theor Comput Sci 334(1–3):3–33

    Article  MathSciNet  MATH  Google Scholar 

  • Keedwell AD, Dénes J (2015) Latin squares and their applications. Elsevier, Amsterdam

    MATH  Google Scholar 

  • Koç CK, Apohan A (1997) Inversion of cellular automata iterations. IEE Proc Comput Digit Tech 144(5):279–284

    Article  Google Scholar 

  • K\(\mathop {{\rm u}}\limits ^{\circ }\)rka P (2003) Topological and symbolic dynamics. Société mathématique de France

  • Leporati A, Mariot L (2014) Cryptographic properties of bipermutive cellular automata rules. J Cell Autom 9(5–6):437–475

    MathSciNet  MATH  Google Scholar 

  • Lidl R, Niederreiter H (1997) Finite fields. Cambridge University Press, Cambridge

    MATH  Google Scholar 

  • Liu Y, Rijmen V, Leander G (2018) Nonlinear diffusion layers. Des Codes Cryptogr 86(11):2469–2484

    Article  MathSciNet  MATH  Google Scholar 

  • Mariot L (2021) Hip to be (Latin) square: maximal period sequences from orthogonal cellular automata. In: CANDAR 2021, Proceedings. IEEE, pp 29–37

  • Mariot L, Leporati A (2014) Sharing secrets by computing preimages of bipermutive cellular automata. In: Was J, Sirakoulis GC, Bandini S (eds) ACRI 2014, Proceedings. Lecture notes in computer science, vol 8751. Springer, Berlin, pp 417–426

  • Mariot L, Leporati A (2018) Inversion of mutually orthogonal cellular automata. In: Mauri G, Yacoubi SE, Dennunzio A, Nishinari K, Manzoni L (eds) ACRI 2018, Proceedings. Lecture notes in computer science, vol 11115. Springer, Berlin, pp 364–376

  • Mariot L, Formenti E, Leporati A (2016) Constructing orthogonal Latin squares from linear cellular automata. CoRR. arXiv:1610.00139

  • Mariot L, Formenti E, Leporati A (2017a) Enumerating orthogonal Latin squares generated by bipermutive cellular automata. In: Dennunzio A, Formenti E, Manzoni L, Porreca AE (eds) AUTOMATA 2017, Proceedings. Lecture notes in computer science, vol 10248. Springer, Berlin, pp 151–164

  • Mariot L, Picek S, Jakobovic D, Leporati A (2017b) Evolutionary algorithms for the design of orthogonal Latin squares based on cellular automata. In: Bosman PAN (ed) GECCO 2017, Proceedings. ACM, pp 306–313

  • Mariot L, Gadouleau M, Formenti E, Leporati A (2020) Mutually orthogonal Latin squares based on cellular automata. Des Codes Cryptogr 88(2):391–411

    Article  MathSciNet  MATH  Google Scholar 

  • Mariot L, Picek S, Leporati A, Jakobovic D (2019) Cellular automata based S-boxes. Cryptogr Commun 11(1):41–62

    Article  MathSciNet  MATH  Google Scholar 

  • Marsaglia G (1996) Diehard: a battery of tests of randomness. http://stat.fsu.edu/geo

  • Martin B (2008) A Walsh exploration of elementary CA rules. J Cell Autom 3(2):145–156

    MathSciNet  MATH  Google Scholar 

  • Meier W, Staffelbach O (1991) Analysis of pseudo random sequence generated by cellular automata. In: Davies DW (ed) EUROCRYPT’91, Proceedings. Lecture notes in computer science, vol 547. Springer, Berlin, pp 186–199

  • Moore C (1997) Quasilinear cellular automata. Physica D 103(1–4):100–132

    Article  MathSciNet  MATH  Google Scholar 

  • Mullen GL, Panario D (2013) Handbook of finite fields. CRC Press, Boca Raton

    Book  MATH  Google Scholar 

  • Picek S, Mariot L, Yang B, Jakobovic D, Mentens N (2017) Design of S-boxes defined with cellular automata rules. In: CF’17, Proceedings. ACM, pp 409–414

  • Shamir A (1979) How to share a secret. Commun ACM 22(11):612–613

    Article  MathSciNet  MATH  Google Scholar 

  • Stinson DR (2004) Combinatorial designs—constructions and analysis. Springer, Berlin

    MATH  Google Scholar 

  • Stinson DR, Paterson M (2018) Cryptography: theory and practice. CRC Press, Boca Raton

    Book  MATH  Google Scholar 

  • Szaban M, Seredynski F (2011) Designing cryptographically strong S-boxes with use of 1d cellular automata. J Cell Autom 6(1):91–104

    MathSciNet  MATH  Google Scholar 

  • Vaudenay S (1994) On the need for multipermutations: cryptanalysis of MD4 and SAFER. In: Preneel B (edi) FSE’94, Proceedings. Lecture notes in computer science, vol 1008. Springer, Berlin, pp 286–297

  • Wolfram S (1985) Cryptography with cellular automata. In: Williams HC (ed) CRYPTO’85, Proceedings. Lecture notes in computer science, vol 218. Springer, Berlin, pp 429–432

Download references

Funding

No funding was received to assist with the preparation of this manuscript.

Author information

Authors and Affiliations

  1. Digital Security Group, Radboud University, PO Box 9010, 6500 GL, Nijmegen, The Netherlands

    Luca Mariot

Authors
  1. Luca Mariot
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Not applicable.

Corresponding author

Correspondence to Luca Mariot.

Ethics declarations

Conflict of interest

The author has no competing interests to declare that are relevant to the content of this article.

Consent to participate

Not applicable.

Consent for publication

Not applicable.

Ethical approval

Not applicable.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Mariot, L. Enumeration of maximal cycles generated by orthogonal cellular automata. Nat Comput 22, 477–491 (2023). https://doi.org/10.1007/s11047-022-09930-1

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11047-022-09930-1

Keywords

Mathematics Subject Classification

Search

Navigation