Method and Apparatus for Public Key Encryption Scheme RLCE and IND-CCA2 Security

Abstract

This invention discloses a method and system for generating a private key and a corresponding public key. These keys can be used for encrypting a message into a cipher-text for transmission through an insecure communication channel, and for decrypting said ciphertext into a clear plaintext. The goal of the present invention is to provide encryption and decryption methods of the McEliece type which are capable of improving the security level of a post-quantum cryptosystem. In one embodiment, this object is achieved by three methods: a method for creating a public key from a private linear code generator matrix, a method for encrypting a message into a ciphertext and a method for decrypting the cipher-text into a plaintext. The key generation and encryption methods of the present invention comprises the following steps: selecting an [n, k] linear code generator matrix G.sub.s=[g.sub.0 , . . . , g.sub.n] over GF(q) as the private key, where k, w, n and q are positive integers and where g.sub.0 , . . . , g.sub.n1 are length k column vectors; selecting k1 random matrices C.sub.0 , . . . , C .sub.w1; selecting a kk non-singular matrix S; selecting an (n+w)(n+w) matrix A; selecting an (n+w)(n+w) permutation matrix P; and setting the public key as G=S[g.sub.0 , . . . , g.sub.nw, C.sub.0 , . . . , g.sub.n1, C.sub.n1]AP. receiving the public key G, which is a k(n+w) matrix over a finite field GF(q); generating an error vector e having elements in GF(q) and having a predetermined weight t; and encrypting a message vector m, to a ciphertext vector y=mG+e.

The main difference between the proposed cryptosystem and known variants of the McEliece cryptosystem consists in the way the private generator matrix is disguised into the public one by inserting and mixing random columns within the private generator matrix.

Claims

1. A method for transmitting a message vector m between a sender and a receiver securely, the method comprising: a) at the receiver: obtaining a kn generator matrix G.sub.s for an [n, k, d] linear code over a finite field GF(q), wherein n, k, d, q are positive integers; obtaining a k(n+w) matrix G.sub.1 by inserting w random columns into said matrix G.sub.s, wherin w is a positive integer; selecting a random kk non-singular matrix S; selecting a random (n+w)(n+w) non-singular matrix A; selecting a random (n+w)(n+w) permutation matrix P; setting a public key G=SG.sub.1AP; sending the public key G to the sender; and setting a private key K=(S, G.sub.s, A, P); b) at the sender: obtaining said integer n; obtaining said integer k; obtaining said finite field GF(q); obtaining said message encryption public key G; obtaining said message vector m; obtaining an integer t; generating an error vector e wherin e has said weight t; computing a ciphertext vector y=mG+e; and sending said ciphertext vector y to said receiver; c) at the receiver: obtaining said ciphertext vector y from the sender; computing an inverse matrix P.sup.1 of said permutation matrix P; computing an inverse matrix A.sup.1 of said non-singular matrix A; computing an inverse matrix S.sup.1 of said non-singular matrix S; computing a vector yP.sup.1 A.sup.1; selecting a sub-vector y of said vector yP.sup.1 A.sup.1 wherin said vector y has said length n; using said generator matrix G.sub.s to decode said subvetor y to a vector m wherin m has said length k; computing said plaintext message m=mS.sup.1; and checking a validity of said message m.

2. The method of claim 1 wherein computing said k(n+w) matrix G.sub.1 comprises: a) obtaining matrix columns g.sub.0 , . . . , g.sub.n1 from said generator matrix G.sub.s; b) selecting random k1 matrices C.sub.0, C.sub.1 , . . . , C.sub.w1 over said GF(q); and c) obtaining said k(n+w) matrix G.sub.1=[g.sub.0, g.sub.1 , . . . , g.sub.nw, C.sub.0 , . . . , g.sub.n1, C.sub.w1].

3. The method of claim 1 wherein selecting said non-singular matrix A comprises: a) selecting random 22 matrices A.sub.0, A.sub.1 , . . . , A.sub.w1 over said GF(q); and b) obtaining said (n+w)(n+w) matrix $A=\mathrm{diag}\left[I_{n-w},A_0,\mathrm{.Math.},A_{w-1}\right]=\left[\begin{array}{cccc}{I}_{n-w}& & & \\ & A_0& & \\ & & & \\ & & & A_{w-1}\end{array}\right]$ wherein I.sub.nw is an identity matrix of dimension nw.

4. The method of claim 3 wherein said k(n+w) matrix G.sub.1 is selected according to the method of claim 2.

5. The method of claim 4 wherein selecting said subvector y comprises: a) obtaining elements y.sub.0 , . . . , y.sub.n+w1 of said vector yP.sup.1 A.sup.1; and b) setting said sub-vector y=[y.sub.0,y.sub.1 , . . . , y.sub.nw;y.sub.nw+2 ; . . . , y.sub.n+w2].

6. The method of claim 5 wherein checking said validity of said message m, comprises: a) computing a Hamming weight w=weight (yMg); and b) accepting said message m, if wt.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0059] For a more complete understanding of the invention, reference is made to the following description and accompanying drawings, in which:

[0060] FIG. 1 is a schematic diagram illustrating a process according to an embodiment of the invention, showing steps taken for generating a private key and steps taken for generating a corresponding public key for a public key encryption scheme;

[0061] FIG. 2 is a schematic diagram illustrating a process according to an embodiment of the invention, showing steps taken for encrypting a message using a public key and steps taken for decrypting a cipher text using a corresponding private key;

[0062] FIG. 3 is a schematic diagram illustrating RLCE simple padding process according to an embodiment of the invention, showing steps taken for padding a message before using the RLCE encryption mechanism; and

[0063] FIG. 4 is a schematic diagram illustrating RLCE padding process according to an embodiment of the invention, showing steps taken for padding a message before using the RLCE encryption mechanism.

DETAILED DESCRIPTION

[0064] The features, structures, or characteristics of the invention described throughout this specification may be combined in any suitable manner in one or more embodiments. For example, the usage of the phrases certain embodiments, some embodiments, or other similar language, throughout this specification refers to the fact that a particular feature, structure, or characteristic described in connection with the embodiment may be included in at least one embodiment of the present invention.

[0065] In the following detailed description of the illustrative embodiments, reference is made to the accompanying drawings that form a part hereof. These embodiments are described in sufficient detail to enable those skilled in the art to practice the invention, and it is understood that other embodiments may be utilized and that logical or structural changes may be made to the invention without departing from the spirit or scope of this disclosure. To avoid detail not necessary to enable those skilled in the art to practice the embodiments described herein, the description may omit certain information known to those skilled in the art. The following detailed description is, therefore, not to be taken in a limiting sense.

[0066] The Random Linear Code based Encryption scheme RLCE reported in the present invention is described in the following paragraphs. FIG. 1 describes a process for generating a private key and for generating a corresponding public key for the proposed public key encryption scheme. Referring therefore to FIG. 1, the public parameter selection engine 100 chooses n, k,d,t,w>0, and GF(q) with the property that nk+1d 2t+1. The private linear code generator matrix selection engine 110 chooses a kn generator matrix G.sub.s=[g.sub.0 , . . . , g.sub.n1] for an [n, k, d] linear code such that there is an efficient decoding algorithm to correct at least t errors for this linear code given by C.sub.s. Random matrix selection engine 120 chooses k1 matrices C.sub.0, C.sub.1 , . . . , C.sub.w1 GF(q).sup.k1 uniformly at random. Matrix column mixing engine 130 defines

