QUANTUM-SAFE CRYPTOGRAPHIC METHODS AND SYSTEMS

Abstract

Cryptographic methods and systems for key exchange, digital signature and zero-knowledge proof. In the digital signature scenario, there is provided a method of signing a digital document, comprising: obtaining a private cryptographic key associated with the signer; obtaining a digital asset from the digital document; selecting a base data element; computing a plurality of signature data elements from (i) the digital asset, (ii) the base data element and (iii) the private cryptographic key; and transmitting the digital document and the plurality of signature data elements to a recipient over a data network. Provenance of the digital document is confirmable by the recipient carrying out a predefined computation involving the digital document, the signature data elements, a plurality of noise variables and a public cryptographic key corresponding to the private cryptographic key associated with the signer. In the zero-knowledge proof scenario, the digital asset plays the role of a challenge data element.

Claims

1. A method of operating a computing apparatus to sign a digital document, comprising: obtaining a private cryptographic key associated with the computing apparatus; obtaining a digital asset from the digital document; selecting a base data element; computing a plurality of signature data elements from (i) the digital asset, (ii) the base data element and (iii) the private cryptographic key; and transmitting the digital document and the plurality of signature data elements to a recipient over a data network; wherein provenance of the digital document is confirmable by the recipient carrying out a predefined computation involving the digital document, the signature data elements, a plurality of noise variables and a public cryptographic key corresponding to the private cryptographic key associated with the computing apparatus.

2. The method defined in claim 1, wherein obtaining the digital asset from the digital document comprises executing a hash function on the digital document, the hash function being known to the recipient.

3. The method defined in claim 1, further comprising transmitting an identity of the computing apparatus to the recipient over the data network.

4. The method defined in claim 1, wherein the base data element represents an integer, wherein the plurality of signature data elements includes a first signature data element, wherein the method further comprises computing the first signature data element by (i) computing a first quantity from the digital asset and the private cryptographic key; and (ii) setting the first signature data element to equal the base data element to the power of said first quantity.

5. The method defined in claim 4, wherein the plurality of signature data elements includes a second signature data element, wherein the method further comprises computing the second signature data element by (i) computing a second quantity from the digital asset and the private cryptographic key; and (ii) setting the second signature data element to equal the base data element to the power of said second quantity.

6. The method defined in claim 5, wherein the plurality of signature data elements includes a third signature data element, wherein the method further comprises computing the third signature data element by (i) computing a third quantity from the digital asset and the private cryptographic key; and (ii) setting the third signature data element to equal the base data element to the power of said third quantity.

7. The method defined in claim 6, wherein the plurality of signature data elements includes a fourth signature data element, wherein the method further comprises computing the fourth signature data element by (i) computing a fourth quantity from the digital asset and the private cryptographic key; and (ii) setting the fourth signature data element to equal the base data element to the power of said fourth quantity.

8. The method defined in claim 7, wherein the plurality of signature data elements includes a fifth signature data element, wherein the method further comprises computing the fifth signature data element by (i) computing a fifth quantity from the digital asset and the private cryptographic key; and (ii) setting the fifth signature data element to equal the base data element to the power of said fifth quantity.

9. The method defined in claim 1, wherein the base data element is selected to be an integer greater than 2 but less than modulo p, where p is selected to be a prime number greater than 2.

10. The method defined in claim 9, wherein the digital asset is constrained to have a value between 0 and p.

11. The method defined in claim 10, wherein p is at least as great as 2.sup.6, 2.sup.8, 2.sup.10, 2.sup.12, 2.sup.14, 2.sup.16, 2.sup.18, 2.sup.20, 2.sup.22 or 2.sup.24.

12. The method defined in claim 1, further comprising encrypting the digital asset with a public key of the recipient before the transmitting.

13. A non-transitory computer-readable storage medium comprising computer-readable instructions which, when executed by a processing entity of a computing apparatus, cause the computing apparatus to carry out operations to sign a digital document, the operations including: obtaining a private cryptographic key associated with the computing apparatus; obtaining a digital asset from the digital document; selecting a base data element; computing a plurality of signature data elements from (i) the digital asset, (ii) the base data element and (iii) the private cryptographic key; and transmitting the digital document and the plurality of signature data elements to a recipient over a data network; wherein provenance of the digital document is confirmable by the recipient carrying out a predefined computation involving the digital document, the signature data elements, a plurality of noise variables and a public cryptographic key corresponding to the private cryptographic key associated with the computing apparatus.

14. A method of operating a computing apparatus to sign a digital asset, comprising: obtaining a private cryptographic key associated with the computing apparatus; selecting a base data element; computing a plurality of signature data elements from (i) the digital asset, (ii) the base data element and (iii) the private cryptographic key; and transmitting the digital asset and the plurality of signature data elements to a recipient over a data network; wherein provenance of the digital asset is confirmable by the recipient carrying out a predefined computation involving the digital asset, the signature data elements, a plurality of noise variables and a public cryptographic key corresponding to the private cryptographic key associated with the computing apparatus.

15. A non-transitory computer-readable storage medium comprising computer-readable instructions which, when executed by a processing entity of a computing apparatus, cause the computing apparatus to carry out operations to sign a digital asset, the operations including: obtaining a private cryptographic key associated with the computing apparatus; selecting a base data element; computing a plurality of signature data elements from (i) the digital asset, (ii) the base data element and (iii) the private cryptographic key; and transmitting the digital asset and the plurality of signature data elements to a recipient over a data network; wherein provenance of the digital asset is confirmable by the recipient carrying out a predefined computation involving the digital asset, the signature data elements, a plurality of noise variables and a public cryptographic key corresponding to the private cryptographic key associated with the computing apparatus.

16. A computing apparatus comprising: a processor; and a non-transitory memory storing computer-readable instructions; the processor being configured for reading and executing the computer-readable instructions in the memory, thereby to cause the computing apparatus to carry out a method according to claim 1.

17. The method defined in claim 16, wherein obtaining the digital asset from the digital document comprises executing a hash function on the digital document, the hash function being known to the recipient.

18. The method defined in claim 16, further comprising transmitting an identity of the computing apparatus to the recipient over the data network.

19. The method defined in claim 16, wherein the base data element represents an integer, wherein the plurality of signature data elements includes a first signature data element, wherein the method further comprises computing the first signature data element by (i) computing a first quantity from the digital asset and the private cryptographic key; and (ii) setting the first signature data element to equal the base data element to the power of said first quantity.

20. The method defined in claim 19, wherein the plurality of signature data elements includes a second signature data element, wherein the method further comprises computing the second signature data element by (i) computing a second quantity from the digital asset and the private cryptographic key; and (ii) setting the second signature data element to equal the base data element to the power of said second quantity.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0027] FIG. 1 is a block diagram illustrating two computing apparatuses engaged in digital communications.

[0028] FIG. 2 is a flowchart showing steps in an example key generation process for determining the components of a recipient's private and public keys, in accordance with a non-limiting embodiment.

[0029] FIG. 3 is a flowchart showing steps in an example encryption process, in accordance with a non-limiting embodiment.

[0030] FIG. 4 is a flowchart showing steps in an example decryption process, in accordance with a non-limiting embodiment.

[0031] FIGS. 5A and 5B are signal flow diagrams illustrating a digital signature process, in accordance with different non-limiting embodiments.

[0032] FIG. 6 is a flowchart showing steps in an example key generation process, in accordance with a non-limiting embodiment.

[0033] FIG. 7 is a flowchart showing steps in an example signing process, in accordance with a non-limiting embodiment.

[0034] FIG. 8 is a flowchart showing steps in an example verification process, in accordance with a non-limiting embodiment.

[0035] FIG. 9 is a signal flow diagram illustrating a digital signature process, in accordance with a non-limiting embodiment.

[0036] FIG. 10 is a block diagram illustrating various elements of a computing apparatus, in accordance with a non-limiting embodiment.

[0037] FIG. 11 is a flowchart showing steps in an example method of operating a sender computing apparatus to securely transmit a digital asset to a recipient over a data network in accordance with a non-limiting embodiment.

[0038] FIG. 12 is a flowchart showing steps in an example method of operating a computing apparatus to authenticate a received message purportedly sent by a given sender in accordance with a non-limiting embodiment.

[0039] FIG. 13 is a flowchart showing steps in an example method of operating a computing apparatus to authenticate a received message purportedly sent by a given sender, in accordance with a non-limiting embodiment.

[0040] FIG. 14 is a flowchart showing steps in an example method of operating a computing apparatus to verify that a given sender has knowledge of a secret, in accordance with a non-limiting embodiment.

[0041] FIG. 15 is a flowchart showing steps in an additional embodiment of an example method of operating a computing apparatus to verify that a given sender has knowledge of a secret, in accordance with a non-limiting embodiment.

DETAILED DESCRIPTION

[0042] Use Case 1: Encryption

[0043] With reference to FIG. 1, a specially designed cryptographic key pair (or simply “key pair”) can be used in an asymmetric cryptography scenario between a sender (hereinafter an “encryptor”) 10 and a recipient 20. The encryptor 10 encrypts a digital asset 30 into an encrypted message (also referred to as a ciphertext) 70 using the recipient's “public key” 40. In various non-limiting embodiments, the digital asset 30 may be a file, a document or a key (such as may be used for encryption of a subsequent digital asset). The recipient's public key 40 can be made available (e.g., transmitted over the Internet or another data network 60 or combination of networks) to entities (such as the encryptor 10) who wish to securely communicate with the recipient 20. The recipient 20 decrypts the digital asset 30 from the encrypted message 70 using the recipient's “private key” 50.

