Appears in collection : 2024 - T3 - WS2 - Emerging topics in design and cryptanalysis of post-quantum schemes

SNOVA is a post-quantum digital signature scheme based on multivariate polynomials, that stands out in the ongoing NIST competition for its efficiency and compactness. Recently, there have been several attacks that reduce to solving a structured system of quadratic polynomials. In this talk, I discuss a recent work in which we propose a polynomial solving algorithm tailored for SNOVA systems, which exploits the stability of the system under the action of a commutative group of matrices, to reduce the complexity to solve SNOVA systems. We show how to adapt the reconciliation and direct attacks in order to profit from this new algorithm. Consequently, we improve the reconciliation attack for all SNOVA parameter sets with speedup factors ranging between 2^3 and 2^{22}. Our algorithm also reduces the complexity of the direct attack for several parameter sets. It is particularly effective for the parameters that give the best performance to SNOVA $(l=4)$, and brings these parameter sets below NIST's security threshold with speedup factors between 2^{33} and 2^{52}, over the state-of-the-art.