부산대학교 도서관

Summary: ``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 $\Bbb F^n_2$ and the power map over a large finite field $\Bbb F_{p^n}$. In this work, we study the growth of the algebraic degree for an SPN cipher over $\Bbb F^m_{2^n}$, whose S-box is defined as the combination of a power map $x\mapsto x^{2^d+1}$ and an $\Bbb F_2$-linearized affine polynomial $x \mapsto c_0+\sum^w_{i=1}c_ix^{2^{h_i}}$ where $c_1,\dots,c+w\neq 0$. 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: \roster \item"1." can the algebraic degree increase exponentially when $w=1$? \item"2." what is the influence of $w$, $d$ and $(h_1,\dots,h_w)$ on the growth of the algebraic degree? \endroster \par ``Based on this, we show (i) how to efficiently find $(h_1,\dots,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,\dots,h_w)$. Therefore, we expect that these results can further advance the understanding of the design and analysis of such primitives.''