Patent ID: 12192318

The drawings are intended to aid in understanding certain aspects of the disclosure and are not intended to be limiting.

DETAILED DESCRIPTION

With reference toFIG.1, there is shown a system2that is a practical application of certain described methods of generating and using a highly secure cryptographic key pair in an asymmetric cryptography scenario. The cryptographic key pair comprises a “public key”40and a corresponding “private key”50generated in accordance with a pre-determined computing process that may be carried out by a key generation server15. The cryptographic key pair is used for secure communications between an encryption server10and a recipient server20. In a non-limiting embodiment, one or both of the encryption server10and the recipient server20may be a mobile device or a laptop/desktop computer communicating over a data network60which may traverse the Internet and may include one or more wireless networks. It is wroth noting that certain embodiments achieve NIST Level I, Level III or even Level V security yet the number of bits taken up by the public and private (secret) keys is small, which makes the current approach more suitable than existing approaches where tolerance to latency is low, where bandwidth may be low, where little computational power may be available and/or where computer memory/storage may be at a premium.

The encryption server10may comprise a user interface110for interfacing with a user6. The user interface110may be a graphical user interface110and may be configured to elicit information from the user (e.g., through a keyboard or a touchscreen) and to exhibit information for the user, e.g., through a display.

The encryption server10is configured to encrypt a digital asset30into an encrypted message (also referred to as a ciphertext)70using the recipient's “public key”40(stored in a memory of the encryption server10). In various non-limiting embodiments, the digital asset30may be a file, a document or a cryptographic key (such as may be used for subsequent encryption of another digital asset). The recipient's public key40can be made available (e.g., distributed or transmitted over the Internet or another data network or combination of networks) to entities (such as the encryption server10) who wish to securely communicate with the recipient server20. The recipient server20applies a decryption technique to the encrypted message70using the recipient's “private key”50, in order to recover the digital asset30. The recipient's private key50may be stored in a memory at the recipient server20and be withheld from other entities such as the encryption server10.

Due to generation of the key pair40,50based on a specific computing process and the use of “noise variables” (as will be described herein below) in the generation of the keys by the encryption server15, the private key50is extremely difficult to obtain from the public key40, even after observing multiple encrypted messages70encrypted with the same public key40. This makes the present encryption scheme highly secure. Also, the operations according to which the digital asset30is encrypted into the encrypted message70and according to which the digital asset30is decrypted/recovered from the encrypted message70are of relatively low computational complexity and relatively low latency.

Generation of Key Pair

FIG.2shows steps in a key generation process (KGP)200for determining the components (data elements) of the recipient's private and public keys, in accordance with a non-limiting embodiment. In one embodiment, the key generation process200may be carried out by executing computer-readable instructions stored in the memory of the same computing apparatus as implements the recipient server20. In another embodiment, the key generation process200may be carried out by the key generation server15by executing computer-readable instructions in a memory of the key generation server15. The key generation server15may be a separate third-party computing apparatus that publishes (or otherwise renders available) the recipient's public key40over the data network60(e.g., to the encryption server10). The key generation server15may also be configured to provide for secure delivery of the recipient's private key50to the recipient server20(e.g., via out-of-band delivery, i.e., not over the data network60, although there is nothing form a technological standpoint to prevent delivery of the private key50to the recipient server20over the data network60).

The steps in the key generation process200include various sub-steps, and not all steps or sub-steps need be performed in the order described.

Step210:

