Quantum Resistant Public Key Cryptography

We develop post-quantum (or quantum resistant) public key encryption techniques. Our first implementation is based on the Random Linear Code Based Public Key Encryption Shceme (RLCE) which was recently introduced by Dr. Yongge Wang.

Publications

Better Performance than RSA

The following table shows the comparison of the RLCE performance against OpenSSL RSA performance. Both RSA and RLCE were tested with a MacOS Sierra on a MacBook Pro with 2.9 GHz Intel Core i7. These results show that RLCE has much better performance than widely deployed RSA scheme.

Table: Comparisson of RLCE and RSA performance (milliseconds)









κc RSA modulus
key setup
encryption
decryption








RSA RLCE RSA RLCE RSA RLCE








128 3072 433.607 151.834 0.135540 0.360 6.576281 1.345








192 7680 9346.846 637.988 0.672769 0.776 75.075443 2.676








256 15360 80790.751 1587.330 2.498523 1.745 560.225740 9.383









Parameters

Table 1 lists the message bandwidth and message padding scheme parameters for the recommended schemes. In case that ν = 8(k1 + k2 + k3) - mLeni > 0, the last ν-bits of the k3-bytes random seed r should be set to zero and the last ν-bit of the encoded string y is discarded. For RLCEspad with ν > 0, the encoding and decoding process are straightforward. For RLCEpad with ν > 0, the decoding process produces an encoded string y with last ν-bits missing. After using H3 to hash the first part of y resulting in k3-bytes hash output, one discards the last ν-bits from the hash output and the remaining (8k3 - ν)-bits with the second half of y to obtain the (8k3 - ν)-bits of r without the ν-bits zero trailer. In the column for sk, the first row is the private key size for RLCE scheme with decoding algorithm 1 and 3. The second row is the private key size for RLCE scheme with decoding algorithm 2.


Table 1: Padding parameters: bE for basicEncoding, mE for mediumEncoding and aE for advancedEncoding




















ID
κc
κq
LD
n
k
t
w
m
sk
cipher
pk
mLen
RLCEspad
RLCEpad




k 1(k2) k3 k1 k2(k3)



















0
128
80
630
470
80
160
10
310116
988
188001
bE 4700 146 296 524 32






mE 5500 171 346 624 32






192029 aE 5869 183 368 670 32



















1
128
80
532
376
78
96
10
179946
785
118441
bE 3760 117 236 406 32






mE 4540 141 286 504 32






121666 aE 4875 152 306 546 32



















2
192
110
1000
764
118
236
10
747393
1545
450761
bE 7640 238 479 859 48






mE 8820 275 553 1007 48






457073 aE 9377 293 587 1077 48



















3
192
110
846
618
114
144
10
440008
1238
287371
bE 6180 193 387 677 48






mE 7320 228 459 819 48






292461 aE 7825 244 491 883 48



















4
256
144
1360
800
280
560
11
1773271
2640
1232001
bE 8800 275 550 980 60






mE 11880 371 743 1365 60






1241971 aE 13025 407 815 1509 60



















5
256
144
1160
700
230
311
11
1048176
2023
742089
bE 7700 240 483 843 60






mE 10230 319 641 1159 60






749801 aE 11145 348 698 1274 60



















6
22
22
40
20
10
5
10
1059
57
626
bE 200 6 13 17 4






mE 300 9 20 30 4






859 aE 331 10 22 34 4






































7
128
80
(13,6663,14)
612
466
76
146
10
284636
948
170091
bE 4660 145 293 519 32






mE 5420 169 340 614 32






173961 aE 5771 180 362 658 32



















8
128
80
(9,3767,10)
520
380
73
87
10
166998
759
107826
bE 3800 118 239 411 32






mE 4530 141 285 503 32






110948 aE 4847 151 304 542 32



















9
192
110
(11,9317,12)
1000
790
108
210
10
703371
1513
414751
bE 7900 246 496 892 48






mE 8980 280 563 1027 48






420946 aE 9500 296 596 1092 48



















10
192
110
(8,5358,9)
828
620
107
128
10
401724
1195
260401
bE 6200 193 389 679 48






mE 7270 227 455 813 48






265324 aE 7748 242 485 873 48



















11
256
144
(26,23350,34)
1200
700
280
500
11
1382314
2338
926501
bE 7700 240 483 843 60






mE 10780 336 676 1228 60






971326 aE 11872 371 742 1364 60



















12
256
144
(62,49149,82)
1050
590
262
330
11
888230
1898
640889
bE 6460 202 408 692 60






mE 9372 292 588 1052 60






648100 aE 10334 322 648 1172 60



















13
24
24
(3, 68,4)
40
20
11
5
10
1059
57
626
bE 200 6 13 13 6






