Coefficient Grouping for Complex Affine Layers

Designing symmetric-key primitives for applications in Fully Homomorphic Encryption (FHE) has become important to address the issue of the ciphertext expansion. In such a context, cryptographic primitives with a low-AND-depth decryption circuit are desired. Consequently, quadratic nonlinear functions are commonly used in these primitives, including the well-known χ function over F n 2 and the power map over a large finite field Fpn . In this work, we study the growth of the algebraic degree for an SPN cipher over F m 2 n , whose S-box is defined as the combination of a power map x → x 2 d +1 and an F2-linearized affine polynomial x → c0 + w i=1 cix 2 h i where c1, . . . , cw ̸ = 0. Specifically, motivated by the fact that the original coefficient grouping technique published at EUROCRYPT 2023 becomes less efficient for w > 1, we develop a variant technique that can efficiently work for arbitrary w. With this new technique to study the upper bound of the algebraic degree, we answer the following questions from a theoretic perspective:

1. can the algebraic degree increase exponentially when w = 1? 2. what is the influence of w, d and (h1, . . . , hw) on the growth of the algebraic degree?

Based on this, we show (i) how to efficiently find (h1, . . . , hw) to achieve the exponential growth of the algebraic degree and (ii) how to efficiently compute the upper bound of the algebraic degree for arbitrary (h1, . . . , hw). Therefore, we expect that these results can further advance the understanding of the design and analysis of such primitives.