MQsoft

A fast multivariate cryptography library

Summary

MQsoft is an efficient library in C for the HFE-based schemes, in cryptography. Several schemes as GeMSS, Gui and DualModeMS are already implemented. However, our library is more general, and permits to use any HFEv- scheme where the base field is GF(2) and the degree of the extension is n≤576.

MQsoft permits, in particular, to:

  • perform an efficient constant-time arithmetic in GF(2n).
  • find the roots of a univariate polynomial in GF(2n)[X]. We have specialized algorithms for the HFE polynomials.
  • evaluate efficiently multivariate quadratic systems in GF(2) (in constant-time and in variable-time).
  • implement the dual mode of Matsumoto-Imai based multivariate signature schemes (cf. DualModeMS).

Performance (MQsoft V3.0)

Here is an example of the performance of MQsoft to run the cryptographic operations of GeMSS, Gui and DualModeMS. We have set the number of iterations of the Feistel-Patarin scheme to 4 for Gui-184 and Gui-185. This permits to achieve a 128-bit level of security

Measurements of cryptographic operations (mega cycles / milliseconds) on a Haswell processor Intel(R) Xeon(R) CPU E3-1275 v3 @ 3.50GHz, PCLMULQDQ and AVX2 are used.
scheme (λ,D,n,Δ,v,nb_ite) keypair generation signature generation verification
GeMSS128 (128,174,513,12,12,4) 44.9 MC / 12.8 ms 962 MC / 275 ms 0.0814 MC / 0.0233 ms
GeMSS192 (192,265,513,22,20,4) 235 MC / 67.1 ms 3080 MC / 881 ms 0.24 MC / 0.0685 ms
GeMSS256 (256,354,513,30,33,4) 694 MC / 198 ms 5930 MC / 1690 ms 0.577 MC / 0.165 ms
Gui-184 (128,184,33,16,16,4) 57.2 MC / 16.3 ms 24.4 MC / 6.96 ms 0.106 MC / 0.0303 ms
Gui-185 (128,185,33,16,16,4) 58.4 MC / 16.7 ms 19.8 MC / 5.65 ms 0.102 MC / 0.0292 ms
Gui-312 (192,312,129,24,20,2) 373 MC / 107 ms 444 MC / 127 ms 0.172 MC / 0.0493 ms
Gui-313 (192,313,129,24,20,2) 380 MC / 108 ms 416 MC / 119 ms 0.174 MC / 0.0498 ms
Gui-448 (256,448,513,32,28,2) 1570 MC / 449 ms 7070 MC / 2020 ms 0.451 MC / 0.129 ms
INNER_DualModeMS128 (128,266,129,10,11,1) 210 MC / 59.9 ms 112 MC / 32 ms 0.0446 MC / 0.0127 ms
INNER_DualModeMS192 (192,402,129,18,18,1) 1030 MC / 293 ms 245 MC / 70.1 ms 0.143 MC / 0.0408 ms
INNER_DualModeMS256 (256,544,129,32,32,1) 4000 MC / 1140 ms 487 MC / 139 ms 0.263 MC / 0.0751 ms
DualModeMS128 (128,266,129,10,11,1) 1980000 MC / 565000 ms 7360 MC / 2100 ms 9.3 MC / 2.66 ms
DualModeMS192 (192,402,129,18,18,1) 7140000 MC / 2040000 ms 24700 MC / 7070 ms 17.1 MC / 4.87 ms
DualModeMS256 (256,544,129,32,32,1) 18000000 MC / 5150000 ms 131000 MC / 37500 ms 28.5 MC / 8.16 ms

Download

MQsoft V1.0

MQsoft V1.0 is composed of the implementations submitted to the first round of the NIST PQC Standardization Process.

SHA2-512 checksum:

b5e5462ff5240ddf514129810626bf84040ee6ffd4292e7e486d680b96901d4b e1d831e0d96e1556c1f0099041b8c829b84d09fd83dc1c44d370978b2e7791db

