DualModeMS: A Dual Mode for Multivariate-based Signature

Principal submitters

• J.-C. Faugère, INRIA, Sorbonne Université, CNRS
• L. Perret, Sorbonne Université, CNRS, INRIA
• J. Ryckeghem, Sorbonne Université, CNRS, INRIA

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.

Since the submission, we have improved the additional implementation of DualModeMS, which is based on the additional implementation of GeMSS. The latter is become MQsoft. MQsoft is an efficient library flexible on the choice of the security parameters.

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)

Package of submission (version of 11/30/2017)

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 373 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). 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.

Here are the theoretical and practical 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. 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 do not improve the sizes.

Performance of the fastest implementations of DualModeMS

Here are new measurements of performance of the additional implementation submitted to NIST. 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 10240 verifications.

Here are the theoretical and practical 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 2080 bytes (and not 2112 bytes) for the category of security 5. 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 do not improve the sizes.

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 τ=2¹⁸,ϑ=18 and k=21. The performance is measured with our new implementation.

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.