GeMSS: A Great Multivariate Short Signature

Principal submitters

Summary

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.

News

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

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.

Measurements of cryptographic operations (mega cycles / milliseconds) on a Skylake processor Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz, PCLMULQDQ and AVX2 are used. Turbo Boost is used.
category of security keypair generation signature generation verification
1 (128 bits) 92.6 Mc / 27.2 ms 978 Mc / 287 ms 0.125 Mc / 0.0368 ms
1 (128 bits) 36.2 Mc / 10.6 ms 597 Mc / 175 ms 0.0666 Mc / 0.0195 ms
3 (192 bits) 424 Mc / 124 ms 2570 Mc / 754 ms 0.35 Mc / 0.103 ms
3 (192 bits) 189 Mc / 55.6 ms 1880 Mc / 552 ms 0.197 Mc / 0.0577 ms
5 (256 bits) 1150 Mc / 336 ms 4040 Mc / 1190 ms 0.883 Mc / 0.259 ms
5 (256 bits) 564 Mc / 166 ms 3100 Mc / 909 ms 0.451 Mc / 0.132 ms

Measurements of cryptographic operations (mega cycles / milliseconds) on a Haswell processor Intel(R) Xeon(R) CPU E3-1275 v3 @ 3.50GHz, PCLMULQDQ and AVX2 are used. Turbo Boost is not used.
category of security keypair generation signature generation verification
1 (128 bits) 125 Mc / 35.6 ms 1510 Mc / 432 ms 0.161 Mc / 0.046 ms
1 (128 bits) 44.9 Mc / 12.8 ms 962 Mc / 275 ms 0.0814 Mc / 0.0233 ms
3 (192 bits) 562 Mc / 160 ms 3870 Mc / 1100 ms 0.439 Mc / 0.125 ms
3 (192 bits) 235 Mc / 67.1 ms 3080 Mc / 881 ms 0.240 Mc / 0.0685 ms
5 (256 bits) 1620 Mc / 463 ms 7300 Mc / 2090 ms 1.01 Mc / 0.288 ms
5 (256 bits) 694 Mc / 198 ms 5930 Mc / 1690 ms 0.577 Mc / 0.165 ms

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.

Theoretical sizes of keys and signatures.
category of security public key secret key signature
1 (128 bits) 352.188 kB 13.438 kB 258 bits
3 (192 bits) 1237.964 kB 34.070 kB 411 bits
5 (256 bits) 3040.700 kB 75.893 kB 576 bits

Pratical sizes of keys and signatures.
category of security public key secret key signature
1 (128 bits) 417.408 kB 14.520 kB 384 bits
1 (128 bits) 417.416 kB 14.520 kB 384 bits
3 (192 bits) 1304.192 kB 40.280 kB 704 bits
3 (192 bits) 1304.192 kB 40.280 kB 704 bits
5 (256 bits) 3603.792 kB 83.688 kB 832 bits
5 (256 bits) 3046.856 kB 83.688 kB 832 bits

Acknowledgement

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