Cryptanalysis on UOV and its Variants

[Hiroki Furue]

Dear all,

In our recent work, we propose a new key-recovery framework for UOV by generalizing the symmetric-algebra attack proposed by Jin et al. Using this framework, we found that it outperforms existing attacks for multiple proposed parameter sets of UOV and SNOVA.

Our proposed framework is constructed as the XL algorithm using the structure of truncated polynomial rings over F_{p^e}, where all monomials involving p^l-th (or higher) powers of variables are set to zero for 1 \le l \le e. Within this framework, we analyze the reconciliation attack and newly take into account the intersection attack.

Applying our framework to the NIST Round-2 parameter sets, we found that the intersection attack becomes more efficient for UOV, reducing the estimated security of uov-Ip, uov-III, and uov-V. We also found that the reconciliation attack using the proposed framework reduces the security of the parameter sets of SNOVA with l=2. By contrast, for MAYO and QR-UOV, our framework does not improve over the best known attacks mainly because their parameter sets do not yield a sufficiently large linear solution space for the intersection attack to be effective.

Details are available on ePrint: https://eprint.iacr.org/2026/298

 

Best regards,

Hiroki Furue and Yasuhiko Ikematsu