GeMSS: A Great Multivariate Short Signature

Principal submitters

• A. Casanova, CS
• J.-C. Faugère, INRIA, Sorbonne Université, CNRS
• G. Macario-Rat, Orange
• J. Patarin, University of Versailles
• L. Perret, Sorbonne Université, CNRS, INRIA
• J. Ryckeghem, Sorbonne Université, CNRS, INRIA

Summary

This web page is dedicated to GeMSS: a Great Multivariate Short Signature. 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 additional implementation of GeMSS, which is become MQsoft. MQsoft is an efficient library flexible on the choice of the security parameters.

Specification

The specification's document submitted to the first round of the NIST PQC Standardization Process is available here.

This submitted to the second round is available here, and the changes are here.

Package of submission

The full submission package (with the implementations) of the first round is available here. The KAT files are here.

This of the second round is available here.

Last version of GeMSS (second round, 04/15/2020)

We propose an updated implementation of GeMSS, available here. We have decreased the size of the keys. For the secret-key, it is now generated from a small secret seed. For the public-key, we have improved the implementation to reach the theoretical size. Thus, these changes modify the KAT files. The new KATs are here.

We have specified the major changes here (in Section II), and updated the specification accordingly.

Updated implementation and KAT for D=513 (first round)

The parameter D is incorrect in the submitted implementation of the first round. 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.

News

Improved implementation

• 08/20/2019. The measurements of an improved version of MQsoft-2.1 (august 2019) have been added for Haswell and Skylake.
• 10/10/2019. An exhaustive table of security parameters has been added for Skylake, based on an improved version of MQsoft-2.1(july 2019).

Old news (first round)

Improved implementation

• 09/20/2018. The measurements of MQsoft, an improved additional implementation, have been added. This implementation is not yet available. For Skylake processors, we obtain a factor between 2 and 2.6 for the keypair generation, a factor between 1.3 and 1.6 for the signing process, and a factor between 1.8 and 2 for the verifying process.
• 09/27/2018. The measurements of MQsoft are available for Skylake and Haswell processors.

Specification

• 01/11/2018. The size of the secret-key is slightly incorrect, the values given are for D=512 instead of 513. Look the tables to have the corrected values.
• 01/11/2018. For the experimental measurements, turbo boost was enabled.

Correction of mistakes in the original implementation

• 01/11/2018. The parameter D is incorrect in the implementation. The value should be 513 and not 512. The update is done here.

Performance of the fastest implementations (second round)

Here are new measurements of performance of GeMSS with the latest version of MQsoft.

Here are the theoretical sizes for keys and signatures.

An exhaustive table of security parameters (second round)

Similarly to Section 9.6 of the GeMSS specification, we propose performance measurements for a large number of security parameters. The main difference with the specification is the use of an improved version of MQsoft.

Performance of the fastest implementations (first round)

Here are new measurements of performance of the additional implementation submitted to the first round of the NIST PQC Standardization Process. 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 practical 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 practical 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.

Acknowledgement

GeMSS has been prepared with the support of the French Programme d'Investissement d'Avenir under national project RISQ P141580.