Cryptanalysis of Matrix-based UOV

The Unbalanced Oil and Vinegar signature scheme (UOV) is one of multivariate quadratic public key cryptosystems and remains unbroken. In Inscrypt 2015, Tan and Tang proposed variants of UOV, Matrix-based UOV, to reduce the size of the secret key and generate signature faster. We show that Matrix-based UOV is entirely broken by finding equivalent keys in polynomial-time. In practice, we can forge Matrix-based UOV signature at 80 and 100 security levels in less than 0.37 seconds and 0.53 seconds, respectively.