CryptoDB
Coefficient Grouping for Complex Affine Layers
| Authors: |
|
|---|---|
| Download: |
|
| 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. |
BibTeX
@inproceedings{crypto-2023-33110,
title={Coefficient Grouping for Complex Affine Layers},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-38548-3_18},
author={Fukang Liu and Lorenzo Grassi and Clémence Bouvier and Willi Meier and Takanori Isobe},
year=2023
}