Multivariate Signatures with Polynomial Factorization
摘要
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.