Paper 2025/739 Original: eprint.iacr.org/2025/739 ↗
An Extended Rectangular MinRank Attack against UOV and Its Variants
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.
- History
- 2025-04-25: last updated
- 2025-04-25: published
- Short URL
- https://ia.cr/2025/739
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}