[Resource Topic] 2023/328: The state diagram of $\chi$

Welcome to the resource topic for 2023/328

Title:
The state diagram of \chi

Authors: Jan Schoone, Joan Daemen

Abstract:

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 as a Boolean map on bi-infinite sequences, \mathbb{F}^{\mathbb{Z}}.
It is defined by \sigma \mapsto \nu where each \nu_i = \sigma_i + (\sigma_{i+1}+1)\sigma_{i+2}.
A map \chi_n is a map that operatos on n-bit arrays with periodic boundary conditions.
This corresponds with \chi restricted to periodic infinite sequences with period that divides n.
This map \chi_n is 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 of \emph{all} periodic sequences.

We will show what sequences will give collisions after one application of \chi.
We prove that, for odd n, the order of \chi_n (in the group of bijective maps on \mathbb{F}^n) is 2^{\lceil \operatorname{lg}(\frac{n+1}2)\rceil}.

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}^{\mathbb{Z}}, thus to include non-periodic sequences.

ePrint: https://eprint.iacr.org/2023/328

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .