Method and apparatus for asymmetric cryptosystem based on quasi-cyclic moderate density parity-check codes over GF(q)

Abstract

Methods and apparatus for code-based asymmetric cryptosystem using Quasi-Cyclic Moderate-Density Parity-Check (QC-MDPC) error correcting codes. Specifically, the method and apparatus generalizes the framework of (QC-MDPC) Code-Based (CB) cryptography from the binary domain (Galois Field of two elements) to an arbitrary size of Galois Field and provides an apparatus for implementing the cryptosystem with a simplified computational complexity of key generation, encryption, and decryption components of the cryptosystems and reduced sizes of the public and private security keys.

Claims

1. A method for encrypting a message using a quasi-cyclic moderate density parity check code over a Galois field, comprising: converting a message to be encrypted into plurality of message components; transforming a message component of the plurality of message components to obtain a transformed message component; transforming a first component of a public key to obtain a first transformed generator component; multiplying the transformed message component with the first transformed generator component to obtain a first multiplied output; inverse transforming the first multiplied output to obtain a first codeword component; transforming a second component of the public key to obtain a second transformed generator component; multiplying the transformed message component with the second transformed generator component to obtain a second codeword component; combining the first codeword component and the second codeword component to obtain a codeword; and multiplying the codeword with an error signal to obtain an encrypted ciphertext.

2. A method as claimed in claim 1, wherein the transforming steps are performed using number theory transform engines; and wherein the inverse transforming steps are performed using inverse number theory transform engines.

3. A method as claimed in claim 1, further comprising: generating a random sparse row vector with elements from a Galois Field (GFq) and with a prescribed vector weight; splitting the sparse row vector into a plurality of polynomials including a left polynomial and a plurality of rightmost polynomials; inverting the rightmost polynomials to provide an inverted rightmost polynomials; and circulant multiplying the left polynomials and the inverted rightmost polynomials to obtain a generator polynomial, wherein the generator polynomial is the public key.

4. A method for encrypting a message using a quasi-cyclic moderate density parity check code over a Galois field, comprising: mapping a component of a plaintext message into a Galois field using a complex mapper to obtain a mapped message component; transforming the mapped message component using a fast Fourier transformer to obtain a transformed message component, wherein the transforming of the mapped message component includes transforming the mapped message component in a fast Fourier transformer having a size M equal to a prime number, the fast Fourier transformer of size M including a fast Fourier transformer of size N.sub.F and an inverse fast Fourier transformer of size N.sub.F, where N.sub.F is larger than M, an output of the fast Fourier transformer of size N.sub.F being mixed with a predetermined signal prior to being provided to an input of the inverse fast Fourier transformer of size N.sub.F; mapping a generator polynomial into a Galois field using a complex mapper to obtain a mapped generator component; transforming the mapped generator component using a fast Fourier transformer to obtain a transformed generator component; multiplying the transformed message component with the transformed generator component to obtain a mixed output; inverse transforming the mixed output to obtain an inverse signal; mapping the inverse signal into a complex to Galois field mapper to obtain a component of a codeword; repeating the above elements for each component of the plaintext message; combining the components of the codeword into a codeword; and adding an error signal to the codeword to obtain an encrypted message.

5. A method as claimed in claim 4, wherein the inverse transforming of the mixed output includes inverse transforming using an inverse fast Fourier transformer of size M including a fast Fourier transformer of size N.sub.F and an inverse fast Fourier transformer of size N.sub.F, the output of the fast Fourier transformer of size N.sub.F being mixed with a predetermined signal prior to being provided to the input of the inverse fast Fourier transformer of size N.sub.F.

6. A method as claimed in claim 5, further comprising: Im scaling the mixed output provided to the inverse fast Fourier transformer of size M to obtain a scaled signal for input to the fast Fourier transformer of size N.sub.F; and Im descaling an output of the inverse fast Fourier transformer of size N.sub.F to obtain an output of the inverse fast Fourier transformer of size M.

