GeMSS: A Great Multivariate Short Signature
This web page is dedicated to GeMSS: a Great Multivariate Signature Scheme. GeMSS is a multivariate based signature scheme producing small signatures. It has a fast verification process, and a medium/large public-key. GeMSS is in direct lineage from the multivariate signature scheme QUARTZ. Thus, GeMSS is built from the Hidden Field Equations cryptosystem (HFE) by using the so-called minus and vinegar modifiers, i.e. HFEv-. GeMSS is a faster variant of QUARTZ that incorporates the latest results in multivariate cryptography to reach higher security levels than QUARTZ whilst improving efficiency.
We have also submitted a variant, DualModeMS, which uses a generic technique permitting to transform any MI-based multivariate signature scheme into a new scheme with much shorter public-key but larger signatures.
Since the submission, we have improved the additionnal implementation of GeMSS, which is become MQsoft. Based on the idea to study the trade-off between security and performance, MQsoft is an efficient library flexible on the choice of the security parameters.
Specification (version of 11/30/2017)The specification's document submitted to the NIST PQC standardization process is available here.
Package of submission (version of 11/30/2017)The full submission package (with the implementations) is available here. The KAT files are here.
Updated implementation and KAT for D=513
The parameter D is incorrect in the submitted implementation. The value should be 513 and not 512. Here is explained how to modify D. The updated implementation is here and the KAT files for D=513 are here.
Correction of mistakes in the original implementation
Performance of the fastest implementations
Here are new measurements of performance of the additional implementation submitted to NIST. We corrected the parameter D in the implementation (513 instead of 512). We compare this corrected version to our new implementation. The measurements are the average on 1,000 keypair generations, 256 signatures and 1,000,000 verifications for the category of security 1, on 100 keypair generations, 256 signatures and 100,000 verifications for the category of security 3, and on 20 keypair generations, 256 signatures and 50,000 verifications for the category of security 5. In the tables, the original implementation is written in red.
Here are the theoretical and pratical sizes for keys and signatures. The correction of the parameter D induces minor modifications of the size of the secret key. As for the performance measurements, we compare the pratical size used by the NIST submission (written in red) to this of our new implementation. For the moment, we have improved only the size of the public key for GeMSS256.
GeMSS has been prepared with the support of the French Programme d'Investissement d'Avenir under national project RISQ P141580.