International Association
for Cryptologic Research

SNOVA is a post-quantum digital signature scheme based on multivariate polynomials. It is a first-round candidate in an ongoing NIST standardization process for post-quantum signatures, where it stands out for its efficiency and compactness. Since its initial submission, there have been several improvements to its security analysis, both on key recovery and forgery attacks. All these works reduce to solving a structured system of quadratic polynomials, which we refer to as SNOVA system. In this work, we propose a polynomial solving algorithm tailored for SNOVA systems, which exploits the \textit{stability} of the system under the action of a commutative group of matrices. This new algorithm reduces the complexity to solve SNOVA systems, over generic ones. We show how to adapt the \textit{reconciliation} and \textit{direct} attacks in order to profit from the new algorithm. Consequently, we improve the reconciliation attack for all SNOVA parameter sets with speedup factors ranging between $2^2$ and $2^{20}$. We also show how to use similar ideas to carry on a forgery attack. In this case we use experimental results to estimate its complexity and discuss its impact. The empirical evidence suggest that our attack is more efficient than previous attacks, and it takes some SNOVA parameter sets below NIST's security threshold.