G.sub.1=[g.sub.0, g.sub.1 ; . . . , g.sub.nw,C.sub.0 . . . , g.sub.n1,C.sub.w1](1)

to be a k(n+w) matrix by inserting random matrices C.sub.0, C.sub.1 , . . . , C.sub.w1 into G.sub.s. The second random matrix selection engine 140 chooses dense nonsingular 22 matrices A.sub.0 , . . . ; A.sub.n1 GF(q).sup.22 uniformly at random and defines

[00002]$\begin{array}{cc}A=\mathrm{diag}\left[I_{n-w},A_0,\mathrm{.Math.}.Math.,A_{w-1}\right]=\left[\begin{array}{cccc}{I}_{n-w}& & & \\ & A_0& & \\ & & & \\ & & & A_{w-1}\end{array}\right]& \left(2\right)\end{array}$

to be an (n+w)(n+w) nonsingular matrix. The engine 140 also chooses a random dense kk nonsingular matrix S and chooses a random (n+w)(n+w) permutation matrix P. The private key 150 is the tuple (S; G.sub.s; P, A) and the public key 160 is the k(n+w) matrix G=SG.sub.1AP.

[0067] FIG. 2 describes a process for encrypting a clear text message using the public key 160 of FIG. 1 and a process for decrypting a ciphertext to a clear text message using the private key 150 of FIG. 1. Referring therefore to FIG. 2, for given public parameters n, k, d, t, w, GF(q), a public key G, and a row message vector m GF(q).sup.k in the box 200, the encryption engine 210 chooses a random row vector e=[e.sub.0 . . . , e.sub.n+w1] CF(q).sup.n+w whose Hamming weight is at most t and computes the cipher text as y=mG+e. The receiver 220 holds the private key S, G .sub.s, A, P and receives the ciphertext y. For the received cipher text y=[y.sub.0 , . . . , y.sub.n+w1], the decryption engine 230 computes

yP.sup.1A.sup.1=[y.sub.0 , . . . , y.sub.n+w)1]=mSG.sub.1+eP.sup.1A.sup.1.

Let y=[y.sub.0,y.sub.1 , . . . , y.sub.nw, y.sub.nw+2; y.sub.nw+4 , . . . , y.sub.n+w2] be a length n row vector selected from the length n+w row vector yP.sup.1A.sup.1. Then y=mSG.sub.s+e for some error vector e GF(q).sup.n where the Hamming weight of e GF(q).sup.n is at most t. Using the efficient decoding algorithm, the receiver computes m=mS and m=mS.sup.1. Finally, the receiver calculates the Hamming weight w=weight(ymG). If wt then the decryption engine 230 outputs m as the decrypted plaintext. Otherwise, the decryption engine 230 outputs an error. The RLCE scheme described above could be formally described as follows with three procedures: RLCE.KeySetup, RLCE.Enc, and RLCE.Dec.

[0068] RLCE.KeySetup(n,k,d,t,w). Let n, k,d,t>0, and w {1 , . . . , n} be given parameters such that nk+1d2t+1. Let G.sub.s be a kn generator matrix for an [n,k,d] linear code C such that there is an efficient decoding algorithm to correct at least t errors for this linear code given by G.sub.s. Let P.sub.1 be a randomly chosen nn permutation matrix and G.sub.sP.sub.1=[g.sub.0 , . . . , g.sub.n1]. [0069] 1. Let r.sub.0, r.sub.1 , . . . , r.sub.w1 GF(q).sup.k be column vectors drawn uniformly at random and let

G.sub.1=[g.sub.0 , . . . , g.sub.nw;r.sub.0 , . . . , g.sub.n1,r.sub.w1](3)

be the k(n+w) matrix obtained by inserting column vectors r, into G.sub.s. [0070] 2. Let

[00003]$A_0=\left(\begin{array}{cc}{a}_{0,00}& a_{0,01}\\ a_{0,10}& a_{0,11}\end{array}\right),\mathrm{.Math.}.Math.,A_{w-1}=\left(\begin{array}{cc}{a}_{w-1,00}& a_{w-1,01}\\ a_{w-1,10}& a_{w,1,11}\end{array}\right)$

GF(q).sup.22 be non-singular 22 matrices chosen uniformly at random such that a.sub.i,00a.sub.i,01a.sub.i,10a.sub.i,11 0 for all i=0 , . . . , w1. Let A=diag[1 , . . . , 1, A.sub.0 , . . . , A.sub.w1] be an (n+w)(n+w) non-singular matrix. [0071] 3. Let S be a random dense kk non-singular matrix and P.sub.2 be an (n+w)(n+w) permutation matrix. [0072] 4. The public key is the k(n+w) matrix G=SG.sub.1AP.sub.2 and the private key is (S, G.sub.s; P.sub.1; P.sub.2, A).

[0073] RLCE.Enc(G, m, e). For a row vector message m GF(q).sup.k, choose a random row vector e=[e.sub.0 , . . . , e.sub.n+w1] GF(q).sup.n+w such that the Hamming weight of e is at most t. The cipher text is c=mG+e.

[0074] RLCE.Dec(S, G.sub.s, P.sub.1, P.sub.2, A, c). For a received cipher text c=[c.sub.0 , . . . , c.sub.n+w1], compute

cP.sub.2.sup.1A.sup.1=mSG.sub.1+eP.sub.2.sup.1A.sup.1=[c.sub.0 , . . . ; c.sub.n+w1].

Let c=[c.sub.0, c.sub.1 , . . . , c.sub.nw,c.sub.nw+2 , . . . ; c.sub.n+w2] be the row vector of length n selected from the length n+w row vector cP.sub.2.sup.1A.sup.1. Then cP.sub.1.sup.1=mSG.sub.s+e for some error vector e GF(q).sup.n where the Hamming weight of e GF(q).sup.n is at most t. Using an efficient decoding algorithm, one can recover mSG.sub.s from cP.sub.1.sup.1. Let D be a kk inverse matrix of SG.sub.s where G.sub.s is the first k columns of G.sub.s. Then m=c.sub.1D where c.sub.1 is the first k elements of mSG.sub.s. Finally, calculate the Hamming weight wt=wt (cmG). If wtt then output m as the decrypted plaintext. Otherwise, output error.

[0075] To reduce RLCE scheme public key sizes, one can use a semantic secure message encoding approach (e.g., an IND-CCA2 padding scheme) so that the public key can be stored in a systematic matrix. For a McEliece encryption scheme over GF(q), one needs to store k(nk) elements from F(q) for a systematic public key matrix instead of nk elements from GF(q) for a non-systematic generator matrix public key.

[0076] In a systematic RLCE encryption scheme, the decryption could be done more efficiently. In the RLCE decryption process, one recovers mSG.sub.s from cP.sub.1.sup.1=mSG.sub.s+e first. Let mSG.sub.sP.sub.1=(d.sub.0 , . . . , d.sub.n1) and

c.sub.d =(d.sub.0 , . . . , d.sub.n+w)=(d.sub.0,d.sub.1 , . . . ; d.sub.nw,d.sub.nw+1,, . . . , d.sub.n1;)P.sub.2