MQsoft V2.0

MQsoft V2.0 is composed of the implementations submitted to the second round of the NIST PQC Standardization Process.

SHA2-512 checksum:

e7d0a180e334cf5ff8a64541ab45a7c8340ff9836583193ee07c6f6a2bc2db80 8d1b1e2a09affac2a25c5a74facedfde7ef174fb32b5a63ef757817e68f050e9

MQsoft V2.1

MQsoft V3.0


SUPERCOP Benchmarks (with the EUF-CMA property)

We have run SUPERCOP to evaluate the performance of Gui from libpqcrypto, and MQsoft. We have applied to MQsoft the EUF-CMA transformation described by the team Gui, in order to have comparable results. Then, we have set the number of iterations of the Feistel-Patarin scheme to 4 for Gui-184. This permits to achieve a 128-bit level of security.

Median in cycles of the cryptographic operations of gui-184 from libpqcrypto, measured with SUPERCOP-20181216. The processor is an Intel(R) Core(TM) i7-6600U CPU @ 2.60GHz (Skylake), and Turbo Boost is not used.
keygen 1 keygen 2 keygen 3
485019167 486631683 487745035
len doc (B) sign 1 sign 2 sign 3 verify 1 verify 2 verify 3
0 160253033 161731956 124602390 252082 276020 266383
1 114424239 124599888 122052601 282296 286119 272706
2 180454737 155080966 114406802 274161 303810 299060
3 131121103 119499582 161950301 286172 283661 295556
4 190322405 98345663 147493948 274880 279438 304132
6 144947495 167882060 209298137 317261 335854 809505
8 172890232 185625450 177338950 271323 282479 366476
11 124599888 142384124 132228462 286119 295375 300529
14 122052601 111873300 210972431 272706 295978 279176
18 137315412 142387491 101692065 277593 259483 282791
23 155080966 195764433 209811277 303810 288718 302298
29 114406802 186600178 114623145 299060 292359 280378
37 119499582 238974533 197459724 283661 301417 273560
47 98345663 138659483 137207035 279438 298892 259328
59 208491545 178344441 129668276 279027 273413 285170
74 160231266 149992804 199556684 281292 291201 279459
93 134767029 120879307 111891677 266054 286511 281369
117 142384124 205951171 104255267 295375 285657 303792
147 111873300 216959523 127113948 295978 289351 264045
184 142387491 147483086 172274887 259483 308465 296577
231 195764433 166088203 142490645 288718 272174 277552
289 244569145 141752101 94078314 294197 274260 295524
362 161950301 88991060 149553342 295556 281006 289779
453 147493948 190769056 175427044 304132 278044 316899
567 172889051 205927006 142385785 288217 282385 272289
709 61027335 139897130 136151968 299522 287515 306871
887 185625450 205929677 160179084 282479 290652 287396
1109 132228462 139908767 147503437 300529 292010 300581
1387 165405926 151411739 162703020 288859 269824 300149
1734 94140508 104243551 160180184 310927 301987 285095
2168 127180521 147517844 153733084 306143 298092 314738
2711 127268944 216187420 132771897 298186 291588 318381
3389 81376167 154801042 132269926 301594 302856 313643
4237 231460632 160261196 152588414 310252 328310 307524
5297 127303458 132252407 109375033 337430 332817 335731
6622 167882060 209648292 110503876 335854 352893 345344
8278 177338950 197968771 183125352 366476 354179 378261
10348 110599400 127239299 159330148 366960 371465 370850
12936 147566597 127461912 188265719 410255 396414 379689
16171 139982911 145041454 135649067 414277 437945 405473
20214 145237420 150236346 185311092 441354 476820 461850
25268 215586720 107023487 193429899 481108 495445 485889
31586 257464735 150306215 124881496 554170 527795 540376
39483 161241500 236799142 145254687 617072 610470 604852
49354 186163471 160133951 176990019 710688 684295 697507
61693 209298137 140382624 124069076 809505 825827 814667
77117 147083906 157583963 287902200 944924 922919 902089
96397 139619423 138161165 163517385 1093319 1095531 1101982