mE 310 9 21 27 6






859 aE 343 10 23 31 6



















14
25
25
(10, 262,14)
40
20
12
5
10
1059
57
626
bE 200 6 13 13 6






mE 320 10 20 28 6






859 aE 354 11 23 33 6




















Table 2 lists the performance results for RLCE encryption scheme that was tested with MacOS Sierra on a MacBook Pro with 2.9 GHz Intel Core i7. The first column contains the encryption scheme ID from Table 1. The second column contains the time needed for a public/private key pair generation. The third two-column group contains the time needed for one plaintext encryption. The fourth two-column group contains kilo-bytes of plaintext messages that could be encrypted within one second. The fifth two-column group contains the time needed for one ciphertext decryption and the last two-column group contains kilo-bytes of plaintext messages that could be decrypted within one second. The message size refers to pre-padded message size.


Table 2: RLCE on MacOS 2.9GHz Intel Core i7 with medium Encoding/Decoding Algorithm 0











ID sec/key
seconds/encryption
KB per/sec
seconds/decryption
KB/sec










RLCEspad RLCEpad RLCEspad RLCEpad RLCEspad RLCEpad RLCEspad RLCEpad










0 0.311375 0.000566 0.000539 294.846 1129.579 0.001754 0.001718 95.182 354.623










1 0.151834 0.000378 0.000360 364.226 1365.873 0.001385 0.001345 99.447 366.073










2 1.151206 0.001229 0.001166 218.578 843.153 0.003474 0.003432 77.296 286.527










3 0.637988 0.000814 0.000776 273.496 1030.626 0.002717 0.002676 81.963 298.924










4 2.745302 0.002832 0.002765 127.921 482.147 0.014171 0.013853 25.567 96.228










5 1.587330 0.002216 0.001745 140.586 648.461 0.009324 0.009383 33.412 120.627











Table 3 lists the performance results for RLCE encryption scheme with pre-computation that was tested with MacOS Sierra on a MacBook Pro with 2.9 GHz Intel Core i7. In the experiment, we pre-compute the inverse sub-matrix corresponding to the un-recovered message portion as discussed in Section ??. The pre-computation time is included in the key generation process.


Table 3: RLCE performance on MacOS 2.9GHz Intel Core i7 (medium Encoding) with pre-computation











ID sec/key
seconds/encryption
KB per/sec
seconds/decryption
KB/sec










RLCEspad RLCEpad RLCEspad RLCEpad RLCEspad RLCEpad RLCEspad RLCEpad










0 0.340616 0.000565 0.000538 295.347 1133.706 0.001574 0.001509 106.093 403.961










1 0.161504 0.000378 0.000372 364.113 1324.587 0.001221 0.001181 112.747 416.892










2 1.253926 0.001255 0.001166 213.930 843.673 0.003034 0.002937 88.509 334.784










3 0.667239 0.000815 0.000791 273.295 1010.965 0.002396 0.002340 92.910 341.868










4 3.215791 0.002836 0.002796 127.757 476.747 0.013092 0.012925 27.673 103.135










5 1.678032 0.002242 0.001763 138.951 641.935 0.008560 0.008572 36.391 132.035











Table 4 lists the performance results for RLCE encryption scheme without using the marix S. It was tested with MacOS Sierra on a MacBook Pro with 2.9 GHz Intel Core i7.


Table 4: RLCE on MacOS 2.9GHz Intel Core i7 with medium Encoding/Decoding Algorithm 2











ID sec/key
seconds/encryption
KB per/sec
seconds/decryption
KB/sec










RLCEspad RLCEpad RLCEspad RLCEpad RLCEspad RLCEpad RLCEspad RLCEpad










0 0.314711 0.000570 0.000533 293.209 1142.783 0.001832 0.001417 91.140 430.170










1 0.154143 0.000385 0.000360 358.031 1367.227 0.001095 0.001133 125.724 434.399










2 1.169991 0.001267 0.001176 212.033 835.997 0.003199 0.002946 83.945 333.760










3 0.635208 0.000814 0.000788 263.291 1015.049 0.002547 0.002300 87.409 347.769










4 2.747790 0.002882 0.003278 125.708 406.614 0.019859 0.019163 18.244 69.563










5 1.561936 0.002263 0.001772 137.650 638.711 0.010939 0.010932 28.477 103.530











For the list-decoding based RLCE encryption scheme, we only tested scheme with ID=7. For RLCE scheme 7, the key generation time is approximately 0.516495 seconds, the encryption time is approximately 0.001598 seconds, and the decryption time is approximately 1865 seconds (that is, approximately 31 minutes).

Tools and Software for Download

Public keys and ciphertext for you to decrypt The following is a sample public key and ciphertext. The ciphertext and public key are in HEX format.