CryptoDB
Improved Cryptanalysis of SNOVA by Solving Multi-homogeneous Systems via Matrix Transformations
| Authors: |
|
|---|---|
| Download: | |
| Conference: | ASIACRYPT 2025 |
| Abstract: | 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. |
BibTeX
@inproceedings{asiacrypt-2025-36080,
title={Improved Cryptanalysis of SNOVA by Solving Multi-homogeneous Systems via Matrix Transformations},
publisher={Springer-Verlag},
author={Hiroki Furue and Yasuhiko Ikematsu and Shuhei Nakamura and Rika Akiyama},
year=2025
}