학술논문
YuX: Finite Field Multiplication Based Block Ciphers for Efficient FHE Evaluation
Document Type
Periodical
Source
IEEE Transactions on Information Theory IEEE Trans. Inform. Theory Information Theory, IEEE Transactions on. 70(5):3729-3749 May, 2024
Subject
Language
ISSN
0018-9448
1557-9654
1557-9654
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.