International Association for Cryptologic Research

International Association
for Cryptologic Research


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
DOI: 10.1007/978-3-031-38548-3_18 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: 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 $\mbb{F}_2^n$ and the power map over a large finite field $\mbb{F}_{p^n}$. In this work, we study the growth of the algebraic degree for an SPN cipher over $\mbb{F}_{2^n}^{\width}$, whose S-box is defined as the combination of a power map $x\mapsto x^{2^d+1}$ and an $\mbb{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: \begin{enumerate} \item can the algebraic degree increase exponentially when $w=1$? \item what is the influence of $w$, $d$ and $(h_1,\ldots,h_w)$ on the growth of the algebraic degree? \end{enumerate} 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.
  title={Coefficient Grouping for Complex Affine Layers},
  author={Fukang Liu and Lorenzo Grassi and Clémence Bouvier and Willi Meier and Takanori Isobe},