A New Cryptanalysis Against UOV-Based Variants MAYO, QR-UOV and VOX

Multivariate public-key cryptography (MPKC) is considered as one of the main candidates for post-quantum cryptography (PQC). In MPKC, the MinRank attacks, which try to solve the MinRank problem obtained from a public key, are important since a lot of multivariate schemes are broken by these attacks. Among them, the rectangular MinRank attack was recently proposed for the Rainbow scheme by Beullens, and it tries to solve a new kind of MinRank problem obtained by transforming the public key of Rainbow. Due to this attack, it is known that the security level of Rainbow was reduced. Rainbow is a multi-layered variant of the UOV scheme, and UOV is considered having a resistance to all MinRank attacks since its public key consists of full rank matrices. Recently, there have been submitted three new variants of the UOV scheme having a small public key, MAYO, QR-UOV and VOX in the NIST PQC standardization of additional digital signature schemes. In this paper, we show that the rectangular MinRank attack is applicable to MAYO, QR-UOV and VOX. Moreover, we estimate the complexity of the attack. In particular, we report that all the parameter sets of VOX submitted to NIST PQC standardization are broken in at most 255 gate operations.