The key generation process includes obtaining from memory an integer p for modulo arithmetic. The integer p can be stored in computer memory using log2p bits. In various embodiments, p can require 6, 8, 10, 12, 14, 16 or more bits. Although in some embodiments, it may be preferable that p be prime, it need not be in all cases. In the following, φ(·) represents Euler's totient function and therefore φ(p) equals the totient function of p. Furthermore, all computations described below are performed as modulo p (“mod p”) unless otherwise indicated. A modulo computation is an arithmetic operation performed in a computer that finds the remainder when a first integer is divided by a second integer, thus limiting the result to between 0 and one less than the second integer.
Step220:The key generation process200includes obtaining from memory a set of data elements that define coefficients of a multivariate base polynomial B(x0, x1, . . . , xm) of order n. In some embodiments, n can be pre-selected and stored in the memory of the key generation server15. 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. Typically, the greater the value of n, the more secure the system2will be.The multivariate base polynomial B(x0, x1, . . . , xm) can be expressed as:
B(x0,x1, . . . ,xm)=Σi=0nΣj=1mbijxjx0i
=Σj=1mBj(x0)xjwhereBj(x0)=Σi=0nbijx0i(j=1,2, . . . ,m).The coefficients of multivariate base polynomial B(x0, x1, . . . , xm) can thus include the coefficients bijfor (i=0, 1, 2, . . . , n) and for (j=1, 2, . . . , m), which can be stored in the memory of the key generation server15.Each Bj(x0), j=1, 2, . . . , m, is a univariate polynomial in the variable x0, and x1. . . , xmcan be referred to as “noise variables” (or permutation data elements), of which there are m. The multivariate base polynomial B(x0, x1, . . . , xm) can therefore be considered a linear combination of m univariate polynomials Bj(x0), j=1, 2, . . . , m, with the coefficients of the linear combination corresponding to the noise variables x1. . . , xm.As will be shown later on, these noise variables x1. . . , xm, whose values are selected at runtime by the encryption server10, add to the security of the encryption process (to be described herein below with reference toFIG.3).The value of m (i.e., the number of noise variables) is a secure parameter that can be arbitrarily set to any positive integer based on the security level, 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 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 or higher.The values of m and n may be stored in the memory of the key generation server15.
Step230:The key generation process200includes choosing the coefficients of a pair of entanglement polynomials f(·) and h(·) of degree λ:
f(x0)=Σi=0λfix0i
h(x0)=Σi=0λhix0iBy keeping the order of each of the entanglement polynomials f(·) and h(·) relatively low (such as by keeping λ equal to 1, 2 or 3, for example), these polynomials have analytically derivable roots, which will be useful as will be shown later on. The value of λ may be stored in the memory of the key generation server15.The values of the fiand the hi(i=0, 1, 2, . . . , λ) can be chose arbitrarily such as from the output of a pseudo-random number generator16implemented by the key generation entity15. The values are selected over the finite field GF(p), which is a prime finite field GF(p) if p is prime.
Step240:The key generation process200includes constructing a pair of product polynomials, P(x0, x1, . . . , xm) and Q(x0, x1, . . . , xm), by multiplying the base polynomial B(x0, x1, . . . , xm) with the univariate entanglement polynomials f(·) and h(·), respectively:
P(x0,x1, . . . ,xm)=B(x0,x1, . . . ,xm)f(x0)=Σj=1mPj(x0)xj, wherePj(x0)=Σj=1mxjΣi=0n+λpijx0iand
Q(x0,x1, . . . ,xm)=B(x0,x1, . . . ,xm)h(x0)=Σj=1mQj(x0)xj, whereQj(x0)=Σj=1mxjΣi=0n+λqijx0i,
and where
pij=Σs+t=ifsbtj
qij=Σs+t=ihsbtj.
Step250:The key generation process200includes creating the recipient's public key40, as will now be described according to one of two options: Option A (homomorphic encryption of “noise functions”) or Option B (homomorphic encryption of product polynomials). Option A and Option B represent different levels of security. These can be chosen by the user6at runtime via the user interface of the encryption server10, in which case both options may be made available ahead of time by the encryption server10.
Option A (Homomorphic Encryption of “Noise Functions”)
Step252A:The key generation process200may be configured to create two noise functions:a first noise function N0(x1. . . , xm)=Σj=1mb0jxjmod p; anda second function Nn(x0, x1. . . xm)=Σj=1mbnjxjx0n+λmod p.
Step254A:The key generation process200then chooses a number S with a bit length ls>=2*log2p+log2m as a modulus for homomorphic encryption. S can be randomly generated (e.g., as the output of the pseudo random number generator16), as long as it obeys the aforementioned constraint that the number of bits needed to express S is at least as great as the sum of twice the number of bits needed to express p and the number of bits needed to express m. In a practical example, if p is a 64-bit value in memory (i.e., needs 64 bits to be represented) and m is an 8-bit value in memory, then the modulus S should be represented using at least 2*64+8=136 bits.
Step256A:The key generation process200may then apply homomorphic encryption to the noise functions, as follows:Choose 2 random numbers R0and Rnas encryption keys for homomorphic encryption and GCD(R0,S)=1 and GCD(Rn,S)=1, i.e., both R0and Rnare coprime with the chosen modulus S. These two random numbers may be produced by the PRNG16, as long as they obey the aforementioned constraints of being coprime with the modulus S.Homomorphically encrypt the first and second noise functions:
N′0(x1, . . . ,xm)=Σj=1m(R0b0jmodS)xj=Σj=1mN0jxj
N′n(x0,x1, . . . ,xm)=Σj=1m(RnbnjmodS)xjx0n+λ=Σj=1mNnjxjx0n+λHomomorphic encryption performs computations on encrypted data without first decrypting it, with the resulting computations being left in an encrypted form and which, when decrypted, result in an identical output to that produced had the operations been performed on the unencrypted data.In particular, the above homomorphic encryption at step256A maps both noise functions to a hidden ring marked by the secret modulo S, as appropriate. A hidden ring means that the largest Integer in the ring (S) is hidden from the encryption server10, the ring being a set equipped with two binary operations satisfying properties analogous to those of addition and multiplication of integers.It is recalled that S is known only to the key generation server15(i.e., it is not known to the encryption server10), and also R0and Rnare also hidden from the encryption server10. As such, an attacker72would only be able to access c=(R0*a)mod S. In order to know the value of “a”, the attacker must know R0and S. The attacker72would need to brute force the ring for both R0and S with a condition GCD(R0, S)=1, which is computationally difficult.
Step258A:The encryption server15then creates a data structure in the memory that includes the recipient's public key40. The data structure for the recipient's public key40may be populated by the following data elements:a. the coefficients of P(x0, x1, . . . , xm) from step240but without the i=0 and i=n+λ terms, i.e., the coefficients of Σj=1mxjΣi=1n+λ−1pijx0ib. the coefficients of Q(x0, x1, . . . , xm) from step240but without the i=0 and i=n+λ terms, i.e., the coefficients of Σj=1mxjΣi=1n+λ−1qijx0ic. the coefficients of the homomorphically encrypted first noise function N′0(x1, . . . , xm)d. the coefficients of the homomorphically encrypted second noise function N′n(x0, x1, . . . , xm)
Option B (Homomorphic Encryption of Product Polynomials)
Step254B:The key generation process200includes choosing two values Spand Sqwith a bit length ls>=2*log2p+log2[m(n+λ+1)] as a modulus for homomorphic encryption. Spand Sqcan be randomly generated, such as the output of a pseudo-random number generator. Spand Sqcan be randomly generated (e.g., as the output of the pseudo random number generator16), as long as they obey the aforementioned constraint that the number of bits needed to express Spand Sqis at least as great as the sum of twice the number of bits needed to express p and the number of bits needed to express the product of m(n+λ+1).
Step256B:The key generation process200applies homomorphic encryption as follows:Choose 2 random numbers Rpand Rqas encryption keys for homomorphic encryption and GCD(Rp,Sp)=1 and GCD(Rq,Sq)=1, i.e., Rpand Rqare coprime with the chosen modulus.Compute the following:
P′(x0,x1, . . . ,xm)=[RpP(x0,x1, . . . xm)]modSp
=Σj=1mxjΣi=0n+λ[(RppijmodSp)]x0i
=Σj=1mΣi=0n+λp′ijx0ixj
Q′(x0,x1, . . . ,xm)=[RqQ(x0,x1, . . . xm)]modSq
=Σj=1mxjΣi=0n+λ[(RqqijmodSq)]x0i
=Σj=1mΣi=0n+λq′ijx0ixj
Step258B:The key generation process200is then configured to form the recipient's public key40is by assembling the following data elements:a. the coefficients of P′(x0, x1, . . . , xm)=Σj=1mΣi=0n+λp′ijx0ixjb. the coefficients of Q′(x0, x1, . . . , xm)=Σj=1mΣi=0n+λq′ijx0ixjThe recipient's public key can thus be represented by matrices P′[n+λ+1, m] and Q′[n+λ+1, m] with elements over the ring Z/SZ, with integers from 0 to Sp−1 or Sq−1 as appropriate.

