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\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 KECCAKf, 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 subcases 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.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 Boolean functionssymmetric cryptographybijectivity
 Contact author(s)
 kamil otal @ gmail com
 History
 20231120: approved
 20231117: received
 See all versions
 Short URL
 https://ia.cr/2023/1782
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1782, author = {Kamil Otal}, title = {A Solution to a Conjecture on the Maps $\chi_n^{(k)}$}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1782}, year = {2023}, url = {https://eprint.iacr.org/2023/1782} }