Lifting Approach against the SNOVA Scheme

In 2022, Wang et al. proposed the multivariate signature scheme SNOVA as a UOV variant over the non-commutative ring of ℓ × ℓ matrices over 𝔽q. This scheme has small public key and signature size and is a second 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 ℓv vinegar-variables and ℓo oil-variables over 𝔽q, and thus we can apply existing key recovery attacks as a plain UOV. In this article, we propose a method that reduces SNOVA to smaller UOV with v vinegar-variables and o oil-variables over 𝔽qℓ. As a result, we show that the previous first round parameter sets at ℓ = 2 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.