DualModeMS: A Dual Mode for Multivariate-based Signature

Principal submitters

Summary

DualModeMS is a multivariate-based signature scheme with a rather peculiar property. Its public-key is small whilst the signature is large. This is in sharp contrast with traditionnal multivariate signature schemes based on the so-called Matsumoto and Imai (MI) constructions that produce short signatures but have larger public-keys. DualModeMS is composed by two distinct layers. The first one is a classical MI-like multivariate scheme based on HFEv-. The second part is based on the method proposed by A. Szepieniec, W. Beullens, and B. Preneel (SBP) in "MQ signatures for PKI" where present a generic technique permitting to transform any MI-based multivariate signature scheme into a new scheme with much shorter public-key but larger signatures. We emphasize that this technique can be viewed as a mode of operations that offers a new flexibility for MI-like signature schemes. Thus, we believe that DualModeMS could also be useful for others multivariate-based signature candidates proposed to NIST.

This submission is somewhat a complement to another multivariate-based signature scheme proposed to NIST: GeMSS. In particular, the security analysis for the first layer is largely similar to the one performed for GeMSS. In fact, it is a re-parametrization of GeMSS imposed by a specificity of SBP.

We propose to study the performance of the Inner mode (small signature but large public key) and that of DualModeMS (small public key but medium signature). Then, we propose other sets of parameters in order to study the trade-off between the size of the public key and that of the signature.

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. Note that these KAT files are not the same that those provided on https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions. Unlike NIST which provides ten intermediate KAT but only one request and response KAT, we provide ten KAT files for the three categories. However, these files are huge (approximately 200 MB).

News

Improved implementation

  • 09/20/2018. The measurements of an improved additional implementation of Inner.DualModeMS have been added. This implementation is not yet available. It has been extended for the three levels of security.
  • 10/19/2018. The measurements of an improved additional implementation of DualmodeMS (in Dual mode) have been added. This implementation is not yet available. It has been extended for the three levels of security. For Skylake processors, we obtain a factor 372.8 for the keypair generation, a factor 1.5 for the signing process, and a factor 6.4 for the verifying process.

Specification

  • 01/11/2018. For the experimental measurements, turbo boost was enabled.
  • 07/24/2018. We have added experimental measurements for Inner.DualModeMS, based on GeMSS128 additional implementation.
  • 07/24/2018. Two sizes of public key are slightly incorrect in the specification. Look the tables to have the corrected values.

Performance of the fastest implementations of Inner.DualModeMS (the first layer)

Here are measurements of performance of the first level of security of Inner.DualModeMS. An implementation of this mode does not have been submitted explicitly. However, since the Inner mode is a re-parametrization of GeMSS, we can easily transform the submitted GeMSS128 implementation to obtain the Inner mode. To do it, we just replace config_HFE.h by this file (only the security parameters are modified). To have the most significative measurements, turbo boost is disabled. For the first level of security, the measurements are the average on 1,000 keypair generation, 1,000 signatures and 1,000,000 verifications. In the tables, this implementation is written in red.

As specified in the web page of GeMSS, we have a new implementation of GeMSS. This implementation provides naturally the three security levels of Inner.DualModeMS. We compare it to the previous implementation.

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) 383 Mc / 136 ms 112 Mc / 39.3 ms 0.182 Mc / 0.064 ms
1 (128 bits) 208 Mc / 74.0 ms 83 Mc / 29.7 ms 0.036 Mc / 0.013 ms
3 (192 bits) 1,119 Mc / 399 ms 185 Mc / 65.8 ms 0.119 Mc / 0.042 ms
5 (256 bits) 3,765 Mc / 1,341 ms 351 Mc / 125 ms 0.374 Mc / 0.133 ms

Here are the theoretical and pratical sizes for keys and signatures of Inner.DualModeMS. We correct the theoretical size of the public key which is 1232.13 kB (and not 1139.06 kB) for the category of security 1.

Theoretical sizes of keys and signatures for Inner.DualModeMS.
category of security public key secret key signature
1 (128 bits) 1,232.128 kB 24.554 kB 277 bits
3 (192 bits) 4,243.728 kB 59.587 kB 420 bits
5 (256 bits) 10,635.328 kB 133.816 kB 576 bits

Pratical sizes of keys and signatures for Inner.DualModeMS.
category of security public key secret key signature
1 (128 bits) 1,232.128 kB 29.080 kB 320 bits
1 (128 bits) 1,232.128 kB 29.080 kB 320 bits
3 (192 bits) 4,243.744 kB 65.352 kB 448 bits
5 (256 bits) 10,635.328 kB 139.248 kB 576 bits

Performance of the fastest implementations of DualModeMS

