Paper 2024/1374

Lifting approach against the SNOVA scheme

Abstract

In 2022, Wang et al. proposed the multivariate signature scheme SNOVA as a UOV variant over the non-commutative ring of $\ell \times \ell$ matrices over ${\mathbb{F}}_q$. This scheme has small public key and signature size and is a first round candidate of NIST PQC additional digital signature project. Recently, Ikematsu and Akiyama, and Li and Ding show that the core matrices of SNOVA with $v$ vinegar-variables and $o$ oil-variables are regarded as the representation matrices of UOV with $$ vinegar-variables and $$ oil-variables over $$, and thus we can apply existing key recovery attacks as a plain UOV. In this paper, we propose a method that reduces SNOVA to smaller UOV with $$ vinegar-variables and $$ oil-variables over $$. As a result, we show that the previous first round parameter sets at $$ do not meet the NIST PQC security levels. We also confirm that the present parameter sets are secure from existing key recovery attacks with our approach.