CROSS-REFERENCE TO RELATED APPLICATION

This application claims priority of Taiwanese Invention Patent Application No. 107134068, filed on Sep. 27, 2018.

FIELD

The disclosure relates to an asymmetric key generation method, and more particularly to a lattice algebra based post-quantum asymmetric key generation method and system, key-refresh method, encryption method, decryption method, and encrypted communication system.

BACKGROUND

Classical cryptosystems can be classified into two main categories: symmetric key algorithms and asymmetric key algorithms. The symmetric key algorithms, such as AES (advanced encryption standard), use shared key to perform encryption and decryption. The asymmetric key algorithms use different keys, namely, paired public key and private key, to perform encryption and decryption. For example, RSA is one of the first public-key cryptosystems and is widely used for secure data transmission; NTRU (number theory research unit) is another asymmetric key algorithm; and ECC (elliptic curve cryptography) is an approach to public key cryptography based on the algebraic structure of elliptic curves. Implementations of the symmetric key algorithms require a secure channel for key exchange between two parties. Although a secure channel is not necessary for implementations of the asymmetric key algorithms, the asymmetric key algorithms may require relatively large amount of computation for generation of the paired keys, encryption and decryption. In comparison to RSA, although ECC may provide better security, more time is required on encryption and decryption.

The classical cryptosystems may have the following drawbacks:

1. Protocols for current asymmetric key algorithms cannot send large amounts of data in a short amount of time, because encryption and decryption are done for one character at a time.

2. Current asymmetric key algorithms use a public key and a private key that have the same mathematical characteristics such as belonging to the same algebraic group, ring or vector space, and that are similar in nature, so they are prone to plaintext attack or brute force attack.

3. For current asymmetric key algorithms, if a user changes his/her public key for a new one, all the other users need to update their private keys to be paired with the new public key, otherwise any possible communication from a user who keeps on using the old private key would be invalid.

4. If a system setup requires everyone to make a key refresh, a centralized entity that indicates the key refresh time is needed.

5. The integer factorization-based algorithms (e.g., RSA, DSA) or the discrete logarithm problem based algorithms (e.g., SCC) are weak against Shor's and Grover's algorithms based post-quantum attacks.

6. Distributed key refresh does not exist in the networks using RSA, AES and NTRU because the distributed key refresh is not part of the fundamental definition of the protocols for these cryptosystems.

7. Classical public key cryptosystems have tightly coupled public-private keys (i.e., each public key is paired with only a unique private key). Attacks on one of the paired keys often reveal information of the other one.

SUMMARY

Therefore, an object of the disclosure is to provide a lattice algebra based post-quantum asymmetric key generation method and system, a key-refresh mechanism, an encryption method, a decryption method, and an encrypted communication system that can alleviate at least one of the drawbacks of the prior art.

According to the disclosure, the post-quantum asymmetric key generation method is implemented by a processing unit, and includes:

A) generating, based on a prime p and one of an arithmetic function and a classical string that serves as a seed, a vector denominated p-vector and denoted as {right arrow over (ƒ)}pthat depends on the prime p and that has an infinite number of components, wherein the p-vector {right arrow over (ƒ)}pis defined as:
{right arrow over (ƒ)}p:=[ƒ(p0),ƒ(p1),ƒ(p2),ƒ(p3), . . . ],
where ƒ represents said one of the arithmetic function and the classical string that serves as the seed;

B) defining the concept of instance as I=(p, s, t), where p is a prime, and s and t are user-defined positive integers;

C) generating, based on the p-vector {right arrow over (ƒ)}pand the instance I=(p, s, t), a p-arrayp|s,tmthat has m number of components and that relates to the prime p and that is defined as:

ps,tm:=∑i=0t⁢[f⁡(ps+im),…⁢,f⁡(ps+im+(m-1))],
wherein the p-arrayp|s,tmcan also be represented as|mif I=(p, s, t) is known;

D) based on the p-array|m, generating an associated matrix [|m] that is defined as:

[m]=(m⁢(0)m⁢(1)…m⁢(m-1)m⁢(m-1)m⁢(0)…m⁢(m-2)⋮⋮⋱⋮m⁢(1)m⁢(2)…m⁢(0)),
where|m(j) represents a (j+1)thone of the m number of components of the p-array, 0≤j≤(m−1);

