DualModeMS: A Dual Mode for Multivariate-based Signature
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 additionnal implementation of DualModeMS, which is based on the additionnal implementation of GeMSS. The latter 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.
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).
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 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. 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 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 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 2080 bytes (and not 2112 bytes) for the category of security 5. 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 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 τ=218,ϑ=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.
DualModeMS has been prepared with the support of the French Programme d'Investissement d'Avenir under national project RISQ P141580.