Paper 2024/1374

Lifting approach against the SNOVA scheme

Shuhei Nakamura, Ibaraki University
Yusuke Tani, Ibaraki University
Hiroki Furue, NTT (Japan)
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 $\ell v$ vinegar-variables and $\ell o$ oil-variables over $\mathbb{F}_q$, 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 $v$ vinegar-variables and $o$ oil-variables over $\mathbb{F}_{q^\ell }$. As a result, we show that the previous first round parameter sets at $\ell = 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.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Post-Quantum CryptographyMultivariate CryptographyUOVSNOVAKey Recovery Attack
Contact author(s)
shuhei nakamura fs71 @ vc ibaraki ac jp
History
2024-11-25: revised
2024-09-02: received
See all versions
Short URL
https://ia.cr/2024/1374
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1374,
      author = {Shuhei Nakamura and Yusuke Tani and Hiroki Furue},
      title = {Lifting approach against the {SNOVA} scheme},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1374},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1374}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.