Paper 2023/782

Coefficient Grouping for Complex Affine Layers

Fukang Liu, Tokyo Institute of Technology
Lorenzo Grassi, Ruhr University Bochum
Clémence Bouvier, Sorbonne University, Inria
Willi Meier, FHNW
Takanori Isobe, University of Hyogo, NICT

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 $\chi$ function over $\mathbb{F}_2^n$ and the power map over a large finite field $\mathbb{F}_{p^n}$. In this work, we study the growth of the algebraic degree for an SPN cipher over $\mathbb{F}_{2^n}^{m}$, whose S-box is defined as the combination of a power map $x\mapsto x^{2^d+1}$ and an $\mathbb{F}_2$-linearized affine polynomial $x\mapsto c_0+\sum_{i=1}^{w}c_ix^{2^{h_i}}$ where $c_1,\ldots,c_w\neq0$. 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 $(h_1,\ldots,h_w)$ on the growth of the algebraic degree? Based on this, we show (i) how to efficiently find $(h_1,\ldots,h_w)$ to achieve the exponential growth of the algebraic degree and (ii) how to efficiently compute the upper bound of the algebraic degree for arbitrary $(h_1,\ldots,h_w)$. Therefore, we expect that these results can further advance the understanding of the design and analysis of such primitives.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2023
Degree evaluationCoefficient grouping techniqueFinite fields
Contact author(s)
liufukangs @ gmail com
Lorenzo Grassi @ ruhr-uni-bochum de
clemence bouvier @ inria fr
willimeier48 @ gmail com
takanori isobe @ ai u-hyogo ac jp
2023-05-30: approved
2023-05-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fukang Liu and Lorenzo Grassi and Clémence Bouvier and Willi Meier and Takanori Isobe},
      title = {Coefficient Grouping for Complex Affine Layers},
      howpublished = {Cryptology ePrint Archive, Paper 2023/782},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.