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.

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 an improved additional implementation have been added. This implementation is not yet available. For Skylake processors, we obtain a factor between 2 and 2.5 for the keypair generation, a factor 1.5 for the signing process, and a factor between 3 and 3.5 for the verifying process.
  • 09/27/2018. The measurements of our improved additional implementation 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. To have the most significative measurements, several corrections are done: the parameter D is 513 (and not 512) and turbo boost is disabled. 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 i7-6600U, PCLMULQDQ and AVX2 are used.
category of security keypair generation signature generation verification
1 (128 bits) 113 Mc / 40.2 ms 1,208 Mc / 430 ms 0.295 Mc / 0.104 ms
1 (128 bits) 45 Mc / 16.1 ms 733 Mc / 260 ms 0.079 Mc / 0.028 ms
3 (192 bits) 527 Mc / 187 ms 3,324 Mc / 1,184 ms 0.653 Mc / 0.232 ms
2 (192 bits) 231 Mc / 82.1 ms 2,264 Mc / 806 ms 0.235 Mc / 0.084 ms
5 (256 bits) 1,416 Mc / 504 ms 5,454 Mc / 1,942 ms 1.764 Mc / 0.628 ms
5 (256 bits) 738 Mc / 263 ms 3,743 Mc / 1,333 ms 0.571 Mc / 0.203 ms

Measurements of cryptographic operations (mega cycles / milliseconds) on a Haswell processor E3-1275 v3, PCLMULQDQ and AVX2 are used.
category of security keypair generation signature generation verification
1 (128 bits) 132 Mc / 37.8 ms 1,437 Mc / 411 ms 0.172 Mc / 0.049 ms
1 (128 bits) 47 Mc / 13.4 ms 988 Mc / 282 ms 0.087 Mc / 0.025 ms
3 (192 bits) 609 Mc / 174 ms 3,906 Mc / 1,116 ms 0.445 Mc / 0.127 ms
2 (192 bits) 240 Mc / 68.6 ms 3,066 Mc / 876 ms 0.245 Mc / 0.070 ms
5 (256 bits) 1,611 Mc / 460 ms 6,788 Mc / 1,939 ms 0.997 Mc / 0.285 ms
5 (256 bits) 754 Mc / 216 ms 5,267 Mc / 1,505 ms 0.604 Mc / 0.172 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.

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) 1,237.964 kB 34.070 kB 411 bits
5 (256 bits) 3,040.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) 1,304.192 kB 40.280 kB 704 bits
3 (192 bits) 1,304.192 kB 40.280 kB 704 bits
5 (256 bits) 3,603.792 kB 83.688 kB 832 bits
5 (256 bits) 3,046.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.