Welcome to the resource topic for 2024/1770
Title:
Improved Attacks for SNOVA by Exploiting Stability under a Group Action
Authors: Daniel Cabarcas, Peigen Li, Javier Verbel, Ricardo Villanueva-Polanco
Abstract: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 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 reconciliation and 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^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 which were not taken below NIST’s security threshold by previous attacks. Our attack brings these parameter sets (l=4) below that threshold with speedup factors between 2^{33} and 2^{52}, over the state-of-the-art.
ePrint: https://eprint.iacr.org/2024/1770
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .