Post-quantum asymmetric key cryptosystem with one-to-many distributed key management based on prime modulo double encapsulation
In a post-quantum asymmetric key generation method and system, a processing unit generates, based on a prime and an arithmetic function or a classical string, a prime vector which has an infinite number of components; generates a prime array based on the prime vector; generates an associated matrix based on the prime array; obtains, based on the associated matrix and a first reference prime, a first reference inverse prime array that serves as a private key; and obtains a public key that is paired with the private key based on a second reference inverse prime array. The second reference inverse prime array is obtained based on the associated matrix, the first reference prime, a second reference prime, and a randomization array.
1. A post-quantum asymmetric key generation method, comprising:
A) generating, by a first processor of a key server of an encrypted communication system, 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 (ƒ)} p that relates to the prime p and that has an infinite number of components, wherein the p-vector {right arrow over (ƒ)} p is defined as:
{right arrow over (ƒ)} p :=[ƒ( p 0 ),ƒ( p 1 ),ƒ( p 2 ),ƒ( p 3 ), . . . ]
where ƒ represents said one of the arithmetic function and the classical string that serves as the seed;
B) generating, by the first processor, based on the p-vector a {right arrow over (ƒ)} p , a p-array p | s,t m that has m number of components and that relates to the prime p and that is defined as:
p
s
,
t
m
:=
∑
i
=
0
t
[
f
(
p
s
+
im
)
,
…
,
f
(
p
s
+
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-array p | s,t m is also represented as | m ;
C) based on the p-array | m , generating, by the first processor, 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) th one of the m number of components of the p-array, 0≤j≤(m−1);
D) based on the associated matrix [ | m ] and a modulus I which is a user-defined positive integer, generating, by the first processor, an inverse p-array l | m with respect to the modulus I, which is defined as:
l | m :=( L l [1,0, . . . ,0][ | m ]*)(mod l )
where L l represents an inverse modulus of a determinant of the associated matrix [ | m ] with respect to the modulus I, and is defined as:
L l :=(det[ | m ]) −1 (mod l), and [ | m ]* represents an adjoint matrix of the associated matrix [ | m ];
E) arbitrarily selecting, by the first processor, a first reference prime p 1 , and determining a second reference prime p 2 based on a predetermined criterion that relates to the first reference prime p 1 , a greatest one of the m number of components of the p-array | m which 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 p 2 >max(p 1 mã{tilde over (b)},mbr);
F) acquiring, by the first processor, a first reference inverse p-array p 1 | m and a second reference inverse p-array by p 2 | m respectively making the first reference prime p 1 and the second reference prime p 2 serve as the modulus I in the inverse p-array l | m , the first reference inverse p-array p 1 | m serving as a private key K private , which is defined as K private =( | m ,p 1 ,ã); and
G) generating, by the first processor, a public key K public with respect to a key-generation randomization array | (ã) m based on the second reference inverse p-array p 2 | m , the first reference prime p 1 , the second reference prime p 2 , and the key-generation randomization array | (ã) m , wherein the key-generation randomization array | (ã) m has m number of numerical components between 0 and the first reference positive integer ã and the public key K public is paired with the private key K private , and is an array public | m that includes m number of numerical components and that is also denoted as K public =( public | m ,p 2 ), representing public | m :=Rand( p 2 | m ,p 1 ,ã) (mod p 2 );
wherein Rand( p 2 | m ,p 1 ,ã) is a key-generation randomization function of the second reference inverse p-array p 2 | m with respect to the key-generation randomization array | (ã) m , and is defined as Rand( p 2 | m ,p 1 ,ã)=p 1 ( p 2 | m {circle around (*)} | (ã) m ), where {circle around (*)} represents a convolution multiplication operator;
whereby the public key K public and the private key K private are generated based on the arithmetic function and the classical string, the p-vector {right arrow over (ƒ)} p , and the p-array, thereby increasing speeds of encryption and decryption of the encrypted communication system;
the method further comprising:
using, by a second processor of a transmitter of the encrypted communication system, the public key K public , the second reference prime p 2 , and an encryption randomization array | ({tilde over (b)}) m that has m number of numerical components between 0 and the second reference positive integer {tilde over (b)} to perform an encryption procedure on a data array | m that corresponds to a plaintext to be transmitted and that has m number of numerical components, and acquiring, by the second processor, a ciphertext | m with respect to the encryption randomization array | ({tilde over (b)}) m , wherein the ciphertext | m has m number of encrypted numerical components; and
transmitting, from the transmitter, the ciphertext | m to a receiver of the encrypted communication system via a communication channel.
2. The method of claim 1 , wherein the plaintext has m number of characters, and each of the m number of numerical components of the data array | m is between 0 and the first reference positive integer ã, and represents a corresponding one of the m number of characters of the plaintext.
3. The encryption method of claim 1 , wherein the encryption procedure includes:
generating, by the second processor, based on the public key K public and the encryption randomization array | ({tilde over (b)}) m , an encryption randomization function | m that is defined as | m :=Rand( public | m ,1,{tilde over (b)}); and
acquiring, by the second processor, the ciphertext | m by performing, by the second processor, modulo operation on a sum of the data array | m and the encryption randomization function | m modulo the second reference prime p 2 , the ciphertext | m being represented by | m :=( | m + | m ) (mod p 2 ).
4. The method of claim 1 , further comprising:
using, by a third processor of the receiver of the encrypted communication system, the p-array | m , the private key K private , the first reference prime p 1 and the second reference prime p 2 to perform a decryption procedure on the ciphertext | m , and acquiring, by the third processor, a plaintext array | m that has m number of decrypted numerical components | m | ({tilde over (b)}) m | m | m | ({tilde over (b)}) m .
5. The method of claim 4 , wherein the decryption procedure includes:
performing, by the third processor, modulo operation on a first convolution result of the ciphertext | m and the p-array | m modulo the second reference prime p 2 to obtain a first modulo operation result, and performing, by the third processor, modulo operation on the first modulo operation result modulo the first reference prime p 1 to obtain a second modulo operation result | m , which is defined as | m :=[( | m {circle around (*)}{circle around (*)} | m ) (mod p 2 )] (mod p 1 ); and
performing, by the third processor, modulo operation on a second convolution result of the second modulo operation result | m and the first reference inverse p-array p 1 | m that serves as the private key K private modulo the first reference prime p 1 to obtain the plaintext array | m , which is defined as | m := | m {circle around (*)} p 1 | m (mod p 1 ).
6. A post-quantum asymmetric key generation system, comprising:
a key server including:
a p-vector generation coprocessor 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 (ƒ)} p that relates to the prime p and that has an infinite number of components, wherein the p-vector {right arrow over (ƒ)} p is defined as:
{right arrow over (ƒ)} p :=[ƒ( p 0 ),ƒ( p 1 ),ƒ( p 2 ),ƒ( p 3 ), . . . ]
where ƒ represents said one of the arithmetic function and the classical string that serves as the seed;
a p-array generation coprocessor coupled to said p-vector generation coprocessor, and configured to generate, based on the p-vector {right arrow over (ƒ)} p , a p-array p | s,t m that has m number of components and that relates to the prime p and that is defined as:
p
s
,
t
m
:=
∑
i
=
0
t
[
f
(
p
s
+
im
)
,
…
,
f
(
p
s
+
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-array p | s,t m , is also represented as | m ;
an associated matrix generation coprocessor coupled to said p-array generation coprocessor, 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) th one of the m number of components of the p-array, 0≤j≤(m−1);
an inverse p-array generation coprocessor coupled to said associated matrix generation coprocessor, and configured to generate, based on the associated matrix [ | m ] and a modulus I which is a user-defined positive integer, an inverse p-array l | m with respect to the modulus I, which is defined as:
l | m :=( L l [1,0, . . . ,0][ | m ]*)(mod l )
where L l represents an inverse modulus of a determinant of the associated matrix [ | m ] with respect to the modulus I, and is defined as: L l :=(det[ | m ]) −1 (mod l), and [ | m ]* represents an adjoint matrix of the associated matrix [ | m ];
a reference prime determining coprocessor configured to arbitrarily select a first reference prime p 1 , and to determine a second reference prime p 2 based on a predetermined criterion that relates to the first reference prime p 1 , a greatest one of the m number of components of the p-array | m which 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 p 2 >max(p 1 mã{tilde over (b)}, mbr);
a private key generation coprocessor coupled to said inverse p-array generation coprocessor and said reference prime determining coprocessor, and configured to acquire a first reference inverse p-array p 1 | m by making the first reference prime p 1 serve as the modulus I in the inverse p-array l | m , the first reference inverse p-array serving as a private key K private , which is defined as K private =( | m ,p 1 ,ã); and
a public key generation coprocessor coupled to said inverse p-array generation coprocessor and said reference prime determining coprocessor, and configured to acquire a second reference inverse p-array p 2 | m by making the second reference prime p 2 serve as the modulus I in the inverse p-array l | m , and to generate a public key K public with respect to a key-generation randomization array | (ã) m based on the second reference inverse p-array p 2 | m , the first reference prime p 1 , the second reference prime p 2 , and the key-generation randomization array | (ã) m , wherein the key-generation randomization array | (ã) m has m number of numerical components between 0 and the first reference positive integer ã, and the public key K public is paired with the private key K private , and is an array public | m that includes m number of numerical components and that is also denoted as K public =( public | m ,p 2 ), representing public | m :=Rand ( p 2 | m ,p 1 ,ã) (mod p 2 );
wherein Rand ( p 2 | m ,p 1 ,ã) is a key-generation randomization function of the second reference inverse p-array p 2 | m with respect to the key-generation randomization array | (ã) m , and is defined as Rand ( p 2 | m ,p 1 ,ã)=p 1 ( p 2 | m {circle around (*)} | (ã) m ), where {circle around (*)} represents a convolution multiplication operator;
whereby the public key K public and the private key K private are generated based on the arithmetic function and the classical string, the p-vector {right arrow over (ƒ)} p , and the p-array, thereby increasing speeds of encryption and decryption of the encrypted communication system; and
the post-quantum asymmetric key generation system further comprising a transmitter including a processor configured to use the public key K public , the second reference prime p 2 , and an encryption randomization array | ({tilde over (b)}) m that has m number of numerical components between 0 and the second reference positive integer {tilde over (b)} to perform an encryption procedure on a data array | ({tilde over (b)}) m that corresponds to a plaintext to be transmitted and that has m number of numerical components, and to acquire a ciphertext | m with respect to the encryption randomization array | ({tilde over (b)}) m , wherein the ciphertext | m has m number of encrypted numerical components, the transmitter configured to transmit the ciphertext | m to a receiver via a communication channel.
7. The post-quantum asymmetric key generation system of claim 6 , the key server further comprising a computer storage coupled to said p-array generation coprocessor, said reference prime determining coprocessor, said private key generation coprocessor and said public key generation coprocessor, and storing the p-array | m received from said p-array generation coprocessor, the first reference prime p 1 and the second reference prime p 2 received from said reference prime determining coprocessor, the first reference inverse p-array received from said private key generation coprocessor, and the second reference inverse p-array p 2 | m received from said public key generation coprocessor.
8. The post-quantum asymmetric key generation system of claim 7 , wherein said public key generation coprocessor is further configured to generate, based on the second reference inverse p-array p 2 | m , the first reference prime p 1 , and the second reference prime p 2 that are stored in said computer storage and another key-generation randomization array | (ã) m which is different from the key-generation randomization array | (ã) m , an updated public key K* public with respect to said another key-generation randomization array | (ã) m , wherein the updated public key K* public is paired with the private key K private , and said another key-generation randomization array | (ã) m has m number of numerical components between 0 and the first reference positive integer ã, and the public key K public is also denoted as K* public =( public | m ,p 2 ), representing public | m =Rand ( p 2 | m ,p 1 ,ã) (mod p 2 )=p 1 ( p 2 | m {circle around (*)} | (ã) m ) (mod p 2 ).
9. An encrypted communication system, comprising:
a key server including:
a p-vector generation coprocessor 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 (ƒ)} p is that relates to the prime p and that has infinite number of components, wherein the p-vector {right arrow over (ƒ)} p is defined as:
{right arrow over (ƒ)} p :=[ƒ( p 0 ),ƒ( p 1 ),ƒ( p 2 ),ƒ( p 3 ), . . . ]
where ƒ represents said one of the arithmetic function and the classical string that serves as the seed;
a p-array generation coprocessor coupled to said p-vector generation coprocessor, and configured to generate, based on the p-vector {right arrow over (ƒ)} p , a p-array p | s,t m that has m number of components and that relates the prime p and that is defined as:
p
s
,
t
m
:=
∑
i
=
0
t
[
f
(
p
s
+
im
)
,
…
,
f
(
p
s
+
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-array p | s,t m is also represented as | m ;
an associated matrix generation coprocessor coupled to said p-array generation coprocessor, 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) th one of the m number of components of the p-array, 0≤j≤(m−1);
an inverse p-array generation coprocessor coupled to said associated matrix generation coprocessor, and configured to generate, based on the associated matrix [ | m ] and a modulus I which is a user-defined positive integer, an inverse p-array l | m with respect to the modulus I, which is defined as:
l | m :=( L l [1,0, . . . ,0][ | m ]*)(mod l )
where L l represents an inverse modulus of a determinant of the associated matrix [ | m ] with respect to the modulus I, and is defined as: L l :=(det [ | m ]) −1 (mod l), and [ | m ]* represents an adjoint matrix of the associated matrix [ | m ];
a reference prime determining coprocessor configured to arbitrarily select a first reference prime p 1 , and to determine a second reference prime p 2 based on a predetermined criterion that relates to the first reference prime p 1 , a greatest one of the m number of components of the p-array | m which 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 p 2 >max(p 1 mã{tilde over (b)},mbr);
a private key generation coprocessor coupled to said inverse p-array generation coprocessor and said reference prime determining coprocessor, and configured to acquire a first reference inverse p-array p 1 | m by making the first reference prime p 1 serve as the modulus I in the inverse p-array l | m , the first reference inverse p-array p 1 | m serving as a private key K private , which is defined as K private =( | m ,p 1 ,ã); and
a public key generation coprocessor coupled to said inverse p-array generation coprocessor and said reference prime determining coprocessor, and configured to acquire a second reference inverse p-array p 2 | m by making the second reference prime p 2 serve as the modulus I in the inverse p-array l | m , and to generate a public key K public with respect to a key-generation randomization array | (ã) m based on the second reference inverse p-array p 2 | m , the first reference prime p 1 , the second reference prime p 2 , and the key-generation randomization array | (ã) m , wherein the key-generation randomization array | (ã) m has m number of numerical components between 0 and the first reference positive integer ã and the public key K public is paired with the private key K private , and is an array public | m that includes m number of numerical components and that is also denoted as K public =( public | m ,p 2 ), representing public | m :=Rand ( p 2 | m ,p 1 ,ã) (mod p 2 );
wherein Rand ( p 2 | m ,p 1 ,ã) is a key-generation randomization function of the second reference inverse p-array p 2 | m with respect to the key-generation randomization array | (ã) m , and is defined as Rand ( p 2 | m ,p 1 ,ã)=p 1 ( p 2 | m {circle around (*)} | (ã) m ), where {circle around (*)} represents a convolution multiplication operator;
whereby the public key K public and the private key K private are generated based on the arithmetic function and the classical string, the p-vector {right arrow over (ƒ)} p , and the p-array, thereby increasing speeds of encryption and decryption of the encrypted communication system;
a transmitter including a first computer storage that stores the public key K public , the second reference prime p 2 and the second reference positive integer {tilde over (b)}, and a first processor coupled to said first computer storage; and
a receiver including a second computer storage that stores the private key K private , the p-array | m , the first reference prime p 1 and the second reference prime p 2 , and a second processor coupled to said second computer storage;
wherein, for a data array | m that corresponds to a plaintext to be transmitted to the receiver and that has m number of numerical components, said first processor uses the public key K public and the second reference prime p 2 that are stored in said first computer storage, and an encryption randomization array | ({tilde over (b)}) m that 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 | m with respect to the encryption randomization array | ({tilde over (b)}) m , and said transmitter transmits the ciphertext | m to said receiver via a first communication channel, wherein the ciphertext | m has m number of encrypted numerical components;
wherein, upon receipt of the ciphertext | m by said second processor, said second processor uses the private key K private , the p-array | m , the first reference prime p 1 and the second reference prime p 2 that are stored in said second computer storage to perform a decryption procedure on the ciphertext | m , and acquires a plaintext array | m that has m number of decrypted numerical components and that is identical to the data array | m .
10. The encrypted communication system of claim 9 , wherein the plaintext has m number of characters, and said first processor has a text conversion coprocessor configured to use a predetermined character-to-numeric technique to convert the plaintext into the data array | m ; and
wherein each of the m number of numerical components of the data array | m is between 0 and the first reference positive integer ã, and represents a corresponding one of the m number of characters of the plaintext.
11. The encrypted communication system of claim 10 , wherein:
said first processor has an encryption randomization function generation coprocessor, and a ciphertext generation coprocessor coupled to said text conversion coprocessor and said encryption randomization function generation coprocessor; and
in the encryption procedure, said encryption randomization function generation coprocessor generates, based on the public key K public and the encryption randomization array | ({tilde over (b)}) m , an encryption randomization function | m that is defined as | m :=Rand ( public | m ,1,{tilde over (b)}); and said ciphertext generation coprocessor acquires the ciphertext | m by performing modulo operation on a sum of the data array | m and the encryption randomization function | m modulo the second reference prime p 2 , the ciphertext | m being represented by | m :=( | m + | m ) (mod p 2 ).
12. The encrypted communication system of claim 9 , wherein:
said second processor has a first convolution coprocessor, and a second convolution coprocessor coupled to said first convolution coprocessor; and
in the decryption procedure, said first convolution coprocessor computes a first convolution result of the ciphertext | m and the p-array | m , performs modulo operation on the first convolution result modulo the second reference prime p 2 to obtain a first modulo operation result, and performs modulo operation on the first modulo operation result modulo the first reference prime p 1 to obtain a second modulo operation result | m , which is defined as | m :=[( | m {circle around (*)} | m ) (mod p 2 )] (mod p 1 ); and said second convolution coprocessor computes a second convolution result of the second modulo operation result | m and the first reference inverse p-array p 1 | m that serves as the private key K private , performs modulo operation on the second convolution result modulo the first reference prime p 1 to obtain the plaintext array | m , which is defined as | m := | m {circle around (*)} p 1 | m (mod p 1 ).
13. The encrypted communication system of claim 9 , wherein:
before the public key K public , the second reference prime p 2 and the second reference positive integer {tilde over (b)} are stored in said first computer storage, said key server transmits the public key K public , the second reference prime p 2 and the second reference positive integer {tilde over (b)} to said transmitter via a second communication channel, and said first processor stores the public key K public , the second reference prime p 2 and the second reference positive integer {tilde over (b)} that are received from said key server into said first computer storage; and
before the private key K private , the p-array | m , the first reference prime p 1 and the second reference prime p 2 are stored in said second computer storage, said key server transmits the private key K private , the p-array | m , the first reference prime p 1 and the second reference prime p 2 to said receiver via a third communication channel, and said second processor stores the private key K private , the p-array | m , the first reference prime p 1 and the second reference prime p 2 that are received from said key server into said second computer storage.
14. The encrypted communication system of claim 13 , wherein said key server further includes a third computer storage coupled to said p-array generation coprocessor, said reference prime determining coprocessor, said private key generation coprocessor and said public key generation coprocessor, and storing the p-array | m received from said p-array generation coprocessor, the first reference prime p 1 and the second reference prime p 2 received from said reference prime determining coprocessor, the first reference inverse p-array p 1 | m received from said private key generation coprocessor, and the second reference inverse p-array p 2 | m received from said public key generation coprocessor.
15. The encrypted communication system of claim 14 , wherein:
said public key generation coprocessor is further configured to generate, based on the second reference inverse p-array p 2 | m , the first reference prime p 1 , the second reference prime p 2 , and another key-generation randomization array | (ã) m which is different from the key-generation randomization array | (ã) m , an updated public key K* public with respect to said another key-generation randomization array | (ã) m , wherein the updated public key K* public is paired with the private key K private , and said another key-generation randomization array | (ã) m has m number of numerical components between 0 and the first reference positive integer ã, and the public key K public is also denoted as K* public =( public | m ,p 2 ), representing public | m =Rand ( p 2 | m ,p 1 ,ã) (mod p 2 )=p 1 ( p 2 | m {circle around (*)} | (ã) m ) (mod p 2 );
said key server transmits the updated public key K* public to said transmitter via the second communication channel;
upon receipt of the updated public key K* public from said key server, said first processor updates the public key K public that is stored in said first computer storage to become the updated public key K* public ;
after updating the public key K public to become the updated public key K* public , said first processor uses the updated public key K* public , the second reference prime p 2 , and the encryption randomization array | ({tilde over (b)}) m to perform the encryption procedure on the data array | m , and acquires another ciphertext with respect to the updated public key K* public and the encryption randomization array | ({tilde over (b)}) m , and said transmitter transmits said another ciphertext to said receiver via the first communication channel, wherein said another ciphertext has m number of encrypted numerical components; and
upon receipt of said another ciphertext by said second processor, said second processor uses the private key K private , the p-array | m , the first reference prime p 1 and the second reference prime p 2 that are stored in said second computer storage to perform the decryption procedure on said another ciphertext , and acquires the plaintext array | m .