7. A method for encrypting a message using a quasi-cyclic moderate density parity check code over a Galois field, comprising: mapping a component of a plaintext message into a Galois field using a complex mapper to obtain a mapped message component; transforming the mapped message component using a fast Fourier transformer to obtain a transformed message component; mapping a generator polynomial into a Galois field using a complex mapper to obtain a mapped generator component; transforming the mapped generator component using a fast Fourier transformer to obtain a transformed generator component; multiplying the transformed message component with the transformed generator component to obtain a mixed output; inverse transforming the mixed output to obtain an inverse signal, wherein the inverse transforming of the mixed output includes inverse transforming using an inverse fast Fourier transformer of size M including a fast Fourier transformer of size N.sub.F and an inverse fast Fourier transformer of size N.sub.F, where N.sub.F is larger than M, the output of the fast Fourier transformer of size N.sub.F being mixed with a predetermined signal prior to being provided to the input of the inverse fast Fourier transformer of size N.sub.F; mapping the inverse signal into a complex to Galois field mapper to obtain a component of a codeword; repeating the above elements for each component of the plaintext message; combining the components of the codeword into a codeword; and adding an error signal to the codeword to obtain an encrypted message.

8. A method as claimed in claim 7, further comprising: Im scaling the mixed output provided to the inverse fast Fourier transformer of size M to obtain a scaled signal for input to the fast Fourier transformer of size N.sub.F; and Im descaling an output of the inverse fast Fourier transformer of size N.sub.F to obtain an output of the inverse fast Fourier transformer of size M.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a functional block diagram of a system for secure communication between two parties over a non-secure communication channel using a public key and a private key;

(2) FIG. 2 is a functional block diagram of a key generation apparatus and method for generating a private key and a public key;

(3) FIG. 3 is a functional block diagram of an apparatus for encryption of a plaintext message using NTT and INTT methods according to a first embodiment;

(4) FIG. 4 is a functional block diagram of an apparatus for encryption of a plaintext message using NTT and INTT methods according to a second embodiment;

(5) FIG. 5 is a functional block diagram of an apparatus and method for QC-MDPC encoding; and

(6) FIG. 6 is a functional block diagram of an apparatus and method for QC-MDPC decryption.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

(7) FIG. 1 shows an example of a communication system 10 for secure communication from a sending device 12 to a receiving device 14 using a non-secure communication channel 16. The communication channel 16 may be any wired or wireless communication channel or may be a combination of the two. The communication channel 16 need not be secure and may carry communications that are accessible by the public. The sending and receiving devices 12 and 14 may be any type of device such as a computer device, server, tablet computer, smart phone or other phone, e-reader, personal digital assistant, television, wired or wireless communication device, or other device that may use secure communications.

(8) A public key and a private key are each needed for the secure communication. A key generator system or device 18 may be used to generate the keys. The key generator system or device 18 may be part of the receiving device 18 or may be separate from the receiving device 14. For instance, the key generator system or device 18 may be included in a central system that distributes the keys. The key generator 18 may generate the keys in advance or when needed. The key generator system and device 18 includes a private key and public key generator 20. The private key that is generated by the generator 20 is transferred as indicated by block 22 to a private key storage 24. The private key storage 24 may be in the receiving device 14 or the key may be provided to the receiving device 14 as needed.

(9) The public key generated by the generator 20 is transmitted from a transmitter 26 in the key generator system or device 18 to a receiver 28 in the sending device 12 over a communication channel 30. The communication channel 30 may be a public communication channel and need not be secure. The public key that has been received in the sending device 12 may be stored in a public key storage 32 for future use or may be requested when needed. A plain text message to send 34 is provided to an encryption system 36 of the sending device 12. The encryption system 36 uses the public key stored in the public key storage 32 to encrypt the plain text message 34 and thereby obtain an encrypted message. The encrypted message is provided to a transmitter 38 which transmits the encrypted message via the non-secure communication channel 16 to a receiver 40 in the receiving device 14. The received encrypted message is transferred from the receiver 40 to a decryption system 42 in the receiving device 14. The decryption system 42 obtains the private key from the private key storage 24 and performs the decryption, yielding a decrypted plain text message 44. This shows but one example of a communication system using the encryption.

(10) A. Code-Based GFq QC-MDPC Key Generation

(11) FIG. 2 illustrates an embodiment of an apparatus and method for QC-MDPC cryptosystem key generation in detail.

(12) In this example, a QC-MDPC code in GFq is provided instead of GF2 (i.e. q=2) specified by its GFq parity check matrix H.sub.q.sup.M×N, where q≥2,

(13) $N=\frac{n}{{\log }_2\left(q\right)},\mathrm{and}M=\frac{m}{{\log }_2\left(q\right)}.$
The first row of the matrix H.sub.q.sup.M×N is defined as h.sub.q.sup.1×N.

(14) In a first step, the private key is generated and stored in a suitable form in a private key storage. The private key may be generated in a user's device or in a central system or other device. The private key storage may be in the user's device, in a central system or other storage location The procedure for key generating is as follows: a random vector generator 50 outputs a temporary sparse row vector ĥ.sub.q.sup.1×N as shown at 52 of weight W and sends it to a rightmost polynomial invertibility detector 54. The random vector generator 50 may be termed a random sparse vector generator or a random weight W vector generator in certain embodiments. The invertibility detector 54 determines whether a lifting matrix of the rightmost polynomial of the temporary sparse row vector ĥ.sub.q.sup.1×N is singular, thus whether the vector is invertible. If the invertibility estimator or detector 54 returns a ‘false’ result for invertibility, then the rightmost polynomials' corresponding lifting matrix is singular, then this causes the temporary sparse row vector ĥ.sub.q.sup.1×N to be discarded and causes a request for a new random sparse vector to be sent from the invertibility detector 54 to the random vector generator 50 as shown at 56. A lifting matrix is a matrix whose diagonal elements are 1s and only non-diagonal elements are nonzero. If the lifting matrix is invertibile and thus not singular, the detector 54 returns a ‘true’ result which indicates that the first row of the H matrix has been successfully generated. The successfully generated first row which may be referred to as row vector h.sub.q.sup.1×N is output from the invertibility detector 54 as shown at output 58. A copy of the row vector h.sub.q.sup.1×N is transmitted as shown at 60 to a sparse vector compressor 62 for processing to produce a more compact form of the vector, which may be referred to as {tilde over (h)}.sub.2.sup.1×L. The compressed vector {tilde over (h)}.sub.2.sup.1×L is output by the compressor 62 as shown at 64 to a private key storage 66, where it is stored in the private key storage 66 as the private key.

(15) Subsequently, the public key is computed using the following procedure: The successfully generated row vector h.sub.q.sup.1×N is output as shown at 58 and is sent to a polynomials splitter 68 that splits the N polynomials of the row vector into n.sub.0 streams each having a length M. Using the example of n.sub.0=2, the first stream consists of the first M symbols of the row vector, which are polynomials h.sub.q.sup.0≤i<M that are output as shown at 70 to a multiplier 78. The second stream is the rightmost polynomials h.sub.q.sup.N-M≤i<N which are the last M symbols of the row vector and which are output by the polynomial splitter 68 at 72. The rightmost polynomials on the output 72 are sent to a polynomials invertor 74, which computes the polynomials' inverses in a ring. The polynomials invertor 74 then outputs the first row of the rightmost matrix as a polynomial (h.sub.q.sup.N-M≤i<N).sup.−1 as shown at output 76. The two polynomials on the outputs 70 and 76 are sent to a circulant polynomials multiplier 78. The output of the polynomials multiplier 78 which is shown at 80 is the public key g.sub.q.sup.(n0−1)×M, which is in the form of a generator polynomial which will be sent for publishing in a public key publishing block 82. The publishing block 82 represents the publishing of the public key or generator polynomial to a user. The public key may be published in advance to the user or may be published when needed for a communication. The publication of the public key may include transmitting the public key on a public communication channel to a user or to a storage device from which it may be retrieved by a user seeking to use the public key.

(16) All of the components 50-82 shown in FIG. 2 may be provided within a device such as a computer, computer system, network, mobile device, server or other device or system. In some embodiments, the publishing block 82 may be outside the device or system for publication of the public key for example by an third party device or system.

(17) Encryption of messages, transmission of encrypted messages, and decryption of the transmitted encrypted message may be performed using the public key and private key generated by this method.

(18) B. Code-Based GFq QC-MDPC Encryption

(19) Two configurations are provided to carry out the encryption process for GFq QC-MDPC code-based cryptosystem. The first configuration utilizes a Number Theory Transform (NTT) while the second configuration uses a complex FFT (Fast Fourier Transform). The FFT based encryption and the NTT based encryption are two different ways to conduct the encryption and get the same results. The NTT based encryption does not need an FFT engine, since the NTT is a fast engine itself. Both FFT and NTT encryption share the same matrix inversion and singularity detection steps.

(20) In this specification, a first configuration is described using the general value of the design parameter n.sub.0 while in a second configuration the value n.sub.0=2 is used for the purpose of illustration and ease of description. The invention is not limited to these values. The generalization to other values of n.sub.0 is straightforward as will be understood by those of skill in this art.

(21) 1) NTT-Based Encryption:

(22) A proposed apparatus for QC-MDPC cryptosystem encryption using number theory transform (NTT) and inverse number theory transform (INTT) is illustrated in FIG. 3. An example of encryption using the public key as generated in FIG. 2 is shown.

(23) A plaintext message m is to be sent as an encrypted message using the public key. The message m is converted to components u.sub.q.sup.K, where q is the size of the finite field (GFq) and K is the length of the plaintext in units of the finite field symbol. An example of converting plaintext message as a vector {right arrow over (m)} to u.sub.q.sup.K, assume the plaintext message vector {right arrow over (m)} has 6 binary bits as follows: {right arrow over (m)}=011011 (binary bits). Assume a finite field size q is 4, which means each finite symbol has 2=(log 2(4)) binary bits. A length of the GF4 plaintext K=6/2=3, can map to the plaintext message vector in to u.sub.q.sup.K as follows:
u.sub.q.sup.K=123(GF4 symbol), where 01.fwdarw.1, 10.fwdarw.2, and 11.fwdarw.3.

(24) In another example, a plaintext message m=“The meeting is at 3:00 pm,” is to be sent. The message m has 26 bytes each of 8 bits. The bit total is 26*8=208 binary bits. This results in 208/log(4)=104 GF4 symbols to be encrypted.

(25) In FIG. 3, the plaintext component u.sub.q.sup.K is provided to an input 90 of an encryption device 92. The plaintext component u.sub.q.sup.K is input directly to a combiner 94 and is also input to a number theory transform (NTT) engine 96 which generates a transformed plaintext component ũ.sub.q.sup.K. A first generator component g.sub.1,q.sup.M of the public key is provided to an input 98 of an NTT engine 100 which generates a transformed generator component {tilde over (g)}.sub.1,q.sup.M. The first generator component g.sub.1,q.sup.M is a generator polynomial of length fM. The output of the NTT engine 100 is provided to a multiplier 102, which may be a polynomials multiplier, that also receives the output of the NTT engine 96. The multiplier 102 combines the two signals and provides the result to an Inverse Number Theory Transform (INTT) engine 104, which generates a first codeword component c.sub.1,q.sup.M that is provided to the combiner 94.

(26) A second generator component g.sub.2,q.sup.M is provided to an input 106 of the encryption device 92 for processing by an NTT engine 108 to produce a transformed generator component {tilde over (g)}.sub.2,q.sup.M that is provided to a multiplier 110 for combination with the transformed plaintext component ũ.sub.q.sup.K. Once combined by the multiplier 110, the result is provided to an INTT engine 112 which generates a second codeword component output c.sub.2,q.sup.M. that is provided to the combiner 94. As indicated by the dotted line between the NTT engine 108 and a last NTT engine 116, additional inputs may be provided to a similar arrangement of elements.

(27) Each generator component undergoes a similar process, including the last generator component g.sub.n0−1,q.sup.M at input 114 that is provided to an NTT engine 116 to generate a transformed last generator component {tilde over (g)}.sub.n0−1,q.sup.M that is mixed with the transformed message component ũ.sub.q.sup.K in a multiplier 118, the result of which is inverse transformed in an INTT engine 120 to generate the last codeword component c.sub.n0−1,q.sup.M that is provided to the combiner 94. The combiner 94 combines the codeword components output from the INTT engines, including from any additional INTT engines as indicated by the dotted line, into a codeword c.sub.q.sup.N. The codeword c.sub.q.sup.N is input to a multiplier 122 which mixes the codeword with an error signal e.sub.q.sup.N that is provided at 124 to provide an encrypted cyphertext x.sub.q.sup.N.

(28) An alternate embodiment of an encoder is shown in FIG. 4. The primary difference over the first embodiment is that the plaintext is divided into components prior to processing. In particular, the plaintext component u.sub.q.sup.K is divided into n.sub.0−1 polynomial components, each having length M and labelled as u.sub.M,i.sup.K (0≤i≤n.sub.0−2) and input at 130 and 132, as well as other possible inputs as indicated by the dotted line between the blocks 140 and 142. Similarly, the generator polynomials are divided into n.sub.0−1 polynomial components of length M and labelled as g.sub.q,i.sup.M(0≤i≤n.sub.0−2) and input at 134 and 136, as well as other possible inputs as indicated by the dotted line. Afterwards, the sets of polynomial components are expanded from GFq to GF.sub.Q, with Q satisfying the equation:
Q=2.sup.└log.sup.2.sup.(M)┘

(29) The resulting two sets of GF.sub.Q plaintext and generating polynomial components are then transformed to frequency domain signals ũ.sub.Q,i.sup.M and {tilde over (g)}.sub.Q,i.sup.M, i=0, . . . , n.sub.0−2 respectively using NTT engines 138, 140, 142 and 144. Subsequently, the frequency domain plaintext and generating polynomial components are paired up according to their matching indices and multiplied by multipliers 146 and 148, for example. The output signal of the multiplication is then transformed back to the GF.sub.Q sequence domain using INTT engines 150 and 152 and shrunk back to the original GFq sequence domain to yield n.sub.0−1 codeword parity components c.sub.q,i.sup.M, i=0, . . . , n.sub.0−2. Other similar arrangements for producing codeword parity components may be provided as indicated by the dotted line. A combiner 154 assembles the codeword parity components into codeword parity and merges it with u.sub.q.sup.K as shown at 156 to form QC-MDPC codeword c.sub.q.sup.N as shown at 158. Finally, the ciphertext denoted by x.sub.q.sup.N as shown at 160 is obtained by adding a sparse GFq error vector e.sub.q.sup.N as shown at 162 of weight W to the codeword c.sub.q.sup.N using a multiplier 164. The result is an encrypted message that may be communicated over non-secure communication channels.

(30) 2) FFT-Based Encryption:

(31) In a further embodiment of the apparatus and method is provided a QC-MDPC cryptosystem encryption using FFT (Fast Fourier Transform) and corresponding to n.sub.0=2, which is show in detail in FIG. 5.

(32) In FIG. 5, the plaintext component u.sub.q.sup.K as show at 170 is mapped into a complex signal of length K using a GFq to complex mapper 172. The resulting signal will be transformed to the frequency domain using a convolutional FFT.sup.M module 174 with size M. Since M is a prime number, the calculations of the convolutional FFT module 174 may be performed by an FFT/IFFT arrangement with a larger size N.sub.F than M and a signal a.sup.N.sup.F as shown at 180 that is pre-calculated as shown inside the convolutional FFT module 174. In particular, the output of the GFq to complex mapper 172 is provided to an FFT.sup.N.sub.F module 176, the output of which is provided to a multiplier 182 that receives the signal a.sup.N.sub.F. The mixed signal is provided to an IFFT.sup.N.sub.F (Inverse Fast Fourier Transform) module 178. The values N.sub.F obtained as the product of small prime numbers and the signal a.sup.N.sup.F 180 is a pre-calculated sequence. The output from the convolutional FFT′ 174 is a frequency domain plaintext with size K(K=M).

(33) In further detail, the convolutional FFT.sup.M module 174 of size M is a large prime number which cannot be factored. For example, M could be equal to 4091. If the size of an FFT is a prime number, there is no way to accelerate processing the transform using a butterfly or radix structure. A butterfly structure is a portion of a computation that combines smaller Fourier transforms into a larger Fourier transform. The name butterfly comes from the shape of the data flow diagram in the radix case. The speed of the Fourier transform with a large prime number size M can be enhanced using a FFT with a slightly larger non-prime number of size N.sub.F. The FFT.sup.N.sub.F module 176 with a non-prime number size uses a number that can be factored into small prime numbers. For example, the value N.sub.F may be 4096, which is a little larger than 4091 and that is equal to 2.sup.12. When the FFT has a non-prime size that can be factored into small prime numbers, the butterfly or radix structure can be used to enhance the speed of the FFT. Use of a slightly larger FFT with non-prime size N.sub.F that can be factored into small prime number is referred to as a convolutional FFT. The convolutional FFT may be used to enhance the speed of a Fourier transform with a large prime number M.

(34) In parallel, a similar procedure is provided to transform the generator polynomials g.sub.q.sup.M that are input at 184. In particular, the generator polynomials are processed by a GFq to complex mapper module 186 that inputs the value to a convolutional FFT.sup.M module 188 that includes an FFT.sup.N.sub.F module 190. The output of the module 190 is provided to a multiplier 192 where it is mixed with a signal a.sup.N.sub.F at 194 and provided to an IFFT.sup.N.sub.F module 196. The output of the convolutional FFT.sup.M module 188 is in the form of frequency domain generator polynomials with size M.

(35) The transformation signals at the output of the module 196 is output from the convolutional FFT module 188 to a multiplier 198. The other input to the multiplier 198 is the transformation output of the convolutional FFT module 174. The transformation signals undergo a dot multiplications process using the multiplier 198 to provide a generated signal. Then, the generated signal is inverse transformed from the frequency domain using an IFFT module 200. In particular, the inverse transform module 200 receives the output of the multiplier 198 at an Im scalar 202 which sends its output to an FFT.sup.N.sub.F module 204 that performs a transform on the scaled signal. A multiplier 206 receives the output of the FFT module 204 and mixes it with a signal a.sup.N.sub.F at the multiplier 206, which is inverse transformed in an IFFT.sup.N.sub.F module 208. The inverse transformed signal is input to an Im descalar 210 to generate a signal v.sup.M that is output from the IFFT.sup.M module 200. The output signal v.sup.M of size M is re-mapped back to the GFq sequence domain using a complex to GFq mapper 212. At the output of the mapper 212 is obtained the parity symbol component c.sub.q.sup.M of the codeword. The parity symbol component c.sub.q.sup.M output by the complex to GFq may be provided as a simple stream output by adding an error signal to the component. A combiner may be unnecessary in this embodiment. Alternately, a plurality of similar circuits may be provided to process a plurality of plaintext components. For example, the processing of the components by the circuits may be performed in parallel. The outputs of the circuits may be combined with one another in a combiner 214 prior to an error signal being added to the combined output. In particular, like the embodiments shown in FIGS. 3 and 4, the embodiment of FIG. 5 combines the parity symbol components c.sub.q.sup.M of the illustrated circuit portion with components from similar circuit portions using the combiner 214. The output of the combiner 214 is mixed with an error signal at 216 to obtain the codeword. The combiner 214 combines the output of complex to GFq de-mapper signals with the original plaintext followed with the error adder 216. The combiner 214 and the error signal adder 216 are shown as block elements in FIG. 5 for the sake of simplifying the drawing, but include the features of the corresponding elements of FIGS. 3 and 4.

(36) A message that has been encrypted according to the embodiments shown in FIG. 3, 4 or 5 may be communicated over a non-secure channel communication without the message being understood should it be intercepted.

(37) C. Code-Based GFq QC-MDPC Decryption

(38) An embodiment of an apparatus and method for iterative QC-MDPC decryption is shown in detail in FIG. 6.

(39) An encrypted message has been received, such as via a non-secure communication channel and is to be decrypted so that it may be understood. The received ciphertext c.sub.q.sup.N, which may also be designated as {right arrow over (c)}, is provided to an input 220 and is sent to a syndrome calculator 222, where the initial syndrome s.sub.q.sup.(0), also designated {right arrow over (s)}.sup.(0), is calculated using the parity-check polynomial h.sub.q.sup.N. At the same time, a copy of the ciphertext s.sub.q.sup.(i) or {right arrow over (s)}.sup.(0) is sent to the parity-check symbol voter block 224. In the parity-check symbol voter block 224, scheduling information obtained from a scheduler 226 and a current syndrome s.sub.q.sup.(i) or {right arrow over (s)}.sup.(0) from the syndrome calculator 222 are used together to generate a vote for the current hard estimation for ciphertext ĉ.sub.q.sup.M. The parity-check symbol voter 224 outputs an integer matrix V.sup.q×N, which describes how many checks votes for the qth index for each symbol.

(40) On the other portion of the decryption system, the original ciphertext c.sub.q.sup.N or {right arrow over (e)} is sent to a multiplier 228, which converts each ciphertext symbol to a q by 1 integer vector αV.sub.0.sup.q×N, which has only one non-zero value a in the GFq index, by mixing the ciphertext symbol with a. For example, if the first ciphertext symbol is 2 in GF4, the first column of the converted vector is αV.sub.0.sup.q×1=[0, 0, α, 0].sup.T.

(41) Subsequently, the output V.sup.q×N of the parity-check symbol voter 224 and the output αV.sub.0.sup.q×N of the multiplier 228 are both sent to a symbol flipper 230. The symbol flipper block 230 conducts a hard decision for each ciphertext symbol. Firstly, it adds the outputs V.sup.q×N of the symbol voter 224 and αV.sub.0.sup.q×N of the multiplier 228 together, and finds the index with the largest votes as the estimated ciphertext symbols for the (i)th iteration ĉ.sub.q.sup.N.sup.(i) also indicated as {right arrow over (c)}.sup.(i). If there is more than one index that has equal large votes, it randomly chooses one of the indexes between them.

(42) The estimated ciphertext symbols ĉ.sub.q.sup.N.sup.(i) or ĉ.sup.(i) is provided into two blocks: First, the symbols are provided to a syndrome flipping updater 232 to update the syndrome using only the flipped ciphertext. If the syndrome S.sub.q.sup.(i+1) also designated as {right arrow over (s)}.sup.(i+1) is provided on output 234 of the syndrome updater 232 is all zeros, it means the decoding is successful, and the deciphered plaintext μ.sub.q.sup.K, also designated as {right arrow over (μ)}, is outputted from the syndrome updater 232 on output 244.

(43) If the syndrome S.sub.q.sup.(i+1) or {right arrow over (s)}.sup.(i+1) on the output 234 of the syndrome updater 232 is are not all zeros, the syndrome updater 232 sends a signal ĉ.sub.q.sup.N.sup.(i+1), which is also designated {right arrow over (c)}.sup.(i+1), on output 236 and syndrome S.sub.q.sup.(i+1) or {right arrow over (s)}.sup.(i+1) on output 234 back to the parity check symbol voter 224 for a next iteration.

(44) Second, the output of the symbol flipper 230 is provided to an error floor detector 238, which detects whether the iteration changes any symbol in the last two iterations or not. The detection result is sent back to a weight controller 240. The weight controller 240 keeps the current weight a unchanged if no error floor is detected. Otherwise, the weight controller reduces the weight a as shown at 242.

(45) The decryption steps continue until the plaintext message μ.sub.q.sup.K or {right arrow over (μ)} has been decoded and provided on the output 244. A decryption of the message has been performed.

(46) Methods and apparatus for code-based asymmetric cryptosystem using Quasi-Cyclic Moderate-Density Parity-Check (QC-MDPC) error correcting codes are provided. Specifically, the methods and apparatus generalizes the framework of (QC-MDPC) Code-Based (CB) cryptography from the binary domain (using a Galois Field of two elements) to an arbitrary size of Galois Field and provides an apparatus for implementing the cryptosystem with a simplified computational complexity of key generation, encryption, and decryption components of the cryptosystems and reduced sizes of the public and private security keys.

(47) Thus, there is shown and described an asymmetric-key cryptosystem. The asymmetric-key cryptosystem has three main components:

(48) Key generation: A public key and a private key are generated to be used for encryption and decryption.

(49) Encryption: a message from “Bob” to “Alice” is encrypted using Alice's public key and sent from Bob to Alice through potentially un-secure communication channels.

(50) Decryption: Alice uses her private key to decrypt Bob's message (Only the owner of the private key is able to successfully decrypt the message)

(51) Although other modifications and changes may be suggested by those skilled in the art, it is the intention of the inventors to embody within the patent warranted hereon all changes and modifications as reasonably and properly come within the scope of their contribution to the art.