US 2017/0104590 A1 · Method and Apparatus for Error Correcting Code Based Public Key Encryption Schemes

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 ciphertext 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 ciphertext 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 Gs=[g0, . . . , gn] over GF(q) as the private key, where k, r, n and q are positive integers and where g0, . . . , gn−1 are length k column vectors; selecting k×r random matrices C0, . . . , Cn−1; selecting a k×k non-singular matrix S; selecting an n(r+1)×n(r+1) matrix A; selecting an n(r+1)×n(r+1) permutation matrix P; and setting the public key as G=S[g0, C0, . . . , gn−1, Cn−1]AP. receiving a public key G, which is a k×n(r+1) 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.

Claims11

Dependent claims

A method for generating a public key G and for generating a private key K from an error correcting code generator matrix Gs, the method comprising:

a) obtaining said k×n generator matrix Gs for an [n, k, d] linear code over a finite field GF(q), wherein n, k, d, q are positive integers;
b) obtaining a k×n(r+1) matrix G1 by inserting rn random columns into said matrix Gs, wherein r is a positive integer;
c) selecting a random k×k non-singular matrix S;
d) selecting a random n(r+1)×n(r+1) non-singular matrix A;
e) selecting a random n(r+1)×n(r+1) permutation matrix P;
f) computing said public key G=SG1AP;
and
g) obtaining said private key K=(S, Gs, A, P).

5 more elements

A method for transmitting a message vector m between a sender and a receiver securely, the method comprising:

a) at the receiver:
obtaining a k×n generator matrix Gs for an [n, k, d] linear code over a finite field GF(q), wherein n, k, d, q, t are positive integers, and wherein a linear code generated by said generator matrix Gs corrects at least t errors;
calculating a k×n(r+1) public key matrix G using said Gs;
sending said public key matrix G to said sender;
and obtaining a private key K from said Gs;
b) at the sender:
obtaining said integer n;
obtaining said integer k, obtaining said integer d;
obtaining said finite field GF(q);
obtaining said message encryption public key G from said receiver;
obtaining said message vector m having elements in GF(q);
generating an error vector e where e has elements in GF(q), and where e has a predetermined weight t;
computing a ciphertext vector y=mG+e;
and sending said ciphertext vector y to the receiver;
c) at the receiver:
obtaining said ciphertext vector y from the sender;
computing an inverse P−1 of said permutation matrix P;
computing an inverse A−1 of said non-singular matrix A;
computing an inverse S−1 of said non-singular matrix S;
computing a vector yP−1 A−1 having a length n(r+1);
selecting a sub-vector y′ of said vector yP−1 A−1, where y′ has a length n;
using said private generator matrix Gs to decode said sub-vector y′ into a vector m′, where m′ has a length k;
computing said plaintext message m=m'S−1;
and checking a validity of said message m.

21 more elements

Dependencies are inferred from the claim text.

Method and Apparatus for Error Correcting Code Based Public Key Encryption Schemes

Life of this patent

Method and Apparatus for Error Correcting Code Based Public Key Encryption Schemes

Life of this patent

Abstract

Claims11