Round 1 (Additional Signatures) OFFICIAL COMMENT: SNOVA
673 views
Skip to first unread message
Po-En Tseng
Aug 22, 2024, 7:46:57 AM8/22/24
to pqc-forum
Dear all,
Three days ago, the SNOVA Team received a preprint titled "Improved Cryptanalysis of SNOVA" from Beullens, which is now available on the Cryptology ePrint Archive. According to the preprint, when the parameter \( l \) is set to 2 or 3, SNOVA exhibits some weak keys that significantly reduce security. However, when \( l = 4 \), SNOVA continues to meet NIST security levels I and III. Therefore, until new SNOVA parameter sets are announced, parameter sets with \( l = 2 \) or \( l = 3 \) are not recommended.
In the preprint, Beullens claims that SNOVA is a weak variant of MAYO, a view we disagree with. Although the two designs share some similarities, SNOVA is derived from a ring UOV—a large, sparse UOV system—before generalizing to a non-sparse system. In contrast, MAYO begins with a small useless UOV and then whips up. Beullens notes that both systems share a similar whipping structure, but an attack on MAYO may not necessarily apply to SNOVA. Furthermore, MAYO's parameter set with the smallest key size does not meet Level I security (under the Hashimoto's solving algorithm) and requires modification. In comparison, SNOVA's Level I parameter set with \( l = 4 \) has a significantly smaller key size than MAYO's smallest key size among the parameter sets that do meet Level I security, further differentiating the two designs.
Beullens defines weak keys based on a lower-rank whipping structure, which can be vulnerable to attacks that combine minrank attacks with solving an under-determined system. However, if the rank does not drop too much, the attack complexity may still satisfy NIST security levels. Thus, labeling these as "weak keys" does not clearly indicate whether the SNOVA keys are insecure. It is more accurate to consider keys that do not meet NIST security levels as weak keys. When \( l = 2 \) or \( l = 3 \), weak keys exist that do not meet NIST security levels.
There are solutions to avoid weak keys. Fixing specific parameters, such as \( A_{\alpha} \), \( B_{\alpha} \), and \( Q_{\alpha, i} \), can prevent or limit the rank reduction. Alternatively, random generation of these parameters followed by checks can also increase the security of SNOVA. Some minor adjustments to SNOVA (probably only fixing the A, B and Q matrices) are prudent to ensure they meet NIST security standards. We are conducting further security analysis, and a more detailed security report will be released soon.
SNOVA with \( l = 4 \) offers the smallest size of public key (1016 bytes) and signature (248 bytes), and the best performance optimization among the proposed parameter sets. It also provides the highest level of security against the attack presented in Beullens' preprint. The Level I parameter set with \( l = 4 \) offers the smallest public key and signature sizes among all NIST post-quantum candidates, excluding very slow or broken systems, and maintains strong performance compared to NIST competitors.
Best regards,
SNOVA Team
Three days ago, the SNOVA Team received a preprint titled "Improved Cryptanalysis of SNOVA" from Beullens, which is now available on the Cryptology ePrint Archive. According to the preprint, when the parameter \( l \) is set to 2 or 3, SNOVA exhibits some weak keys that significantly reduce security. However, when \( l = 4 \), SNOVA continues to meet NIST security levels I and III. Therefore, until new SNOVA parameter sets are announced, parameter sets with \( l = 2 \) or \( l = 3 \) are not recommended.
In the preprint, Beullens claims that SNOVA is a weak variant of MAYO, a view we disagree with. Although the two designs share some similarities, SNOVA is derived from a ring UOV—a large, sparse UOV system—before generalizing to a non-sparse system. In contrast, MAYO begins with a small useless UOV and then whips up. Beullens notes that both systems share a similar whipping structure, but an attack on MAYO may not necessarily apply to SNOVA. Furthermore, MAYO's parameter set with the smallest key size does not meet Level I security (under the Hashimoto's solving algorithm) and requires modification. In comparison, SNOVA's Level I parameter set with \( l = 4 \) has a significantly smaller key size than MAYO's smallest key size among the parameter sets that do meet Level I security, further differentiating the two designs.
Beullens defines weak keys based on a lower-rank whipping structure, which can be vulnerable to attacks that combine minrank attacks with solving an under-determined system. However, if the rank does not drop too much, the attack complexity may still satisfy NIST security levels. Thus, labeling these as "weak keys" does not clearly indicate whether the SNOVA keys are insecure. It is more accurate to consider keys that do not meet NIST security levels as weak keys. When \( l = 2 \) or \( l = 3 \), weak keys exist that do not meet NIST security levels.
There are solutions to avoid weak keys. Fixing specific parameters, such as \( A_{\alpha} \), \( B_{\alpha} \), and \( Q_{\alpha, i} \), can prevent or limit the rank reduction. Alternatively, random generation of these parameters followed by checks can also increase the security of SNOVA. Some minor adjustments to SNOVA (probably only fixing the A, B and Q matrices) are prudent to ensure they meet NIST security standards. We are conducting further security analysis, and a more detailed security report will be released soon.
SNOVA with \( l = 4 \) offers the smallest size of public key (1016 bytes) and signature (248 bytes), and the best performance optimization among the proposed parameter sets. It also provides the highest level of security against the attack presented in Beullens' preprint. The Level I parameter set with \( l = 4 \) offers the smallest public key and signature sizes among all NIST post-quantum candidates, excluding very slow or broken systems, and maintains strong performance compared to NIST competitors.
Best regards,
SNOVA Team
Po-En Tseng
Sep 30, 2024, 12:49:52 AM9/30/24
to pqc-forum, Po-En Tseng, 王立中, 官彥良, 周君彥, pqcl...@gmail.com
Dear all.
In response to the Beullens attack, and after further research, we have found that SNOVA's current parameter set maintains its security with appropriate adjustments. Meanwhile, these adjustments will not affect our public key and signature size.
Please refer to the following link for more details.
Po-En Tseng 在 2024年8月22日 星期四晚上7:46:57 [UTC+8] 的信中寫道：
Reply all
Reply to author
Forward
0 new messages