DuX: a block cipher for efficient FHE evaluation

Abstract With the development and practical application of technologies such as Fully Homomorphic Encryption (FHE), Secure Multi-Party Computation (MPC), and Zero-Knowledge Proof (ZK), it has become crucial to research the design and analysis of symmetric cryptographic primitives with low multiplicative complexity and depth. First, by using multiplication and addition over the finite field $$\mathbb {F}_{q}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> </mml:msub> </mml:math> , where $$q$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>q</mml:mi> </mml:math> is either a prime number $$p$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>p</mml:mi> </mml:math> or $$2^{n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:msup> </mml:math> , we proposed a non-linear function over $$\mathbb {F}_{q}^{4}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mrow> <mml:mi>q</mml:mi> </mml:mrow> <mml:mn>4</mml:mn> </mml:msubsup> </mml:math> based on the generalized Feistel structure. This function features a multiplicative complexity of 4, a multiplicative depth of 2 and 8 additions, and its maximum differential/linear probability of the function is bounded by $$q^{-2}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>q</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:math> . Then, we designed a family of HE-friendly block ciphers called DuX. We conduct a comprehensive security analysis of DuX within certain parameters against various cryptanalysis methods, including differential cryptanalysis, linear cryptanalysis, impossible differential cryptanalysis, zero-correlation linear cryptanalysis, integral analysis, related-key differential cryptanalysis, algebraic attacks, slide attacks, reflection attacks, and boomerang attacks. Our research indicates that DuX maintains a robust security margin against those attacks. Finally, based on the BGV scheme in HElib, we present a detailed homomorphic decryption implementation of the DuX instantiated with $$q = 2^{8}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>q</mml:mi> <mml:mo>=</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>8</mml:mn> </mml:msup> </mml:mrow> </mml:math> , $$2^{16}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>16</mml:mn> </mml:msup> </mml:math> and $$65537$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>65537</mml:mn> </mml:mrow> </mml:math> , respectively. The results show that, for the same block size, the throughput of the DuX-128 over $$\mathbb {F}_{2^{8}}^{16}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>8</mml:mn> </mml:msup> </mml:mrow> <mml:mn>16</mml:mn> </mml:msubsup> </mml:math> can reach approximately 14.95 times, 7.85 times and 20.76 times that of the AES-128, Low MC-128 and CHAGHRI, respectively. Compared with YuX-128, its throughput has increased approximately by 21.59%.