In either case (option A after execution of steps252A,254A,256A,258A or option B after execution of steps254B,256B,258B), the key generation process200returns to the main branch of the flowchart inFIG.2.

Step260:

The encryption server15then creates a data structure in the memory that includes the recipient's private key50. The data structure for the recipient's private key50may be populated by the following data elements:a. the coefficients of f(·) (i.e., f0, f1, . . . , fλ);b. the coefficients of h(·) (i.e., h0, h1, . . . , hλ); andc. S and R0and Rn(under option A/step260A) or Sp, Sq, Rpand Rq(under option B/step260B)
Step270:The key generation process200may cause the recipient's private key50to be securely stored in a memory of the recipient server20. For example, the key generation server15may communicate the recipient's private key50to the recipient server20over the data network60, over another network that is not the data network60or over an out-of-band connection. In another embodiment, the key generation process200is carried out by the recipient server20itself. The key generation process200may also cause the recipient's public key40to be made available to would-be encryptors such as the encryption server10. This can be done by sending the public key40to the encryption server10over the data network60or sending the public key40to a key server17, which may be a web server17reachable over the data network60. The key server17may store a database17A in which a network address of the recipient server20(e.g., an internet address or URL) is associated with the recipient's public key40. In this way, the recipient's public key40can be accessible to entities such as the encryption server10. However, the recipient's private key50remains withheld from the encryption server10, is kept secret and is not made available over the data network60.
Data Encryption

Armed with the recipient's public key40as defined above, the encryption server10may perform an encryption process300in accordance with a non-limiting embodiment, now described with reference toFIG.3. The steps in the encryption process300include various sub-steps, and not all steps or sub-steps need be performed in the order described.

Step310:

The encryption server10determines a digital asset x0. In one embodiment, the digital asset x0may be retrieved from the memory120of the encryption server10. In such a scenario, the digital asset x0may comprise a file, image, video, cryptographic key or other data element stored in a non-transitory medium. Such data element may represent a document, transaction, financial instrument or other information of value to the user. In another embodiment, the digital asset x0may be obtained from the user6by the user providing the digital asset via the user interface110, such as a graphical user interface. In such a scenario, the digital asset x0may comprise credentials such as a username, password, social insurance number or other information that the user wishes to transmit to the recipient server in secrecy.In an embodiment, the digital asset x0is restricted to be converted to or represented by an integer value from 1 to p−1. It is recalled that p can be expressed using a certain number of bits, such as 8, 16, 32, 64 or more (or any number of bits in between, depending on operational considerations). The value of p is known to the encryption server10and may be stored in the memory120. It is noted that for the integer p to be known to the encryption server10, the integer p can be part of the recipient's public key40or it can be a known security parameter (i.e., known to the encryption server10and other participants in the system). The integer p may be odd or even, prime or compound. In some cases, it may be preferable for p to be a prime for security considerations. For example, if p is represented using b bits, then p could be the largest prime less than 2b. An example is the largest prime number of a 64-bit field (which is p=264−59=18,446,744,073,709,551,557). Taking p as a prime, particularly a large prime, might improve the performance for key generation.
Step330:The encryption server10obtains the recipient's public key40which. As mentioned above, the recipient's public key40is different for Option A and for Option B. The choice between Option A and Option B may be part of the encryption process300. Specifically, the encryption process may provide via the GUI110an opportunity for the user6to select between Option A (high security) and Option B (higher security). As such, based on the input received via the user interface110, the encryption process300determines whether to use the recipient's public key40for Option A or for Option B. In other embodiments, the choice of Option A or Option B is pre-determined without user input. In still other embodiments, the encryption server10is configured to only carry out the encryption process400for Option A or for Option B.It is noted that for Option A, the public key40comprises:the coefficients pijwithout the i=0 and i=n+λ termsthe coefficients qijwithout the i=0 and i=n+λ termsthe coefficients N0jthe coefficients NnjAs for Option B, the public key40comprises:the coefficients p′ijthe coefficients q′ij
Depending on the Option:
OPTION A:—Homomorphically Encrypted Noise Functions Only
Step320A:The encryption server10chooses m noise variables x1, . . . , xm, which are generated mod p, i.e., from 1 to p−1. For example, these could be random numbers such as may be output from a pseudo-random number generator (PRNG)130, and in some embodiments this may indeed be preferable. In other cases, the noise variables x1, . . . , xmare randomly chosen by the encryption server/module10and they need not be committed to memory. In a further embodiment, the PRNG130operates based on a seed provided or triggered by the system timer.
Step340A:The encryption server10computes the following quantities, based on the digital asset x0and the recipient's public key40:
P′=Σj=1mΣi=1n+λ−1pijxjx0imodpa.
Q′=Σj=1mΣi=1n+λ−1qijxjx0imodpb.
N′0=N0(x1, . . . ,xm)=Σj=1mN0jxjc.
N′n=Nn(x0,x1, . . . ,xm)=Σj=1mNnj(xjx0n+λmodp)  d.The data elementsP′,Q′,N′0,N′ncan be stored in a data structure in the memory120of the encryption server10. The encryption server10may create a ciphertext70containing data elementsP′,Q′,N′0,N′n(which also can be referred to as a “ciphertext tuple”).
OPTION B: Homomorphically Encrypted Product Polynomials—No Use of Noise Functions
Step320B:The encryption server/module10chooses m noise variables x1, . . . , xm, which are generated mod p, i.e., from 1 to p−1. For example, these could be random numbers such as may be output from a pseudo-random number generator (PRNG)130, and in some embodiments this may indeed be preferable. In other cases, the noise variables x1, . . . xmare randomly chosen by the encryption server/module10and they need not be committed to memory. In a further embodiment, the PRNG130operates based on a seed provided or triggered by the system timer.
Step340B:The encryption server/module10computes the following quantities, based on the digital asset x0and the recipient's public key40:
P′=Σj=1mΣi=0n+λp′ij(xjx0imodp); and  a.
Q′=Σj=1mΣi=0n+λq′ij(xjx0imodp).  b.The data elementsP′,Q′ can be stored in a data structure in the memory120of the encryption server10. The encryption server10creates a ciphertext70containing data elementsP′ andQ′ (which can also be referred to as a “ciphertext tuple”). It is noted that the ciphertext tuple has two integers with a bit length>log2S.
In Either Case (Option A or Option B), the Encryption Process300now Returns now to the Main Branch of the Flowchart:
Step350:The encryption server10sends the ciphertext70containing the appropriate “ciphertext tuple” (whose composition depends on the chosen option) to the recipient server20. This can be done by sending a packet over the data network160via the network interface150. The packet may have a destination address an address of the recipient server20. On its way from the encryption server10to the recipient server20, the packet including ciphertext70may traverse the data network60(e.g., the Internet) and other networks.
Decryption Using Private Key

In order to decrypt the digital asset x0, the recipient server20may perform a decryption process400in accordance with a non-limiting embodiment, now described with reference toFIG.4. The recipient server20stores in its memory22the private key50corresponding to the public key40used by the encryption server10, as previously received from the key generation entity15. The steps in the decryption process400include various sub-steps, and not all steps or sub-steps need be performed in the order described.

Step410:

The decryption process400includes a step of receiving the ciphertext70containing the appropriate ciphertext tuple70which consists ofP′,Q′,N′0, andN′n(if option A was chosen) or justP′ andQ′ (if option B was chosen). The ciphertext70may be received over a network interface24through which the recipient server20is connected to the data network60. It is recalled that the choice of Option A or Option B may be made at the encryption server10and in some cases may be selected y the user60via the user interface110. As such, the choice of Option A or Option B may accompany the packet that carries the ciphertext70from the encryption server10. Specifically, this packet may include a flag that informs the recipient server20as to whether Option A or Option B was selected. In other embodiments, the recipient server20knows which option is applicable based on the fact that it knows ahead of time that the encryption server10is implementing Option A or Option B. In still further examples, a second user66may inform the recipient server20via a user interface26as to the selection of Option A or Option B.
Option A—Homomorphic Encryption of Noise Functions Only, Ciphertext Tuple70Consists ofP′,Q′,N′0andN′n
Step420A:The decryption process400comprises computing the following variables (which can include intermediate quantities V1and V2) based on the data elements of the received ciphertext tuple70(P′,Q′,N′0, andN′n) and based on some of the data elements of the private key50held in memory22by the recipient server20(certain examples being: f0, fλ, h0, hλ, R0, Rnand S).
N0=(R0−1N′0modS)modp
Nn=(Rn−1N′nmodS)modp
V1=f0N0+P′+fλNn
V2=h0N0+Q′+hλNn
Option B—Homomorphic Encryption of Noise Functions Only, Ciphertext Tuple70Consists ofP′ andQ′
Step420B:The decryption process400includes computing the following variables V1and V2based on the data elements of the received ciphertext tuple70(P′ andQ′) and based on some of the data elements of the private key50held in the memory22by the recipient server20(certain examples being: Rp, Rq, and Spand Sq):
V1=[(Rp−1P′)modSp]modp
V2=[(Rp−1Q′)modSq]modp
In Either Case (Option A or Option B), the Encryption Process400now Returns now to the Main Branch of the Flowchart:
Step430:The encryption process400includes the step of using the processor to solve the following equation for x:

(V⁢1V⁢2⁢mod⁢p)⋆h⁡(x)-f⁡(x)=0.It is recalled that the coefficients of the univariate entanglement polynomials f(·) and of h(·) are part of the recipient's private key50stored in memory22and therefore are known to the recipient server20.Since each of f(·) and h(·) is of relatively low order (e.g., λ=1, 2 or 3), the above equation is also of the same order and has derivable roots with radicals, simplifying analytical root derivation.Therefore, in one embodiment, the roots can be computed based on an analytical derivation, whereas in another embodiment, the roots are computed purely numerically.

Those skilled in the art will appreciate that steps420A/B and430may be collapsed into a single arithmetic expression involving the plurality of ciphers (data elements of the ciphertext70) and the data elements of the private key50, which is then solvable using the processor28.

Specifically, steps420A and430can be reduced to solving for x in the equation:
[(f0(R0−1N′0modS)+P′+fλ(Rn−1N′nmodS))/(h0(R0−1N′0modS)+Q′+hλ(Rn−1N′nmodS))]*h(x)−f(x)=0 modp
whereP′,Q′,NN′0andN′ncorrespond to the data elements in the received ciphertext70, and R0, Rnand S are data elements of the private key50. The aforementioned equation is solved for x using the processor28.

Similarly, steps420B and430can be reduced to solving for x in the equation:
[(Rp−1P′ modSp)/(Rq−1Q′ modSq)]*h(x)−f(x)=0 modp

whereP′ andQ′ correspond to data elements in the received ciphertext70, and Rp, Rq, Spand Sqare data elements of the private key50. The aforementioned equation is solved for x using the processor28.

In both of the above cases, f(·) is the first entanglement function defined by coefficients f0, f1, . . . fλincluded in the private key50stored in the memory22and h(·) is the second entanglement function defined coefficients h0, h1, . . . hλincluded in the private key50stored in the memory22.

It should also be appreciated that the values of m, n and p are predetermined and known to the encryption server10and the recipient server20for the purposes of a given instantiation of the encryption process300and the decryption process400.

Step440:

Decryption is now complete: the recipient server20assigns the solution to above equation (which should be an integer) to the digital asset x0(which was the subject of the encryption process300). The decrypted digital asset x0can be communicated to the second user66via the user interface26(which can be a graphical user interface). In another embodiment, the decrypted digital asset x0can be packaged in a message sent over a data network (such as the data network60). In yet another embodiment, the decrypted digital asset x0can be stored in the non-transitory memory22.
Explanation

Consideration is now given to explaining why it is the case that a root of the above equation (step430) corresponds to the digital asset x0.

Option A

It is recalled that:V1was defined as f0N0+P′+fλNnandV2was defined as h0N0+Q′+hλNn, where
N0=[(R0−1N′0modS)modp],
Nn=[(Rn−1N′nmodS)modp],

