The state diagram of $$\chi $$

AbstractIn 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 $$χas a Boolean map on bi-infinite sequences,$${\mathbb {F}}_2^{{\mathbb {Z}}}$$F2Z. It is defined by$$\sigma \mapsto \nu $$σ↦νwhere each$$\nu _i = \sigma _i + (\sigma _{i+1}+1)\sigma _{i+2}$$νi=σi+(σi+1+1)σi+2. A map$$\chi _n$$χnis a map that operates onn-bit arrays with periodic boundary conditions. This corresponds with$$\chi $$χrestricted to periodic infinite sequences with period that dividesn. This map$$\chi _n$$χnis used in various permutations, e.g.,Keccak-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 $$χon periodic sequences. It turns out that$$\chi $$χis surjective on the set ofallperiodic sequences. We will show what sequences will give collisions after one application of$$\chi $$χ. We prove that, for oddn, the order of$$\chi _n$$χn(in the group of bijective maps on$${\mathbb {F}}_2^n$$F2n) is$$2^{\lceil {\text {lg}}(\frac{n+1}{2})\rceil }$$2⌈lg(n+12)⌉. A given periodic sequence lies on a cycle in the graph of$$\chi $$χ, 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 $$χit will. Furthermore, we can see, for a given$$\sigma $$σ, the length of the cycle in its component in the state diagram. Finally, we extend the surjectivity of$$\chi $$χto$${\mathbb {F}}_2^{{\mathbb {Z}}}$$F2Z, thus to include non-periodic sequences.