Quantum Resistant Public Key Cryptography

Publications

• Yongge Wang: Random Linear Code Based Public Key Encryption Scheme RLCE. In Proc ISIT 2016 (pdf)
• Yongge Wang: Decoding Generalized Reed-Solomon Codes and Its Application to RLCE Encryption Schemes. Manuscripts 2017. (pdf)
• Yongge Wang. Revised Quantum Resistant Public Key Encryption Scheme RLCE and IND-CCA2 Security for McEliece Schemes. (pdf)
• Yongge Wang. RLCE Key Encapsulation Mechanism (RLCE-KEM) Specification (pdf)

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.

Parameters

Table 1 lists the message bandwidth and message padding scheme parameters for the recommended schemes. In case that ν = 8(k₁ + k₂ + k₃) - mLen_i > 0, the last ν-bits of the k₃-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 H₃ to hash the first part of y resulting in k₃-bytes hash output, one discards the last ν-bits from the hash output and ⊕ the remaining (8k₃ - ν)-bits with the second half of y to obtain the (8k₃ - ν)-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 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 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 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.

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

• RLCE parameter package: RLCE.jar (19KB). RLCE.jar will test the security strength for given parameters and calculates the padding parameters. It runs on all platforms. For instructions, run: java -jar RLCE.jar
• CPP Code for RLCE filtration attack analysis.
• The C code implementation for the RLCE scheme should be available soon. Please get tuned.

• An example ciphertext for RLCE scheme ID=1 (hex format):

        47d997fd9809c5e3fe08513cb1ca5aace9e42777796e9cbffb802e295626a017eca37caa7093f964919511fb7
        634eb0fd2bcbe2efaa10c3e0e3018e3cc5461c6d3505dbc27f6646eaabf60a34b19702cc0ecce15ff365c348a
        e96438ba65384c22b52df461ecb86acd7560b08cb12431a3cf78f2241bf683f4c4856e9d6abfcb2b68f8c814c
        cf40956100d73db624939a309bae5fe43650010cb24b642d34f2954b7713bfa817473b18a9afd93e6bc4b3b28
        f3613d1110d713f1245b1736073c473005a93323c46ba037da79d4d33ec866320e220fdf9d2839d9dad4570c9
        7ce0d2e16cef0e86eca35241a1bd9d1ab537a6574a4f1d2e0f003cd1c12d584685b67db5dfa7a253d4193cf17
        ecc0a8a66b8fe627ebe656fbca21089516916c89612dd5ad449e36f39e0293d571679a3b4011d413e7afddb25
        3590fad3dfbcb0730102a985e39d10515cf56c825c4b5b1bb405011ed8185b32c7ac4539e3e205d439e21384c
        da075adcc380293bc0caf6a4e781cd617bb2c21f43192239e4a2f4e14b64ad044063c6debc205dae7acfbe564
        a6aef7337444ef9cc2da3a4a26996f3091f6f047d2da86e8877f6c9c09d5c0e3219071c3572e9dfcc60686f94
        647a96eba66cdf18082a0a6ffc7b2e13d74e328c38ee4b5633c9461a32ab66d80f4f34d85b836aacaab04a0d6
        aa9cd3e557480a2408cde65e57d79a7260d40d27dbc41b216913095481329d05cb7a6d6a36f22258054861829
        354c1947b8702636b978364404263b665f0df4a478df59ee35cbe42db3f3ac74e30d5b0da7c389854f2e58ce0
        1a4c3780ba6ea52b115c01c348fbca2a63f0fa4c8029ca56c996a742567e3aa74f25a583d10d1652138c05abb
        c82571ae32e0f304e795f4137e5ce8a7e0ec3fb418db81d7f8fe6c74b0d2b17d773719006307b6e422c068e54
        b0bdc0acc74bacacf8e468797db6fafa705b0acee8c2363e447af9799d4fb218d131da0106b5222fd96fc1dc4
        100627fe91c2d1e9d7c10865c308afb30564b93e5501069c8dd4f83669e9b56ddf7155b34b20874c3758897fb
        c73527d527f61320442851984217a52053a2d61b2328bbbbac8706da3
        

• Public Key for RLCE scheme ID=1: public key (this is the public key used for generating the above ciphertext)