Method and device for code-based generation of a key pair for asymmetric cryptography
According to various embodiments, a method for code-based generation of a key pair for asymmetric cryptography is described including generating a private key defining a linear code, determining a parity check or generator matrix for the linear code, blinding a sub-matrix of the parity check or generator matrix, generating a blinded inverse matrix by inverting the blinded sub-matrix or by inverting a quadratic matrix contained in the blinded sub-matrix, de-blinding the blinded inverse matrix to generate an inverse matrix and generating a public key for the private key using the inverse matrix.
1. A method for code-based generation of a key pair for asymmetric cryptography comprising:
generating a private key defining a linear code;
determining a parity check or generator matrix for the linear code;
blinding a sub-matrix of the parity check or generator matrix;
generating a blinded inverse matrix by inverting the blinded sub-matrix or by inverting a quadratic matrix contained in the blinded sub-matrix;
de-blinding the blinded inverse matrix to generate an inverse matrix; and
generating a public key for the private key using the inverse matrix,
wherein the blinded inverse matrix is generated by determining an invertible quadratic matrix contained in the blinded sub-matrix of the parity check or generator matrix and inverting the invertible quadratic matrix, and wherein the inverse matrix is the inverse of the de-blinded invertible quadratic matrix.
2. The method of claim 1 , wherein generating the private key comprises selecting random elements of a finite field and an irreducible polynomial with coefficients in the finite field.
3. The method of claim 2 , wherein the irreducible polynomial is the Goppa polynomial of the linear code.
4. The method of claim 1 , wherein the public key is generated by multiplying the inverse matrix with a part of the parity check or generator matrix which remains when removing a part to which the inverse matrix is the inverse.
5. The method of claim 1 , wherein the parity check or generator matrix is a binary matrix, and wherein the sub-matrix of the parity check or generator matrix has a same number of rows as the parity check or generator matrix and at least as many columns as rows in case the parity check matrix has more columns than rows, and wherein the sub-matrix of the parity check or generator matrix has a same number of columns as the parity check or generator matrix and at least as many rows as columns in case the parity check matrix has more rows than columns.
6. The method of claim 1 , wherein blinding the sub-matrix comprises multiplying the sub-matrix with a blinding matrix.
7. The method of claim 6 , wherein the blinding matrix is random or pseudo-random.
8. The method of claim 6 , wherein the blinding matrix is invertible.
9. The method of claim 6 ,
wherein the multiplication is a multiplication of the blinding matrix from the left and the blinding matrix has as many columns as the parity check or generator matrix has rows and as at least as many rows as the parity check or generator matrix has rows, or
wherein the multiplication is a multiplication of the blinding matrix from the right and the blinding matrix has as many rows as the parity check or generator matrix has columns and as at least as many columns as the parity check or generator matrix has columns.
10. The method of claim 1 , comprising blinding the sub-matrix of the parity check or generator matrix such that the blinded sub-matrix of the parity check or generator matrix is quadratic, wherein the blinded inverse matrix is generated by inverting the sub-matrix of the parity check or generator matrix and the inverse matrix is the inverse of the sub-matrix.
11. The method of claim 1 , wherein blinding the sub-matrix comprises multiplying the sub-matrix with a blinding matrix, and wherein the blinding matrix has as many columns as the parity check or generator matrix has rows and as many rows as the parity check or generator matrix has rows.
12. The method of claim 1 , comprising blinding the sub-matrix of the parity check or generator matrix such that the blinded sub-matrix of the parity check or generator matrix has more columns, more rows or more columns and more rows than a difference between code length and code dimension.
13. The method of claim 1 ,
wherein blinding the sub-matrix comprises multiplying the sub-matrix with a blinding matrix from the left, and the blinding matrix has as many columns as the parity check or generator matrix has rows and has more rows than the parity check or generator matrix has rows, or
wherein blinding the sub-matrix comprises multiplying the sub-matrix with a blinding matrix from the right, and the blinding matrix has as many rows as the parity check or generator matrix has columns and has more columns than the parity check or generator matrix has columns.
14. The method of claim 1 , wherein blinding the sub-matrix comprises multiplying the sub-matrix with a blinding matrix from the left and the invertible quadratic matrix has as many rows and columns as the parity check or generator matrix has rows or wherein blinding the sub-matrix comprises multiplying the sub-matrix with a blinding matrix from the right and the invertible quadratic matrix has as many rows and columns as the parity check or generator matrix has columns.
15. The method of claim 1 , wherein the parity check or generator matrix is a binary matrix, and wherein the sub-matrix of the parity check or generator matrix has more columns as rows or has more rows as columns.
16. The method of claim 1 , comprising generating the private key, the parity check or generator matrix and the public key according to systematic Niederreiter or McEliece cryptosystem.
17. The method of claim 1 , comprising:
generating the private key by a first data processing element;
blinding the sub-matrix of the parity check or generator matrix by the first data processing element;
transmitting the blinded sub-matrix of the parity check or generator matrix from the first data processing element to a second data processing element;
receiving the blinded inverse matrix from the second data processing element at the first data processing element; and
generating the public key by the first data processing element.
18. The method of claim 17 , comprising generating the blinded inverse matrix by the second data processing element.
19. A key generation device for code-based generation of a key pair for asymmetric cryptography comprising one or more hardware processors, wherein the one or more hardware processors are configured to:
generate a private key defining a linear code;
determine a parity check or generator matrix for the linear code;
blind a sub-matrix of the parity check or generator matrix;
generate a blinded inverse matrix by inverting the blinded sub-matrix or by inverting a quadratic contained in the blinded sub-matrix;
de-blind the blinded inverse matrix to generate an inverse matrix; and
generate a public key for the private key using the inverse matrix,
wherein the blinded inverse matrix is generated by determining an invertible quadratic matrix contained in the blinded sub-matrix of the parity check or generator matrix and inverting the invertible quadratic matrix, and wherein the inverse matrix is the inverse of the de-blinded invertible quadratic matrix.
20. A method for code-based generation of a key pair for asymmetric cryptography performed by a key generation device having a hardware security module and a hardware processor, the method comprising:
generating a private key defining a linear code through the hardware security module;
determining a parity check or generator matrix for the linear code by the hardware security module;
blinding a sub-matrix of the parity check or generator matrix by the hardware security module;
generating a blinded inverse matrix by inverting the blinded sub-matrix or by inverting a quadratic matrix contained in the blinded sub-matrix by the hardware processor;
de-blinding the blinded inverse matrix to generate an inverse matrix by the hardware security module; and
generating a public key for the private key using the inverse matrix by the hardware security module,
wherein the blinded inverse matrix is generated by determining an invertible quadratic matrix contained in the blinded sub-matrix of the parity check or generator matrix and inverting the invertible quadratic matrix, and wherein the inverse matrix is the inverse of the de-blinded invertible quadratic matrix.