BecauseP′=Σj=1mΣi=1n+λ−1pijxjx0imod p (see step340A) and because of the above definitions ofN′0andN′nit follows that the aforementioned quantity V1is actually equal to P(x0, x1, . . . , xm)=B(x0, x1, . . . , xm)f(x0).

BecauseQ′=Σj=1mΣi=1n+λ−1qijxjx0imod p (see step340A) and because of the above definitions ofN′0andN′n, it follows that the aforementioned quantity V2is actually equal to Q(x0, x1, . . . xm)=B(x0, x1, . . . , xm)h(x0).

Option B

It is recalled that:V1was defined as [(Rp−1P′)mod Sp] mod pV2was defined as [(Rq−1Q′)mod Sq] mod p

BecauseP′=Σj=1mΣi=0n+λp′ij(xjx0imod p) (see step340B) and because q′ij=(Rppijmod Sp) (see step264B), it turns out that the aforementioned quantity V1is actually equal to P(x0, x1, . . . xm)=B(x0, λ1, . . . , λm)f(x0).

Similarly, becauseQ′=Σj=1mΣi=0n+λq′ij(xjx0imod p) (see step340B) and because q′ij=(Rpqijmod Sq) (see step264B), it turns out that the aforementioned quantity V1is actually equal to Q(x0, x1, . . . , xm)=B(x0, x1, . . . , xm)h(x0).

Conclusion for Both Options

Therefore, for either option A or option B, when computing the ratio of V1to V2at step430, it is the same as computing the ratio of P(x0, x1, . . . , xm) to Q(x0, x1, . . . , xm). In other words:

V⁢1V⁢2=P⁡(x0,x1,…,xm)Q⁡(x0,x1,…,xm).

Now, recalling (from step220) that P(x0, x1, . . . , xm) was defined as B(x0, x1, . . . , xm)f(x0) and Q(x0, x1, . . . , xm) was defined as B(x0, x1, . . . , xm)h(x0), one has:

P⁡(x0,x1,…,xm)Q⁡(x0,x1,…,xm)=f⁡(x0)h⁡(x0)

Therefore, from the above two equations, one has:

V⁢1V⁢2=f⁡(x0)h⁡(x0)⁢mod⁢p.

This further yields:

V⁢1V⁢2*h⁡(x0)-f⁡(x0)=0.

As a result, x0is the solution to (or, of there is more than one solution, is one of the solutions to):

V⁢1V⁢2⋆h⁡(x)-f⁡(x)=0.

With f(x) and h(x) being of order no more than 3, it may be possible to derive roots without requiring significant computational effort on the part of the recipient server20, yet it is extremely difficult for a malicious entity72to determine this root without the recipient's private key50.

Of course, it is possible to derive roots numerically, which can be done for lambda greater than 3 as well.

Disambiguation

There are instances where the above equation has an integer-valued root and one or more other real-valued roots (for example, one other real root if the equation at step430is a quadratic in x, one or two other real roots if it is a cubic). In that case, the integer-valued root is assigned to the digital asset x0because it is known that x0is an integer.

There are also instances where the above equation has more than one integer-valued real solution (for example, two real roots if the equation at step430is a quadratic, two or three real roots if it is a cubic). In that case, it may not be possible for the recipient server20to know which one to assign to the digital asset x0without further information. To this end, and with additional reference toFIG.6, the encryption server10stores a flag602in the memory120. The flag602(for example, a predetermined code such as a message authentication code (MAC)) may be received by the encryption server10from the key generation server15over the data network60, possibly together with the recipient's public key40. Additionally, the flag602is stored in the memory22of the recipient server20. As such, the key generation server15may be configured to transmit the flag602to the recipient server20, which can be done possibly over the data network60(or out of band), and possibly together with the recipient's private key50.

The encryption process200is configured to append the flag602to the digital asset x0prior to encryption, e.g., prior to step340A (for Option A) or step340B (for Option B). This results in an augmented digital asset x0*=x0|602. Moreover, step340A (or340B) is performed with x0* rather than the original version of the digital asset x0. As such, the resulting ciphertext (denoted70*) will be different from the ciphertext70produced based on the original digital asset x0.

At the recipient server20, steps410,420A/420B and430of the decryption process400are executed, which will reveal one of several possible roots, only one of which will be x0*=x0|602. Since the decryption process400knows the value of the flag602, the decryption process400can call a disambiguation sub-process410that identifies which of the candidate solutions includes the flag602. The remainder of this identified solution is returned by the disambiguation process410and is assigns the value of the remainder to the digital asset x0. In this way, the one root/solution that passes the disambiguation sub-process410is then considered to be the digital asset. The disambiguation sub-process410may be encoded as computer-readable instructions stored in the memory22and executed by the processor28, potentially under control of the decryption process400.