be a length n+w vector. For each i<k such that d.sub.i=d.sub.j for some j<nw, we have m.sub.i=d.sub.i. Let

I.sub.R={i:m.sub.i is recovered via mSG.sub.s} and I.sub.R={0 , . . . , k1}\I.sub.R.

Assume that |.sub.R|=u. It suffices to recover the remaining u message symbols m.sub.i with i .sub.R. In the following paragraphs, we present three approaches to recover these message symbols.

[0077] Decoding algorithm 0 for systematic RLCE encryption scheme: In the first approach, one recovers mS from mSG.sub.s first. Then one multiplies m with the corresponding u columns S.sub..sub.R of the matrix S.sup.1 to get m.sub.i with i .sub.R.

[0078] Decoding algorithm 1 for systematic RLCE encryption scheme: Instead of recovering mS first, one may use public key to recover the remaining message symbols from mSG.sub.s directly. Let i.sub.0 , . . . , i.sub.u1k be indices such that for each i.sub.j, we have d.sub.i.sub.j=d.sub.i for some i<nw. The remaining message symbols with indices in .sub.R could be recovered by solving the linear equation system

m[g.sub.i.sub.0 , . . . , g.sub.i.sub.u1]=[d.sub.i.sub.0 , . . . , d.sub.i.sub.u1]

where g.sub.i.sub.0 , . . . , g.sub.i.sub.u1 are the corresponding columns in the public key. Let P be a permutation matrix so that m.sub.i (i I.sub.R) are the first ku elements in mP. That is,

mPP.sup.1[g.sub.i.sub.0 , . . . , g.sub.i.sub.u1]=(m.sub.I.sub.r,m.sub..sub.r)P.sup.1[h.sub.i.sub.0 , . . . , g.sub.i.sub.u1]=[d.sub.i.sub.0 , . . . , d.sub.i.sub.u1]

where m.sub.I.sub.r is the message symbols with indices in I.sub.R. Let

[00004]$P^{-1}\left[g_{i_0},\mathrm{.Math.}.Math.,g_{i_{u-1}}\right]-\left(\begin{array}{c}V\\ W\end{array}\right)$

where V is a (ku)u matrix and W is a uu matrix. Then we have

m.sub..sub.rW=[d.sub.i.sub.0 , . . . , d.sub.i.sub.u1]m.sub.I.sub.rV.

Furthermore, one may pre-compute the inverse of W and include W.sup.1 in the private key. Then one can recover the message symbols

m.sub..sub.r=([d.sub.i.sub.0 , . . . , d.sub.i.sub.u1]m.sub.I.sub.rV)W.sup.1.

[0079] Decoding algorithm 2 for systematic RLCE encryption scheme: In practice, one may use a larger I.sub.R. Recall that in the RLCE decryption process, one recovers mSG.sub.s from cP.sub.1.sup.31 1=mSG.sub.s+e first. Let eP.sub.1=(e.sub.0 , . . . , e.sub.n1) and

e.sub.c=(e.sub.0 , . . . , e.sub.n+w)=(e.sub.0,e.sub.1 , . . . , e.sub.nw,.sub.nw;e.sub.nw+1,.sub.nw+1 , . . . , e.sub.n1, .sub.n1)P.sub.2

be a length n+w vector. For each e.sub.nw+i.sub.0=0 (0 i.sub.0<w), if e.sub.i=e.sub.nw+i.sub.0 or e.sub.i=.sub.nw+i.sub.0 for some i<k, then with high probability, we have m.sub.i =c.sub.i since matrices A.sub.i do not contain zero elements. Thus m.sub.i might be recovered as c.sub.i. Let

I.sub.R.sup.a32 I.sub.R{i<k:e.sub.i=e.sub.nw+i.sub.0 or e.sub.i=.sub.nw+i.sub.0 for some i.sub.0<w with e.sub.nw+i.sub.0=0}

and .sub.R.sup.a={0 , . . . , k1}\I.sub.R.sup.a. Using the decoding algorithm 1 with (I.sub.R, .sub.R) replaced by (I.sub.R.sup.a, .sub.R.sup.a), one can then recover message symbols with indices in .sub.R.sup.a. With a small probability, the message recovered via (I.sub.R.sup.a, .sub.R.sup.a) might be incorrect. If this happens, one restarts the decoding process using the pair (I.sub.R; .sub.R).

[0080] Defeating side-channel attacks: The decoding algorithm 2 described might be vulnerable to side-channel attacks. The attacker may generate ciphertexts with appropriately chosen error locations and watch whether the decoding time is significantly long (which means that the message recovered via (I.sub.R.sup.a; .sub.R.sup.a) might be incorrect). This information may be used to recover part of the private permutation P.sub.2. If such kind of attacks needs to be defeated, then one should not use the decoding algorithm 2.

[0081] For the decoding algorithms 0 and 1, the value u is dependent on the choice of the private permutation P.sub.2. Though the leakage of the size of u is not sufficient for the adversary to recover P.sub.2 or to carry out other attacks against RLCE scheme, this kind of side-channel information leakage could be easily defeated. Table 0.1 lists the values of u.sub.0 such that, for each scheme, the value of u is smaller than u.sub.0 for 90% of the choices of P.sub.2 where the RLCE ID is the scheme ID described in Table 0.3. Thus one can select P.sub.2 in such a way that u is smaller than the given u.sub.0 of Table 0.1. Furthermore, during the decoding process, one can use dummy computations so that the decoding time is the same as the decoding time for u=u.sub.0.

TABLE-US-00001 TABLE 0.1 The value u.sub.0 for RLCE schemes RLCE ID 0 1 2 3 4 5 6 u.sub.0 200 123 303 190 482 309 7

[0082] Similar to most cryptographic systems, each type of McElience schemes may contain some weak keys and one should avoid using these weak keys when setting up the scheme. For example, Loidreau (1998) pointed out some weak keys for binary Goppa code based McElience schemes. The second straightforward observation is that one can modify an McElience encryption scheme ciphertext c=mG+e without knowing the message m. For example, one can obtain a valid ciphertext for a message m+m by setting c=c+mG. This kind of attacks could be defeated by using IND-CCA2-secure message padding schemes which will be discussed in the next Section.

[0083] Information-set decoding (ISD) is one of the most important message recovery attacks on McEliece encryption schemes. The state-of-the-art ISD attack for non-binary McEliece scheme is the one presented in Peters (2010), which is an improved version of Stern's algorithm (1989). Peters's attack (2010) also integrated analysis techniques for ISD attacks on binary McEliece scheme discussed in literature. For the RLCE encryption scheme, the ISD attack is based on the number of columns in the public key G instead of the number of columns in the private key G.sub.s. The cost of ISD attack on an [n, k, t; w]-RLCE scheme is equivalent to the cost of ISD attack on an [n+w, k; t]-McEliece scheme.

[0084] For the naive ISD, one first uniformly selects k columns from the public key and checks whether it is invertible. If it is invertible, one multiplies the inverse with the corresponding ciphertext values in these coordinates that correspond to the k columns of the public key. If these coordinates contain no errors in the ciphertext, one recovers the plain text. To be conservative, we may assume that randomly selected k columns from the public key is invertible. For each k x k matrix inversion, Strassen algorithm takes O(k.sup.2.807) field operations (though Coppersmith-Winograd algorithm takes O(k.sup.2.376) field operations in theory, it may not be practical for the matrices involved in RLCE encryption schemes). In a summary, the naive information-set decoding algorithm takes approximately 2.sup.k.sup.c steps to find k-error free coordinates where, by Sterling's approximation,

