New Coefficient Grouping for Complex Affine Layers

Recently, designing symmetric primitives for applications in cryptographic protocols including multi-party computation, fully homomorphic encryption, and zero-knowledge proofs has become an important research topic. Among many such new symmetric schemes, a power function over a large finite field <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{F}_{q}$</tex> is commonly used. In this paper, we revisit the algebraic degree's growth for a substitution-permutation network (SPN) cipher over <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{F}_{2^{n}}(n\geq 3)$</tex>, whose S-box is defined as a composition of a power function <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$P(x)=x^{2^{d}+1}$</tex> where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d\geq 1$</tex> with a polynomial <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$A(x)=a_{0}+ \sum\limits_{w=1}^{W}a_{w}x^{2^{\beta_{w}}}$</tex> where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$a_{i}\in \mathbb{F}_{2^{n}}$</tex> for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$0\leq i\leq W$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$a_{w}\neq 0$</tex> for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1\leq w\leq W$</tex>. We propose a new coefficient grouping technique, which is based on our new description of the monomials that will probably appear in the state. Specifically, we propose a new measure to find proper <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(\beta_{1},\beta_{2}, \ldots,\beta_{W})$</tex> for the algebraic degree's fastest growth and a new method to compute the algebraic degree's upper bound for arbitrary <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$A(x)$</tex>. Especially for Chaghri, which was presented at ACM CCS 2022, we obtained a tighter upper bound on the algebraic degree.