International Association
for Cryptologic Research

SNOVA is a multivariate-based signature scheme constructed as a variant of unbalanced oil and vinegar over a non-commutative ring. This scheme has been selected as one of the second-round candidates for the NIST PQC competition for additional signatures and is attracting much attention due to its efficiency and compactness. Various security analyses have been conducted on SNOVA, and some have improved the efficiency of attacks by exploiting the structure of extension fields. In particular, Cabarcas et al. showed that the forgery and reconciliation attacks can be made more efficient by utilizing the multi-homogeneous structure derived from transformed public keys over an extension field.However, it has not been clarified whether other key recovery attacks can be improved by using the multi-homogeneous structure over the extension field. In this work, we first clearly describe the transformation of public key systems to an extension field, which has been used in some previous analysis, as a concrete form of matrix transformation. We can construct multi-homogeneous systems from the matrices obtained through this transformation. We then provide a way of improving the intersection and rectangular MinRank attacks, which are key recovery attacks on UOV, solving the resulting multi-homogeneous systems. Further, to estimate the complexity of the proposed rectangular MinRank attack, we analyze the solving degree of the multi-homogeneous version of the MinRank problem. As a result, we show that the proposed attacks are more efficient than known attacks for some parameters of SNOVA.

The unbalanced oil and vinegar signature scheme (UOV) is a multivariate signature scheme that has essentially not been broken for over 20 years. However, it requires the use of a large public key; thus, various methods have been proposed to reduce its size. In this paper, we propose a new variant of UOV with a public key represented by block matrices whose components correspond to an element of a quotient ring. We discuss how it affects the security of our proposed scheme whether or not the quotient ring is a field. Furthermore, we discuss their security against currently known and newly possible attacks and propose parameters for our scheme. We demonstrate that our proposed scheme can achieve a small public key size without significantly increasing the signature size compared with other UOV variants. For example, the public key size of our proposed scheme is 85.8 KB for NIST's Post-Quantum Cryptography Project (security level 3), whereas that of compressed Rainbow is 252.3 KB, where Rainbow is a variant of UOV and is one of the third-round finalists of the NIST PQC project.