New Coefficient Grouping for Complex Affine Layers

Abstract

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$\mathbb{F}_{q}$is commonly used. In this paper, we revisit the algebraic degree's growth for a substitution-permutation network (SPN) cipher over$\mathbb{F}_{2^{n}}(n\geq 3)$, whose S-box is defined as a composition of a power function$P(x)=x^{2^{d}+1}$where$d\geq 1$with a polynomial$A(x)=a_{0}+ \sum\limits_{w=1}^{W}a_{w}x^{2^{\beta_{w}}}$where$a_{i}\in \mathbb{F}_{2^{n}}$for$0\leq i\leq W$and$a_{w}\neq 0$for$1\leq w\leq 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 a new measure to find proper$(\beta_{1},\beta_{2}, \ldots,\beta_{W})$for the algebraic degree's fastest growth and a new method to compute the algebraic degree's upper bound for arbitrary$A(x)$. Especially for Chaghri, which was presented at ACM CCS 2022, we obtained a tighter upper bound on the algebraic degree.