Paper 2025/2061 Original: eprint.iacr.org/2025/2061 ↗

Multivariate Signatures with Polynomial Factorization

Abstract

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-kilobyte 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.