Median in cycles of the cryptographic operations of mqsoft_gui184, measured with SUPERCOP-20181216. The processor is an Intel(R) Core(TM) i7-6600U CPU @ 2.60GHz (Skylake), and Turbo Boost is not used.
keygen 1 keygen 2 keygen 3
53658151 54004083 53699069
len doc (B) sign 1 sign 2 sign 3 verify 1 verify 2 verify 3
0 112020650 122962796 115365788 107652 109254 98869
1 108441642 93608424 123030223 102476 110351 112711
2 123138615 134207448 112104982 97060 102984 110141
3 95823345 72193238 130403846 106577 104763 114817
4 102846480 110106909 128512946 109280 105764 115822
6 134245687 94376975 130908593 107358 161795 623610
8 163379109 86230923 114953993 104522 114712 176274
11 93608424 167111847 99128765 110351 112725 117876
14 123030223 78854892 123015029 112711 108727 107470
18 173891236 95604991 122489184 106008 110476 100507
23 134207448 64270042 95445693 102984 100856 111340
29 112104982 141347668 146983933 110141 103884 110103
37 72193238 60566049 77055054 104763 104318 106968
47 110106909 86281932 73480983 105764 111015 104846
59 73786141 122149719 128516383 100629 99840 107000
74 108222061 117694980 158129178 100243 107719 106922
93 86243736 175873109 110076839 100342 106991 110835
117 167111847 114038671 106476568 112725 107028 116460
147 78854892 128503497 133913498 108727 111941 111312
184 95604991 88130369 80669884 110476 117519 106611
231 64270042 92490582 104653369 100856 104019 114830
289 69706408 152252734 124586603 113024 104029 106686
362 130403846 84483802 108501548 114817 113623 106345
453 128512946 137772059 134015120 115822 110359 101705
567 130425008 118642046 119351230 105141 115302 107610
709 157853281 103973204 207413065 106572 114561 120872
887 86230923 107405580 145158356 114712 115451 119487
1109 99128765 114124699 130507325 117876 125343 115405
1387 123126765 149865679 86452022 123108 112439 117349
1734 89927614 153494709 124778846 115580 121890 124181
2168 124818521 102640507 111985403 127536 129620 124569
2711 105019099 78146073 117650062 137939 131365 128029
3389 148696660 138859853 77046754 125144 131928 128000
4237 183754990 77149054 90012589 144985 143376 141080
5297 95008863 90022632 130026794 143018 150113 147543
6622 94376975 65917030 122987711 161795 164800 162580
8278 114953993 156194965 127397409 176274 171863 174615
10348 176645692 139640886 109244226 186939 186849 189128
12936 128020415 82745597 82723553 216999 202768 211744
16171 90073584 132417485 139750648 245762 245226 239192
20214 66314846 106761247 121439809 276856 277003 279539
25268 158073756 130644340 104277444 311678 320996 319890
31586 113299816 70399925 92014435 370817 365186 366468
39483 103351904 73761861 103004287 445209 429241 431238
49354 105250549 84979428 97722669 511714 520366 521048
61693 130908593 116202248 108880769 623610 617760 626731
77117 131920957 138398320 77759867 746192 748102 748564
96397 92918101 100087860 118276281 903270 913782 912937



