# US 12,192,333 B2 · Method and device for code-based generation of a key pair for asymmetric cryptography > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,192,333 B2 - Document ID: US12192333B2 - Status: Granted - Kind: B2 - Application number: 17/857,502 - Filed: 2022-07-05 - Published: 2023-02-16 - Granted: 2025-01-07 - Earliest claimed: 2021-07-16 - Assignees: Infineon Technologies AG - Applicants: Infineon Technologies AG - Inventors: Rainer Urian - Web page: https://patentgrep.com/patent/US12192333B2 ## CPC - H04L 9/0825: {using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates} - H04L 9/0861: {Generation of secret information including derivation or calculation of cryptographic keys or passwords} - G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} - G06F 21/602: {Providing cryptographic facilities or services} - H04L 1/0063: {Single parity check} - H04L 9/0869: {involving random numbers or seeds} - H04L 9/3026: {details relating to polynomials generation, e.g. generation of irreducible polynomials} - H04L 9/3033: {details relating to pseudo-prime or prime number generation, e.g. primality test} - H04L 9/304: {based on error correction codes, e.g. McEliece} - H04L 9/3066: {involving algebraic varieties, e.g. elliptic or hyper-elliptic curves} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract 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. ## Claims ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 2) The method of claim 2, wherein the irreducible polynomial is the Goppa polynomial of the linear code. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 1) 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. ### Claim 6 (depends on 1) The method of claim 1, wherein blinding the sub-matrix comprises multiplying the sub-matrix with a blinding matrix. ### Claim 7 (depends on 6) The method of claim 6, wherein the blinding matrix is random or pseudo-random. ### Claim 8 (depends on 6) The method of claim 6, wherein the blinding matrix is invertible. ### Claim 9 (depends on 6) 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. ### Claim 10 (depends on 1) 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. ### Claim 11 (depends on 1) 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. ### Claim 12 (depends on 1) 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. ### Claim 13 (depends on 1) 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. ### Claim 14 (depends on 1) 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. ### Claim 15 (depends on 1) 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. ### Claim 16 (depends on 1) 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. ### Claim 17 (depends on 1) 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. ### Claim 18 (depends on 17) The method of claim 17, comprising generating the blinded inverse matrix by the second data processing element. ### Claim 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. ### Claim 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.