Monoidic Codes in Cryptography - Post-Quantum Cryptography - page 190

Table 1. Encryption quasi-monoidic codes

level pm n k t key(bits) syndrome(bits)

80 2 12 3840 768 256 9216 3072

80 3 8 2430 486 243 6163 3082

80 5 5 1000 375 125 4354 1452

80 167 3 668 167 167 3700 3700

112 2 12 2944 1408 128 16896 1536

112 3 8 2673 729 243 9244 3082

112 11 5 1089 484 121 8372 2093

112 241 3 964 241 241 5722 5722

128 2 12 3200 1664 128 19968 1536

128 3 9 3159 972 243 13866 3467

128 5 5 5000 625 625 10159 10159

128 373 3 1492 373 373 9560 9560

192 2 14 6144 2560 256 35840 3584

192 3 10 4131 1701 243 26961 3852

192 29 6 5887 841 841 24514 24514

192 547 4 2735 547 547 19901 19901

256 2 15 11264 3584 512 53760 7680

256 7 9 5145 2058 343 51998 8667

256 37 6 9583 1369 1369 42791 42791

256 907 4 4535 907 907 35645 35645

Table 2. Encryption quasi-monoidic codes yielding short syndromes

level pm n k t key(bits) syndrome(bits)

80 2 11 1792 1088 64 11968 704

80 7 5 735 490 49 6879 688

80 41 3 451 328 41 5272 659

128 2 12 3200 1664 128 19968 1536

128 3 9 2106 1377 81 19643 1156

128 7 6 1813 1519 49 25587 826

192 2 14 5376 3584 128 50176 1792

192 3 11 4536 3645 81 63550 1413

monoidic sequence. This may cause some entries in the sequence to be 0, so we
cannot invert them in the final step of the algorithm and just leave them at
0, since no legal entry can have that value. Now, after selecting the submatrix
in QuasiMonoidic (Fig. 3), i.e., after line 7, we need to check that all matrix
coecients are non-zero and restart if there are any. This is unlikely since the
submatrix is usually small.
The whole relaxation allows us to work with smaller extension fields F Q ,

F ∗ Q , where before we needed
2 N . So the codes we produce will be denser and thus more suited for the CFS
signature scheme.

because we now need only t + n distinct elements in