Median in cycles of the cryptographic operations of mqsoft_gui185, measured with SUPERCOP-20181216. The processor is an Intel(R) Core(TM) i7-6600U CPU @ 2.60GHz (Skylake), and Turbo Boost is not used.
keygen 1 keygen 2 keygen 3
55236842 54735529 54683698
len doc (B) sign 1 sign 2 sign 3 verify 1 verify 2 verify 3
0 69202276 80271151 110315257 105113 107943 102579
1 100760701 120389926 96053355 114674 106307 109050
2 121721888 52090859 77343050 104033 113381 104051
3 99747305 107516704 90953934 115901 109044 115873
4 94214080 121496098 108953021 111462 112830 127463
6 98886316 81799105 136712456 113646 160011 621063
8 111649481 50122833 83223308 110339 110799 176177
11 120389926 50143154 74568709 106307 108338 112899
14 96053355 86004154 107770293 109050 110493 107326
18 121831345 67313285 104600496 108677 103396 108100
23 52090859 77429270 64496551 113381 109454 112314
29 77343050 67322415 70294396 104051 104943 108225
37 107516704 65930550 120369779 109044 105851 108731
47 121496098 71787071 134685643 112830 110932 104463
59 104647408 102232237 131969436 107095 102343 106780
74 75895150 83169222 139033153 108449 108949 98101
93 87402510 75971733 75776623 108568 103238 101381
117 50143154 68815985 75991700 108338 112942 101062
147 86004154 43118972 65962046 110493 100819 104057
184 67313285 81659371 54449492 103396 117667 113534
231 77429270 68774585 77466927 109454 105605 104543
289 89328510 73070688 77150702 117170 113286 115207
362 90953934 68883405 71583317 115873 107708 116229
453 108953021 78886520 101562976 127463 117117 112161
567 108883690 86040801 74561147 110823 109952 117612
709 84542401 84524048 53050717 108768 115271 113654
887 50122833 80276773 85626438 110799 109206 123010
1109 74568709 73147811 74554490 112899 111646 110099
1387 99097574 113253071 98921458 114343 118113 112560
1734 70334524 94610666 52980612 126146 123054 113047
2168 93155430 70334879 74554542 123426 133429 123310
2711 123369379 117483044 107620769 126156 128097 133737
3389 87833224 77158741 104634366 142177 126273 138436
4237 63120079 87444882 96087275 142873 141277 148527
5297 151958956 73139657 91746706 146218 153298 153149
6622 81799105 131933400 74321450 160011 167591 169080
8278 83223308 65936431 101420082 176177 183975 179964
10348 66444359 84690504 121310425 191686 199150 194799
12936 70336813 114778277 98988320 202874 209367 226580
16171 113275855 91818219 126319724 239745 242347 245756
20214 82149481 56098464 71834010 274178 279354 271898
25268 119236283 124945807 47486998 320457 314252 327579
31586 51816510 103447614 94838318 376491 373988 378261
39483 61930323 69193939 92089476 446734 445072 442085
49354 122374437 146371147 92178119 518097 521251 517904
61693 136712456 75092224 72241283 621063 619739 635467
77117 56504355 75187839 103937599 754135 747864 747240
96397 128888935 106850083 58155469 922109 923685 910077