E) based on the associated matrix [|m] and a moduluswhich is a user-defined positive integer, generating an inverse p-array|mwith respect to the modulus, which is defined as:
|m:=([1,0, . . . ,0][|m]*)(mod),
whererepresents an inverse modulus of a determinant of the associated matrix [|m] with respect to the modulus, and is defined as::=(det[|m])−1(mod), and [|m]* represents an adjoint matrix of the associated matrix [|m];

F) arbitrarily selecting a first reference prime p1, and determining a second reference prime p2, based on a predetermined criterion that relates to the first reference prime p1, a greatest one of the m number of components of the p-array|mwhich is denoted by b, a first reference positive integer ã, and a second parameter set S that is composed of the parameter m, a second reference positive integer {tilde over (b)} and a third reference positive integer r, wherein the predetermined criterion includes p2>max(p1mã{tilde over (b)},mbr);

G) acquiring a first reference inverse p-arrayp1|mand a second reference inverse p-array byp2|mby respectively making the first reference prime p1and the second reference prime p2serve as the modulusin the inverse p-array|m, the first reference inverse p-arrayp1|mserving as a private Kprivate, which is defined as Kprivate=(|m,p1,ã); and

H) generating a public key Kpublicwith respect to the second reference inverse p-arrayp2|m, the first reference prime p1, the second reference prime p2, and the key-generation randomization array|(ã)m, wherein the key-generation randomization array|(ã)mhas m number of numerical components between 0 and the first reference positive integer ã, and the public key Kpublicis paired with the private key Kprivate, and is an arraypublic|mthat includes m number of numerical components and that is also denoted as Kpublic=(public|m,p2), representingpublic|m:=Rand(p2|m,p1,ã)(mod p2);

wherein Rand(p2|m,p1,ã) is a key-generation randomization function of the second reference inverse p-arrayp2|mwith respect to the key-generation randomization array|(ã)m, and is defined as Rand(p2|m,p1,ã)=p1(p2|m|(ã)m), whererepresents a convolution multiplication operator.

According to this disclosure, the encryption method is implemented by a processor, and includes:using the public key Kpublicgenerated according to the post-quantum asymmetric key generation method of this disclosure, the second reference prime p2used in the post-quantum asymmetric key generation method of this disclosure, and an encryption randomization array|({tilde over (b)})mthat has m number of numerical components between 0 and the second reference positive integer {tilde over (b)} used in the post quantum asymmetric key generation method of this disclosure to perform an encryption procedure on a data array|mthat corresponds to a plaintext to be transmitted and that has m number of numerical components, and acquiring a ciphertext|mwith respect to the encryption randomization array|({tilde over (b)})m, wherein the ciphertext|mhas m number of encrypted numerical components.

According to this disclosure, the decryption method is implemented by a processor, and includes:using the p-array|m, the private key Kprivate, the first reference prime p1and the second reference prime p2that are used in the post-quantum asymmetric key generation. Method of this disclosure to perform a decryption procedure on a ciphertext|m, and acquiring a plaintext array|mthat has m number of decrypted numerical components, wherein the ciphertext|mis generated by:using the public key generated according to the post-quantum asymmetric key generation method of this disclosure, the second reference prime p2used in the post-quantum asymmetric key generation method of this disclosure, and an encryption randomization array|({tilde over (b)})mthat has m number of numerical components between 0 and the second reference positive integer {tilde over (b)} used in the post-quantum asymmetric key generation method of this disclosure to perform an encryption procedure on a data array|mthat corresponds to a plaintext to be transmitted and that has m number of numerical components, and acquiring the ciphertext|mthat relates to the encryption randomization array|({tilde over (b)})mand that has m number of encrypted numerical components.

According to this disclosure, the post-quantum asymmetric key generation system includes:a p-vector generation module configured to generate, based on a prime p and one of an arithmetic function and a classical string that serves as a seed, a p-vector {right arrow over (ƒ)}pthat relates to the prime p and that has an infinite number of components, wherein the p-vector {right arrow over (ƒ)}pis defined as:
{right arrow over (ƒ)}p:=[ƒ(p0),ƒ(p1),ƒ(p2),ƒ(p3), . . . ],
where ƒ represents said one of the arithmetic function and the classical string that serves as the seed;a p-array generation module coupled to said p-vector generation module, and configured to generate, based on the p-vector {right arrow over (ƒ)}p, a p-arrayp|s,tmthat has m number of components and that relates to the prime p and that is defined as:

