YuX: Finite Field Multiplication Based Block Ciphers for Efficient FHE Evaluation

Abstract

With the growing practical applications of fully homomorphic encryption (FHE), secure multi-party computation (MPC), and zero-knowledge proofs (ZK), there has been an increasing need to design and analyze symmetric primitives that have low multiplication complexity and depth. In this paper, we propose a permutation constructed upon a 4-round nonlinear feedback resistor over$ \mathbb {F}_{q}^{4}$. Our proposed permutation has a multiplication depth of 2 and a multiplication complexity of 4. Significantly, its maximum differential/linear probability is bounded by$q^{-2}$. Based on this nonlinear function, we propose a new family of block ciphers over$ \mathbb {F}_{q}^{16}$called$ \mathsf {YuX}$, whose decryption circuit is highly efficient for FHE evaluation. We further provide specific instantiations, denoted as$ \mathsf {Yu_{2}X}$and$ \mathsf {Yu_{\mathrm {p}}X}$, wherein$q$takes the form of either$2^{n}$or a prime$p$, respectively. Furthermore, we conduct a comprehensive security analysis of$ \mathsf {YuX}$within certain parameters against various cryptanalysis methods employing automatic analysis tools, including the differential attack, linear attack, impossible differential attack, zero-correlation attack, and integral attack, as well as Gröbner basis and linearization attacks. Our research indicates that$ \mathsf {YuX}$maintains a robust security margin against those attacks. Finally, we present a detailed implementation of$ \mathsf {Yu_{2}X}$and$ \mathsf {Yu_{\mathrm {p}}X}$employing the BGV homomorphic encryption scheme. In comparison to ciphers over a field of characteristic 2, the outcomes evince that$ \mathsf {Yu_{2}X}$-8 (over$ \mathbb {F}_{2^{8}}^{16}$) and$ \mathsf {Yu_{2}X}$-16 (over$ \mathbb {F}_{2^{16}}^{16}$) achieve remarkably competitive throughputs, boasting performance approximately 12 times, 17 times, and 9 times superior to AES-128, CHAGHRI, and LowMC-128 (under 128-bit security), respectively. Furthermore, when juxtaposed with ciphers over a field of characteristic$p$, the outcomes affirm that the throughput of$ \mathsf {Yu_{\mathrm {p}}X}$-65537 (over$ \mathbb {F}_{65537}^{16}$) retains considerable competitiveness, registering an approximate fivefold enhancement relative to HERA. Evidently,$ \mathsf {YuX}$exhibits superior throughput compared to a majority of symmetric ciphers within this category.