Paper 2026/2045

Practical Key Recovery Attacks on Full DuX and Reduced-Round YuX

Abstract

DuX and YuX are two recent families of FHE-friendly block ciphers, designed for efficient evaluation under fully homomorphic encryption. Both keep a state of sixteen words of a large finite field, arranged in four blocks, and each round applies a block-wise S-box of low degree followed by a circulant linear layer. We show that, in the chosen-ciphertext model, the algebraic degree of their decryption functions grows far more slowly than the designers' evaluation of the encryption direction suggests, and we turn this observation into practical key-recovery attacks. The starting point is a sufficient criterion for zero sums. It treats affine subspaces in characteristic 2, full prime fields, multiplicative cosets and arbitrary point sets in one statement, and over prime fields it is tight on every cell we could compute exactly. Three techniques turn the criterion into attacks. Full block structures make the first S-box layer free. Cheap coordinate elimination extracts equations from states that are only partially balanced, helped in characteristic 2 by a second cheap coordinate that exists only there. Weighted moments yield thousands of equations from a single structure, and weights with several indices take the place of further structures. We recover the master key of the full twelve-round DuX over $\mathbb{F}_{65537}$ from $2^{29}$ chosen ciphertexts and over $\mathbb {F}_{2^{16}} $ from $2^{32}$, in both cases in complete runs on random keys, the former in $20$ hours on one processor core. For YuX, we recover the key of eleven of the fourteen rounds of YupX-65537 and of Yu2X-16 from $2^{32}$ chosen ciphertexts, again in complete runs, where the best previous attack on Yu2X-16 needed $2^{96}$. Our distinguishers on DuX coincide with those of concurrent and independent work by Liu and Sun (eprint 2026/1907). Furthermore, our key recovery attacks lower the data of their full-round attacks from $2^{67.59}$ and $2^{67.32}$ chosen ciphertexts to $2^{29}$ and $2^{32}$.

Note: We now add a practical full-round key recovery on DuX(2^16) from a single structure of 2^32 chosen ciphertexts and re-run all practical attacks under a uniform single-thread benchmark.