[0044] Due to special design of the key pair 40, 50 and the use of noise variables 80 (as will be described herein below), the private key 50 is extremely difficult to obtain from the public key 40, even after observing multiple encrypted messages 70. This makes the present encryption scheme highly secure.

[0045] Design of Key Pair

[0046] FIG. 2 shows a key generation process 200 for determining the components (data elements) of the recipient's private and public keys, in accordance with a non-limiting embodiment. The key generation process 200 may be carried out by a key generation entity. The key generation entity could be implemented within the recipient 20 itself, but could also be implemented by a third party that publishes the recipient's public key 40 and guarantees secure delivery of the recipient's private key 50 to the recipient 20 (e.g., out-of-band or via manual delivery). The steps in the key generation process 200 include various sub-steps, and not all steps or sub-steps need be performed in the order described.

[0047] Step 210: [0048] The key generation entity chooses an integer p for modulo arithmetic; p may or may not be a prime number, although in some embodiments, it may be preferable that p be prime. In the following, (pH represents Euler's totient function and therefore φ(p) equals the totient function of p. Furthermore, all computations described below for Use Case 1 are mod p. In some embodiments p can have a value at least as great as 2.sup.6, 2.sup.8, 2.sup.10, 2.sup.12, 2.sup.14 or 2.sup.16, or even more.

[0049] Step 220: [0050] The key generation entity chooses a multivariate base polynomial B(x.sub.0, x.sub.1, . . . , x.sub.m) of order n, which can be an arbitrary integer. There is no particular limitation on the value of n. Non-limiting examples for the value of n include 3, 4, 5, 6, 7, 8, 9, 10 or higher. [0051] The multivariate base polynomial B(x.sub.0, x.sub.1, . . . , x.sub.m) can be rewritten as a polynomial of a single variable x.sub.0:

B(x.sub.0,x.sub.1, . . . , x.sub.m)=Σ.sub.i=0.sup.nb.sub.i(x.sub.1, . . . , x.sub.m)x.sub.0 [0052] where b.sub.i(x.sub.1, . . . x.sub.m)=Σ.sub.j=1.sup.mΣ.sub.j=0.sup.l b.sub.ij(Π.sub.k=1.sup.mx.sub.k.sup.j.sup.k), in other words each of the coefficients b.sub.i(x.sub.1, . . . , x.sub.m) is itself a multivariate polynomial with its own coefficients. [0053] As such, b.sub.i(x.sub.1, . . . , x.sub.m) can be considered as a multivariate polynomial in m variables, where such variables will be referred to as “noise variables” x.sub.1, . . . , x.sub.m. As will be shown later on, these noise variables, whose values are selected at runtime by the encryptor 10, add to the security of the encryption process (to be described herein below with reference to FIG. 3). [0054] The value of m (i.e., the number of noise variables) is a system variable that can be arbitrarily set to any positive integer, without any particular limitation except for security considerations, i.e., the higher the value of m, the greater the security level, all other variables being equal. Non-limiting examples for the value of m include 3, 4, 5, 6, 7, 8, 9, 10 or higher.

[0055] Step 230: [0056] The key generation entity chooses the coefficients of a pair of polynomials f(⋅) and h(⋅) of degree X:

f(x.sub.0)=Σ.sub.j=0.sup.λf.sub.jx.sub.0.sup.j

h(x.sub.0)=Σ.sub.j+0.sup.λx.sub.0′ [0057] By keeping the order of each of f(⋅) and h(⋅) relatively low (such as by keeping X equal to 1, 2 or 3, for example), these polynomials have analytically derivable roots, which will be useful as will be shown later on.

[0058] Step 240: [0059] The key generation entity constructs a pair of product polynomials, P(x.sub.0, x.sub.1, . . . , x.sub.m) and Q(x.sub.0, . . . , x.sub.m), by multiplying the base polynomial B(x.sub.0, x.sub.1, . . . , x.sub.m) with the lower-order polynomials f(⋅) and h(⋅), respectively: [0060] P(x.sub.0, x.sub.1, . . . , x.sub.m)=B(x.sub.0, x.sub.1, . . . , x.sub.M)f(x.sub.0)=Σ.sub.i=0.sup.n+λp.sub.i(x.sub.1, . . . , x.sub.m) x.sub.0.sup.i [0061] Q(x.sub.0, x.sub.1, . . . , x.sub.m)=B(x.sub.0, x.sub.1, . . . , x.sub.m)h(x.sub.0)=Σ.sub.i=0.sup.n+λq.sub.i(x.sub.1, . . . , x.sub.m) x.sub.0′ [0062] where [0063] p.sub.0(x.sub.1, . . . , x.sub.m)=p.sub.0=f.sub.0 b.sub.0(x.sub.1, . . . , x.sub.m) [0064] q.sub.0(x.sub.1, . . . , x.sub.m)=q.sub.0=h.sub.0 b.sub.0(x.sub.1, . . . , x.sub.m) [0065] p.sub.n+λ(x.sub.1, . . . , x.sub.m)=p.sub.n+λ=f.sub.λ b.sub.n(x.sub.1, . . . , x.sub.m) [0066] q.sub.n+λ(x.sub.1, . . . , x.sub.m)=q.sub.n+λ=h.sub.λ b.sub.n(x.sub.1, . . . , x.sub.m) [0067] p.sub.i(x.sub.1, . . . , x.sub.m)=Σ.sub.s+t=i f.sub.s b.sub.t(x.sub.1, . . . , x.sub.m), i=1, 2, . . . , n+λ−1 [0068] q.sub.i(x.sub.1, . . . , x.sub.m)=Σ.sub.s+t=i h.sub.s b.sub.t(x.sub.1, . . . , x.sub.m), i=1, 2, . . . , n+λ−1

[0069] Step 250: [0070] The key generation entity creates a first “noise function” N.sub.0(x.sub.1, . . . , x.sub.m) from b.sub.0(x.sub.1, . . . , x.sub.m) excluding the pure constant term b.sub.0(0, . . . , 0) and a first selected arbitrary number R.sub.0. In this example, the multivariate polynomial b.sub.0(x.sub.1, . . . , x.sub.m) is multiplied by R.sub.0, which is an integer (e.g., it can be the output of a pseudo-random number generator if desired): [0071] N.sub.0(x.sub.1, . . . , x.sub.m)=R.sub.0 [b.sub.0(x.sub.1, . . . , x.sub.m)−b.sub.0(0, . . . , 0)], [0072] where b.sub.0(0, . . . , 0) should be selected so as not to be equal to zero. [0073] In addition, the key generation entity creates a second noise function N.sub.n(x.sub.0, x.sub.1, . . . , x.sub.m) from b.sub.n(x.sub.1, . . . , x.sub.m), x.sub.0.sup.n+λ and a second selected arbitrary number R.sub.n: [0074] N.sub.n(x.sub.0, x.sub.1, . . . , x.sub.m)=R.sub.n b.sub.n(x.sub.1, . . . , x.sub.m) x.sub.0.sup.n+λ [0075] where R.sub.0 and R.sub.n are modulo p. It is noted that, unlike N.sub.0, N.sub.n is not just a function of x.sub.1, . . . , x.sub.m but also of x.sub.0.

[0076] Step 260: [0077] The key generation entity creates the recipient's private key 50 by assembling the following data elements: [0078] a. R.sub.0 and R.sub.n, and optionally R.sub.p and R.sub.q (see step 270) [0079] b. the coefficients of f(⋅) (i.e., f.sub.0, f.sub.1, . . . , f.sub.λ) [0080] c. the coefficients of h(⋅) (i.e., h.sub.0, h.sub.1, . . . , h.sub.λ) [0081] d. the individual terms p.sub.0=f.sub.0b.sub.0(0, . . . , 0) and q.sub.0=h.sub.0b.sub.0(0, . . . , 0) (or, equivalently, just b.sub.0(0, . . . , 0), since f.sub.0 and h.sub.0 are already part of the private key); [0082] The values of the above data elements can be arbitrarily chosen by the key generation entity.

[0083] Step 270: [0084] The key generation entity creates the recipient's public key 40 by assembling the following data elements (the integer p can be part of the recipient's public key or can be a known system variable): [0085] a. the coefficients of the first noise function N.sub.0(x.sub.1, . . . , x.sub.m) [0086] b. the coefficients of the second noise function N.sub.n(x.sub.0, x.sub.1, . . . , x.sub.m) [0087] c. the set of coefficients p.sub.i(x.sub.1, . . . , x.sub.m) for i=1, 2, . . . , n+λ−1, optionally multiplying with R.sub.p [0088] d. the set of coefficients q.sub.i(x.sub.1, . . . , x.sub.m) for i=1, 2, . . . , n+λ−1, optionally multiplying with R.sub.q

[0089] Step 280: [0090] The key generation entity causes the recipient's private key 50 to be securely stored in a memory of the recipient 20. The key generation entity also causes the recipient's public key 40 to be made available to would-be encryptors such as the encryptor 10.

[0091] Encryption Using Public Key

[0092] Armed with the public key 40 as defined above, the encryptor 10 may perform an encryption process 300 in accordance with a non-limiting embodiment, now described with reference to FIG. 3. The steps in the encryption process 300 include various sub-steps, and not all steps or sub-steps need be performed in the order described.

