Practical key-recovery attack on MQ-Sign

This note describes attacks on the UOV-based signature scheme called MQ-Sign. In more detail, it presents a polynomial-time key-recovery attack on the variants MQ-Sign-RS and MQ-Sign-SS and an improved direct attack on the variant MQ-Sign-SR. The scheme is a first-round candidate in the Korean Post-Quantum Cryptography Competition. Our attack exploits the sparsity of the secret central polynomials in combination with the specific structure of the secret linear map $S$. We provide a verification script for the polynomial-time attack, that recovers the secret key in less than seven seconds for security level V. Furthermore, we added an implementation of the non-guessing part of the direct attack, confirming our complexity estimates