We propose a new multivariate digital signature scheme whose central mapping arises from the product of two one-variate polynomials over a finite field \(\mathbb {F}_q\) . The resulting quadratic transformation is efficiently invertible through polynomial factorization, defining the trapdoor mechanism. The public key comprises m bilinear forms in 2n variables, obtained by masking the central map with secret linear transformations. A reference implementation targeting NIST security level 1 achieves a 24-byte signature and a 12-KB public key. This signature size is among the smallest ever proposed for level 1 security and the scheme achieves verification efficiency comparable to the fastest existing designs. Security relies on the hardness of solving certain bilinear systems, for which it seems no efficient classical or quantum algorithms are known.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Multivariate Signatures with Polynomial Factorization

  • Irene Di Muzio,
  • Martin Feussner,
  • Igor Semaev

摘要

We propose a new multivariate digital signature scheme whose central mapping arises from the product of two one-variate polynomials over a finite field \(\mathbb {F}_q\) . The resulting quadratic transformation is efficiently invertible through polynomial factorization, defining the trapdoor mechanism. The public key comprises m bilinear forms in 2n variables, obtained by masking the central map with secret linear transformations. A reference implementation targeting NIST security level 1 achieves a 24-byte signature and a 12-KB public key. This signature size is among the smallest ever proposed for level 1 security and the scheme achieves verification efficiency comparable to the fastest existing designs. Security relies on the hardness of solving certain bilinear systems, for which it seems no efficient classical or quantum algorithms are known.