Tracking Algebraic Degree with Exponent Sets: Higher-Order Differential Attacks on FHE-Friendly Cipher Yu2X

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 Fq16, where q can be 28,216, or a prime number p=65537, corresponding to three variants: Yu2X-8, Yu2X-16, and YupX. 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 Yu2X-8 and Yu2X-16, collectively referred to as Yu2X. 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 Yu2X round function. By tracking the evolution of exponent sets across rounds, we formally prove that the algebraic degree of Yu2X 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 Yu2X 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 Yu2X-8 and 11-round Yu2X-16. Furthermore, by converting the high-degree algebraic equations into low-degree Boolean systems, we present improved attacks that reach 10 rounds of Yu2X-8 and the 12 rounds of Yu2X-16. These results provide new insights into the algebraic structure and security margin of Yu2X.