In another embodiment, instead of using a predetermined flag602that is known to the encryption server10and the recipient server20, the encryption server10produces a checksum from the digital asset x0. The checksum could be an XOR of the various bits that make up the digital asset x0. Since the checksum is generated from the digital asset x0itself, it need not be stored in or received from the key generation server15, and it need not be shared with the recipient server20. In this embodiment, the encryption process200is configured to append the checksum to the digital asset x0prior to encryption, e.g., prior to step340A (for Option A) or step340B (for Option B). This results in an augmented digital asset x0**=x0|checksum. Moreover, step340A (or340B) is performed with x0** rather than the original version of the digital asset x0. As such, the resulting ciphertext will be different from the ciphertext70or from ciphertext70*.

At the recipient server20, steps410,420A/420B and430of the decryption process400are executed, which will reveal one of several possible roots, only one of which will be x0**=x0|checksum. The decryption process400can again call the disambiguation sub-process410which, in this embodiment, performs the checksum on the portion of each solution that could potentially correspond to the digital asset x0and compares it to the portion of each solution that potentially corresponds to the checksum. The correct solution (and assigned to the value of the digital asset x0) is the one for which there is a match between the computed checksum and the data element occupying the checksum position.

Security Analysis

Option A

Without knowledge of R0, Rnand S over a ring Z/SZ, the public key40is not helpful to a malicious party72trying to crack the private key50. The modular arithmetic computations cannot be performed without knowing S. The brute force complexity of the triple {R0, Rn, S} is more than O (p4−mn+3m=2λ−2mλ), using Big-O notation. As such, even relatively small bit sizes for p (e.g., 16, 32 or 64) make the computational complexity required to crack the private key50prohibitive.

The table below shows possible parameter values log2p (i.e., number of bits for p), n, λ and m, expressed as a quadruple (_,_,_,_), to achieve various NIST (National Institute of Standards and Technology of the U.S. Department of Commerce) security levels for Option A.

SecuritySecuritySecurityOption ALevel ILevel IIILevel V(log2p, n, λ, m)(64, 1, 1, 5)(64, 1, 1, 6)(64, 1, 1, 7)

The security levels are described by NIST as follows:Level I: At least as hard to break as AES128 (exhaustive key search)Level: II At least as hard to break as SHA256 (collision search)Level III: At least as hard to break as AES192 (exhaustive key search)Level IV: At least as hard to break as SHA384 (collision search)Level V: At least as hard to break as AES256 (exhaustive key search)

Those skilled in the art will obtain more information about these security levels at nist.gov and/or in a paper entitled “NIST PQC Standardization Update” by Dustin Moody, September 2020, available at https://csrc.nist.gov/CSRC/media/Presentations/pqc-update-round-2-and-beyond/images-media/pgcrypto-sept2020-moody.pdf, hereby incorporated by reference herein.

FIG.7shows a comparison of private key (or secret key), public key and ciphertext sizes for various encryption methods including a non-limiting embodiment of Option A. It is seen that Option A uses a significantly smaller number of total bits for the keys and the ciphertext than any of McEllice, Kyber, NTRU or Saber for the same NIST level of security. This allows Option A to achieve outstanding security performance with shorter data elements and a smaller memory footprint, allowing better compatibility with devices that have lower computational power and/or smaller memory storage and/or have lower toleration to latency (i.e., are sensitive to real-time responses).

Option B

Without knowledge of Rp, Rq, Spand Sqover a ring Z/SZ, the public key40is not helpful to a malicious party72trying to crack the private key50. The modular arithmetic computations cannot be performed without knowing Spand Sq. The brute force complexity of the quadruple {Rp, Rq, Sp, Sq} is more than O(Sp4){tilde over ( )}O(Sq4){tilde over ( )}O(p8), using Big-O notation. As such, even relatively small bit sizes for p (e.g., 16, 32 or 64) make the computational complexity required to crack the private key50prohibitive. It is noted that in some embodiments of Option B, Spmay be set equal to Sq.

In particular, the applicable attacking strategy is to extract plaintext from HPPK ciphertextsP′ andQ′ by solving the following equations:
P′=Σj=1mΣi=0n+λp′ij(xjx0imodp)==Σj=1mΣi=0n+λp′ijvjj
Q′=Σj=1mΣi=0n+λq′ij(xjx0imodp)==Σj=1mΣi=0n+λq′ijvjj

With unknown variables vij=(xjx0imod p) defined over GF(p) for i=0, 1, . . . , λ and j=1, 2, . . . , m, the total number of unknown variables is m(n+λ+1). Due to unknown modulus (S, or Spand Sq), possible modular arithmetic calculations are restricted so the better strategy is to perform modulo p to above two equations:
P′=Σj=1mΣi=0n+λp″ijxjx0i
Q′=Σj=1mΣi=0n+λq″ijxjx0i
With p″ij=p′ijmod p and q″ij=q′ijmod p, so one has two equations with m+1 variables (namely x0, x1, . . . , xm). Using Gaussian elimination, one can easily reduce these two equations into a general form:
G(x0,x1, . . . ,xm−1)=0 modp.

This is a modular Diophantine Equation problem. Such a Diophantine equation problem is NP-complete with a complexity only O(pm−1). Therefore, the overall complexity of this technique is O(pm−1).

