Paper 2023/782
Coefficient Grouping for Complex Affine Layers
Abstract
Designing symmetrickey 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 lowANDdepth decryption circuit are desired. Consequently, quadratic nonlinear functions are commonly used in these primitives, including the wellknown $\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 Sbox 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.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 A major revision of an IACR publication in CRYPTO 2023
 Keywords
 Degree evaluationCoefficient grouping techniqueFinite fields
 Contact author(s)

liufukangs @ gmail com
Lorenzo Grassi @ ruhrunibochum de
clemence bouvier @ inria fr
willimeier48 @ gmail com
takanori isobe @ ai uhyogo ac jp  History
 20230530: approved
 20230529: received
 See all versions
 Short URL
 https://ia.cr/2023/782
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/782, 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{https://eprint.iacr.org/2023/782}}, url = {https://eprint.iacr.org/2023/782} }