[00005]$\begin{array}{cc}\begin{array}{c}{}_c^{}=.Math.{\log }_2\left(\frac{\left(\begin{array}{c}n+w\\ k\end{array}\right).Math.\left(k^{2.807}+k^2\right)}{\left(\begin{array}{c}n+w-t\\ k\end{array}\right)}\right)\\ .Math.\left(n+w\right).Math.I\left(\frac{k}{n+w}\right)-\left(n+w-t\right).Math.I\left(\frac{k}{n+w-t}\right)+{\log }_2\left(k^{2.807}+k^2\right)\end{array}& \left(4\right)\end{array}$

and I(x)=x log.sub.2(x)(1x) log.sub.2(1x) is the binary entropy of x. There are several improved ISD algorithms in the literature. These improved ISD algorithms allow a small number of error positions within the selected k ciphertext values or select k+ columns of the public key matrix for a small number >0 or both. Peters (2010) provided a script to calculate the security strength of a McEliece encryption scheme using the improved ISD algorithms. For the security strength 128.sub.c256, our experiment shows that generally we have ,.sub.c10,.sub.c,.sub.c4.

[0085] An RLCE scheme is said to have quantum security level .sub.q if the expected running time (or circuit depth) to decrypt an RLCE ciphertext using Grover's algorithm based ISD is 2.sup..sup.q. For a function : {0, 1}.sup.l.fwdarw.{0, 1} with the property that there is an x.sub.0 {0, 1}.sup.1 such that (x.sub.0)=1 and (x)=0 for all xx.sub.0, Grover's algorithm finds the value x.sub.0 using

[00006]$\frac{}{4}.Math.\sqrt{2^l}$

Grover iterations and O (l) qubits. Specifically, Grover's algorithm converts the function to a reversible circuit C.sub. and calculates

[00007]$.Math.x.Math.\stackrel{C_f}{.fwdarw.}.Math.{\left(-1\right)}^{f\left(x\right)}.Math..Math.x$

in each of the Grover iterations, where |x is an l-qubit register. Thus the total steps for Grover's algorithm is bounded by

[00008]$\frac{.Math..Math.C_f.Math.}{4}.Math.\sqrt{2^l}.$

[0086] For the RLCE scheme, quantum ISD could be carried out similarly as in Bernstein (2010). One first uniformly selects k columns from the public key and checks whether it is invertible. If it is invertible, one multiplies the inverse with the ciphertext. If these coordinates contain no errors in the ciphertext, one recovers the plain text. Though Grover's algorithm requires that the function evaluate to 1 on only one of the inputs, there are several approaches (see, e.g., Grassl et al (2016)) to cope with cases that evaluates to 1 on multiple inputs.

[0087] For randomly selected k columns from a RLCE encryption scheme public key, the probability that the ciphertext contains no errors in these positions is

[00009]$\frac{\left(\begin{array}{c}n+w-t\\ k\end{array}\right)}{\left(\begin{array}{c}n+w\\ k\end{array}\right)}.$

Thus

[0088] the quantum ISD algorithm requires

[00010]$\sqrt{\left(\begin{array}{c}n+w\\ k\end{array}\right)/\left(\begin{array}{c}n+w-t\\ k\end{array}\right)}$

Grover iterations. For each Grover iteration, the function needs to carry out the following computations: [0089] 1. Compute the inverse of a kk sub-matrix G.sub.sub of the public key and multiply it with the corresponding entries within the ciphertext. This takes O (k.sup.2.807+k.sup.2) field operations if Strassen algorithm is used. [0090] 2. Check that the selected k positions contain no errors in the ciphertext. This can be done with one of the following methods: [0091] a) Multiply the recovered message with the public key and compare the differences from the ciphertext. This takes O ((n+w)k) field operations. [0092] b) Use the redundancy within message padding scheme to determine whether the recovered message has the correct padding information. The cost for this operation depends on the padding scheme.
It is expensive for circuits to use look-up tables for field multiplications. Using Karatsuba algorithm, Kepley and Steinwandt (2015) constructed a field element multiplication circuit with gate counts of 7.Math.(log.sub.2q).sup.1.585. In a summary, the above function for the RLCE quantum ISD algorithm could be evaluated using a reversible circuit C.sub.with O (7((n+w)k+k.sup.2.807+k.sup.2) (log.sub.2q).sup.1.585) gates. To be conservative, we may assume that a randomly selected k-columns sub-matrix from the public key is invertible. Thus Grover's quantum algorithm requires approximately

[00011]$\begin{array}{cc}7.Math.\left(\left(n+w\right).Math.k+k^{2.807}+k^2\right).Math.{\left({\log }_2.Math..Math.q\right)}^{1.585}.Math.\sqrt{\frac{\left(\begin{array}{c}n+w\\ k\end{array}\right)}{\left(\begin{array}{c}n+w-t\\ k\end{array}\right)}}& \left(5\right)\end{array}$

steps for the simple ISD algorithm against RLCE encryption scheme. Advanced quantum ISD techniques may be developed based on improved ISD algorithms. However our analysis shows that the reduction on the quantum security is marginal. For each of the recommended schemes in Table 0.3, the row (.sub.c,,.sub.q) in Table 0.2 shows the security strength under the classical ISD and classical quantum ISD attacks. For example, the RLCE scheme with ID=1 in Table 0.3 has 139-bits security strength under classical ISD attacks and 89-bits security strength under quantum ISD attacks.

TABLE-US-00002 TABLE 0.2 Security strength for RLCE schemes in Table 0.3 Scheme ID (.sub.c, .sub.q) 0 (128, 80) 1 (128, 80) 2 (192, 110) 3 (192, 110) 4 (256, 144) 5 (256, 144) (.sub.c, .sub.q) (139, 90) (139, 89) (205, 124) (206, 124) (269, 156) (269, 156) (.sub.c.sup.s, .sub.q.sup.s) (135, 86) (135, 85) (202, 120) (202, 120) (266, 154) (266, 153) (.sub.c.sup.Stern, .sub.q.sup.Stern) (130, 80) (131, 80) (195, 113) (195, 113) (257, 145) (256, 144) (.sub.n,k,w.sup., .sub.q.sup.) (128, 85) (210, 127) (260, 153)

[0093] In this paragraph, we consider improved ISD attacks. We first briefly review

[0094] Stern's (1989) algorithm. Let the k(n+w) matrix G be the public key and c be an RLCE scheme ciphertext. Let

[00012]$G_e=\left(\begin{array}{c}c\\ G\end{array}\right)$