ps,tm:=∑i=0t⁢[f⁡(ps+im),…⁢,f⁡(ps+im+(m-1))],
where each of parameters m, s and t is a user-defined positive integer, and the prime p and the parameters s, t cooperatively compose a first parameter set I, and wherein the p-arrayp|s,tmis also represented as|m;an associated matrix generation module coupled to said p-array generation module, and configured to generate, based on the p-array|m, an associated matrix [|m] that is defined as:

[m]=(m⁢(0)m⁢(1)…m⁢(m-1)m⁢(m-1)m⁢(0)…m⁢(m-2)⋮⋮⋱⋮m⁢(1)m⁢(2)…m⁢(0)),
where|m(j) represents a (j+1)thone of the m number of components of the p-array, 0≤j≤(m−1);an inverse p-array generation module coupled to said associated matrix generation module, and configured to generate, based on the associated matrix [|m] and a moduluswhich is a user-defined positive integer, an inverse p-array|mwith respect to the modulus, which is defined as:
|m:=([1,0, . . . ,0][|m]*)(mod),
whererepresents an inverse modulus of the determinant of the associated matrix [|m] with respect to the modulus, and is defined as::=(det[|m])−1(mod), and [|m]* represents an adjoint matrix of the associated matrix [|m];a reference prime determining module configured to arbitrarily select a first reference pride p1, and to determine a second reference prime p2based on a predetermined criterion that relates to the first reference prime p1, a greatest one of the m number of components of the p-array|mwhich is denoted by b, a first reference positive integer ã, and a second parameter set S that is composed of the parameter m, a second reference positive integer {tilde over (b)} and a third reference positive integer r, wherein the predetermined criterion includes p2>max(p1mã{tilde over (b)},mbr);a private key generation module coupled to said inverse p-array generation module and said reference prime determining module, and configured to acquire a first reference inverse arrayp1|mby making the first reference prime p1serve as the modulusin the inverse p-array|m, the first reference inverse p-arrayp1|mserving as a private key Kprivate, which is defined as Kprivate=(|m,p1,ã); anda public key generation module coupled to said inverse p-array generation module and said reference prime determining module, and configured to acquire a second reference inverse p-arrayp2|mby making the second reference prime p2serve as the modulusin the inverse p-array|m, and to generate a public key Kpublicwith respect to a key-generation randomization array|(ã)mbased on the second reference inverse p-arrayp2|m, the first reference prime p1, the second reference prime p2, and the key generation randomization array|(ã)m, wherein the key-generation randomization array|(ã)mhas m number of numerical components between 0 and the first reference positive integer ã, and the public key Kpublicis paired with the private key Kprivate, and is an arraypublic|mthat includes m number of numerical components and that is also denoted as Kpublic=(public|m,p2), representingpublic|m:=Rand(p2|m,p1,ã)(mod p2);

wherein Rand(p2|m,p1,ã) is a key generation randomization function of the second reference inverse p-arrayp2|mwith respect to the key-generation randomization array|(ã)m, and is defined as Rand(p2|m,p1,ã)=p1(p2|m|(ã)m), whererepresents a convolution multiplication operator.

According to this disclosure, the encrypted communication system includes:a key server including:a p-vector generation module configured to generate, based on a prime p and one of an arithmetic function and a classical string that serves as a seed, a p-vector {right arrow over (ƒ)}pthat relates to the prime p and that has infinite number of components, wherein the p vector {right arrow over (ƒ)}pis defined as:
{right arrow over (ƒ)}p:=[ƒ(p0),ƒ(p1),ƒ(p2),ƒ(p3), . . . ],
where ƒ represents said one of the arithmetic function and the classical string that serves as the seed;a p-array generation module coupled to said p-vector generation module, and configured to generate, based on the p-vector {right arrow over (ƒ)}p, a p-arrayp|s,tmthat has m number of components and that relates the prime p and that is defined as:

ps,tm:=∑i=0t⁢[f⁡(ps+im),…⁢,f⁡(ps+im+(m-1))],
where each of parameters m, s and t is a user-defined positive integer, and the prime p and the parameters s, t cooperatively compose a first parameter set I, and wherein the p-arrayp|s,tmis also represented as|m;an associated matrix generation module coupled to said p-array generation module, and configured to generate, based on the p-array|m, an associated matrix [|m] that is defined as:

[m]=(m⁢(0)m⁢(1)…m⁢(m-1)m⁢(m-1)m⁢(0)…m⁢(m-2)⋮⋮⋱⋮m⁢(1)m⁢(2)…m⁢(0)),
where|m(j) represents a (j+1)thof the m number of components of the p-array, 0≤j≤(m−1);an inverse p-array generation module coupled to said associated matrix generation module, and configured to generated, based on the associated matrix [|m] and a moduluswhich is a user-defined positive integer, an inverse p-array|mwith respect to the modulus, which is defined as:
|m:=([1,0, . . . ,0][|m]*)(mod),
whererepresents an inverse modulus of a determinant of the associated matrix [|m] with respect to the modulus, and is defined as::=(det[|m])−1(mod), and [|m]* represents an adjoint matrix of the associated matrix [|m];a reference prime determining module configured to arbitrarily select a first reference prime p1, and to determine a second reference prime p2based on a predetermined criterion that relates to the first reference prime p1, a greatest one of the m number of components of the p-array|mwhich is denoted by b, a first reference positive integer ã, and a second parameter set S that is composed of the parameter m, a second reference positive integer {tilde over (b)} and a third reference positive integer r, wherein the predetermined criterion includes p2>max(p1mã{tilde over (b)},mbr);a private key generation module coupled to said inverse p-array generation module and said reference prime determining module, and configured to acquire a first reference inverse p-arrayp1|mby making the first reference prime p1serve as the modulusin the inverse p-array|m, the first reference inverse p-arrayp1|mserving as a private key Kprivate, which is defined as Kprivate=(|m,p1,ã); anda public key generation module coupled to said inverse p-array generation module and said reference prime determining module, and configured to acquire a second reference inverse p-arrayp2|mby making the second reference prime p2serve as the modulusin the inverse p-array|m, and to generate a public key Kpublicwith respect to a key-generation randomization array|(ã)mbased on the second reference inverse p-arrayp2|m, the first reference prime p1, the second reference prime p2, and the key-generation randomization array|(ã)m, wherein the key-generation randomization array|(ã)mhas m number of numerical components between 0 and the first reference positive integer ã, and the public key Kpublicis paired with the private key Kprivate, and is an arraypublic|mthat includes m number of numerical components and that is also denoted as Kpublic=(|m,p2), representingpublic|m:=Rand(p2|m,p1,ã)(mode p2);wherein Rand(p2|m,p1,ã) is a key generation randomization function of the second reference inverse p-arrayp2|mwith respect to the key-generation randomization array|(ã)m, and is defined as Rand(p2|m,p1,ã)=p1(p1|m|(ã)m), whererepresents a convolution multiplication operator;a transmitting end including a first that stores the public key Kpublic, the second reference prime p2and the second reference positive integer {tilde over (b)}, and a first processor coupled to said first storage unit; anda receiving end including a second storage unit that stores the private key Kprivate, the p-array|m, the first reference prime p1and the second reference prime p2, and a second processor coupled to said second storage unit;wherein, for a data array|mthat corresponds to a plaintext to be transmitted to the receiving end and that has m number of numerical components, said first processor uses the public key Kpublicand the second reference prime p2that are stored in said first storage unit, and an encryption randomization array|({tilde over (b)})mthat has m number of numerical components between 0 and the second reference positive integer {tilde over (b)}, to perform an encryption procedure on the data array|m, and acquires a ciphertext|mwith respect to the encryption randomization array|({tilde over (b)})m, and said transmitting end transmits the ciphertext|mto said receiving end via a first communication channel, wherein the ciphertext|mhas m number of encrypted numerical components;

wherein, upon receipt of the ciphertext|mby said second processor, said second processor uses the private key Kprivate, the p-array|m, the first reference prime p1and the second reference prime p2that are stored in said second storage unit to perform a decryption procedure on the ciphertext|m, and acquires a plaintext array|mthat has m number of decrypted numerical components and that is identical to the data array|m.