More specifically, for recovery of x0, the modular Diophantine Equation with m noise variables produces pm−1solutions of (x, x1, . . . , xm), with each possible x being equally likely found with a probability 1/p. For NIST level V of 256 bits, p would be 64 bits. As for recovery of the private key50, Option B requires the attacker to brute force minimum (Rp, Sp) and (Rq, Sq) with a complexity O(p4+o(1)).

The table below shows possible parameter values log2p (i.e., number of bits for p), n, λ and m, expressed as a quadruple (_,_,_,_), to achieve various NIST security levels for Option B.

SecuritySecuritySecurityOPTION BLevel ILevel IIILevel V(log2p, n, λ, m)(32, 1, 1, 2)(48, 1, 1, 2)(64, 1, 1, 2)(log2p, n, λ, m)(32, 1, 1, 3)(48, 1, 1, 3)(64, 1, 1, 3)

FIG.8shows a comparison of private key, public key and ciphertext sizes for various encryption methods including two non-limiting embodiments of Option B. It is seen that Option B uses a significantly smaller number of total bits for the keys and the ciphertext than any of McEllice, Kyber, NTRU or Saber for the same NIST level of security. This allows Option B to achieve outstanding security performance with shorter data elements and a smaller memory footprint, allowing better compatibility with devices that have lower computational power and/or smaller memory storage and/or have lower toleration to latency (i.e., are sensitive to real-time responses).

Those skilled in the art will appreciate that the entities referred to above as “sender”, “encryptor”, “recipient”, “destination”, “key generation entity” and the like, which carry out the various encryption and decryption 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.

The encryption server10includes a computer-readable storage medium120, which can be a tangible device capable of storing program instructions for use by a processor140. The computer-readable storage medium120may 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 medium120includes 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.

The program instructions can be downloaded to the computer-readable storage medium120from an external computer or external storage device via the data network60, which can include the Internet, a local area network, a wide area network and/or a wireless network. The data network60may comprise copper transmission cables, optical transmission fibers, wireless transmission, routers, firewalls, switches, gateway computers and/or edge servers. A network adapter card or network interface150in the encryption server10receives program instructions over the data network60and forwards them to the computer-readable storage medium120for storage and execution by the processor140. Execution of the program instructions by the processor140results in the encryption server10carrying out processes such as the encryption process300and other processes (including an operating system, for example).

A user interface110is also connected to the processor and may include various input and/or output devices, as well as program instructions that interact with the various input and/or output devices so as to elicit input from the user60and provide output to the user60via the input and/or output devices. The user interface110may be a graphical user interface for interfacing with the user6. A bus architecture160may interconnect the user interface110, the processor140, the memory120and the network interface150.

A pseudo-random number generator130may also be implemented by the encryption server10and may be interconnected to other components of the encryption server10by the bus architecture. In other embodiments, the pseudo-random number generator130may be implemented in software by the processor140executing program code stored in the memory120.

The key generation server15includes a computer-readable storage medium17, which can be a tangible device capable of storing program instructions for use by a processor19. The computer-readable storage medium17may 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 medium17includes 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.

The program instructions can be downloaded to the computer-readable storage medium17from an external computer or external storage device via the data network60. A network adapter card or network interface18in the key generation server15receives program instructions over the data network60and forwards them to the computer-readable storage medium17for storage and execution by the processor19. Execution of the program instructions by the processor19results in the key generation server15carrying out processes such as the key generation process200and other processes (including an operating system, for example).

A bus architecture may interconnect the processor19, the memory17and the network interface18.

A pseudo-random number generator16may also be implemented by the key generation server15and may be interconnected to other components of the key generation server15by the bus architecture. In other embodiments, the pseudo-random number generator16may be implemented in software by the processor19executing program code stored in the memory17.

The recipient server20includes a computer-readable storage medium22, which can be a tangible device capable of storing program instructions for use by a processor28. The computer-readable storage medium22may 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 medium22includes 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.

The program instructions can be downloaded to the computer-readable storage medium22from an external computer or external storage device via the data network60. A network adapter card or network interface24in the recipient server20receives program instructions over the data network60and forwards them to the computer-readable storage medium22for storage and execution by the processor28. Execution of the program instructions by the processor28results in the recipient server20carrying out processes such as the decryption process400and other processes (including an operating system, for example).

A user interface26is also connected to the processor and may include various input and/or output devices, as well as program instructions that interact with the various input and/or output devices so as to elicit input from the user60and provide output to the user60via the input and/or output devices. The user interface26may be a graphical user interface for interfacing with the second user66. A bus architecture may interconnect the user interface26, the processor28, the memory22and the network interface24.

The various program instructions referred to above 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.

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 processor530of the computing apparatus510, direct the processor530to 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.

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.

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.

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.

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.

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.

Also, when the phrase “at least one of C and D” is used, this phrase is intended to and is hereby defined as a choice of C or D or both C and D, 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.

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.