An Extended Rectangular MinRank Attack against UOV and Its Variants

Toshihiro Suzuki; Hiroki Furue; Takuma Ito; Shuhei Nakamura; Shigenori Uchiyama

Paper 2025/739

An Extended Rectangular MinRank Attack against UOV and Its Variants

Toshihiro Suzuki, Tokyo Metropolitan University, National Institute of Information and Communications Technology

Hiroki Furue, NTT Social Informatics Laboratories

Takuma Ito, National Institute of Information and Communications Technology

Shuhei Nakamura, Ibaraki University

Shigenori Uchiyama, Tokyo Metropolitan University

Abstract

Multivariate public key cryptography (MPKC) is considered a promising candidate for post-quantum cryptography, with its security relying on the hardness of solving systems of multivariate quadratic equations. Among MPKC schemes, the unbalanced oil and vinegar (UOV) and its variants have been actively studied. Pébereau and Luyten showed that the Kipnis–Shamir attack and the singular point attack can be described within the same framework using the Jacobian matrix. In this study, we demonstrate that the rectangular MinRank attack can also be described within this framework. Furthermore, by leveraging this framework, we extend the feasible target ranks of the rectangular MinRank attack and use this extended attack to analyze the security of UOV and its variants. In conclusion, we confirm that the currently proposed parameters for UOV, MAYO, QR-UOV, and SNOVA are resistant to this attack.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Post-Quantum Cryptography Multivariate Cryptography UOV Rectangular MinRank Attack Singular Point
Contact author(s): szk uui t @ gmail com
hiroki furue @ ntt com
tito @ nict go jp
shuhei nakamura fs71 @ vc ibaraki ac jp
uchiyama-shigenori @ tmu ac jp
History: 2025-04-27: approved; 2025-04-25: received; See all versions
Short URL: https://ia.cr/2025/739
License: CC BY

BibTeX

@misc{cryptoeprint:2025/739,
      author = {Toshihiro Suzuki and Hiroki Furue and Takuma Ito and Shuhei Nakamura and Shigenori Uchiyama},
      title = {An Extended Rectangular {MinRank} Attack against {UOV} and Its Variants},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/739},
      year = {2025},
      url = {https://eprint.iacr.org/2025/739}
}