[0093] Step 310: [0094] The encryptor 10 determines a digital asset x.sub.0 from 0 to p−1. The digital asset x.sub.0 could be a message or a hash of a message. The message may carry or convey a document, a file, an image, a transaction, a document, a financial instrument, an encryption key or any other information of value. In some embodiments p can have a value at least as great as 2.sup.6, 2.sup.8, 2.sup.10, 2.sup.12, 2.sup.14, 2.sup.16, 2.sup.18, 2.sup.20, 2.sup.22, 2.sup.24 or even more.

[0095] Step 320: [0096] The encryptor 10 obtains the recipient's public key 40, which includes: [0097] the coefficients of the first noise function N.sub.0(x.sub.1, . . . , x.sub.m) [0098] the coefficients of the second noise function N.sub.n(x.sub.0, x.sub.1, . . . , x.sub.m) [0099] the set of coefficients p.sub.i(x.sub.1, . . . , x.sub.m) for i=1, 2, . . . , n+λ−1 [0100] the set of coefficients q.sub.i(x.sub.1, . . . , x.sub.m) for i=1, 2, . . . , n+λ−1

[0101] Step 330: [0102] The encryptor 10 chooses m arbitrary noise variables x.sub.1, . . . , x.sub.m. For example, these could be random numbers such as may be output from a pseudo-random number generator, and in some embodiments they should be.

[0103] Step 340: [0104] The encryptor 10 computes the following quantities, based on the above quantities and the public key 40: [0105] a. P′=Σ.sub.i=1.sup.n+λ−1 p.sub.i(x.sub.1, . . . , x.sub.m)x.sub.0.sup.i; [0106] b. Q′=Σ.sub.i=1.sup.n+λ−1 q.sub.i(x.sub.1, . . . , x.sub.m)x.sub.0.sup.i; [0107] c. N.sub.0=N.sub.0(x.sub.1, . . . , x.sub.m); [0108] d. N.sub.n=N.sub.n(x.sub.0, x.sub.1, . . . , x.sub.m);

[0109] Step 350: [0110] The encryptor 10 sends an encrypted message (e.g., the ciphertext 70) containing data elements P′, 0′, No and N.sub.n (which can be referred to as a “ciphertext tuple”) to the recipient 20. On its way from the encryptor 10 to the recipient 20, the ciphertext 70 may traverse the data network 60 (e.g., the Internet), for example.

[0111] Decryption Using Private Key

[0112] In order to decrypt the digital asset x.sub.0, the recipient 20 (which stores the private key 50 corresponding to the public key 40 used by the encryptor 10) may perform a decryption process 400 in accordance with a non-limiting embodiment, now described with reference to FIG. 4. The steps in the decryption process 400 include various sub-steps, and not all steps or sub-steps need be performed in the order described.

[0113] Step 410: [0114] The recipient 20 receives the ciphertext 70 containing data elements P′, Q′, N.sub.0 and N.sub.n.

[0115] Step 420: [0116] The recipient 20 computes the following variables V1 and V2 based on the data elements of the received ciphertext tuple 70 (i.e., P′, Q′, No and N.sub.n) and based on some of the data elements of the private key 50 held by the recipient 20 (namely, R.sub.0, R.sub.n, f.sub.0, f.sub.λ, h.sub.0, h.sub.λ, p.sub.0 and q.sub.0, as well R.sub.p and R.sub.q, as when used):

[00001]$V1=p_0+\frac{N_0}{R_0}{f}_0+\frac{P^{\prime }}{R_p}+\frac{N_n}{R_n}{f}_{\lambda },$  if the optional factor R.sub.p was used in key generation, otherwise the denominator of P′ is simply unity.

[00002]$V2=q_0+\frac{N_0}{R_0}{h}_0+\frac{Q^{\prime }}{R_q}+\frac{N_n}{R_n}{h}_{\lambda },$  if the optional factor R.sub.q was used in key generation, otherwise the denominator of Q′ is simply unity.

