Recent applications of advanced cryptographic protocols like fully homomorphic encryption (FHE) and zero-knowledge proofs (ZKP) have led to the development of new symmetric primitives over large finite fields, known as arithmetization-oriented (AO) ciphers. These designs, which focus on minimizing field multiplications, are highly susceptible to algebraic attacks, particularly higher-order differential attacks. YuX is an FHE-friendly Substitution–Permutation Network (SPN)-based block cipher proposed by Liu et al. in IEEE Trans. Inf. Theory. Its internal state is defined over \(\mathbb {F}_q^{16}\) , where q can be \(2^8, 2^{16}\) , or a prime number \(p=65537\) , corresponding to three variants: \({\textsf {Yu}_{2}\textsf {X}\textsf {-8}}\) , \({\textsf {Yu}_{2}\textsf {X}\textsf {-16}}\) , and \({\textsf {Yu}_{p}\textsf {X}}\) . By using an S-box derived from a Nonlinear Feedback Shift Register (NLFSR), YuX achieves low multiplicative complexity and circuit depth. This paper presents the first third-party cryptanalysis of \({\textsf {Yu}_{2}\textsf {X}\textsf {-8}}\) and \({\textsf {Yu}_{2}\textsf {X}\textsf {-16}}\) , collectively referred to as \({\textsf {Yu}_{2}\textsf {X}}\) . While the designers claim that all YuX variants have at most 6-round integral distinguishers, they did not leverage higher-order differential properties in their analysis. We propose a novel technique based on the concept of exponent sets to efficiently estimate the upper bound on the algebraic degree of the \({\textsf {Yu}_{2}\textsf {X}}\) round function. By tracking the evolution of exponent sets across rounds, we formally prove that the algebraic degree of \({\textsf {Yu}_{2}\textsf {X}}\) increases linearly. Our theoretical findings are validated through both the general monomial prediction technique and experimental zero-sum verification. Based on the derived upper bounds on the algebraic degree, we construct the first higher-order differential distinguishers for \({\textsf {Yu}_{2}\textsf {X}}\) by exploiting the lower algebraic degree of the inverse S-box used in decryption. We then extend these distinguishers to mount key-recovery attacks against 7-round \({\textsf {Yu}_{2}\textsf {X}\textsf {-8}}\) and 11-round \({\textsf {Yu}_{2}\textsf {X}\textsf {-16}}\) . Furthermore, by converting the high-degree algebraic equations into low-degree Boolean systems, we present improved attacks that reach 10 rounds of \({\textsf {Yu}_{2}\textsf {X}\textsf {-8}}\) and the 12 rounds of \({\textsf {Yu}_{2}\textsf {X}\textsf {-16}}\) . These results provide new insights into the algebraic structure and security margin of \({\textsf {Yu}_{2}\textsf {X}}\) .