be a (k+1)(n+w) matrix. Stern's algorithm will find the minimal weight code e that is generated by G.sub.e. It is straightforward to show that e is the error vector for the ciphertext c. Stern's information set decoding algorithm for finding the vector e is as follows. [0095] 1. Select two small numbers p<k/2 and l<n+wk. [0096] 2. Select k columns g.sub.i.sub.1 , . . . , g.sub.i.sub.k from G.sub.e and l columns g.sub.i , . . . , q.sub.j.sub.l from the remaining n+wk columns of G.sub.e where 0i.sub.1 , . . . , i.sub.k, j.sub.1 , . . . , j.sub.ln+w1 are distinct numbers. It is expected that the ciphertext c contains 2p errors within the locations i.sub.1 , . . . , i.sub.k and no errors within the positions j.sub.1 , . . . , j.sub.t. [0097] 3. Let P.sub.i.sub.1 , . . . , i.sub.k, j.sub.1 , . . . , j.sub.l be a (n+w)(n+w) permutation matrix so that

G.sub.eP.sub.i.sub.1 , . . . , i.sub.k,j.sub.1 , . . . , j.sub.l=(g.sub.i.sub.1 , . . . , g.sub.i.sub.k,g.sub.j.sub.1 , . . . , g.sub.j.sub.l,G.sub.r),

where G.sub.r is a (k+1)(n+wkl) matrix. [0098] 4. Compute the echelon format

G.sub.E=E(G.sub.eP.sub.i.sub.1 , . . . , i.sub.k,j.sub.1 , . . . , j.sub.l)=SG.sub.eP.sub.i.sub.1 , . . . , i.sub.k,j.sub.1 , . . . , j.sub.l=(I,L,G.sub.r)

where S is a (k+1)(k+1) matrix. [0099] 5. Find random vectors u, v GF(q).sup.(k+1)/2 of weight p such that (u, v)L=0. If no such u, v found, go to Step 2. [0100] 6. If (u, v)L=0, then check whether (u, v)G.sub.r has weight t2p. If it does not have weight t2p, go to Step 2. [0101] 7. If (u, v)G.sub.r has weight t2p, then e=(u,v)G.sub.EP.sub.i.sub.1.sup.1 , . . . , i.sub.k,j.sub.1 , . . . , k.sub.l is the error vector for the ciphertext c.

[0102] It is noted that if we take p=l=0, then Stern's algorithm is the naive ISD algorithm that we have discussed in the preceding section. For the convenience of analysis, we assume that pl>0 in the following discussion. The algorithm takes approximately

[00013]$\begin{array}{cc}{S}_I=\frac{\left(\begin{array}{c}n+w\\ .Math.k.Math.\text{/}.Math.2.Math.\end{array}\right).Math.\left(\begin{array}{c}n+w-.Math.k.Math.\text{/}.Math.2.Math.\\ k-.Math.k.Math.\text{/}.Math.2.Math.\end{array}\right).Math.\left(\begin{array}{c}n+w-k\\ l\end{array}\right)}{\left(\begin{array}{c}n+w-t\\ .Math.k.Math.\text{/}.Math.2.Math.-p\end{array}\right).Math.\left(\begin{array}{c}t\\ p\end{array}\right).Math.\left(\begin{array}{c}n+w-l-.Math.k.Math.\text{/}.Math.2.Math.-p\\ k-.Math.k.Math.\text{/}.Math.2.Math.-p\end{array}\right).Math.\left(\begin{array}{c}t-p\\ p\end{array}\right).Math.\left(\begin{array}{c}n+w-t-k+2.Math.p\\ l\end{array}\right)}& \left(6\right)\end{array}$

iterations. For each iteration, Step 4 takes (2n+2wk)k.sup.2 field operations, and Step 5 takes 2(.sub.p.sup.k/2) (q1).sup.pl(k+1) field operations. For each iteration, Step 6 runs (.sub.p.sup.k/2).sup.2(q1).sup.2pl times approximately and each runs takes (nkl)(k+1) field operations. In a summary, Stern's ISD takes approximately 2.sup..sup.c steps to find the error vector e where,

