Paper 2023/1782 Original: eprint.iacr.org/2023/1782 ↗

A Solution to a Conjecture on the Maps $\chi_n^{(k)}$

Abstract

The Boolean map $\chi_n^{(k)}:\mathbb{F}_{2^k}^n\rightarrow \mathbb{F}_{2^k}^n$, $x\mapsto u$ given by $u_i=x_i+(x_{(i+1)\ \mathrm{mod}\ n}+1)x_{(i+2)\ \mathrm{mod}\ n}$ appears in various permutations as a part of cryptographic schemes such as KECCAK-f, ASCON, Xoodoo, Rasta, and Subterranean (2.0). Schoone and Daemen investigated some important algebraic properties of $\chi_n^{(k)}$ in [IACR Cryptology ePrint Archive 2023/1708]. In particular, they showed that $\chi_n^{(k)}$ is not bijective when $n$ is even, when $n$ is odd and $k$ is even, and when $n$ is odd and $k$ is a multiple of $3$. They left the remaining cases as a conjecture. In this paper, we examine this conjecture by taking some smaller sub-cases into account by reinterpreting the problem via the Gröbner basis approach. As a result, we prove that $\chi_n^{(k)}$ is not bijective when $n$ is a multiple of 3 or 5, and $k$ is a multiple of 5 or 7. We then present an algorithmic method that solves the problem for any given arbitrary $n$ and $k$ by generalizing our approach. We also discuss the systematization of our proof and computational boundaries.