Back to results
US 2020/0028674 A1Published application
METHOD AND APPARATUS FOR ASYMMETRIC CRYPTOSYSTEM BASED ON QUASI-CYCLIC MODERATE DENSITY PARITY-CHECK CODES OVER GF(q)
AssigneeZenith Electronics Corporation
InventorsKyle Xingkai Bao, Nejib Ammar
Life of this patent
Estimating the term…
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.
Claims20
A method of generating keys for encryption, comprising:
- generating a random sparse row vector with elements from a Galois Field (GFq) and with a prescribed vector weight;
- checking the sparse row vector for rightmost polynomials invertibility;
- requesting a new sparse row vector with the same vector weight if the checking determines that the rightmost polynomials are not invertible;
- storing the sparse row vector as a first row of a matrix, wherein the matrix is a private key for use in decrypting an encrypted message;
- 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 a public key for use in encrypting a message to be decrypted by the private key.
5 more elements
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 the message component of the message 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.
7 more elements
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 transform module 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 transform module 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.
8 more elements
A method for decrypting a ciphertext that has been encrypted using a quasi-cyclic moderate density parity check code over a Galois field, comprising:
- calculating a syndrome of the ciphertext using a parity check polynomial to obtain an initial syndrome;
- scheduling a vote on an estimation for a checked ciphertext;
- voting for an estimation of the checked ciphertext when scheduled to obtain an integer matrix;
- multiplying the ciphertext by a weight value to obtain an integer vector;
- deciding on a ciphertext symbol based on the integer matrix and the integer vector to obtain a flipped ciphertext;
- updating the syndrome if needed based on the flipped ciphertext;
- and
- outputting a deciphered plaintext if no updates are needed, otherwise voting on a next iteration of the syndrome of the ciphertext.
5 more elements
An apparatus for generating a private key and a public key, comprising:
- a random sparse vector generator having an output;
- a rightmost polynomials invertibility detector connected to the output of the random sparse vector generator and configured to determine if a lifting matrix of a rightmost polynomial of a vector received from the random sparse vector generator is singular, the rightmost polynomials invertibility detector being operable to request a new vector from the random sparse vector generator if a vector received from the random sparse vector generator is singular;
- a sparse vector compressor connected to receive the output of the rightmost polynomials invertibility detector and configured to output the private key to a private key storage;
- a polynomials splitter having an input connected to the output of the rightmost polynomials invertibility detector and having first and second outputs, the polynomials splitter having a first output and a second output;
- a polynomials inverter connected to the second output of the polynomials splitter and having an inverted output;
- and
- a multiplier connected to the first input of the polynomials splitter and to the inverted output of the polynomials inverter, the multiplier having an output on which the public key is output.
4 more elements
An apparatus for encrypting a message, comprising:
- a first number theory transform module having an input connected to receive a component of the message to be encoded and configured to perform a number theory transform on the component of the message;
- a second number theory transform module having an input connected to receive a first component of a private key and configured to perform a number theory transform on the first component of the private key;
- a first multiplier connected to an output of the first number theory transform module and to an output of the second number theory transform module and configured to mix the transformed message component and the transformed first private key component;
- a first inverse number theory transform module having an input connected to the first multiplier and configured to inverse transform the mixed first transformed components;
- a third number theory transform module having an input connected to receive a second component of the private key and configured to perform a number theory transform on the second component of the provide key;
- a second multiplier connected to the first number theory transform module and to the third number theory transform module and configured to mix the transformed message component and the transformed second private key component;
- a second inverse number theory transform module having an input connected to the second multiplier and configured to inverse transform the mixed second transformed components;
- a combiner connected to the first and second inverse number theory transform modules and configured to combine the first and second inverse transformed components;
- and
- a multiplier connected to an output of the combiner and configured to mix an error signal with the combiner output to provide an encrypted signal.
7 more elements
An apparatus for encrypting a message, comprising:
- a first Galois field to complex mapper having an input configured to receive a plaintext component of the message and configured to map the plaintext component into a complex message signal;
- a first fast Fourier transform module connected to receive the output of the first Galois field to complex mapper and configured to transform the complex message signal into frequency domain;
- a second Galois field to complex mapper having an input configured to receive a generator polynomial of a private key and configured to map the generator polynomial into a complex key signal;
- a second fast Fourier transform module connected to receive the output of the second Galois field to complex mapper and configured to transform the complex key signal into frequency domain;
- a first multiplier connected to outputs of the first and second fast Fourier transform modules and configured to mix the frequency domain signals from the first and second fast Fourier transform modules;
- an inverse fast Fourier transform module connected to receive the mixed signals from the first multiplier and configured to inverse transform the mixed signals;
- a complex to Galois field mapper connected to map the inverse transformed mixed signals into a Galois field domain to obtain a parity symbol component of an encrypted code word;
- and
- an adder connected to an output of the complex to Galois field mapper and configured to mix an error signal into parity symbol of the encrypted code word.
6 more elements
An apparatus for decoding an encrypted ciphertext, comprising:
- a syndrome calculator configured to receive the encrypted ciphertext;
- a parity check symbol voter connected to receive an output of the syndrome calculator;
- a symbol flipper connected to an output of the parity check symbol voter;
- a syndrome updater connected to an output of the symbol flipper to output a deciphered plaintext if no changes are made in the symbol in a predetermined number of iterations, otherwise if changes are made in the symbol then to implement another iteration;
- and
- an error floor detector connected to an output of the symbol flipper to detect changes in a symbol in a predetermined number of iterations and to change a weight value if changes are made in the predetermined number of iterations.
3 more elements
Dependencies are inferred from the claim text.