.sub.c=min.sub.p,l{log.sub.2(S.sub.I((2n+2wk)k.sup.2+2(.sub.p.sup.k/2)(q1).sup.pl(k+1) +(.sub.p.sup.k/2).sup.2(q1).sup.2pl(nkl))}. (7)

Our experiments show that for RLCE schemes that we have interest in, the equation (7) is always achieved with p=1 and l=3. For quantum version of Stern's ISD algorithm, the Grover's algorithm could be used to reduce the iteration steps to {square root over (S.sub.r)}. Thus the quantum security level under Stem attacks is approximately

.sub.q=min.sub.p,l,{log.sub.2 ({square root over (S.sub.1)}((2n+2wk)k.sup.2+2(.sub.p.sup.k/2)(q1).sup.pl(k+1)+(.sub.p.sup.k/2).sup.2(q1).sup.2pl(nll))}. (8)

[0103] In order to speed up Stern's algorithm, Peters (2010) considers the following improvement: [0104] 1. For each iteration, one does not randomly selects k columns from G.sub.e in Step 2. Instead, one reuses kc columns from the previous iteration where c is a fixed constant. [0105] 2. For a small finite field, fix a parameter r>1 for certain pre-computation of row sums. This will not provide any benefit for a large field size such as those used in RLCE schemes. [0106] 3. For a small finite field, fix a parameter m>1 such that one can use m error-free sets of size l. This will not provide any benefit for a large field size such as those used in RLCE schemes.
Our experiments show that for .sub.c200, Peters's improved version is at most 8 times fast than Stern's algorithm discussed in this section. That is, we generally have .sub.c3.sub.c.sup.Peter.sub.c where .sub.c.sup.Peter is the .sub.c obtained from Peter's improved algorithm. For .sub.c250, our experiments show that Peter's improved version has the same performance as Stern's algorithm discussed in this section. Furthermore, our experiments show that the optimal values for p, l in Peter's improved algorithm on all RLCE schemes are p=1 and l=3 also.

[0107] Using distinguisher techniques by Faugere (2013), Couvreur et al. (2013) designed a filtration technique to attack GRS code based McEliece scheme. The filtration technique was further developed by Couvreur et al (2014) to attack wild Goppa code based McEliece scheme. In the following, we briefly review the filtration attack in Ccouvreur et al (2014). For two codes C.sub.1 and C.sub.2 of length n, the star product code C.sub.1*C.sub.2 is the vector space spanned by a*b for all pairs (a, b) C.sub.1C.sub.2 where

a*b=[a.sub.0b.sub.0, a.sub.1b.sub.1 , . . . , a.sub.n1b.sub.n1].

For the square code C.sup.2=C*C of C, we have

[00014]$\dim .Math..Math.C^2\min .Math..Math.\left\{n,\left(\begin{array}{c}\dim .Math..Math.C+1\\ 2\end{array}\right)\right\}.$

For an [n, k] GRS code C, let a, b GRS.sub.k(x, y) where a=(y.sub.0p.sub.1(x.sub.0), . . . , y.sub.n1p.sub.1(x.sub.n1)) and b=(y.sub.0p.sub.2(x.sub.0), . . . , y.sub.n1p.sub.2(x.sub.n1)). Then a*b=(y.sub.0.sup.2p.sub.1(x.sub.0)p.sub.2(x.sub.0), . . . , y.sub.n1.sup.2p.sub.1(x.sub.n1)p.sub.2(x.sub.n1)). Thus GRS.sub.k(x, y).sup.2 .Math. GRS.sub.2k1(x, y*y) where we assume 2k1n.

[0108] Let G be the public key for an (n, k, d, t, w) RLCE encryption scheme based on a GRS code. Let C be the code generated by the rows of G. Let D.sub.1 be the code with a generator matrix D.sub.1 obtained from G by replacing the randomized 2w columns with all-zero columns and let D.sub.2 be the code with a generator matrix D.sub.2 obtained from G by replacing the nw non-randomized columns with zero columns. Since CD.sub.1+D.sub.2 and the pair (D.sub.1, D.sub.2) is an orthogonal pair, we have C.sup.2D.sub.2.sup.2+D. It follows that

2k1dim C.sup.2min{2k1,nw}2w (9)

where we assume that 2wk.sup.2. In the following discussion, we assume that the 2w randomized columns in D.sub.2 behave like random columns in the filtration attacks. We first consider the simple case of knw. In this case, we have dim C.sup.2=D.sub.1.sup.2+D.sub.2.sup.2=nw+D.sub.2.sup.2=n+w. Furthermore, for any code C of length n that is obtained from C using code puncturing and code shortening, we have dim C.sup.2=n. Thus filtration techniques could not be used to recover any non-randomized columns in D.sub.1.

[0109] Next we consider the case for k<nw. For this case, we distinguish two sub-cases: nw2k and nw<2k. For the case nw2k, let C.sub.i be the punctured C code at position i. We distinguish the following two cases: [0110] Column i of G is a randomized column: the expected dimension for is C.sub.i.sup.2 is 2k+2w2. [0111] Column i of G is a non-randomized column: the expected dimension for is C.sub.i.sup.2 is 2k+2w1.
This shows that if nw2k, then the filtration techniques could be used to identify the randomized columns within the public key G. Thus it is recommended to have nw <2k for RLCE scheme.

[0112] Now we consider the case of k<nw<2k. In order to carry out filtration attacks, we need to shorten the code C at certain locations. Assume that we shorten l<k1 columns from G. Among the l=l.sub.1+l.sub.2 columns, l.sub.1 columns are non-randomized columns from D.sub.1 and l.sub.2 columns are randomized columns from D.sub.2. Then the shortened code has dimension

d.sub.l,l.sub.1=min{(kl).sup.2, min{2(kl.sub.1)1,nwl.sub.1,(kl).sup.2}+min{2wl.sub.2,(kl).sup.2}}. (10)

A necessary condition for the filtration attack to be observable is that, after the shortening of the l.sub.1 columns in D.sub.1, the following condition is satisfied

d.sub.l,l.sub.1=2(kl.sub.1)1+min{2wl.sub.2,(kl).sup.2}. (11)

[0113] Thus for a given l, the probability for the filtration attack to be successful is bounded by the probability

[00015]$\frac{{.Math.}_{l_1=\max .Math.\left\{0,l-2.Math.w\right\}}^l.Math.\left(d_{l,l_1}\right).Math.\left(\begin{array}{c}n-w\\ l_1\end{array}\right).Math.\left(\begin{array}{c}2.Math.w\\ l-l_1\end{array}\right)}{\left(\begin{array}{c}n+w\\ l\end{array}\right)}$

where (d.sub.l,l.sub.1)=1 if (11) holds and (d.sub.l,l.sub.1)=0 otherwise. For a given 1, one randomly selects l columns from G and shortens G from these locations. This process takes O (kl(n+w)) field operations. Then one calculates the dimension of the shortened code to see whether the equation (11) is achieved which takes O ((kl).sup.4(n+wl)) field operations. In a summary, the expected time for one to carry out the filtration attack for a given l is

[00016]${\mathrm{PF}}_{n,k,w,l}=\frac{\left(\begin{array}{c}n+w\\ l\end{array}\right).Math.\left(O\left(\mathrm{kl}\left(n+w\right)\right)+O\left({\left(k-l\right)}^4.Math.\left(n+w-l\right)\right)\right)}{{.Math.}_{l_1=\max .Math.\left\{0,l-2.Math.w\right\}}^l.Math.\left(d_{l,l_1}\right).Math.\left(\begin{array}{c}n-w\\ l_1\end{array}\right).Math.\left(\begin{array}{c}2.Math.w\\ l-l_1\end{array}\right)}$

[0114] Let

.sub.n,k,w.sup.=log.sub.2 min{PF.sub.n,k,w,l:2kn+wlk2}. (12)

Then in order to guarantee that the RLCE scheme is secure against filtration attacks, the parameters should be chosen in such a way that nwk or nw<2k and .sub.c.sub.n,k,w.sup..

[0115] Filtration attacks could be combined with Grover's quantum search algorithm. The quantum Filtration attacks works in the same way as the filtration attack that we have discussed in the preceding paragraph except that one uses Grover's quantum computer to select 1 columns from the public key C. It can be shown that, under quantum filtration attacks, the attack against the RLCE scheme takes

[00017]$\begin{array}{cc}\underset{2.Math.k-n+wlk-2}{\min }.Math.\left\{\frac{7.Math.{\left({\log }_2.Math..Math.q\right)}^{1.585}.Math.\left(O\left(\mathrm{kl}\left(n+w\right)\right)+O\left({\left(k-l\right)}^4.Math.\left(n+w-l\right)\right)\right).Math.\sqrt{\left(\begin{array}{c}n+w\\ l\end{array}\right)}}{\sqrt{{.Math.}_{l_1=\max .Math.\left\{0,l-2.Math.w\right\}}^l.Math.\left(d_{l,l_1}\right).Math.\left(\begin{array}{c}n-w\\ l_1\end{array}\right).Math.\left(\begin{array}{c}2.Math.w\\ l-l_1\end{array}\right)}}\right\}.& \left(13\right)\end{array}$

steps.

[0116] For each of the recommended schemes in Table 0.3, the row (.sub.n,k,w.sup., .sub.q.sup.) in Table 0.2 shows the security strength under the filtration attack and quantum filtration attacks. For example, the RLCE scheme with ID=1 in Table 0.3 has 128-bits security strength under filtration attacks and 85-bits security strength under quantum filtration attacks.

[0117] We mentioned several attacks on RLCE schemes in the preceding paragraphs. To avoid these attacks, it is necessary to use message padding schemes so that the encryption scheme is secure against adaptive chosen ciphertext attacks (IND-CCA2).

[0118] We first analyze the amount of information that could be encoded within each ciphertext. Let (n, k, t, w) be the parameters where the public key is of dimension k(n+w) and G F(q) (with q=2.sup.m) be the underlying finite field. There are three approaches to encode messages within the ciphertext. [0119] 1. basicEncoding: Encode information within the vector m GF(q).sup.k and the ciphertext is c=mG+e. In this case, we can encode mLen=mk bits information within each ciphertext. [0120] 2. mediumEncoding: In addition to basicEncoding, further information is encoded in the non-zero entries of e. That is, let e.sub.i.sub.1 , . . . , e.sub.i.sub.t G F(q)\{0} be the non-zero elements within e and encode further information within e.sub.i.sub.1 , . . . , e.sub.i.sub.t. In this case, we can encode mLen=m(k+t) bits information within each ciphertext. Strictly speaking, the encoded information is less than m(k+t) bits since cannot be zeros. [0121] 3. advancedEncoding: In addition to mediumEncoding, further information are encoded within locations of non-zero entries within e. Since there are

[00018]$\left(\begin{array}{c}n+w\\ t\end{array}\right)$

candidates for the choice of non-zero entries within e, we can encode

[00019]$\mathrm{mLen}=m\left(k+t\right)+.Math.{\log }_2\left(\begin{array}{c}n+w\\ t\end{array}\right).Math.$

bits information within each ciphertext.

[0122] The basicEncoding approach is straightforward. For the mediumEncoding, after one recovers the vector m, one needs to compute mGc to obtain the values of e.sub.i.sub.t , . . . , e.sub.i.sub.t. For the advancedEncoding approach, we need to compute an invertible function

[00020]$\begin{array}{cc}.Math.\text{:}.Math.W_{n+w,t}.Math.\left\{i.Math.\text{:}.Math.1i\left(\begin{array}{c}n+w\\ t\end{array}\right)\right\}& \left(14\right)\end{array}$

where W.sub.n+w,t .Math. GF(2).sup.n+w is the set of all (n+w)-bit binary string of weight t. For the invertible function in (14), one may use the enumerative source encoding construction in Cover (1973):

[00021]$.Math.\text{:}.Math.W_{n+w,t}.Math.\left[0,\left(\begin{array}{c}n+w\\ t\end{array}\right)\right]$

where

[00022]$\left(i_1,\mathrm{.Math.},i_t\right)=\left(\begin{array}{c}{i}_t-1\\ t\end{array}\right)+\mathrm{.Math.}+\left(\begin{array}{c}{i}_1-1\\ 1\end{array}\right)$

and 0i.sub.1<i.sub.2<. . . <i.sub.t<n+w are the positions of ones. The function could be evaluated with the cost of

[00023]$O\left({\left({\log }_2.Math..Math.\left(\begin{array}{c}n+w\\ t\end{array}\right).Math.\right)}^2\right)$

operations (see, e.g., Sendrier 2005).

[0123] We assume that the message bandwidth is mLen-bits for each ciphertext. We present two efficient IND-CCA2 padding schemes for the RLCE encryption scheme. Our padding schemes are adapted from the well analyzed Optimal Asymmetric Encryption Padding (OAEP) for RSA/Rabin encryption schemes and its variants OAEP+(Shoup 2001) and SAEP+(Boneh 2001). The first simple padding scheme RLCEspad is a one-round of a Feistel network that is similar to SAEP+. RLCEspad could be used to encrypt short messages (e.g., mLen/4-bits) and is sufficient for applications such as symmetric key transportation using the RLCE public key encryption scheme. The second padding scheme RLCEpad is a two-round Feistel network that is similar to OAEP+. RLCEpad could be used to encrypt messages that are almost as long as mLen-bits. In the following discussions, we assume that messages are binary strings. After padding, it will be converted to field elements and/or other information required for the RLCE scheme. For a RLCE setup process RLCE.KeySetup(n, k, d, t, w), let k(n+w) matrix G be a public key and (S, G.sub.s, P.sub.1, P.sub.2, A) be a corresponding private key. The RLCEspad proceeds as follows.

[0124] FIG. 3 describes a process for the padding scheme RLCEspad(mLen, k.sub.1, k.sub.2, k.sub.3). Referring therefore to FIG. 3, let k.sub.1, k.sub.2, k.sub.3 be parameters such that mLen=k.sub.1+k.sub.2+k.sub.3, k.sub.1+k.sub.2<k.sub.3, and k.sub.1mLen/4. Let H.sub.1 and H.sub.2 be random oracles that take any-length inputs and outputs k.sub.2-bytes and (k.sub.1+k.sub.2)-bytes respectively. The box 300 is the message m {0, 1}.sup.8k.sup.1 to be encrypted and the box 320 is a randomly selected binary sequence r {0, 1}.sup.8k.sup.3. The random oracle engine 310 outputs a k.sub.2-bytes sequence H.sub.1 (m, r, e.sub.0) on the inputs m, r, e.sub.0. The random oracle engine 330 outputs a (k.sub.1+k.sub.2)-bytes sequence H.sub.2(r, e.sub.0) on the inputs r, e.sub.0. The exclusive-or engine 340 outputs a (k.sub.1+k.sub.2)-bytes sequence (mH.sub.1(m,r,e.sub.0))H.sub.2(r,e.sub.0). The copy engine 350 outputs the value in the box 320.

[0125] Specifically, RLCEspad could be described for various encoding methods that we have discussed in the preceding paragraphs. We distinguish the following three cases: [0126] basicEncoding: select a random e GF(q).sup.n+w of weight t and set

y=((mH.sub.1(m,r,e))H.sub.2(r,e))r (15)

Convert y to an element y.sub.l GF(q).sup.k. Let the ciphertext be c=y.sub.1G+e. [0127] mediumEncoding: select a random e.sub.0 W.sub.n+w,t and set

y=((mH.sub.1(m,r,e.sub.0)) H.sub.2(r,e.sub.0))r. (16) [0128] Convert y to an element y.sub.1 GF(q).sup.k and an element e.sub.l GF(q).sup.t. Integrate e.sub.l within e.sub.0 to form an error vector e GF(q).sup.n+w of weight t. Let the ciphertext be c=y.sub.1G+e. [0129] advancedEncoding: set y=((mH.sub.1(m, r) H.sub.2 (r))r. Convert y to an element y.sub.1 GF(q).sup.k and a vector e GF(q).sup.n+w of weight t. Let the ciphertext be c=y.sub.1G+e.

[0130] Assuming the hardness of decoding RLCE ciphertexts, a similar proof as in Boneh (2001) could be used to show that RLCE-RLCEspad scheme is secure against IND-CCA2 attacks. As an example with .sub.c=128 bits security RLCE scheme (600, 464, 68) over GF(2.sup.10) in Table 0.3, we use k.sub.1=k.sub.2=160-bytes for mediumEncoding and k.sub.1=k.sub.2=170-bytes for advancedEncoding.

[0131] FIG. 4 describes a process for our next padding scheme RLCEpad(mLen, k.sub.1, k.sub.2, k.sub.3) reported in this invention. Referring therefore to HG. 4, let k.sub.1, k.sub.2, k.sub.3 be parameters such that mLen=k.sub.1+k.sub.2+k.sub.3 and H.sub.1, H.sub.2, and H.sub.3 be a random oracle that takes any-length inputs and outputs k.sub.2, k.sub.2, and k.sub.3 bits respectively. Let The box 400 is the message m {0, 1}.sup.8k.sup.1 to be encrypted and the box 420 is a randomly selected binary sequence r {0, 1}.sup.8k.sup.3. The random oracle engine 410 outputs a k.sub.2-bytes sequence H.sub.i (m, r, e.sub.0) on the inputs m, r, e.sub.0. The random oracle engine 430 outputs a (k.sub.1+k.sub.2)-bytes sequence H.sub.2(r, e.sub.0) on the inputs r, e.sub.0. The random oracle engine 440 outputs a k.sub.3-bytes sequence H.sub.3((MH.sub.1(m, r, e.sub.0)) H.sub.2(r, e.sub.0)). The exclusive-or engine 450 outputs a (k.sub.1+k.sub.2)-bytes sequence (mH.sub.1(m, r, e.sub.0)) H.sub.2(r, e.sub.0) The exclusive-or engine 460 outputs a k.sub.3-bytes sequence r H.sub.3((mH.sub.1(m, r, e.sub.0)) H.sub.2(r, e.sub.0)).

[0132] Specifically, RLCEpad could be described for various encoding methods that we have discussed in the preceding paragraphs. We distinguish the following three cases: [0133] basicEncoding: select a random e GF(q).sup.n+w,t of weight t and set

y=((mH.sub.1(m,r,e)) H.sub.2(r,e))r H.sub.3(((mH.sub.1(m,r,e)) H.sub.2(r,e))) (17)

Convert y to an element y.sub.1 GF(q).sup.k. Let the ciphertext be c=y.sub.1G+e. [0134] mediumEncoding: select a random e.sub.0 W.sub.n+w,t and set

y=((mH.sub.1(m, r, e.sub.0)) H.sub.2(r, e.sub.0))(rH .sub.3((mH.sub.1(m,r,e.sub.0)) H.sub.2(r,e.sub.0))) (18)

Convert y to an element y.sub.1 GF(q).sup.k and an element e.sub.l GF(q).sup.t. Integrate e.sub.l within e.sub.0 to form an error vector e GF(q).sup.n+w of weight t. Let the ciphertext be c=y.sub.1G+e. [0135] advancedEncoding: set

y=((mH.sub.1(m,r)) H.sub.2(r))(r H.sub.3((mH.sub.1(m,r)) H.sub.2(r))) (19)

Convert y to an element y.sub.1 GF(q).sup.k and a vector e GF(q).sup.n+w of weight t. Let the ciphertext be c=y.sub.1G+e.

[0136] Assuming the hardness of decoding RLCE ciphertexts, a similar proof as in Shoup (2001) could be used to show that RLCE-RLCEpad scheme is secure against IND-CCA2 attacks. As an example with =128 bits security RLCE scheme (600, 464, 68) over GF(2.sup.10) in Table 0.3, we use k.sub.2=32-bytes and k.sub.3=33-bytes for both mediumEncoding and advancedEncoding.

[0137] Note that either error positions e.sub.0 or error vector e is used in the RLCEspad/RLCEpad schemes and the message recipient needs to have the exact e.sub.0 or e for message decoding. In case that the randomly generated error values contain zero field elements, the corresponding error positions will be unavailable for the recipient. To avoid this potential issue, the message encryption process needs to guarantee that error values should never be zero. A simple approach to address this challenge is when calculated error values (using the given random value r) contain zero field elements, one revises the random value r to a new value and tries the padding approach again. This process continues until all error values are non-zero.

[0138] Taking into account of the cost of Sidelnikov-Shestakov attacks, the cost of recovering McEliece encryption scheme secret keys from the public keys, and the cost of recovering plaintext messages from ciphertexts using the information-set decoding methods, we generated a recommended list of parameters for RLCE scheme in Table 0.3. In particular, the recommendation takes into account of the conditions for avoiding improved classical and quantum information set decoding, the conditions for avoiding Sidelnikov-Shestakov attacks, the conditions for filtration attacks (with or without brute force), the cost of recovering McEliece encryption scheme secret keys from the public keys, and the cost of recovering plaintext messages from ciphertexts. In Table 0.3, n, denotes the conventional security strength and .sub.q denotes the quantum security strength. For example, .sub.c=128 means an equivalent security of AES-128. The recommended parameters is based on any underlying MDS linear code (e.g., GRS code) over GF(q) where q=2.sup.[log.sup.2.sup.n]. For GRS codes, the BCH-style construction requires n=q1. However, GRS codes could be shortened to length n<q1 codes by interpreting the unused q1n information symbols as zeros.

[0139] In Table 0.3, the schemes with ID=0, 1, 2, 3, 4, 5, 6 are for MDS codes with

[00024]$t=\frac{n-k}{2}.$

The scheme with ID=6 is for testing purpose only.

[0140] Table 0.3 also lists the message bandwidth and message padding scheme parameters

TABLE-US-00003 TABLE 0.3 Padding parameters: bE for basicEncoding, mE for mediumEncoding and aE for advancedEncoding RLCEspad RLCEpad .sub.1 .sub.2 ID .sub.c, .sub.q, n, k, t, w, m sk cipher, pk mLen (.sub.2) .sub.3 .sub.1 (.sub.3) 0 128, 80, 630, 470, 80, 160, 10 310116 988, 188001 bE 4700 146 296 524 32 192029 mE 5500 171 346 624 32 aE 5869 183 368 670 32 1 128, 80, 532, 376, 78, 96, 10 179946 785, 118441 bE 3760 117 236 406 32 121666 mE 4540 141 286 504 32 aE 4875 152 306 546 32 2 192, 110, 1000, 764, 118, 236, 10 747393 1545, 450761 bE 7640 238 479 859 48 457073 mE 8820 275 553 1007 48 aE 9377 293 587 1077 48 3 192, 110, 846, 618, 114, 144, 10 440008 1238, 287371 bE 6180 193 387 677 48 292461 mE 7320 228 459 819 48 aE 7825 244 491 883 48 4 256, 144, 1360, 800, 280, 560, 11 1773271 2640, 1232001 bE 8800 275 550 980 60 1241971 mE 11880 371 743 1365 60 aE 13025 407 815 1509 60 5 256, 144, 1160, 700, 230, 311, 11 1048176 2023, 742089 bE 7700 240 483 843 60 749801 mE 10230 319 641 1159 60 aE 11145 348 698 1274 60 6 22, 22, 40, 20, 10, 5, 10 1059 57, 626 bE 200 6 13 17 4 859 mE 300 9 20 30 4 aE 331 10 22 34 4
for the recommended schemes. In case that v=8(k.sub.1+k.sub.2+k.sub.3)mLen.sub.i>0, the last v-bits of the k.sub.3-bytes random seed r should be set to zero and the last v-bit of the encoded string y is discarded. For RLCEspad with v>0, the encoding and decoding process are straightforward. For RLCEpad with v>0, the decoding process produces an encoded string y with last v-bits missing. After using H.sub.3 to hash the first part of y resulting in k.sub.3-bytes hash output, one discards the last v-bits from the hash output and the remaining (8k.sub.3v)-bits with the second half of y to obtain the (8k.sub.3v)-bits of r without the v-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.

REFERENCE CITED

[0141] Marco Baldi, Marco Bianchi, Franco Chiaraluce, Joachim Jakob Rosenthal, and Davide Mose' Schipani. Method and apparatus for public-key cryptography based on error correcting codes. U.S. Pat. No. 9,191,199 B2 (2015) [0142] Martin Tomlinson, Cen Jung Tjhai. Public key cryptosystem based on goppa codes and puf based random generation. U.S. Pat. No. 8,958,553 B2 (2015) [0143] Martin Tomlinson and Cen Jung Tjhai. Public key encryption using error correcting codes. WO2012066328 A1 (2012) [0144] Eran Kanter, Ido Kanter. A secure and linear public-key cryptosystem based on parity-check error-correcting code. WO2001050675 A2 (2001). [0145] Yongge Wang. Method and Apparatus for Random Linear Code Based Public Key Encryption Schemes. U.S. patent application Ser. No. 15/270,824, filed on Sep. 20, 2016. [0146] Yongge Wang. Method and Apparatus for Quantum Resistant Public Key Encryption Scheme RLCE and IND-CCA2 Security. U.S. Patent application U.S. 62/435,151, filed on Dec. 16, 2016.