Median in cycles of the cryptographic operations of mqsoft_GeMSS128, measured with SUPERCOP-20181216. The processor is an Intel(R) Core(TM) i7-6600U CPU @ 2.60GHz (Skylake), and Turbo Boost is not used.
keygen 1 keygen 2 keygen 3
44769047 44795939 44739374
len doc (B) sign 1 sign 2 sign 3 verify 1 verify 2 verify 3
0 1379745051 1155434547 1155108081 91482 98619 94423
1 1493520387 1378923166 804336122 88658 93988 98948
2 1610911771 1034115089 1264090416 102569 92357 93699
3 1490227892 689375524 1034084658 87123 96642 101981
4 1263829304 1264436322 1604965671 89287 91180 100779
6 1034170718 1149034952 1034939535 94492 160257 705240
8 1267853303 1148943843 1149132281 89293 94245 184434
11 1378923166 1153105399 1149003358 93988 87655 104646
14 804336122 1263964814 1155434384 98948 89394 87783
18 1149130980 1264302839 1156090358 93184 87261 87543
23 1034115089 1383146957 1271309430 92357 92807 89889
29 1264090416 1386532350 1155819941 93699 87361 98399
37 689375524 1271182339 1617743607 96642 92859 89174
47 1264436322 1270713422 1502734779 91180 93584 93140
59 1378772667 1386640046 1272726571 89303 96132 87968
74 1493582875 1040013807 1271399835 91133 97454 93330
93 1149247706 1501721755 923547879 87889 88846 94359
117 1153105399 1271203167 1155593181 87655 90792 94454
147 1263964814 1619927560 1617548920 89394 93773 85009
184 1264302839 1155204370 1039992545 87261 90120 91841
231 1383146957 1155653503 1271142296 92807 99503 95896
289 1263892910 1270806996 1039825271 99777 98569 96224
362 1034084658 1155578645 1502331103 101981 97907 88595
453 1604965671 1386273421 1502199634 100779 90012 96363
567 919141327 1501924466 1271308432 95081 93410 95569
709 1608417338 1386316323 1155448070 102667 103021 100023
887 1148943843 1506137615 1612493625 94245 95826 92360
1109 1149003358 1617544617 1502210931 104646 101951 102956
1387 1148854873 1502137845 1155391838 103866 108441 101122
1734 1149147706 1270964819 924247705 108229 111595 108148
2168 919558720 1039807068 1502111631 112397 109700 108213
2711 1034348066 1155349413 1386255181 116175 117367 113591
3389 1609245556 1502119262 1386954672 122965 127451 132771
4237 919324099 1155581759 924836982 133303 124613 128573
5297 1494257347 1388368477 1155353632 148789 149795 142269
6622 1149034952 1386402165 1155700930 160257 152800 164415
8278 1149132281 924598780 1155674252 184434 176216 172964
10348 1264072724 1270821097 1270955056 188108 192189 189113
12936 1493970030 1502053644 1155734703 212084 218822 212653
16171 1034457943 1387574443 1271731076 253374 260397 246711
20214 1609031151 924407348 1155702666 288677 296537 286646
25268 1149643605 1386803824 1040034016 336194 337588 341458
31586 919709686 1040222276 1271299502 405900 395315 407932
39483 1379398878 1386632318 1503640070 482061 481869 477128
49354 1380284778 1617646979 1502288551 573790 575091 573742
61693 1034939535 1271377091 1263704955 705240 699527 703275
77117 1380795475 1155676303 1040799141 849623 856436 855807
96397 1380293575 1618855362 1156300224 1046493 1045777 1043261

Statistics on the performance of MQsoft in EUF-CMA

Here, we give statistics on the performance of Gui from libpqcrypto, and of MQsoft. As in the previous section, we use the EUF-CMA transformation, and we set the number of iterations to 4 for Gui-184.

