{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T15:37:16Z","timestamp":1774021036075,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,1,17]],"date-time":"2024-01-17T00:00:00Z","timestamp":1705449600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,1,17]],"date-time":"2024-01-17T00:00:00Z","timestamp":1705449600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["788980"],"award-info":[{"award-number":["788980"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2024,5]]},"abstract":"Abstract<\/jats:title>In symmetric cryptography, block ciphers, stream ciphers and permutations often make use of a round function and many round functions consist of a linear and a non-linear layer. One that is often used is based on the cellular automaton that is denoted by$$\\chi $$<\/jats:tex-math>\u03c7<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>as a Boolean map on bi-infinite sequences,$${\\mathbb {F}}_2^{{\\mathbb {Z}}}$$<\/jats:tex-math>F<\/mml:mi>2<\/mml:mn>Z<\/mml:mi><\/mml:msubsup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. It is defined by$$\\sigma \\mapsto \\nu $$<\/jats:tex-math>\u03c3<\/mml:mi>\u21a6<\/mml:mo>\u03bd<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>where each$$\\nu _i = \\sigma _i + (\\sigma _{i+1}+1)\\sigma _{i+2}$$<\/jats:tex-math>\u03bd<\/mml:mi>i<\/mml:mi><\/mml:msub>=<\/mml:mo>\u03c3<\/mml:mi>i<\/mml:mi><\/mml:msub>+<\/mml:mo>(<\/mml:mo>\u03c3<\/mml:mi>i<\/mml:mi>+<\/mml:mo>1<\/mml:mn><\/mml:mrow><\/mml:msub>+<\/mml:mo>1<\/mml:mn>)<\/mml:mo><\/mml:mrow>\u03c3<\/mml:mi>i<\/mml:mi>+<\/mml:mo>2<\/mml:mn><\/mml:mrow><\/mml:msub><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. A map$$\\chi _n$$<\/jats:tex-math>\u03c7<\/mml:mi>n<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is a map that operates onn<\/jats:italic>-bit arrays with periodic boundary conditions. This corresponds with$$\\chi $$<\/jats:tex-math>\u03c7<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>restricted to periodic infinite sequences with period that dividesn<\/jats:italic>. This map$$\\chi _n$$<\/jats:tex-math>\u03c7<\/mml:mi>n<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is used in various permutations, e.g.,Keccak<\/jats:sc>-f (the permutation in SHA-3), ASCON (the NIST standard for lightweight cryptography), Xoodoo, Rasta and Subterranean (2.0). In this paper, we characterize the graph of$$\\chi $$<\/jats:tex-math>\u03c7<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>on periodic sequences. It turns out that$$\\chi $$<\/jats:tex-math>\u03c7<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is surjective on the set ofall<\/jats:italic>periodic sequences. We will show what sequences will give collisions after one application of$$\\chi $$<\/jats:tex-math>\u03c7<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We prove that, for oddn<\/jats:italic>, the order of$$\\chi _n$$<\/jats:tex-math>\u03c7<\/mml:mi>n<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>(in the group of bijective maps on$${\\mathbb {F}}_2^n$$<\/jats:tex-math>F<\/mml:mi>2<\/mml:mn>n<\/mml:mi><\/mml:msubsup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>) is$$2^{\\lceil {\\text {lg}}(\\frac{n+1}{2})\\rceil }$$<\/jats:tex-math>2<\/mml:mn>\u2308<\/mml:mo>lg<\/mml:mtext>(<\/mml:mo>n<\/mml:mi>+<\/mml:mo>1<\/mml:mn><\/mml:mrow>2<\/mml:mn><\/mml:mfrac>)<\/mml:mo><\/mml:mrow>\u2309<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. A given periodic sequence lies on a cycle in the graph of$$\\chi $$<\/jats:tex-math>\u03c7<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, or it can be represented as a polynomial. By regarding the divisors of such a polynomial one can see whether it lies in a cycle, or after how many iterations of$$\\chi $$<\/jats:tex-math>\u03c7<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>it will. Furthermore, we can see, for a given$$\\sigma $$<\/jats:tex-math>\u03c3<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the length of the cycle in its component in the state diagram. Finally, we extend the surjectivity of$$\\chi $$<\/jats:tex-math>\u03c7<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>to$${\\mathbb {F}}_2^{{\\mathbb {Z}}}$$<\/jats:tex-math>F<\/mml:mi>2<\/mml:mn>Z<\/mml:mi><\/mml:msubsup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, thus to include non-periodic sequences.<\/jats:p>","DOI":"10.1007\/s10623-023-01349-8","type":"journal-article","created":{"date-parts":[[2024,1,17]],"date-time":"2024-01-17T15:02:22Z","timestamp":1705503742000},"page":"1393-1421","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["The state diagram of $$\\chi $$"],"prefix":"10.1007","volume":"92","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0751-291X","authenticated-orcid":false,"given":"Jan","family":"Schoone","sequence":"first","affiliation":[]},{"given":"Joan","family":"Daemen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,1,17]]},"reference":[{"issue":"4","key":"1349_CR1","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1016\/S0021-9800(69)80032-3","volume":"6","author":"S Ahmad","year":"1969","unstructured":"Ahmad S.: Cycle structure of automorphisms of finite cyclic groups. J. Comb. Theory 6(4), 370\u2013374 (1969).","journal-title":"J. Comb. Theory"},{"key":"1349_CR2","unstructured":"Bertoni G., Daemen J., Peeters M., Van Assche G.: KECCAK specifications, NIST SHA-3 Submission (2008). http:\/\/keccak.noekeon.org\/."},{"key":"1349_CR3","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1016\/j.ffa.2007.08.003","volume":"14","author":"A \u00c7e\u015fmelio\u011flu","year":"2008","unstructured":"\u00c7e\u015fmelio\u011flu A., Meidl W., Topuzo\u011flu A.: On the cycle structure of permutation polynomials. Finite Fields Appl. 14, 593\u2013614 (2008).","journal-title":"Finite Fields Appl."},{"key":"1349_CR4","doi-asserted-by":"crossref","unstructured":"Claesen L., Daemen J., Genoe M., Peeters G.: Subterranean: a 600 mbit\/sec cryptographic vlsi chip, pp. 610\u2013613 (1993).","DOI":"10.1109\/ICCD.1993.393304"},{"key":"1349_CR5","unstructured":"Daemen J.: Cipher and Hash Function Design Strategies based on linear and differential cryptanalysis. Ph.D. thesis, Katholieke Universiteit Leuven (1995)."},{"issue":"4","key":"1349_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.46586\/tosc.v2018.i4.1-38","volume":"2018","author":"J Daemen","year":"2018","unstructured":"Daemen J., Hoffert S., Van Assche G., Van Keer R.: The design of Xoodoo and Xoofff. IACR Trans. Symmetric Cryptol. 2018(4), 1\u201338 (2018).","journal-title":"IACR Trans. Symmetric Cryptol."},{"issue":"S1","key":"1349_CR7","doi-asserted-by":"publisher","first-page":"262","DOI":"10.46586\/tosc.v2020.iS1.262-294","volume":"2020","author":"J Daemen","year":"2020","unstructured":"Daemen J., Massolino P.M.C., Mehrdad A., Rotella Y.: The subterranean 2.0 cipher suite. IACR Trans. Symmetric Cryptol. 2020(S1), 262\u2013294 (2020).","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"1349_CR8","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1007\/978-3-319-96884-1_22","volume-title":"Advances in Cryptology\u2013CRYPTO 2018","author":"C Dobraunig","year":"2018","unstructured":"Dobraunig C., Eichlseder M., Grassi L., Lallemand V., Leander G., List E., Mendel F., Rechberger C.: Rasta: a cipher with low AND depth and few ANDs per Bit. In: Shacham H., Boldyreva A. (eds.) Advances in Cryptology\u2013CRYPTO 2018, pp. 662\u2013692. Springer, Cham (2018)."},{"key":"1349_CR9","unstructured":"Dobraunig C., Eichlseder M., Mendel F., Schl\u00e4ffer M.: Ascon v1.2 Submission to NIST (2021)."},{"key":"1349_CR10","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/s001459900025","volume":"10","author":"S Even","year":"1997","unstructured":"Even S., Mansour Y.: A construction of a cipher from a single pseudorandom permutation. J. Cryptol. 10, 151\u2013161 (1997).","journal-title":"J. Cryptol."},{"issue":"4","key":"1349_CR11","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/s00145-022-09439-x","volume":"35","author":"F Liu","year":"2022","unstructured":"Liu F., Sarkar S., Meier W., Isobe T.: The inverse of $$\\chi $$ and its applications to rasta-like ciphers. J. Cryptol. 35(4), 28 (2022).","journal-title":"J. Cryptol."},{"key":"1349_CR12","first-page":"105","volume":"8","author":"AF M\u00f6bius","year":"1832","unstructured":"M\u00f6bius A.F.: \u00dcber eine besondere Art von Umkehrung der Reihen. J. f\u00fcr die reine und angewandte Mathematik 8, 105\u2013123 (1832).","journal-title":"J. f\u00fcr die reine und angewandte Mathematik"},{"issue":"1","key":"1349_CR13","doi-asserted-by":"publisher","first-page":"53","DOI":"10.7146\/math.scand.a-11616","volume":"38","author":"H Niederreiter","year":"1976","unstructured":"Niederreiter H.: On the cycle structure of linear recurring sequences. Mathematica Scandinavica 38(1), 53\u201377 (1976).","journal-title":"Mathematica Scandinavica"},{"key":"1349_CR14","unstructured":"NIST: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Fucntions. FIPS PUB 202 (2015). https:\/\/nvlpubs.nist.gov\/nistpubs\/FIPS\/NIST.FIPS.202.pdf."},{"key":"1349_CR15","unstructured":"NIST: Lightweight Cryptography Standardization Process: NIST Selects Ascon (2023). https:\/\/csrc.nist.gov\/News\/2023\/lightweight-cryptography-nist-selects-ascon."},{"key":"1349_CR16","doi-asserted-by":"crossref","unstructured":"Sakzad A., Sadeghi M.R., Panario D.: Cycle structure of permutation functions over finite fields and their applications (2012).","DOI":"10.3934\/amc.2012.6.347"},{"key":"1349_CR17","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/BF01782364","volume":"102","author":"A Tychonoff","year":"1930","unstructured":"Tychonoff A.: \u00dcber die topologische Erweiterung von R\u00e4umen. Mathematische Annalen 102, 544\u2013561 (1930).","journal-title":"Mathematische Annalen"},{"key":"1349_CR18","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1007\/BF01472255","volume":"111","author":"A Tychonoff","year":"1935","unstructured":"Tychonoff A.: \u00dcber einen Funktionenraum. Mathematische Annalen 111, 762\u2013766 (1935).","journal-title":"Mathematische Annalen"},{"key":"1349_CR19","volume-title":"General Topology","author":"S Willard","year":"1970","unstructured":"Willard S.: General Topology. Addison-Wesley Publishing Company Inc., Boston (1970)."},{"key":"1349_CR20","volume-title":"A New Kind of Science","author":"S Wolfram","year":"2002","unstructured":"Wolfram S.: A New Kind of Science. Wolfram Media, Champaign (2002)."}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-023-01349-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-023-01349-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-023-01349-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T06:57:48Z","timestamp":1731049068000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-023-01349-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,17]]},"references-count":20,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["1349"],"URL":"https:\/\/doi.org\/10.1007\/s10623-023-01349-8","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,17]]},"assertion":[{"value":"1 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 July 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 December 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}