New security analysis for UOV-based signature candidates with small public key size

Among candidates for the NIST PQC additional call for digital signatures, there exist seven UOV-based multivariate schemes. Further, four UOV-based candidates, MAYO, QR-UOV, VOX, and SNOVA, achieve small public key size compared with the plain UOV. This work gives a new security analysis for these UOV variants with small public keys. Our main contributions are the following two points: First, we show that the rectangular MinRank attack originally proposed on the Rainbow scheme by Beullens is applicable to MAYO, QR-UOV, and VOX. Second, we explain the construction of SNOVA from a different point of view from the original papers, and reconsider its security analysis. Through our analysis, we show that all parameters of VOX and some parameters of SNOVA submitted in the additional call do not satisfy the claimed security levels.