Quantum Resistant Public Key Cryptography

Yongge Wang

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. The scheme RLCE-KEM has been submitted to NIST PQC project.

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




















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



















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




















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










2 1.151206 0.001229 0.001166 218.578 843.153 0.003474 0.003432 77.296 286.527










4 2.745302 0.002832 0.002765 127.921 482.147 0.014171 0.013853 25.567 96.228











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










2 1.253926 0.001255 0.001166 213.930 843.673 0.003034 0.002937 88.509 334.784










4 3.215791 0.002836 0.002796 127.757 476.747 0.013092 0.012925 27.673 103.135











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










2 1.169991 0.001267 0.001176 212.033 835.997 0.003199 0.002946 83.945 333.760










4 2.747790 0.002882 0.003278 125.708 406.614 0.019859 0.019163 18.244 69.563











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.