New Coefficient Grouping for Complex Affine Layers

Recently, designing symmetric primitives for applications in cryptographic protocols including MPC (Multi-Party Computation), FHE (Fully Homomorphic Encryption), and ZK (Zero-Knowledge) proofs has become an important research topic. Among many such new symmetric schemes, a power function over a large finite field \mathbbF_q is commonly used. In this paper, we revisit the algebraic degree’s growth for an SPN cipher over \mathbbF_2^n (n\ge3) , whose S-box is defined as a composition of a power function P(x)=x^2^d+1 where d\ge1 with a polynomial A(x)=a_0+ \sum_w=1^Wa_wx^2^\beta_w where a_i\in\mathbbF_2^n for 0\le i\le W and a_w\neq0 for 1\le w\le W . 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 (i) a new measure to find proper (\beta_1,\dots,\beta_W) for the algebraic degree’s fastest growth. (ii) a new method to compute the algebraic degree’s upper bound for arbitrary A(x) . Especially, for the Chaghri (CCS 2022), we obtain a tighter upper bound of the algebraic degree.