Practical and Theoretical Cryptanalysis of VOX

VOX is a UOV-like hash-and-sign signature scheme from the Multivariate Quadratic (MQ) family, which has been submitted to NIST Post-Quantum Cryptography Project, in response to NIST’s Call for Additional Digital Signature Schemes for the PQC Standardization Process. In 2023, the submitters of VOX updated the sets of recommended parameters of VOX, due to the rectangular MinRank attack proposed by Furue and Ikematsu. In this work we demonstrate the insecurity of the updated VOX from both the practical and the theoretical aspects. First, we conduct a practical MinRank attack against VOX, which uses multiple matrices from matrix deformation of public key to form a large rectangular matrix and evaluate the rank of this new matrix. By using Kipnis–Shamir method and Gröbner basis calculation only instead of support-minors method, our experiment shows it could recover, within two seconds, the secret key of almost every updated recommended instance of VOX. Moreover, we propose a theoretical analysis on VOX by expressing public/secret key as matrices over a smaller field to find a low-rank matrix, resulting in a more precise estimation on the concrete hardness of VOX; for instance, the newly recommended VOX instance claimed to achieve NIST security level 3 turns out to be 69-bit-hard, as our analysis shows.