Paper 2024/1770 Original: eprint.iacr.org/2024/1770 ↗

Improved Attacks for SNOVA by Exploiting Stability under a Group Action

Abstract

SNOVA is a post-quantum digital signature scheme based on multivariate polynomials. It is a second-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 of solving 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$ 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 we discuss its impact. The empirical evidence suggests that our attack is more efficient than previous attacks, and it takes some SNOVA parameter sets below NIST's security threshold.