Welcome to the resource topic for 2023/1782
Title:
A Solution to a Conjecture on the Maps \chi_n^{(k)}
Authors: Kamil Otal
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.
ePrint: https://eprint.iacr.org/2023/1782
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 .