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 is composed of the implementations submitted to the first round of the NIST PQC Standardization Process.
SHA2-512 checksum:
b5e5462ff5240ddf514129810626bf84040ee6ffd4292e7e486d680b96901d4b
e1d831e0d96e1556c1f0099041b8c829b84d09fd83dc1c44d370978b2e7791db
MQsoft V2.0 is composed of the implementations submitted to the second round of the NIST PQC Standardization Process.
SHA2-512 checksum:
e7d0a180e334cf5ff8a64541ab45a7c8340ff9836583193ee07c6f6a2bc2db80
8d1b1e2a09affac2a25c5a74facedfde7ef174fb32b5a63ef757817e68f050e9
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 |
|