Paper 2026/2045

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

Abstract

DuX and YuX are recent block cipher families designed for efficient evaluation under fully homomorphic encryption. Both keep sixteen words of a large finite field in four blocks, with a low-degree block-wise S-box and 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' encryption-side evaluation suggests, and we turn this into practical key-recovery attacks. Our starting point is a sufficient criterion for zero sums. It treats affine subspaces in characteristic 2, full prime fields, and multiplicative cosets uniformly, then over prime fields it is tight on every cell we could compute exactly. To turn it into attacks, we add full-block structures, cheap-coordinate elimination, and weighted moments. The first makes the initial S-box layer free, the second extracts equations from states that are only partially balanced, and the third yields thousands of equations from a single structure. We recover the master key of the full twelve-round DuX over $\mathbb{F}_{65537}$ from $2^{32}$ chosen ciphertexts in 45 core-hours, executed on random keys. For YuX, we recover the key of eleven of the fourteen rounds of both YupX-65537 and Yu2X-16 from $2^{32}$ chosen ciphertexts, with both attacks experimentally executed, reducing the data complexity for Yu2X-16 from the previously reported $2^{96}$ to $2^{32}$. Our distinguishers on DuX coincide with those of independent concurrent work by Liu and Sun (eprint 2026/1907). Furthermore, our key recovery attack lowers the data complexity of their full-round attack from $2^{67.58}$ to $2^{32}$.