IACR News item: 06 March 2023
Jan Schoone, Joan Daemen
ePrint Report
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.
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.
Additional news items may be found on the IACR news page.