Here are new measurements of performance of the additional implementation submitted to NIST. To have the most significative measurements, turbo boost is disabled. In the tables, this implementation is written in red. We compare it to our new implementation. The measurements are the average on 1 keypair generation, 256 signatures and 10,240 verifications.

Measurements of cryptographic operations on a Skylake processor i7-6600U, PCLMULQDQ and AVX2 are used.
category of security keypair generation signature generation verification
1 (128 bits) 1,988,572 Mc / 708 s 7,870 Mc / 2.80 s 9.868 Mc / 3.514 ms
1 (128 bits) 5,334 Mc / 1.90 s 5,397 Mc / 1.92 s 1.549 Mc / 0.552 ms
3 (192 bits) 9,833 Mc / 3.50 s 17,982 Mc / 6.40 s 3.635 Mc / 1.295 ms
5 (256 bits) 20,214 Mc / 7.20 s 92,225 Mc / 32.84 s 8.016 Mc / 2.855 ms

Here are the theoretical and pratical sizes for keys and signatures of DualModeMS. A seed of size the level of security is counted two times: one time in the public key and one time in the secret key. This seed has been removed in our new implementation. We correct the theoretical size of the public key which is 2,080 bytes (and not 2,112 bytes) for the category of security 5.

Theoretical sizes of keys and signatures for DualModeMS.
category of security public key secret key signature
1 (128 bits) 0.528 kB 18,032.890 kB 32.002 kB
3 (192 bits) 1.560 kB 29,466.091 kB 79.415 kB
5 (256 bits) 2.080 kB 44,319.512 kB 149.029 kB

Pratical sizes of keys and signatures for DualModeMS.
category of security public key secret key signature
1 (128 bits) 0.528 kB 18,038.184 kB 32.640 kB
1 (128 bits) 0.512 kB 18,038.168 kB 32.640 kB
3 (192 bits) 1,536 kB 29,473.608 kB 81,872 kB
5 (256 bits) 2,048 kB 44,326.896 kB 153,608 kB

Other sets of parameters

The transformation proposed by SBP allows to choose the trade-off between the size of the public key and that of the signature. Here, we propose to compare different sets of parameters for a 128 bits level of security. By default, the security parameters of the dual mode are τ=218,ϑ=18 and k=21. The performance is measured with our new implementation.

Performance in function of the parameters set. A Skylake processor i7-6600U with PCLMULQDQ and AVX2 is used. The original NIST submissions are written in red.
* τ=220,ϑ=14,k=21
Target Parameters Theoretical sizes (|pk|, |sk|, |sign|) Perf. (keygen, sign, verif) Specificity
minimizing |pk| α=2,σ=64,δ=0 0.032 kB, 18,033.834 kB, 34.306 kB 1.90 s, 1.92 s, 0.592 ms the smallest pk
DualModeMS128 α=2,σ=64,δ=4 0.512 kB, 18,032.874 kB, 32.002 kB 1.90 s, 1.92 s, 0.552 ms reference
|pk|≈|sign| α=2,σ=64,δ=9 16.384 kB, 18,001.130 kB, 29.122 kB 1.90 s, 1.92 s, 0.511 ms medium pk
minimizing |pk|+|sign| α=1,σ=128,δ=5 1.024 kB, 18,031.850 kB, 28.829 kB 1.90 s, 3.81 s, 0.578 ms slower sign
minimizing |pk|+|sign| α=2,σ=64,δ=4 * 0.512 kB, 68,364.522 kB, 28.418 kB 7.90 s, 1.92 s, 0.522 ms slower keygen
minimizing |pk|+|sign| α=1,σ=128,δ=4 * 0.512 kB, 68,364.522 kB, 25.821 kB 7.90 s, 3.81 s, 0.555 ms slower keygen / sign
Inner.DualModeMS128 n=266, D=129 1,232.128 kB, 24.554 kB, 277 bits 74.0 ms, 29.7 ms, 0.013 ms fast sign/verif
GeMSS128 n=174, D=513 352.188 kB, 13.438 kB, 258 bits 16.1 ms, 260 ms, 0.028 ms the smallest sign

The inner mode permits to have a very small signature (277 bits). In contrast, the dual mode allows to have a very small public key (32 B). The original submission proposes a small public key (512 B) and a smaller size of |pk|+|sign| (32.514 kB). On the one hand, |pk|+|sign| can be minimized by losing a factor two during the signature generation. This implies |pk|+|sign|=29.853 kB. On the other hand, |pk|+|sign| can be minimized by increasing by four the size of the secret key and the time of the keypair generation. This implies |pk|+|sign|=28.930 kB. We can merge the two ideas to obtain |pk|+|sign|=26.333 kB. Finally, we can decrease the size of the signature by increasing δ. This choice increases the size of the public key (16.384 kB) and improves slightly the performance.

Acknowledgement

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