Paper 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\to {\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 $$ and $$ by generalizing our approach. We also discuss the systematization of our proof and computational boundaries.