A Cryptographic System and Method

Abstract

A system and method for encryption of data. The system and method utilizes a cryptographic function that provides asymmetric encryption/decryption and digital signing capabilities that are hardened against cyber attack from quantum computers.

Claims

1. A cryptographic system, comprising: an input device configured to receive data to be encrypted, decrypted, signed, and verified; and a processor configured to receive the data to be encrypted, decrypted, signed, and verified and to encrypt, decrypted, signed, and verified the data using instructions from a cryptographic engine; wherein the instructions, when executed, cause encryption, decrypted, signed, and verified of the data using a code-based encryption scheme based on binary irreducible Goppa code in which a support set consists of rational functions with a degree of a denominator not greater than a degree of a Goppa polynomial and wherein the encrypted data is protected against an attack from a quantum computer.

2. The cryptographic system of claim 1, wherein the instructions when executed also use the Goppa code in a weighted Hamming metric.

3. The cryptographic system of claim 1, wherein the Goppa polynomial has the degree not less than r, where r is a maximum degree of a denominator of a rational function over F.sub.2.sub.m[x] in the set of L, where L is a set of rational functions of degree not greater than r where r is greater than to 1, and with coefficients from a finite field GF(2.sup.m).

4. The cryptographic system of claim 3, wherein the instructions when executed also uses the Goppa code in a weighted Hamming metric.

5. The cryptographic system of claim 4, wherein the code based encryption scheme is a generalized (L, G) code in which a set of proper rational functions (L) over (F.sub.2.sub.m[x]) are chosen, wherein the denominators of L are various irreducible polynomials from F.sub.2.sub.m[x] with degree less than or equal to r where r is greater than 1, and where the numerators are formal derivatives of the denominators.

6. The cryptographic system of claim 5, wherein the instructions when executed further generate a private key satisfying the relationship K={S, P, L, G(x)} wherein: a parity check matrix H is generated for binary generalized Goppa code with Goppa polynomial G(x) of degree equal to t, where G(x) is an irreducible polynomial with coefficients from a Galois field GF(2.sup.m) locator polynomials for support set L of binary generalized (L, G) code are generated as irreducible polynomials with coefficients from the field GF(2.sup.m) having a degree not greater than r; a vector length set N={n.sub.1, n.sub.2, . . . , n.sub.r} of Goppa code is generated, where n.sub.i=I.sub.2.sub.m(i), i=1, . . . , r, and n=Σ.sub.i=1.sup.r n.sub.i, where I.sub.2.sub.m(i) is a number of irreducible polynomials of degree i with coefficients from the field GF(2.sup.m); a vector position weight set W={w.sub.1, w.sub.2, . . . , w.sub.r} is generated, where the first n.sub.1 positions have weight w.sub.1=1, the second n.sub.2 positions have weight w.sub.2=2, and the last n.sub.r positions have weight w.sub.r=r; a random mt×mt non-singular matrix S is selected, where deg G(x)=t; a random n×n permutation matrix P is selected; and a public key H*=S×H×P is computed.

7. A cryptographic system, comprising: an input device configured to receive data to be encrypted, decrypted, signed, and verified; and a processor configured to receive the data to be encrypted, decrypted, signed, and verified and to encrypt, decrypted, signed, and verified the data using instructions from a cryptographic engine; wherein the instructions, when executed, cause encryption, decrypted, signed, and verified of the data using a code-based encryption scheme based on binary irreducible Goppa code in which locator polynomials for support set L have degree not greater than r, where r is the maximum degree of the denominator of a rational function over F.sub.2.sub.m[x] and wherein the encrypted, decrypted, signed, and verified data is protected against attack from a quantum computer.

8. The cryptographic system of claim 7, wherein the instructions when executed also uses the Goppa code in a weighted Hamming metric.

9. A method of encrypting, decrypted, signed, and verified data, comprising the steps of: receiving data at an input device; and forwarding the data to a processor for encrypting, decrypted, signed, and verified the data using instructions provided by a cryptographic engine; wherein the instructions, when executed, encrypt, decrypted, signed, and verified the data using a code-based encryption scheme based on binary irreducible Goppa code in which a support set consists of rational functions with a degree of a denominator not greater than the degree of Goppa polynomial and wherein the encrypted, decrypted, signed, and verified data is protected against attack from a quantum computer.

10. The method of claim 9, wherein the instructions when executed also use the Goppa codes in a weighted Hamming metric.

