## 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
## SummaryDualModeMS 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 ( This submission is somewhat a complement to another multivariate-based signature scheme proposed to NIST: G Since the submission, we have improved the additional implementation of DualModeMS,
which is based on the additional implementation of G 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 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 G
*e*MSS128 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 G As specified in the web page of G
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 DualModeMSHere 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 parametersThe 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
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. ## AcknowledgementDualModeMS has been prepared with the support of the French Programme d'Investissement d'Avenir under national project RISQ P141580. |