[0117] Step 430: [0118] The recipient 20 solves the following equation for x (recalling that the coefficients of f(⋅) and of h(⋅) are part of the recipient's private key 50 and therefore known to the recipient 20):

[00003]$\frac{V1}{V2}*h\left(x\right)-f\left(x\right)=0.$ [0119] Since each of f(⋅) and h(⋅) is of relatively low order (e.g., λ=1, 2 or 3), the above equation is also of relatively low order and has analytically derivable roots.

[0120] Decryption is now complete: the recipient 20 declares solution to above equation (which should be an integer) as being the digital asset x.sub.0 that was the subject of the encryption process 300.

[0121] The decrypted digital asset x.sub.0 can be communicated via a graphical user interface, encoded in a signal sent over a data network or stored in a non-transitory memory.

[0122] In the case where the above equation (at step 430) has more than one integer-valued solution (for example, two real integer roots if it is a quadratic, two or three real integer roots if it is a cubic), then it is likely that only one of these solutions will make sense in view of the communications context, and it is considered a straightforward task to discriminate between a potential solution that makes sense and one that does not. For example, one simple non-limiting way to ensure that the right choice is made, is to format the digital asset by pre-appending a flag to it and then treating the formatted digital asset as the secret to be encrypted. The flag can be simply generated by XORing each byte each other of the digital asset in encryption and verified in the decryption. The one root that passes the flag verification is then considered to be the digital asset.

[0123] Those skilled in the art will appreciate that steps 420 and 430 may be collapsed into a single arithmetic expression involving the plurality of ciphers (data elements of the ciphertext) and the data elements of the private key 50.

[0124] It should also be appreciated that the values of m, n and p are predetermined and known to the encryptor 10 and the recipient 20 for the purposes of a given instantiation of the encryption process 300 and the decryption process 400.

[0125] Explanation of how it Works [0126] Consideration is now given to explaining why it is the case that a root of the above equation (step 430) corresponds to the digital asset x.sub.0. [0127] To this end, it is recalled that: [0128] V1 was computed as

[00004]$p_0+\frac{N_0}{R_0}{f}_0+\frac{P^{\prime }}{R_p}+\frac{N_n}{R_n}{f}_{\lambda }$  and [0129] V2 was computed as

[00005]$q_0+\frac{N_0}{R_0}{h}_0+\frac{Q^{\prime }}{R_q}+\frac{N_n}{R_n}{h}_{\lambda },$  in both cases assuming the optional factors R.sub.p and [0130] R.sub.q were used in key generation (otherwise the denominators of P′ and Q′ are simply 1). [0131] Now, because P′=Σ.sub.i=1.sup.n+λ−1 p.sub.i(x.sub.1, . . . , x.sub.m)x.sub.0.sup.i (see step 330), because P(x.sub.0, x.sub.1, . . . , x.sub.m)=E.sub.i=0.sup.n+λ p.sub.i(x.sub.1, . . . , x.sub.m) x.sub.0.sup.i (see step 240) and because of the above definitions of p.sub.i(x.sub.1, . . . , x.sub.m), N.sub.0(x.sub.1, . . . , x.sub.m) and N.sub.n(x.sub.0, x.sub.1, . . . , x.sub.m) (see steps 240 and 250), it follows that the aforementioned quantity V1 is actually equal to P(x.sub.0, x.sub.1, . . . , x.sub.m). [0132] Similarly, because Q′=Σ.sub.i=1.sup.n+λ−1 q.sub.i(x.sub.1, . . . , x.sub.m)x.sub.0.sup.i (see step 330), because Q(x.sub.0, x.sub.1, . . . , x.sub.m)=Σ.sub.i=1.sup.n+λq.sub.i(x.sub.1, . . . , x.sub.m) x.sub.0.sup.i (see step 240) and because of the above definitions of q.sub.i(x.sub.1, . . . , x.sub.m), N.sub.0(x.sub.1, x.sub.m) and N.sub.n(x.sub.0, x.sub.1, . . . , x.sub.m) (see steps 240 and 250), it follows that the aforementioned quantity V2 is actually equal to Q(x.sub.0, x.sub.1, . . . , x.sub.m). [0133] Therefore, when computing the ratio of V1 to V2 at step 430, it is the same as computing the ratio of P(x.sub.0, x.sub.1, . . . , x.sub.m) to Q(x.sub.0, x.sub.1, . . . , x.sub.m). In other words:

[00006]$\frac{V1}{V2}=\frac{P\left(x_0,x_1,.Math.,x_m\right)}{Q\left(x_0,x_1,.Math.,x_m\right)}.$ [0134] Next, it is also recalled (from step 220) that P(x.sub.0, x.sub.1, . . . , x.sub.m) was defined as B(x.sub.0, x.sub.1, . . . , x.sub.m)f(x.sub.0) and Q(x.sub.0, x.sub.1, . . . , x.sub.m) was defined as B(x.sub.0, x.sub.1, . . . , x.sub.m)h(x.sub.0). Thus, from a mathematical standpoint:

[00007]$\begin{array}{cc}\frac{P\left(x_0,x_1,.Math.,x_m\right)}{Q\left(x_0,x_1,.Math.,x_m\right)}=\frac{f\left(x_0\right)}{h\left(x_0\right)}& \end{array}$ [0135] Therefore, one has:

[00008]$\begin{array}{cc}\frac{V1}{V2}=\frac{f\left(x_0\right)}{h\left(x_0\right)},& \end{array}$ [0136] from which one obtains:

[00009]$\frac{V1}{V2}*h\left(x_0\right)-f\left(x_0\right)=0.$ [0137] As a result, x.sub.0 is the solution to (or, of there is more than one solution, is one of the solutions to):

[00010]$\frac{V1}{V2}*h\left(x\right)-f\left(x\right)=0.$

[0138] Security Analysis for Use Case 1

[0139] It will be appreciated that the values of x.sub.1, . . . , x.sub.m (i.e, the noise variables) do not affect the decryption process 400 if the correct private key 50 is used, but they make it all the more difficult for someone who does not have the private key 50 to derive it from the public key 40 and the ciphertext 70.

[0140] The complexity of obtaining the private key 50 from the public key 40 can be determined as follows: [0141] Leveraging from key construction in terms of transformation in a polynomial vector space, one can write public key coefficients (for an example of n=4 and λ=2):

[00011]$\left[\begin{array}{c}p1\\ p2\\ p3\\ p4\\ p5\end{array}\right]=\left[\begin{array}{ccccc}f1& f0& 0& 0& 0\\ f2& f1& f0& 0& 0\\ 0& f2& f1& f0& 0\\ 0& 0& f2& f1& f0\\ 0& 0& 0& f2& f1\end{array}\right]\left[\begin{array}{c}b0\\ b1\\ b2\\ b3\\ b4\end{array}\right]$ [0142] Then with the reverse transformation, one has:

[00012]$\stackrel{.fwdarw.}{b}=\left[\begin{array}{c}b0\\ b1\\ b2\\ b3\\ b4\end{array}\right]={\left[\begin{array}{ccccc}f1& f0& 0& 0& 0\\ f2& f1& f0& 0& 0\\ 0& f2& f1& f0& 0\\ 0& 0& f2& f1& f0\\ 0& 0& 0& f2& f1\end{array}\right]}^{-1}\left[\begin{array}{c}p1\\ p2\\ p3\\ p4\\ p5\end{array}\right]$ [0143] Then one can write the transformation with reference to the base polynomial:

[00013]$T_b=\left[\begin{array}{ccccc}b1& b0& 0& 0& 0\\ b2& b1& b0& 0& 0\\ b3& b2& b1& b0& 0\\ b4& b3& b2& b1& b0\\ 0& b4& b3& b2& b1\end{array}\right]$ [0144] Using T.sub.b, we can calculate the second polynomial h(x)'s coefficients:

[00014]$\left[\begin{array}{c}h0\\ h1\\ h2\\ 0\\ 0\end{array}\right]={\left[\begin{array}{ccccc}b1& b0& 0& 0& 0\\ b2& b1& b0& 0& 0\\ b3& b2& b1& b0& 0\\ 0& b3& b2& b1& b0\\ 0& 0& b3& b2& b1\end{array}\right]}^{-1}\left[\begin{array}{c}q1\\ q2\\ q3\\ q4\\ q5\end{array}\right]$ [0145] Based on this process, knowing public key P′ and Q′, one can crack the private key {{right arrow over (b)}.sub.i, {right arrow over (f)}.sub.i, {right arrow over (h)}.sub.i} by brute-forcing f.sub.0, f.sub.1, and f.sub.2. The complexity is O(p.sup.3) or in a general case, O(p.sup.λ+1).

[0146] Turning now to the issue of the size of the public key, private key and cipher in Use Case 1 (in terms of the number of data elements over GF(p)), the following will be noticed: [0147] The size of the public key (see step 270)=m[2(n+λ−1)+2]=2m(n+λ); [0148] The size of the private key (see step 260)=2λ+6 without R.sub.p and R.sub.q and 2λ+8 with R.sub.p and R.sub.q.

[0149] Use Case 2: Digital Signature

[0150] Digital signatures have a wide variety of commercial applications, including the signed transmission of certificates or keys from a certification authority. Another application of digital signatures is the establishment of a sender's identity when sending digital files, messages, legal documents or electronic funds (including digital fiat currency and decentralized currency such as Bitcoin and other cryptocurrencies). Digital signatures are also used to access, add to, modify or confirm elements of a blockchain database in various financial, industrial, commercial and consumer applications.

[0151] In this use case, now described with reference to a first variant in FIG. 5A, an entity (referred to as a “verifier”) 550 wishes to verify that a received digital asset 520, purportedly sent by a given sender, was indeed sent by the given sender. Assuming this to be the case, the sender 510 (referred to as a “signer”) will have generated a digital signature 530 by signing the digital asset 520 with a private key 540 (that is part of a specially designed private/public key pair 540, 570 associated with the signer 510). The signer 510 then sends the digital asset 520 and the signature 530 to the verifier 550.

[0152] The verifier 550 receives both the digital asset 520 and the digital signature 530. The digital signature 530 is purported to have come from the signer 510, but the verifier 550 must verify this to be true. As such, the verifier 550 carries out a verification process on the received digital asset 520 and the accompanying digital signature 530. The verification process involves evaluating mathematical expressions based on (i) the received digital asset 520, (ii) the public key 570 associated with the signer 510 and (iii) a set of “noise variables” 580. Such noise variables 580 are selected by the verifier 550 at its discretion and without involving the signer 510. The verifier 550 then checks whether the mathematical expressions correspond. If so, the verifier 550 concludes that the signer 510 is the true originator of the received digital asset 520, otherwise, the verifier 550 concludes that the received digital asset 520 was not sent by the signer 510.

[0153] The variant of FIG. 5B is similar to the variant of FIG. 5A, except that it shows the digital asset 520 being generated from a message 522, both at the signer 510 and the verifier 530. This derivation of the digital asset 520 from the message 522 can be done using a cryptographic hash function, for example. As such, in this variant, it is the message 522 that is sent with the digital 530 signature, which means that the digital asset 520 is not explicitly sent from the signer 510 to the verifier 530, but rather is implicitly sent, in the sense that it can be derived from the message at either end.

[0154] Design of Key Pair

[0155] The signer's private/public key pair 540, 570 is specially designed so that regardless of the values selected by the verifier 550 for the noise variables 580, the mathematical expressions computed as part of the verification process will always corresponds. Conversely, a single instance of non-correspondence of the mathematical expressions will be taken as a sign that the digital signature 530 was not sent by the signer 510.

[0156] As a result, even if a malicious party (spoofer) creates a digital signature which somehow causes the computed mathematical expressions to correspond, there is close to zero probability that this would occur a second time if the mathematical expressions were re-computed based on a different set of noise variables (which, it is recalled, are controlled by the verifier 550, not the signer 510). Without the signer's private key 540, it is virtually impossible for the spoofer to derive a “fake signature” that would result in mathematical correspondence to be maintained for an arbitrary set of noise variables. Yet this is precisely what happens if the correct private key 540 is used.

[0157] To illustrate this concept in more detail, FIG. 6 shows a key generation process 600 for determining the data elements of a signer's private and public keys, in accordance with a non-limiting embodiment. The key generation process 600 may be carried out by a key generation entity. The key generation entity could be integrated with the signer 510 itself, but it could also be a third party that guarantees secure delivery of the signer's private key 540 to the signer 510 (e.g., out-of-band or via manual delivery) and publishes the signer's public key 570 to interested entities (such as the verifier 550). The steps in the key generation process 600 include various sub-steps, and not all steps or sub-steps need be performed in the order described.

[0158] Step 610: [0159] The key generation entity chooses an integer p for modulo arithmetic. In contrast to Step 210 of Use Case 1, where p may be not required to be a prime number, in Use Case 2, p is a prime number and, moreover, should be selected such that (p−1)/2.sup.γ is also prime for some integer γ. In the following, (pH continues to represent Euler's totient function. In Use Case 2 (and Use Case 3), all computations in key generation, polynomial computations in signing and verifying processes are mod φ(p) because those computations are eventually used in the exponents of modular arithmetic computations. However, the ground modulo in the arithmetic exponentiation is with the prime p. In some embodiments, p is at least as great as 2.sup.6, 2.sup.8, 2.sup.10, 2.sup.122.sup.14, 2.sup.16, 2.sup.18, 2.sup.20, 2.sup.22 or 2.sup.24.

[0160] Step 620 (corresponds to step 220 in Use Case 1): [0161] The key generation entity chooses a multivariate base polynomial B(x.sub.0, x.sub.1, . . . , x.sub.m) of order n, which can again be an arbitrary integer. There is no particular limitation on the value of n. Non-limiting examples for the value of n include 3, 4, 5, 6, 7, 8, 9, 10 or higher. [0162] The multivariate base polynomial B(x.sub.0, x.sub.1, . . . , x.sub.m) can be rewritten as a polynomial of a single variable x.sub.0 in which the coefficients are b.sub.i(x.sub.1, . . . , x.sub.m): [0163] B(x.sub.0, x.sub.1, . . . , x.sub.m)=Σ.sub.i=0.sup.n b.sub.i(x.sub.1, . . . , x.sub.m) x.sub.0.sup.i [0164] where b.sub.i(x.sub.1, . . . , x.sub.m)=Σ.sub.j=0.sup.mΣ.sub.j=0.sup.lb.sub.ij(Π.sub.k=1.sup.mx.sub.k.sup.j.sup.k) [0165] Here again, b.sub.i(x.sub.1, . . . , x.sub.m) can be considered as a multivariate polynomial in m variables, where such variables will be referred to as “noise variables” x.sub.1, . . . , x.sub.m. As will be shown later on, these noise variables, whose values are selected at runtime by the encryptor, add to the security of the encryption process. [0166] The value of m (i.e., the number of noise variables) is a system variable that can be arbitrarily set to any positive integer, without any particular limitation except for security consideration. Non-limiting examples for the value of m include 3, 4, 5, 6, 7, 8, 9, 10 or higher.

[0167] Step 630 (corresponds to step 230 in Use Case 1): [0168] The key generation entity chooses the coefficients of a pair of polynomials f(⋅) and h(⋅) of degree λ: [0169] f(x.sub.0)=Σ.sub.j=0.sup.λf.sub.jx.sub.0.sup.i [0170] h(x.sub.0)=Σ.sub.j=0.sup.λh.sub.jx.sub.0.sup.j [0171] over [0, 1, 2, . . . , φ(p)] with X to be any integer greater than 1. In contrast to Use Case 1, the order of each of f(⋅) and h(⋅) need not kept relatively low (such as by keeping λ equal to 1, 2 or 3, for example), because there is no decryption process.

[0172] Step 640 (corresponds to step 240 in Use Case 1): [0173] The key generation entity constructs a pair of product polynomials, P(x.sub.0, x.sub.1, . . . , x.sub.m) and Q(x.sub.0, x.sub.1, . . . , x.sub.m), by multiplying the base polynomial B(x.sub.0, x.sub.1, . . . , x.sub.m) with the polynomials f(⋅) and h(⋅), respectively: [0174] P(x.sub.0, x.sub.1, . . . , x.sub.m)=B(x.sub.0, x.sub.1, . . . , x.sub.m)f(x.sub.0)=Σ.sub.i=0.sup.n+λp.sub.i(x.sub.1, . . . , x.sub.m) x.sub.0.sup.i [0175] Q(x.sub.0, x.sub.1, . . . , x.sub.m)=B(x.sub.0, x.sub.1, . . . , x.sub.m)h(x.sub.0)=Σ.sub.i=0.sup.n+λq.sub.i(x.sub.1, . . . , x.sub.m) x.sub.0.sup.i [0176] where [0177] p.sub.0(x.sub.1, . . . , x.sub.m)=p.sub.0=f.sub.0 b.sub.0(x.sub.1, . . . , x.sub.m) [0178] q.sub.0(x.sub.1, . . . , x.sub.m)=q.sub.0=h.sub.0 b.sub.0(x.sub.1, . . . , x.sub.m) [0179] p.sub.n+λ(x.sub.1, . . . , x.sub.m)=p.sub.n+λ=f.sub.λb.sub.n(x.sub.1, . . . , x.sub.m) [0180] q.sub.n+λ(x.sub.1, . . . , x.sub.m)=q.sub.n+λ=h.sub.λb.sub.n(x.sub.1, . . . , x.sub.m) [0181] p.sub.i(x.sub.1, . . . , x.sub.m)Σ.sub.s+t=i f.sub.sb.sub.t(x.sub.1, . . . , x.sub.m), i=1, 2, . . . , n+λ−1 [0182] q.sub.i(x.sub.1, . . . , x.sub.m)Σ.sub.s+t=ih.sub.sb.sub.t(x.sub.1, . . . , x.sub.m), i=1, 2, . . . , n+λ−1 [0183] The aforementioned calculations are done mod φ(p).

[0184] Step 650 (corresponds to step 250 in Use Case 1, with the added constraint that R.sub.0 and R.sub.n should be even integers): [0185] The key generation entity creates a first “noise function” N.sub.0(x.sub.1, . . . , x.sub.m) from b.sub.0(x.sub.1, . . . , x.sub.m) and a first selected arbitrary number R.sub.0: [0186] N.sub.0(x.sub.1, . . . , x.sub.m)=R.sub.0 b.sub.0(x.sub.1, . . . , x.sub.m). [0187] In addition, the key generation entity creates a second noise function N.sub.n(x.sub.0, x.sub.1, . . . , x.sub.m) from b.sub.n(x.sub.1, . . . , x.sub.m), x.sub.0.sup.n+λ and a second selected arbitrary number R.sub.n: [0188] N.sub.n(x.sub.0, x.sub.1, . . . , x.sub.m)=R.sub.n b.sub.n(x.sub.1, . . . , x.sub.m) x.sub.0.sup.n+λ [0189] where R.sub.0 and R.sub.n are not coprime with φ(p). Here again, it is noted that, unlike N.sub.0, N.sub.n is not just a function of x.sub.1, . . . , x.sub.m but also of x.sub.0.

[0190] Step 660: [0191] The key generation entity creates the signer's private key 540 by assembling the following data elements, which resemble those previously described with respect to Use Case 1: [0192] a. R.sub.0 and R.sub.n [0193] b. the coefficients of f(⋅) (i.e., f.sub.0, f.sub.1, . . . , f.sub.λ) [0194] c. the coefficients of h(⋅) (i.e., h.sub.0, h.sub.1, . . . , h.sub.λ) [0195] In addition, for Use Case 2, the signer's private key 540 includes the coefficients E.sub.pi and E.sub.qi, i=1, 2, . . . , n+λ−1, of two extra univariate polynomials: [0196] d. E.sub.p(x.sub.0)=E.sub.p1x.sub.0+E.sub.p2x.sub.0.sup.2+ . . . +E.sub.p2x.sub.0.sup.n+λ−1 [0197] e. E.sub.q(x.sub.0)=E.sub.q1x.sub.0+E.sub.q2x.sub.0.sup.2+ . . . +E.sub.q2x.sub.0.sup.n+λ−1 [0198] The above data elements can be arbitrarily chosen from 0 to φ(p) by the key generation entity.

[0199] Step 670: [0200] The key generation entity creates the signer's public key 570 in a manner that is similar to way in which the recipient's public key 40 was derived in Use Case 1, with slight differences. Specifically, the signer's public key 570 includes the following data elements (the integer p can be part of the signer's public key 570 or can be a known system variable): [0201] a. the coefficients of the first noise function N.sub.0(x.sub.1, . . . , x.sub.m) [0202] b. the coefficients of the second noise function N.sub.n(x.sub.0, x.sub.1, . . . , x.sub.m) [0203] c. the set of coefficients p′.sub.i(x.sub.1, . . . , x.sub.m)=R.sub.0[p.sub.i(x.sub.1, . . . , x.sub.m)−E.sub.pi] for i=1, 2, . . . , n+λ−1, (with p.sub.i(x.sub.1, . . . , x.sub.m) as defined in step 640) [0204] d. the set of coefficients q′.sub.i(x.sub.1, . . . , x.sub.m)=R.sub.n[q.sub.i(x.sub.1, . . . , x.sub.m)−E.sub.pi] for i=1, 2, . . . , n+λ−1, (with q.sub.i(x.sub.1, . . . , x.sub.m) as defined in step 640) [0205] It is noted that each of the coefficients p′.sub.i(x.sub.1, . . . , x.sub.m) and q′.sub.i(x.sub.1, . . . , x.sub.m) will be even because R.sub.0 and R.sub.n are even.

[0206] Step 680: [0207] The key generation entity causes the signer's private key 540 to be securely stored in a memory of the signer's 510. The key generation entity also causes the signer's public key 570 to be made available to any destination desirous of carrying out a verification process (such as the verifier 550).

[0208] Signing of Digital Asset Using Private Key

[0209] Armed with the private key 540 as defined above, the signer 510 may perform a signing process 700 in accordance with a non-limiting embodiment, now described with reference to FIG. 7. The steps in the signing process 700 include various sub-steps, and not all steps or sub-steps need be performed in the order described.

[0210] Step 710: [0211] The signer 510 derives a digital asset x.sub.0 from a digital message (which can be a digital document, an online transaction, a public key for a certificate, etc.). This derivation can be carried out using a cryptographic hash algorithm, to name a non-limiting example.

[0212] Step 720: [0213] The signer 510 chooses a secret base g for signing the digital asset. This can be any arbitrarily selected integer from [2, 3, . . . , p−1]. It can in some cases be the output of a pseudo-random number generator. The base g is not revealed to the eventual verifier.

[0214] Step 730: [0215] The signer 510 computes the following quantities, based on its knowledge of the private data elements chosen in steps 710-720 and on its knowledge of the data elements of the private key 540 (see steps 610-670): [0216] A=g.sup.f(X.sup.0.sup.) R.sup.0 .sup.mod φ(p) mod p [0217] B=g.sup.h(x.sup.0.sup.) R.sup.n .sup.mod φ(p) mod p [0218] C=g.sup.s.sup.0.sup.(x.sup.0.sup.) mod φ(p) mod p [0219] D=g.sup.s.sup.n.sup.(x.sup.0.sup.) mod φ(p) mod p [0220] E=g.sup.t(x.sup.0.sup.) mod φ(p) mod p [0221] where [0222] s.sub.0(x.sub.0)=R.sub.n[h(x.sub.0)f.sub.0−f(x.sub.0)h.sub.0] [0223] s.sub.n(x.sub.0)=R.sub.0[h(x.sub.0)f.sub.λ−f(x.sub.0)h.sub.λ] [0224] t(x.sub.0)=R.sub.0R.sub.n[h(x.sub.0)E.sub.p(x.sub.0)−f(x.sub.0)E.sub.q(x.sub.0)]

[0225] Step 740: [0226] The signer 510 sends the digital message together with the digital signature 530 which in this case comprises the quantities A, B, C, D and E (computed at step 730) to a recipient (in this case, to the verifier 550). This can be done over the data network 60 (e.g., the Internet), for example.

[0227] Verifying Provenance of a Received Signature Using Public Key

[0228] Consider that the verifier 550 wishes to confirm that the digital asset x.sub.R, which can be derived from the received message and, from the verifier's point of view is merely purported to come from the signer 510, does truly come from the signer 510. Accordingly, the verifier 550 may perform a verification process 800 in accordance with a non-limiting embodiment, now described with reference to FIG. 8. The steps in the verification process 800 include various sub-steps, and not all steps or sub-steps need be performed in the order described.

[0229] Step 810: [0230] The verifier 550 receives a message purported to come from the signer 510, and which carries (either explicitly, as in FIG. 5A, or implicitly, as in FIG. 5B) the digital asset x.sub.0, and the digital signature 530 containing data elements A, B, C, D and E. In the case of FIG. 5B, the digital asset can be derived from the received message x.sub.0 using a cryptographic hash function, for example.

[0231] Step 820: [0232] The verifier 550 obtains the public key 570 of the signer 510. It is recalled that the public key 570 includes: [0233] the coefficients of the first and second noise functions N.sub.0(x.sub.1, . . . , x.sub.m), N.sub.n(x.sub.0, x.sub.1, . . . , x.sub.m) [0234] the sets of coefficients p′.sub.i(x.sub.1, . . . , x.sub.m) and q′.sub.i(x.sub.1, . . . , x.sub.m), for i=1, 2, . . . , n+λ−1

[0235] Step 830: [0236] The verifier 550 chooses m arbitrary noise variables x.sub.1, . . . , x.sub.m. In a non-limiting embodiment, these may be random numbers.

[0237] Step 840: [0238] The verifier 550 computes the following quantities based on (i) the digital asset x.sub.0 (derived from the digital message using a hash function); (ii) the noise variables x.sub.1, . . . , x.sub.m; and (iii) the data elements of the signer's public key 570: [0239] P′=Σ.sub.l=1.sup.n+λ−1p′.sub.i(x.sub.1, . . . , x.sub.m)x.sub.0.sup.j [0240] Q′=Σ.sub.l=1.sup.n+λ−1q′.sub.i(x.sub.1, . . . , x.sub.m)x.sub.0.sup.j [0241] N.sub.0=N.sub.0(x.sub.1, . . . , x.sub.m) [0242] N.sub.n=N.sub.n(x.sub.0, x.sub.1, . . . , x.sub.m) [0243] with the above calculations being mod φ(p).

[0244] Step 850: [0245] The verifier 550 verifies whether the following mathematical relationship is true (recalling that A, B, C, D and E are part of the received digital signature 530): [0246] A.sup.Q′=B.sup.p′C.sup.N.sup.0D.sup.N.sup.nE mod p [0247] If the relationship is true, the verifier 550 concludes that the signer 510 is the true source of the message from which the digital asset x.sub.0 was derived, otherwise, the verifier concludes that the message from which the digital asset x.sub.0 was derived was not sent by the signer 510. [0248] Equivalently, step 850 could involve comparing A.sup.Q′−B.sup.p′C.sup.N.sup.0D.sup.N.sup.nE to zero.

[0249] The verification process 800 is thus complete. The outcome of the verification process 800 can be communicated via a graphical user interface, encoded in a signal sent over a data network or stored in a non-transitory memory.

[0250] It is noted that the conclusion reached at step 850 holds independently of the values of the noise variables x.sub.1, . . . , x.sub.m, which allows the verifier to re-run the above steps 810-850 for an entirely different set of noise variables, in case of any doubt as to the provenance of the message from which the received digital asset x.sub.0 was derived.

[0251] It should be appreciated that the values of m, n and p are predetermined and known to the signer 510 and the verifier 550 for the purposes of a given instantiation of the signing process 700 and the verification process 800.

[0252] Explanation of how it Works

[0253] Consideration is now given to explaining why it is the case that verification of the above mathematical relationship (step 850) serves as an authentication of provenance of the message from which digital asset x.sub.0 was derived, irrespective of the values of the noise variables x.sub.1, . . . , x.sub.m, despite the fact that the noise variables are chosen by the verifier 550 (and not the signer 510).

[0254] To this end, it is recalled that P(x.sub.0, x.sub.1, . . . , x.sub.m) was defined as B(x.sub.0, x.sub.1, . . . , x.sub.m)f(x.sub.0) and Q(x.sub.0, x.sub.1, . . . , x.sub.m) was defined as B(x.sub.0, x.sub.1, . . . , x.sub.m)h(x.sub.0). Therefore, from a mathematical standpoint:

[00015]$\begin{array}{cc}\frac{P\left(x_0,x_1,.Math.,x_m\right)}{Q\left(x_0,x_1,.Math.,x_m\right)}=\frac{f\left(x_0\right)}{h\left(x_0\right)}& \end{array}$

[0255] This leads to:

R.sub.0R.sub.nf(x.sub.0)Q(x.sub.0,x.sub.1, . . . ,x.sub.m)=R.sub.0R.sub.nh(x.sub.0)P(x.sub.0,x.sub.1, . . . ,x.sub.m).[Equation (1)]

[0256] Now, since P′=Σ.sub.i=1.sup.n+λ−1x.sub.m)x.sub.0.sup.i and since p′.sub.i(x.sub.1, . . . , x.sub.m)=R.sub.0[p.sub.i(x.sub.1, . . . , x.sub.m)−E.sub.pi], this means that R.sub.0R.sub.nh(x.sub.0)P(x.sub.0, x.sub.1, . . . , x.sub.m) can be rewritten as:

[00016]$R_0{R}_{n}h\left(x_0\right)P\left(x_0,x_1,.Math.,x_m\right)=R_{n}h\left(x_0\right)\left(R_{0}P\left(x_0,x_1,.Math.,x_m\right)\right)=R_{n}h\left(x_0\right)\left(R_0[P\left(x_0,x_1,.Math.,x_m\right)-E_{pi}+E_{pi}\right)\mathrm{Recognizing}\mathrm{that}P\left(x_0,x_1,.Math.,x_m\right)=\frac{N_0}{R_0}{f}_0+p_i\left(x_1,.Math.,x_m\right)+\frac{N_n}{R_n}{f}_{\lambda },\mathrm{this}\mathrm{continues}\mathrm{as}:=R_{n}h\left(x_0\right)[R_0\left(p_i\left(x_1,.Math.,x_m\right)-E_{pi}+E_{pi}+\frac{N_0}{R_0}{f}_0+\frac{N_n}{R_n}{f}_{\lambda }\right)=R_{n}h\left(x_0\right)\left[R_0\left(p_i\left(x_1,.Math.,x_m\right)-E_{pi}\right)+R_0\left(E_{pi}+\frac{N_0}{R_0}{f}_0+\frac{N_n}{R_n}{f}_{\lambda }\right)\right]=R_{n}h\left(x_0\right)\left[P^{\prime }+R_0\left(E_{pi}+\frac{N_0}{R_0}{f}_0+\frac{N_n}{R_n}{f}_{\lambda }\right)\right]=R_{n}h\left(x_0\right)P^{\prime }+R_0{R}_{n}h\left(x_0\right)\left(E_{pi}+\frac{N_0}{R_0}{f}_0+\frac{N_n}{R_n}{f}_{\lambda }\right)=R_{n}h\left(x_0\right)P^{\prime }+R_0{R}_{n}h\left(x_0\right)E_{pi}+R_{n}h\left(x_0\right)N_0{f}_0+R_{0}h\left(x_0\right)N_n{f}_{\lambda }.$

[0257] Similarly, since Q′=Σ.sub.i=1.sup.n+λ−1 q′.sub.i(x.sub.1, . . . , x.sub.m)x.sub.0.sup.j, since q′.sub.i(x.sub.1, . . . , x.sub.m)=R.sub.n[q.sub.i(x.sub.1, . . . , x.sub.m)−E.sub.pi], P(x.sub.0, x.sub.1, . . . , x.sub.m), this means that R.sub.0R.sub.nf(x.sub.0)Q(x.sub.0, x.sub.1, . . . , x.sub.m) can be rewritten as:

R.sub.0R.sub.nf(x.sub.0)Q(x.sub.0,x.sub.1, . . . ,x.sub.m)=R.sub.0f(x.sub.0)Q′+R.sub.0R.sub.nf(x.sub.0)E.sub.qi+R.sub.0f(x.sub.0)N.sub.nf.sub.0+R.sub.nf(x.sub.0)N.sub.nf.sub.λ.

Therefore, Equation (1) can be rewritten as:

R.sub.0f(x.sub.0)Q′+R.sub.0R.sub.nf(x.sub.0)E.sub.qi+R.sub.0f(x.sub.0)N.sub.nf.sub.0+R.sub.nf(x.sub.0)N.sub.nf.sub.λ=R.sub.nh(x.sub.0)P′+R.sub.0R.sub.nh(x.sub.0)E.sub.pi+R.sub.nh(x.sub.0)N.sub.0f.sub.0+R.sub.0h(x.sub.0)N.sub.nf.sub.λ  [Equation (2)]

[0258] This can be reorganized it into:

f(x.sub.0)R.sub.0Q′=h(x.sub.0)R.sub.nP′+s.sub.0(x.sub.0)N.sub.0+s.sub.n(x.sub.0)N.sub.n+t(x.sub.0)  [Equation (3)]

where:

s.sub.0(x.sub.0)=R.sub.n[h(x.sub.0)f.sub.0−f(x.sub.0)h.sub.0]

s.sub.n(x.sub.0)=R.sub.0[h(x.sub.0)f.sub.λ−f(x.sub.0)h.sub.λ]

t(x.sub.0)=R.sub.0R.sub.n[h(x.sub.0)E.sub.p(x.sub.0)−f(x.sub.0)E.sub.q(x.sub.0)]

[0259] Using modular exponentiation with base g (which, it is recalled, can be arbitrarily selected by the signer) over the Galois Field GF(p) or ring of integers: [2, 3, . . . , p−1]:

g.sup.f(x.sup.0.sup.)R.sup.0.sup.Q′ mod φ(p)=g.sup.[h(x.sup.0.sup.)R.sup.n.sup.P′+s.sup.0.sup.(x.sup.0.sup.)N.sup.0.sup.+s.sup.n.sup.(x.sup.0.sup.)N.sup.n.sup.+t(x.sup.0.sup.)]mod φ(p) mod p

or:

A.sup.Q′ mod φ(p)=B.sup.P′ mod φ(p)C.sup.N.sup.0.sup.mod φ(p)D.sup.N.sup.n.sup.mod φ(p)E mod p   [Equation (4)]

[0260] where [0261] A=g.sup.f(x.sup.0.sup.)R.sup.0 .sup.mod φ(p) mod p, [0262] B=g.sup.h(x.sup.0.sup.)R.sup.n .sup.mod φ(p) mod p. [0263] C=g.sup.s.sup.0.sup.(x.sup.0.sup.) mod φ(p) mod p. [0264] D=g.sup.s.sup.n.sup.(x.sup.0.sup.) mod φ(p) mod p. [0265] E=g.sup.t(x.sup.0.sup.) mod φ(p) mod p.

[0266] Or, we can simply rewrite Equation (4) as:

A.sup.Q′=B.sup.P′C.sup.N.sup.0D.sup.N.sup.nE[Equation (5)]

[0267] Equation (5) can be used by the verifier 550 (which receives the public key 570 comprising the coefficients necessary to calculate P′, Q′, N.sub.0 and N.sub.n) to verify whether the digital asset x.sub.0 was indeed signed by the signer 510.

[0268] It is noted that the elements of the digital signature A, B, C, D, E are only related to (i) the base g chosen arbitrarily by the signer 510, (ii) the digital asset x.sub.0 and (iii) data elements f(x.sub.0) and h(x.sub.0) of the private key. It is noted that the digital signature does not depend on the noise variables x.sub.1, . . . , x.sub.m. In other words, if the correct private key 540 was used to create the digital signature A, B, C, D, E for the digital asset x.sub.0, then Equation (5) will hold for all sets of noise variables x.sub.1, . . . , x.sub.m that could be chosen by the verifier 550. On the other hand, Equation (5) will not hold if the incorrect private key was used to generate the digital signature.

[0269] Security Analysis for Use Case 2

[0270] The complexity of obtaining the private key 540 from the public key 570 is as follows: [0271] O(φ(p).sup.n+1+2.sup.x+1)=O(q.sup.n+12.sup.x(n+1)+2.sup.x+1) [0272] where p=2.sup.x q+1, and where q is a prime number, and x is an integer denting a number of bits. In some embodiments x can have a value of 6, 8, 10, 12, 14, 16 or more, and p can have a value at least as great as 2.sup.6, 2.sup.8, 2.sup.10, 2.sup.12, 2.sup.14, 2.sup.16, 2.sup.18, 2.sup.20, 2.sup.22, 2.sup.24 or even more.

[0273] The complexity of obtaining the private key 540 from the signature 530 is as follows: [0274] O(q 2.sup.x(n+1)+1)

[0275] The complexity of spoofing is as follows: [0276] O(φ(p).sup.5+m)=O(q.sup.5+m2.sup.x(5+m)) with m to be the number of noise terms and m>=1.

[0277] Therefore, the overall complexity of Use Case 2 is the lowest among the above, namely O(q 2.sup.x(n+1)+1)=O(2.sup.log q+x(n+1)+1).

[0278] Turning now to the issue of the size of the public key and the private key in Use Case 2 (in terms of the number of data elements over GF(p)), the following will be noticed: [0279] The size of the public key (see step 670)=m[2(n+λ−1)+2]=2m(n+λ), which is the same as for the public key in Use Case 1; [0280] The size of the private key (see step 660)=2λ+2+2(n+λ−1)=2(n+2λ). [0281] The size of the digital signature is 5*K with K to be the size of required security (for example, 16 bytes for level I, 24 bytes for level III and 32 bytes for level V).

[0282] By way of specific example, the following shows the size of the public key, private key and digital signature for various numbers of noise variables (i.e., m=2 and m=3) and various orders of the multivariate base polynomial (i.e., n=2, n=4 and n=6), based on the formulas in the aforementioned table, while X is kept equal to 2:

TABLE-US-00001 (n, λ, x, log q) (2, 2, 32, 32) (4, 2, 32, 32) (6, 2, 32, 32) (2, 2, 64, 64) Complexity O(2.sup.129): O(2.sup.193): O(2.sup.257): O(2.sup.257): O(2.sup.log q+x(n+1)+1) Security level Security level Security level Security level “I” “III” “V” “V” Size of public key for 16 * 8 = 128 24 * 8 = 192 32 * 8 = 256 16 * 16 = 256 m = 2 (bytes) Size of public key for 24 * 8 = 192 36 * 8 = 288 48 * 8 = 384 24 * 16 = 284 m = 3 (bytes) Size of private key 12 * 8 = 96 16 * 8 = 128 20 * 8 = 160 12 * 16 = 192 (bytes) Signature Size (bytes) 80 120 160 160

[0283] Use Case 3: Zero-Knowledge Proof (ZKP)

[0284] In this use case, now described with reference to FIG. 9, a sender (or prover) 910 associated with a public key 920 of a public/private key pair wishes to prove to a recipient (or verifier) 930 that it has knowledge of the associated private key 940. The private key 940 can represent an identity, for example. If the public key 920 and the private key 940 are designed as described above for Use Case 2, a single-iteration ZKP scheme can be used.

[0285] In particular, the sender 910 sends to the recipient 930 a request 950 including the sender's public key 920 (public key can be pre-known by the recipient). The recipient 930 generates a challenge variable 960 and sends the challenge variable 960 to the sender 910. In response, the sender 910 generates a digital signature 970 from the challenge variable 960 and the private key 940, resulting in a digital signature 980 to be returned to the recipient as a response of the challenge.

[0286] The recipient 930 then evaluates two mathematical expressions based on (i) the challenge variable 960, (ii) the public key 920 that was received from the sender 910 and (iii) a set of “noise variables” 990. Such noise variables 990 are selected by the recipient 930 at its discretion and without involving the sender 910. The recipient 930 then checks whether the two quantities on both sides of verification equation are identical. If so, the recipient 930 concludes, with a fairly high degree of certainty, that the sender 910 has knowledge of the private key 940, otherwise, the recipient 930 concludes that the sender 910 does not have knowledge of the private key 940.

[0287] To increase the degree of certainty, the recipient 930 can select a new set of noise variables and can again compute the two quantities to see if they are identical. This can be done on the recipient's end as many times as desired, for as many sets of noise variables as required, and without additional interaction with the sender 910.

[0288] Mathematically, Use Case 3 is the same as Use Case 2, but from an application standpoint, the role of x.sub.0 is different. Specifically, it is recalled that for Use Case 2 (digital signature), x.sub.0 is a digital asset to be signed and either explicitly (FIG. 5A) or implicitly (FIG. 5B) accompanies the signature (A, B, C, D, E) sent from the signer 510 to the verifier 550. In Use Case 3 (zero-knowledge proof, see FIG. 9), x.sub.0 represents a challenge variable sent from the recipient 930 to the sender 910, in response to which sender 910 sends the signature (A, B, C, D, E) to the recipient 930 in order to demonstrate that the sender 910 has knowledge of the private key 940. It is noted that the challenge-response need occur only once, and that to increase the degree of confidence that the sender 910 has knowledge of the private key 940, the recipient 930 need simply change the noise variables and re-run the computation (without further challenging or involving the sender 910).

[0289] As such, the ZKP scheme described above may provide a quantum-safe authentication protocol that usable for a wide range of applications including identity authentication in the absence of a trusted third party.

[0290] Accordingly, and with reference to FIG. 11, there has been provided a method 1100 of operating a sender computing apparatus to securely transmit a selected digital asset to a recipient over a data network. As shown at step 1110, the method includes obtaining a public key of the recipient corresponding to a private key of the recipient. As shown at step 1120, the method includes selecting a plurality of noise variables. As shown at step 1130, the method includes computing a plurality of different ciphers from (i) the selected digital asset, (ii) the noise variables and (iii) the public key of the recipient. As shown at step 1140, the method includes transmitting the plurality of ciphers to the recipient over the data network. Of note is the fact that the digital asset is derivable by carrying out a predefined computation involving the plurality of ciphers and the recipient's private key.

[0291] Also, and with reference to FIG. 12, there has been provided a method 1200 of operating a computing apparatus to authenticate a received message purportedly sent by a given sender, the message comprising a digital asset and a digital signature, the digital signature comprising a plurality of data elements. As shown at step 1210, the method includes obtaining a public key of the given sender. As shown at step 1220, the method includes selecting a plurality of noise variables. As shown at step 1230, the method includes computing a plurality of data elements based on the digital asset, the noise variables and the public key of the purported sender. As shown at step 1240, the method includes evaluating whether the computed data elements and the data elements of the digital signature obey a predetermined relationship. As shown at step 1240, in case the predetermined relationship is obeyed, concluding that the message was sent by the given sender, otherwise, concluding that the message was not sent by the given sender.

[0292] Also, and with reference to FIG. 13, there has been provided a method 1300 of operating a computing apparatus to authenticate a received message purportedly sent by a given sender, the message comprising a digital asset and a digital signature, the digital signature comprising a plurality of data elements. As shown at step 1310, the method includes obtaining a public key of the given sender. As shown at step 1320, the method includes selecting a plurality of noise variables. As shown at step 1330, the method includes computing a plurality of data elements based on the digital asset, the noise variables and the public key of the purported sender. As shown at step 1340, the method includes evaluating whether the computed data elements and the data elements of the signature obey a predetermined relationship. As shown at step 1350, in case the predetermined relationship is not obeyed, concluding that the message was not sent by the given sender. As shown at step 1360, in case the predetermined relationship is obeyed the method includes selecting a plurality of new noise variables. As shown at step 1370, the method includes computing a plurality of new data elements based on the digital asset, the new noise variables and the public key of the purported sender. As shown at step 1380, the method includes evaluating whether the computed new data elements and the data elements of the signature obey the predetermined relationship. As shown at step 1390, in the case the predetermined relationship is not obeyed, concluding that the message was not sent by the given sender. As shown at step 1395, in the case the predetermined relationship is obeyed, concluding that the message was sent by the given sender.

[0293] Also, and with reference to FIG. 14, there has been provided a method 1400 of operating a computing apparatus to verify that a given sender has knowledge of a secret, the given sender being associated with a public key. As shown at step 1410, the method includes generating a test data element. As shown at step 1420, the method includes sending the test data element to the given sender. As shown at step 1430, the method includes receiving a response from the sender, the response comprising a digital signature. As shown at step 1440, the method includes selecting a plurality of noise variables. As shown at step 1450, the method includes computing a plurality of data elements based on the test data element, the noise variables and the public key of the given sender. As shown at step 1460, the method includes evaluating whether the computed data elements and the data elements of the digital signature obey a predetermined relationship. As shown at step 1470, in the case the predetermined relationship is obeyed, concluding that the given sender has knowledge of the secret, otherwise, as shown at step 1480, concluding that the given sender does not have knowledge of the secret.

[0294] Also, and with reference to FIG. 15, there has been provided a method 1500 of operating a computing apparatus to verify that a given sender has knowledge of a secret, the given sender being associated with a public key. As shown at step 1510, the method includes generating a test data element. As shown at step 1520, the method includes sending the test data element to the given sender. As shown at step 1530, the method includes receiving a response from the sender, the response comprising a digital signature. As shown at step 1540, the method includes selecting a plurality of noise variables. As shown at step 1550, the method includes computing a plurality of data elements based on the test data element, the noise variables and the public key of the given sender. As shown at step 1560, the method includes evaluating whether the computed data elements and the data elements of the digital signature obey a predetermined relationship. As shown at step 1570, in the case the predetermined relationship is obeyed the method includes selecting a plurality of new noise variables. As shown at step 1580, the method includes computing a plurality of new data elements based on the test data element, the new noise variables and the public key of the given sender. As shown at step 1590, the method includes evaluating whether the computed new data elements and the data elements of the digital signature obey the predetermined relationship. As shown at step 1595, the method includes in case the predetermined relationship is obeyed, concluding that the given sender has knowledge of the secret, otherwise, as shown in step 1598, concluding that the given sender does not have knowledge of the secret.

[0295] The entities referred to above as “sender”, “encryptor”, “recipient”, “signer”, “verifier”, “destination”, “key generation entity” and the like, which carry out the various encryption, decryption, signature, verification and ZKP methods and protocols described above, can be realized by computing apparatuses executing computer-readable program instructions stored on non-transitory computer-readable media. Such computing apparatuses could be any of a smartphone, laptop, desktop computer, tablet, mainframe, vehicle ECU or IoT (Internet-of-Things) device, to name a few non-limiting possibilities.

[0296] With reference to FIG. 10, various elements of a suitable computing apparatus are now described. The computing apparatus 1010 includes a computer-readable storage medium 1020, which can be a tangible device capable of storing program instructions for use by a processor 1030. The computer-readable storage medium 1020 may be, for example, but is not limited to, an electronic storage device, a magnetic storage device, an optical storage device, an electromagnetic storage device, a semiconductor storage device, or any suitable combination of the foregoing. A non-exhaustive list of more specific examples of the computer-readable storage medium 1020 includes the following: a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), a static random access memory (SRAM), a portable compact disc read-only memory (CD-ROM), a digital versatile disk (DVD), a memory stick, a floppy disk, a mechanically encoded device such as punch-cards or raised structures in a groove having instructions recorded thereon, and any suitable combination of the foregoing. A computer-readable storage medium, as used herein, does not include transitory signals per se, such as radio waves or other freely propagating electromagnetic waves, electromagnetic waves propagating through a waveguide or other transmission media (e.g., light pulses passing through a fiber-optic cable), or electrical signals transmitted through a wire.

[0297] The program instructions can be downloaded to the computer-readable storage medium 1020 from an external computer or external storage device via a network 1040, for example, the Internet, a local area network, a wide area network and/or a wireless network. The network 1040 may comprise copper transmission cables, optical transmission fibers, wireless transmission, routers, firewalls, switches, gateway computers and/or edge servers. A network adapter card or network interface 1050 in the computing apparatus 1010 receives program instructions over the network 1040 and forwards them to the computer-readable storage medium 1020 for storage and execution by the processor 1030. Execution of the program instructions by the processor 1030 results in the computing apparatus 1010 carrying out aspects of the present disclosure.

[0298] The program instructions may be assembler instructions, instruction-set-architecture (ISA) instructions, machine instructions, machine dependent instructions, microcode, firmware instructions, state-setting data, or either source code or object code written in any combination of one or more programming languages, including an object oriented programming language such as Smalltalk, C++ or the like, and conventional procedural programming languages, such as the “C” programming language or similar programming languages. In some embodiments, electronic circuitry including, for example, programmable logic circuitry, field-programmable gate arrays (FPGA), or programmable logic arrays (PLA) may execute the program instructions by utilizing state information to personalize the electronic circuitry, in order to carry out aspects of the present disclosure.

[0299] Aspects of the present disclosure are described herein with reference to flowcharts and block diagrams of methods and apparatus (systems), according to various embodiments. It will be understood that each block of the flowcharts and block diagrams, and combinations of such blocks, can be implemented by execution of the program instructions. Namely, the program instructions, which are read and processed by the processor 1030 of the computing apparatus 1010, direct the processor 1030 to implement the functions/acts specified in the flowchart and/or block diagram block or blocks. It will also be noted that each block of the flowcharts and/or block diagrams, and combinations of such blocks, can also be implemented by special purpose hardware-based systems that perform the specified functions or acts or carry out combinations of special purpose hardware and computer instructions.

[0300] The flowcharts and block diagrams illustrate the architecture, functionality, and operation of possible implementations of systems, methods, and computer program products according to various embodiments of the present disclosure. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of instructions, which comprises one or more executable instructions for implementing the specified logical function(s). In some alternative implementations, the functions noted in the block may occur out of the order noted in the drawings. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved.

[0301] The descriptions of the various embodiments of the present disclosure have been presented for purposes of illustration and are not intended to be exhaustive or limited to the embodiments disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments. The terminology used herein was chosen to best explain the principles of the embodiments, the practical application or technical improvement over technologies found in the marketplace, or to enable others of ordinary skill in the art to understand the embodiments disclosed herein.

[0302] It should be appreciated that throughout the specification, discussions utilizing terms such as “processing”, “computing”, “calculating”, “determining”, “analyzing” or the like, can refer to the action and/or processes of a computer or computing system, or similar electronic computing device, that manipulate and/or transform data represented as physical, such as electronic, quantities into other data similarly represented as physical quantities.

[0303] As used herein, unless otherwise specified, the use of the ordinal adjectives “first”, “second”, “third”, etc., to describe a common object or step, merely indicate that different instances of like objects or steps are being referred to, and are not intended to imply that the objects or steps so described must be in a given sequence, either temporally, spatially, in ranking, or in any other manner.

[0304] It is noted that various individual features may be described only in the context of one embodiment. The particular choice for description herein with regard to a single embodiment is not to be taken as a limitation that the particular feature is only applicable to the embodiment in which it is described. Various features described in the context of one embodiment described herein may be equally applicable to, additive, or interchangeable with other embodiments described herein, and in various combinations, groupings or arrangements. In particular, use of a single reference numeral herein to illustrate, define, or describe a particular feature does not mean that the feature cannot be associated or equated to another feature in another drawing figure or description.

[0305] Also, when the phrase “at least one of A and B” is used, this phrase is intended to and is hereby defined as a choice of A or B or both A and B, which is similar to the phrase “and/or”. Where more than two variables are present in such a phrase, this phrase is hereby defined as including only one of the variables, any one of the variables, any combination of any of the variables, and all of the variables.

[0306] The foregoing description and accompanying drawings illustrate the principles and modes of operation of certain embodiments. However, these embodiments should not be considered limiting. Additional variations of the embodiments discussed above will be appreciated by those skilled in the art and the above-described embodiments should be regarded as illustrative rather than restrictive. Accordingly, it should be appreciated that variations to those embodiments can be made by those skilled in the art without departing from the scope of the invention.