11. The method of claim 9, wherein the polynomials have degree not greater than r, where r is the maximum degree of the denominator of a rational function over F.sub.2.sub.m[x] in the set of L, where L is a set of rational functions of degree not greater than r where r is greater than 1, and with coefficients from a finite field GF(2.sup.m).

12. The method of claim 11, wherein the instructions when executed also use the Goppa codes in a weighted Hamming metric.

13. The method of claim 12, wherein the code based encryption scheme is a generalized (L, G) code in which a set of proper rational functions (L) over (F.sub.2.sub.m[x]) are chosen, wherein the denominators of L are various irreducible polynomials from F.sub.2.sub.m[x] with degree less than or equal to r where r is greater than 1, and where the numerators are formal derivatives of the denominators.

14. The method of claim 13, wherein the instructions when executed further generate a private key satisfying the relationship K={S, P, L, G(x)} wherein: a parity check matrix H is generated for binary generalized Goppa code with Goppa polynomial G(x) of degree equal to t, where G(x) is an irreducible polynomial with coefficients from a Galois field GF(2.sup.m); locator polynomials for support set L of binary generalized (L, G) code are generated as irreducible polynomials with coefficients from the field GF(2.sup.m) having a degree not greater than r; a vector length set N={n.sub.1, n.sub.2, . . . , n.sub.r} of Goppa code is generated, where n.sub.i=I.sub.2.sub.m(i), i=1, . . . , r, and n=Σ.sub.i=1.sup.r n.sub.i, where I.sub.2.sub.m(i) is a number of irreducible polynomials of degree i with coefficients from the field GF(2.sup.m); a vector position weight set W={w.sub.1, w.sub.2, . . . , w.sub.r} is generated, where the first n.sub.1 positions have weight w.sub.1=1, the second n.sub.2 positions have weight w.sub.2=2, and the last n.sub.r positions have weight w.sub.r=r; a random mt×mt non-singular matrix S is selected, where deg G(x)=t; a random n×n permutation matrix P is selected; and a public key H*=S×H×P is computed.

15. A method of encrypting data, comprising the steps of: receiving data to be encrypted at an input device; and providing the data to be encrypted to a processor for encrypting that data using instructions from a cryptographic engine; wherein the instructions, when executed, cause encryption of the data using a code-based encryption scheme based on binary irreducible Goppa code in which locator polynomials for support set L have degree not greater than r, where r is the maximum degree of the denominator of a rational function over F.sub.2.sub.m[x] and wherein the encrypted data is protected against attack from a quantum computer.

16. The method of claim 15, wherein the instructions when executed also use the Goppa codes in a weighted Hamming metric.

17. The method of claim 9 wherein the data to be encrypted is a message vector to be securely transmitted from a sender to a receiver.

18. The method of claim 15 wherein the data to be encrypted is a message vector to be securely transmitted from a sender to a receiver.

19. The method of claim 9 wherein the data when encrypted is a digital signature.

20. The method of claim 15 wherein the data when encrypted is a digital signature.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0042] FIG. 1 is a block diagram of a system for carrying out a cryptographic method in accordance with one embodiment of the present invention whereby the system is used for encryption, decryption, generating digital signatures, verifying digital signatures, etc.

[0043] FIG. 2 is a block diagram of a system for carrying out a cryptographic method in accordance with an additional embodiment of the present invention whereby the system provides further security through use of a trusted platform module (TPM) or a universal serial bus (USB) interface.

[0044] FIG. 3 is a block diagram of a system for carrying out a cryptographic method in accordance with another embodiment of the invention whereby the system generates a public key and a private key based on a set of input parameters.

[0045] FIG. 4 is a block diagram of a system for carrying out a cryptographic method in accordance with another embodiment of the invention whereby a Post-Quantum Blockchain (PQBC) is created so that data security of the PQBC is strengthened against cyber attacks from quantum computers and classical computers.

[0046] FIG. 5 is a flowchart illustrating a process of generating a private key and a corresponding public key in a public key cryptographic device in accordance with an embodiment of the present invention.

[0047] FIG. 6 is a flowchart illustrating the process of encrypting data using a public key in the public key cryptographic device in accordance with an embodiment of the present invention.

[0048] FIG. 7 is a flowchart illustrating the process of decrypting an encrypted data using a corresponding private key in a public key cryptographic device in accordance with an embodiment of the present invention.

[0049] FIG. 8 is a flowchart illustrating the process of digital signing data using a private key in a public key cryptographic device in accordance with an embodiment of the present invention.

[0050] FIG. 9 is a flowchart illustrating the process of verifying a digital signature using a corresponding public key in a public key cryptographic device in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION

[0051] The invention will now be described with reference to the drawing figures in which like reference numerals refer to like parts throughout. In FIG. 1, a public key cryptographic device 100 in accordance with an exemplary embodiment of the invention is depicted. The cryptographic device 100 to receives an encryption key from memory 102, which can be a public key or private key. The cryptographic device also receives from an input device 104, data that is to be encrypted. The data can include, but is not limited to, a message vector to be securely transmitted from a sender to a receiver, or data from a network interface, a data storage device such as a hard drive, a key board, and the like. As described below, the data to be encrypted can also be the hash value of data to be digitally signed.

[0052] The encryption key and encrypted data may be received from inside a computing device, such as a personal computer, from one or more devices within a network or from third party devices outside the network. As described in more detail below, it will be readily understood that the public key cryptographic device can be any device capable of performing the processes described herein whether integrated into a single semiconductor package or distributed amongst several semiconductor devices contained within a single computer or server or distributed over multiple devices within one or more networks.

[0053] The cryptographic device 100 includes an input/output device 106, which can, for example, be a network communication interface, for receiving the plain data from the input device 104 and receiving the encryption key. The plain data and encryption key are then forwarded to an Input/Output Bridge 108 and a Memory Bridge 110 for storage in system memory 112. In exemplary embodiments the System Memory 112 may contain operating instructions such as, but not limited to, the Operating System 114. In addition to the operating system as well as other operating instructions 114 that are stored in system memory 112, the system memory includes the processing instructions of a cryptographic engine 116. The cryptographic engine 116 provides the operational instructions for the cryptographic functions such as encryption, decryption, digital signature, verification of digital signature, etc.

[0054] The cryptographic processing of the encrypted data is performed in the CPU 118 that is linked to system memory 112 via a Memory Bus. The CPU 118 can be implemented as a parallel co-processor, a field programmable gate array (FPGA), microprocessor, or the like, as is well understood.

[0055] Where all components of the system are contained within a single device, as depicted in FIG. 1, the cryptographic device 100 can be implemented as a single purpose computing device, e.g., a special device performing one or more special cryptography function like a secure key device, a credit card chip, passport chip, etc.) Alternatively, the components and functioning depicted in FIG. 1 can be can be distributed within a multiple purpose computing device, e.g., a general computer or server, or distributed over multiple devices within a network. For example, the functioning can be implemented on a cluster of server computers in a manner that is well-known.

[0056] The embodiment of FIG. 1 can be implemented on a computer network such as the Internet that is strengthened against cyber attack from both classical computers and quantum computers and has a manageable key size and improved computational efficiency using a variant of the McEliece and Niederreiter schemes. In the classical McEliece and Niederreiter algorithms, the scheme parameters are determined by two key elements m and t and the error correcting code is considered in the classical, i.e., un-weighted, Hamming metric. In one embodiment of the scheme of the present application there is significant flexibility in choosing the parameter of the code length n based on a third key parameter r and the use of Goppa codes in a weighted Hamming metric. In this embodiment, a special type of locator set, L*, is used that is a set of rational functions of degree not greater than r where r is greater than 1, and with coefficients from a finite field GF(2.sup.m). This is contrasted with the classical scheme, in which the elements of the field GF(2.sup.m) are used as the locator set. This change in the locator set significantly increases the length of the code, while the calculations remain in the field GF(2.sup.m).

[0057] In this embodiment, a special representation of the parity check matrix H, and the generator matrix G of the code, a special selection of the error vector, and/or a special selection of the codeword presentation by the additional field(s) inclusion are utilized. In an embodiment a parity check matrix H is generated for an n, k, d binary generalized (L, G) code wherein n, k, and d, are positive integers, n is a code length, k is a number of information symbols and d is a minimal distance n≤Σ.sub.i=1.sup.r I.sub.2.sub.m(i),k≥n−tm. Where I.sub.2.sub.m(i) is a number of irreducible polynomials of degree i with coefficients from GF(2.sup.m). It is also possible to present transformation A×H×P=H* (or S×G×P=G*) as a special permutation of the support set L. Therefore, matrix G* or H* can be obtained directly, without matrix S or A and P, from L* and G(x), where L* is a special secret permutation of support set L. In such case we can interpret L* as a second part of a secret key. This embodiment of the invention can be applied to make changes in the main components of, including, but not limited to, the encryption and signature schemes.

[0058] In this embodiment, by using the L* support set directly instead of L with matrix S and P, we can obtain the following variant of McEliece scheme:

[0059] Private key: (Decoding algorithm, L*, G(x))

[0060] Public key: G*

[0061] Encryption: Let m be a k-bit message, and let e be a random n-bit vector with Hamming weight W.sub.H(e)≤t. Then c=m×G*⊕e is a ciphertext.

[0062] Decryption: Obtaining m by using decoding algorithm (error correcting) with knowledge L* and G.

[0063] In the Niederreiter scheme, by using the two matrices and parity check matrix H, obtained from L and G(x), a public key matrix H*=A×H×P is calculated. As with the McEliece scheme, by using the L* support set directly instead of L with matrix A and P, we can obtain the following variant of Niederreiter scheme:

Private key: (Decoding algorithm, L*, G(x))

[0064] Public key: H*

[0065] Encryption: Let m be a message, with Hamming weight W.sub.H(e)≤t. Then c=m×H*.sup.T is a ciphertext.

[0066] Decryption: Obtaining m by using decoding algorithm (error correcting) with knowledge L* and G(x).

[0067] This implementation allows for: 1) the expansion of the selection of a support set, thereby expanding the available private keys; 2) use of rational functions of degree greater than one to keep the calculation in a finite field with a comparable code length. For example, for rational functions of degree 2 with coefficients from the field GF(2.sup.m), the code length is n=2.sup.2m-1+2.sup.m-1. The practical benefits of using rational functions with different degree are: 1) reducing the amount of CPU cycles needed in the encryption, decryption, and key generation processes; and 2) increasing the security for codes with the same parameters (n, k, d), as in classical Goppa codes.

[0068] The generalized (L, G) code of an embodiment of the present invention is characterized by a set L where the proper rational functions of F.sub.2.sub.m[x] are chosen whose denominators are various irreducible polynomials from F.sub.2.sub.m[x] with degree less than or equal r (r>1), and whose numerators are formal derivatives of the denominators.

[0069] In an embodiment of the invention, a special support set L is used as a second part of the private secret key in the McEliece and Niederreiter method. In this embodiment, we have the following additional definitions:

[0070] Definition #5: Support set L is defined as follows:

[00002]$L=\left\{\frac{f_1^{\prime }\left(x\right)}{f_1\left(x\right)},\frac{f_2^{\prime }\left(x\right)}{f_2\left(x\right)},\mathrm{.Math.},\frac{f_n^{\prime }\left(x\right)}{f_n\left(x\right)}\right\},$

where f′.sub.i(x) is a formal derivative of f.sub.i(x) in GF(2.sup.m) and f.sub.i(x)=x.sup.l.sup.i+c.sub.l.sub.i.sub.−1,ix.sup.l.sup.i-1+ . . . c.sub.1,ix+c.sub.0,i, c.sub.j,i∈GF(2.sup.m), gcd(f.sub.i(x), f.sub.j(x))=1, gcd(f.sub.i(x), G(x))=1, ∀i, j, i≠j, deg G(x)=t.

[0071] Definition #6: Binary vector a=(a.sub.1, a.sub.2, . . . , a.sub.n) is a codeword of generalized (L, G) code if and only if the following equality is satisfied: Σ.sub.i=1.sup.n

[00003]$a_i\frac{f_i^{\prime }\left(x\right)}{f_i\left(x\right)}=0\mathrm{mod}G\left(x\right)$ [0072] For such codes the design bound for the minimum distance:

[00004]$d_G\ge \frac{2t+1}{l},l$

=max l.sub.i and the decoding algorithm corresponding to it is determined. To construct a parity check matrix for such generalized (L, G) code the following presentation for rational functions

[00005]$\frac{f_i^{\prime }\left(x\right)}{f_i\left(x\right)}$

by modulo G(x) is used:

[00006]$\frac{f_i^{\prime }\left(x\right)}{f_i\left(x\right)}=s_i\left(x\right)=b_{i,t-1}{x}^{t-1}+b_{i,t-2}{x}^{t-2}+\mathrm{.Math.}.+b_{i,1}{x}^1+b_{i,0}\mathrm{mod}G\left(x\right),b_{i,j}\in \mathrm{GF}\left(2^m\right)$

[0073] The equation for the generalized Goppa code can then be rewritten as:

[00007]$\begin{array}{cc}\underset{i=1}{\overset{n}{.Math.}}{a}_i\frac{f_i^{\prime }\left(x\right)}{f_i\left(x\right)}=& \underset{i=1}{\overset{n}{.Math.}}{a}_i{s}_i\left(x\right)\\ =& \underset{i=1}{\overset{n}{.Math.}}{a}_i{b}_{i,t-1}{x}^{t-1}+\underset{i=1}{\overset{n}{.Math.}}{a}_i{b}_{i,t-2}{x}^{t-2}+\mathrm{.Math.}.+\\ & \underset{i=1}{\overset{n}{.Math.}}{a}_i{b}_{i,1}{x}^1+\underset{i=1}{\overset{n}{.Math.}}{a}_i{b}_{i,0}\\ =& 0\mathrm{mod}G\left(X\right),\end{array}$

[0074] From this equation a parity check matrix His obtained:

[00008]$H=\left[\begin{array}{cccc}{b}_{1,t-1}& b_{2,t-1}& \mathrm{.Math.}& b_{n,t-1}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ b_{1,0}& b_{2,0}& \mathrm{.Math.}& b_{n,0}\end{array}\right]$

[0075] From this parity check matrix we can obtain a generator matrix G for the generalized (L, G) code and by using matrix S and P to calculate the public key matrix G*=S×G×P.

[0076] In another embodiment we can also use the fractions

[00009]$\frac{f_i^{\prime }\left(x\right)}{f_i\left(x\right)}$

with different degrees of f.sub.i(x) for support set L. By using irreducible polynomials f(x) with degree not greater than r for support set we can obtain a generalized Goppa code with codeword length n≤Σ.sub.i=1.sup.r I.sub.2.sub.m(i), where I.sub.2.sub.m(i) is a number of irreducible polynomials of degree i with coefficients from GF(2.sup.m).

[0077] The following two examples are provided for illustration purposes:

[0078] Example 1: In this example m=6 and r=2. Since

[00010]$I_{2^6}\left(1\right)=64,I_{2^6}\left(2\right)=\frac{2^{12}-2^6}{2}$

we obtain n=2048+32=2080. Let d=61, t=30 then we have k≥2080−60.Math.6=1720.

[0079] Example 2: For l=2 and f.sub.i(x)=(x−β.sub.i)(x−β.sub.i.sup.2m), β.sub.i∈GF (2.sup.2m)\GF (2.sup.m), G(x) which is an irreducible polynomial from the polynomial ring F.sub.2.sub.m[x]. The parity check matrix for this example is:

[00011]$\frac{1}{x-\beta }=\frac{G\left(x\right)-G\left(\beta \right)}{x-\beta }{G\left(\beta \right)}^{-1}\mathrm{mod}G\left(x\right)$$\mathrm{and}$$\frac{\beta +{\beta }^{2^m}}{\left(x-\beta \right)\left(x-{\beta }^{2^m}\right)}=G\left(x\right)\frac{-G\left(\beta \right)}{x-\beta }{G\left(\beta \right)}^{-1}+\frac{G\left(x\right)-G\left({\beta }^{2^m}\right)}{x-{\beta }^{2^m}}{G\left({\beta }^{2^m}\right)}^{-1}\mathrm{mod}G\left(x\right)$$\frac{G\left(x\right)-G\left(\beta \right)}{x-\beta }=g_t\left(x^{t-1}+x^{t-2}\beta +\mathrm{.Math.}+{\beta }^{t-1}\right)+g_{t-1}\left(x^{t-2}+x^{t-3}\beta +\mathrm{.Math.}+{\beta }^{t-2}\right)+\mathrm{.Math.}{g}_2\left(x+\beta \right)+g_1,\mathrm{where}G\left(x\right)=\underset{i=0}{\overset{t}{.Math.}}{g}_i{x}^i,g_i\in \mathrm{GF}\left(2^m\right),g_t\ne 0,g_0\ne 0$$\mathrm{and}$$\frac{G\left(x\right)-G\left({\beta }^{2^m}\right)}{x-{\beta }^{2^m}}=g_t\left(x^{t-1}+x^{t-2}{\beta }^{2^m}+\mathrm{.Math.}+{\beta }^{2^m\left(t-1\right)}\right)+g_{t-1}\left(x^{t-2}+x^{t-3}{\beta }^{2^m}+\mathrm{.Math.}+{\beta }^{2^m\left(t-2\right)}\right)+\mathrm{.Math.}{g}_2\left(x+{\beta }^{2^m}\right)+g_1,$

The coefficients at x.sup.t-1, x.sup.t-2, . . . , x, 1 in the sum

[00012]$\frac{G\left(x\right)-G\left(\beta \right)}{x-\beta }{G\left(\beta \right)}^{-1}+\frac{G\left(x\right)-G\left({\beta }^{2^m}\right)}{x-{\beta }^{2^m}}{G\left({\beta }^{2^m}\right)}^{-1}$$x^{t-1}\text{:}\left({G\left(\beta \right)}^{-1}+{G\left({\beta }^{2^m}\right)}^{-1}\right),g_t,x^{t-2}\text{:}\left({G\left(\beta \right)}^{-1}+{G\left({\beta }^{2^m}\right)}^{-1}\right)g_{t-1}+\left(\beta {G\left(\beta \right)}^{-1}+{\beta }^{2^m}{G\left({\beta }^{2^m}\right)}^{-1}\right)g_t.x^{t-3}\text{:}\left({G\left(\beta \right)}^{-1}+{G\left({\beta }^{2^m}\right)}^{-1}\right)g_{t-2}+\left(\beta {G\left(\beta \right)}^{-1}+{\beta }^{2^m}{G\left({\beta }^{2^m}\right)}^{-1}\right)g_{t-1}+\left({\beta }^2{G\left(\beta \right)}^{-1}+{\beta }^{2.Math.2^m}{G\left({\beta }^{2^m}\right)}^{-1}\right)g_t,x^0\text{:}\left({G\left(\beta \right)}^{-1}+{G\left({\beta }^{2^m}\right)}^{-1}\right)g_1+\left(\beta {G\left(\beta \right)}^{-1}+{\beta }^{2^m}{G\left({\beta }^{2^m}\right)}^{-1}\right)g_2+\mathrm{.Math.}+\left({\beta }^{t-1}{G\left(\beta \right)}^{-1}+{\beta }^{\left(t-1\right).Math.2^m}{G\left({\beta }^{2^m}\right)}^{-1}\right)g_t.$

[0080] A parity check matrix H is defined by:

[00013]$H=\left[\begin{array}{ccc}{G\left({\beta }_1\right)}^{-1}+{G\left({\beta }_1^{2^m}\right)}^{-1}& {G\left({\beta }_2\right)}^{-1}+{G\left({\beta }_2^{2^m}\right)}^{-1}& {G\left({\beta }_n\right)}^{-1}+{G\left({\beta }_n^{2^m}\right)}^{-1}\\ {\beta }_1{G\left({\beta }_1\right)}^{-1}+{\beta }_1^{2^m}{G\left({\beta }_1^{2^m}\right)}^{-1}& {\beta }_2{G\left({\beta }_2\right)}^{-1}+{\beta }_2^{2^m}{G\left({\beta }_2^{2^m}\right)}^{-1}& {\beta }_n{G\left({\beta }_n\right)}^{-1}+{\beta }_n^{2^m}{G\left({\beta }_n^{2^m}\right)}^{-1}\\ & \mathrm{.Math.}& \\ {\beta }_1^{t-1}{G\left({\beta }_1\right)}^{-1}+{\beta }_1^{\left(t-1\right)2^m}{G\left({\beta }_1^{2^m}\right)}^{-1}& {\beta }_2^{t-1}{G\left({\beta }_2\right)}^{-1}+{\beta }_2^{\left(t-1\right)2^m}{G\left({\beta }_2^{2^m}\right)}^{-1}& {\beta }_n^{t-1}{G\left({\beta }_n\right)}^{-1}+{\beta }_n^{\left(t-1\right)2^m}{G\left({\beta }_n^{2^m}\right)}^{-1}\end{array}\right]$

[0081] By way of the foregoing, a special generalization of Goppa codes is constructed with a support set L as a set of rational functions

[00014]$\frac{f_i^{\prime }\left(x\right)}{f_i\left(x\right)}.$

The special generalization of Goppa codes is neither a Reed Solomon (RS) code nor an alternant code.

[0082] For decoding these generalized Goppa codes, the Goppa polynomial G(x) and support set L must be known. A classical decoding algorithm (Euclidean, Berlekamp-Massey, Patterson, etc.) can then be used.

[0083] Using a set of position numerators of degree greater than 1, the degree of Galois field extension m for obtaining a support set L is reduced, thereby reducing the complexity of the calculations in the decoding process. The degree m of the field extension is reduced by r times, where r is the degree of the position numerators.

[0084] By way of example, a scheme (2060, 1720, t=30) can be constructed close in parameters to the classical McEliece and Niederreiter (2048, 1718, t=30) scheme by using elements from the Galois field GF(2.sup.6) instead of the field GF(2.sup.11) used in the original scheme. Therefore in the scheme of this example, all calculations in the decoding procedure can be done in the Galois field GF(2.sup.6) with only 2.sup.6 elements instead of the Galois field GF(2.sup.11) with 2.sup.11 elements required.

[0085] In the embodiment depicted in FIG. 1, after the cryptographic operations are performed, the result 120 of this computation is returned to the input/output device 106 and output from the cryptographic device 100. An embodiment in accordance with one aspect of the present invention provides a public key cryptographic system and method that can be used to build a highly secure system for data storage, access, encryption, decryption, digital signing, digital signature verification, etc.

[0086] FIG. 2 depicts an alternative embodiment of a system in which the foregoing encryption method can be employed. In the system of FIG. 2, the cryptographic engine 116 is implemented on a Chip 130, such as field programmable gate array (FPGA), operating as an independent processing module 132 such as, but not limited to, a TPM-Trusted Platform Module (TPM) or a Universal Serial Bus (USB) Module, rather than being stored in system memory. An advantage of implementing the cryptographic engine 116 on an independent processing module 132 is that the private key 124 is stored on the chip 130 and therefore separated from the operating system contained in the System Memory 114. This provides an added layer of security as the Private Key 124 is not directly exposed to the file system of the operating system which can be compromised as can the system memory 114.

[0087] In the alternative embodiment of FIG. 3, the public key cryptographic device 100 generates a private key 124 and its corresponding public key 126 using an input list of parameters 122. As previously described, the public key 126 (FIG. 3) can be used in encryption and decryption operations. In one embodiment, the public key cryptographic device 100 of FIG. 3 can be implemented as described in connection with FIG. 1 except for the instructions being implemented by the cryptographic engine 116.

[0088] An application of the foregoing systems is depicted in FIG. 4, in which the cryptographic engine can be applied to create a Post-Quantum Blockchain (PQBC) 140. In the exemplary embodiment of FIG. 4, the last data block 152 in the PQBC 140 is created by participant node 146 preceded by the data block 150 created by participant node 144 and further preceded by the data block 148 created by participant node 142. All participant nodes use a public key cryptographic device 100 for cryptographic functions. For example, when node 146 creates the last data block 152, node 146 digitally signs the block and records the hash value of the previous data block 150 in the PQBC using a digital signature function in the public key cryptographic device 100. Similarly the other participant nodes 142 and 144 perform the same steps when creating a new data block. Transaction data inside each of the data blocks can optionally be encrypted using the encryption function in the public key cryptographic device 100. End point security can be further enhanced by employing the system of FIG. 3 in which the private key 124 is maintained separate from the operating system.

[0089] Alternative instructions that can be implemented by the device of FIG. 3 are depicted in connection with FIG. 5 in which a method of generating a private and public key pair is shown. The private key 124 and its corresponding public key 126 are used for different functions in the public key cryptographic device 100 such as, but not limited to, encryption, decryption, digital signing, and digital signature verification. The code parameter selection engine 132 chooses m, r, t, n with the property that code length n≤Σ.sub.i=1.sup.r I.sub.2.sub.m(i), t>r and wherein: m is the degree of the field expansion GF(2.sup.m) in which the operations will be performed during decoding and signature calculations, and which will thereby determine the complexity of the circuit calculations; r is the maximum degree of the denominator of a rational function over F.sub.2.sub.m[x] in the set of L; and t is the number of errors in the weighted Hamming metric that can be corrected by the code. There is no limit on how m, r, and t are selected.

[0090] For illustration purposes, m determines the Galois field GF(2.sup.m) used in the calculations while r and m determine the size of support set L. Since code length n, r, and t determine a minimal distance of the code, therefore these parameters also determine the number of errors that could be corrected by such error correcting code. The private support set L generator 160 chooses or generates n elements (rational functions

[00015]$\frac{f_i^{\prime }\left(x\right)}{f_i\left(x\right)})$

to support set L. For the sake of clarity, f.sub.i(x) should be an irreducible polynomial of degree r. There are well-known methods to generate such polynomial, which are outside the scope of this invention. The Private Goppa Polynomial G(x) processor 162 chooses and/or generates primitive polynomial degree t from F.sub.2.sub.m[x]. For the sake of clarity, G(x) is an irreducible (separable) polynomial of degree t with coefficients from GF(2.sup.m). There are well-known methods to generate such polynomial, any of which can be used. The two elements G and L of Goppa code are defined unequally. Therefore, by using the (f.sub.i (c)).sup.−1 mod G(x) generator 164 and obtaining r.sub.i(x) using the i-th column r.sub.i(x) of parity check matrix H generator 166, it is now possible to use the i-th binary column of parity check matrix H generator 168 to obtain a number of binary elements equal to the multiplication oft and m (tm), and collect all necessary n columns and tm binary rows r.sub.i1, r.sub.i2, . . . , r.sub.imt of parity check matrix H from the i-th column r.sub.i(x)∈GF(2.sup.m), deg r.sub.i(x)=t−1 during n cycles of the process of steps 160, 164, and 166. For the sake of clarity, r.sub.i(x)=f′.sub.i(x) f.sub.i(x)).sup.−1 mod G(x), where f′.sub.i(x) is formal derivative of fi(x). The binary parity check matrix H 170 is represented as a tm×n binary matrix. Together with a randomly selected mt×mt non-singular matrix S 172 and another randomly selected n×n permutation matrix P 174 the public key 126 can be obtained by performing a matrix multiplication of H*=S×H×P. On the other hand, the private key 124 can be obtained as K={S, P, L, G(x)}.

[0091] A method of encrypting a message in accordance with an embodiment of the present invention is depicted in FIG. 6 in which the Message 176 is presented as a binary vector e of length n and Hamming weight no more than t/r. The Encrypted Message 178 is obtained as an encrypted vector w of length mt by using matrix multiplication of the public key 126 and the message 176 whereby w=e×(H*).sup.T.

[0092] A method of decrypting an encrypted message in accordance with a preferred embodiment of the invention is depicted in FIG. 7 in which the encrypted message 180 of length mt is decoded by decoder 182 using a Berlekamp-Massey algorithm or an extended Euclidean algorithm or Patterson algorithm. The private key 124 and the elements of field GF(2.sup.m) 186 are provided to the decoder 182 for the decoding process. For the sake of clarification, in the private key 124 G(x) is an irreducible polynomial of degree t with coefficients from the field GF(2.sup.m) with support set L as a set of rational functions

[00016]$\frac{f_i^{\prime }\left(x\right)}{f_i\left(x\right)}.$

The decoded message 184 is an information vector e of the length n and weight in the weighted Hamming metric less than or equal to t.

[0093] A method of obtaining a digital signature for input data, using the cryptographic device 100, is depicted in FIG. 8. This method uses the secret Goppa code elements of a Goppa polynomial G(x) with support set L in a well-known digital signature generation process such as, but not limited to, the Courtois-Finiasz-Sendrier (CFS) signature scheme. Data 190 to be digitally signed is provided to a first hash process 192. The resulting hash value h is used by a second hash process 194 to generate hash value H using h and i (H=hash(h∥i) where the length of H is mt bits) where i is a looping incremental value starting at 1. The second hash value H is then used by the decoder 196 in a decoding process based on elements of a Galois field GF(2.sup.m) 198 and a private key 124 using an Berlekamp-Massey or Extended Euclidean algorithm. For the sake of clarification, in the private key 124, G(x) is an irreducible polynomial of degree t with coefficients from the field GF(2.sup.m)) with support set L as a set of rational functions

[00017]$\frac{f_i^{\prime }\left(x\right)}{f_i\left(x\right)}.$

The second hash process 194 and the decoder 196 are repeated with an incrementing i value until a successful decoding is reached. The resulting digital signature 120, represented as {s,i}, consists of two elements: 1) a vector s of the length n and weight in the weighted Hamming metric of less than or equal to t; and 2) a parameter i equal to the number of the successful steps.

[0094] A method of verifying a digital signature for given data, in the cryptographic device 100, is depicted in FIG. 9. In this embodiment, the digital signature 202 to be verified is represented as {s*,i}. The data 204, which is signed by the digital signature 202, is provided to a hash process 206 as w. Hash process 206 is operated so that the resulting hash value h*=Hash(h∥i), where Hash(w)=h and i is the parameter in the digital signature 202. From the digital signature 202 we can obtain the signature vector s* of length n and weight less than or equal to t in the weighted Hamming metric. A binary vector h** of the length tm, h**=s*×(H*).sup.T, can be obtained by using matrix multiplication of the public key 126 and the binary vector of the signature s from digital signature 202. The determination between valid signature 208 and an invalid signature 210 can be obtained by comparing the value h** and h*.

[0095] Although specific embodiments of the invention have been set forth herein, it is not intended that those be limiting. It should be understood that alternate embodiments, including variations and modifications thereto as well as various other features or functions, can be added to the present invention without departing from the scope of the present invention.