Statistics in cycles of the cryptographic operations. The processor is an Intel(R) Core(TM) i7-6600U CPU @ 2.60GHz (Skylake), and Turbo Boost is not used.
name operation average standard deviation first quartile median third quartile
Gui184_libpq keygen 771412829 9623904 763929566 768808874 776005107
sign 1 215359127 201055082 66808162 154249599 300758304
sign 2 224998587 216649859 69414452 161949628 303323164
sign 3 214227556 210702008 67251531 146536054 287881319
verify 1 298064 28123 284712 292051 300478
verify 2 294745 20009 285211 291574 298560
verify 3 295551 22169 284713 292093 298923
Gui312_libpq keygen 5054482984 25443811 5040388778 5050028534 5058981818
sign 1 817346051 712905163 328728492 575383968 1061267025
sign 2 794207448 675066459 247665856 575389806 1068771513
sign 3 897153217 853751329 328791480 575537098 1234239239
verify 1 802284 166154 747860 770279 794970
verify 2 798509 101964 744548 769896 803746
verify 3 795889 101415 746444 768806 795259
Gui448_libpq keygen 30095911573 157959104 29918374902 30120108411 30164730532
sign 1 10349501922 8684640074 3833110363 7657227737 15310131731
sign 2 9054466983 7591471244 3832884248 6708002470 11498824075
sign 3 10092820707 8769289516 3833339170 7666883681 13416731946
verify 1 2774148 458150 2663394 2709531 2762489
verify 2 2743455 170468 2653332 2710082 2762453
verify 3 2752631 219662 2659000 2708291 2757473
Gui184_MQsoft keygen 59505441 4095472 56439564 58381497 61967442
sign 1 152611072 151882756 44164626 106660605 207625965
sign 2 154824115 145952056 49685722 109447987 218739404
sign 3 154408843 150677580 49987054 107647084 207900762
verify 1 206831 18846 193024 205162 217574
verify 2 205900 19638 192039 204028 217282
verify 3 206684 33676 192371 204051 217304
Gui185_MQsoft keygen 59353725 3460637 56517066 59063162 60695628
sign 1 120297545 114754668 38759996 85977517 165083978
sign 2 124805240 123175163 38673049 87381514 165177584
sign 3 123897416 120251582 40072641 88866169 171935390
verify 1 208651 19899 194739 206770 219639
verify 2 209858 20775 195469 208380 220743
verify 3 210214 21102 195231 208147 221372
Gui312_MQsoft keygen 378076380 11556471 369247873 372763780 381952832
sign 1 623051139 634955110 269832432 472576813 744413412
sign 2 643992835 552738390 266451798 472085810 868007404
sign 3 662506748 541422324 269699810 503152649 876458258
verify 1 239368 36448 224105 231565 240819
verify 2 242392 106783 221711 229961 238723
verify 3 240706 42134 222349 231190 240264
Gui313_MQsoft keygen 381563783 12185266 373779442 379481328 382740942
sign 1 598099042 536432320 241023589 432736282 742342003
sign 2 569941836 437248198 247340655 432930445 783353152
sign 3 608417322 539325873 247294117 432891875 804249818
verify 1 237775 32731 223964 231519 241388
verify 2 241030 39619 223415 232745 242347
verify 3 237823 31168 223565 232571 242236
Gui448_MQsoft keygen 1704238867 20694070 1689285821 1693263512 1722883724
sign 1 9770624028 8455098536 3159914305 7359146058 14703268994
sign 2 11299961016 8553550492 5231228936 9456114224 14753585134
sign 3 10523794027 9850152172 4204094583 8400353191 12643286732
verify 1 772344 97792 720990 748188 783991
verify 2 779469 101036 722435 753113 787759
verify 3 770672 91421 716883 748598 784293
GeMSS128_MQsoft keygen 45525316 1017575 45227655 45263115 45304169
sign 1 1672523617 1336637387 694251689 1262149983 2180617505
sign 2 1698397260 1400182791 697178922 1278349753 2207674420
sign 3 1643576861 1331861895 688756400 1261340521 2069490459
verify 1 181822 16840 169740 179754 191073
verify 2 181609 16436 169977 179566 190069
verify 3 181808 16952 170296 179732 190732
GeMSS192_MQsoft keygen 232951340 6060364 230049519 230967049 231415615
sign 1 5368867909 4309403942 2150954650 3787553459 7566751945
sign 2 5025836209 4194221956 2161429033 3963002651 6478893030
sign 3 5215536848 4377337577 2146076720 3607016165 6845978442
verify 1 357349 37472 339607 349881 360777
verify 2 358810 33637 339681 350247 362792
verify 3 360884 37519 339483 350320 372326
GeMSS256_MQsoft keygen 750575100 19449646 739500670 742249044 749948544
sign 1 8673387100 7060076168 4134670833 6497172234 10663476097
sign 2 8189614394 6706852638 2957082794 6500710210 11234732662
sign 3 8442114972 6520840933 3541574790 6487854856 11225690049
verify 1 672460 81026 634127 647317 670890
verify 2 678529 100597 631736 646933 672002
verify 3 676337 104078 632233 644412 667800