Paper 2025/2061
Multivariate Signatures with Polynomial Factorization
, University of Bergen, University of BergenAbstract
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.
Note: Due to an observation by Ward Beullens, the analysis may be reduced to the case S_1 = S_2. So, we now assume that from the beginning.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- Multivariate cryptographySignature schemePolynomial factorizationBilinear equations
- Contact author(s)
-
irene muzio @ uib no
martin feussner @ uib no
igor semaev @ uib no - History
- 2025-11-25: last of 3 revisions
- 2025-11-07: received
- See all versions
- Short URL
- https://ia.cr/2025/2061
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/2061,
author = {Irene Di Muzio and Martin Feussner and Igor Semaev},
title = {Multivariate Signatures with Polynomial Factorization},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/2061},
year = {2025},
url = {https://eprint.iacr.org/2025/2061}
}
