Welcome to the resource topic for 2023/782
Title:
Coefficient Grouping for Complex Affine Layers
Authors: Fukang Liu, Lorenzo Grassi, Clémence Bouvier, Willi Meier, Takanori Isobe
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 \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.
ePrint: https://eprint.iacr.org/2023/782
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .