Method and apparatus for asymmetric cryptosystem based on quasi-cyclic moderate density parity-check codes over GF(q)
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.
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 F and an inverse fast Fourier transformer of size N F , where N F is larger than M, an output of the fast Fourier transformer of size N F being mixed with a predetermined signal prior to being provided to an input of the inverse fast Fourier transformer of size N 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 F and an inverse fast Fourier transformer of size N F , the output of the fast Fourier transformer of size N F being mixed with a predetermined signal prior to being provided to the input of the inverse fast Fourier transformer of size N 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 F ; and
Im descaling an output of the inverse fast Fourier transformer of size N 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 F and an inverse fast Fourier transformer of size N F , where N F is larger than M, the output of the fast Fourier transformer of size N F being mixed with a predetermined signal prior to being provided to the input of the inverse fast Fourier transformer of size N 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 F ; and
Im descaling an output of the inverse fast Fourier transformer of size N F to obtain an output of the inverse fast Fourier transformer of size M.