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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Improved Cryptanalysis of SNOVA by Solving Multi-homogeneous Systems via Matrix Transformations

  • Hiroki Furue,
  • Yasuhiko Ikematsu,
  • Shuhei Nakamura,
  • Rika Akiyama

摘要

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.