Lattice-based public key cryptosystem and electronic device included in the same
Embodiments of the present disclosure may include a key generation device of a lattice-based public key cryptosystem. In some embodiments, the key generation device may include a communication unit, a storage unit, and a processor that may be configured to control the key generation device to perform operations. In some embodiments, the operations may include generating a public key by using a public key polynomial, where the public key polynomial may belong to a first polynomial ring. In some embodiments, the operations may additionally include generating a secret key that may correspond to the public key. In some embodiments, the secret key may be generated by using a secret key polynomial that may belong to a second polynomial ring. In some embodiments, the operations may additionally include storing the public key and the secret key.
1 . A key generation device of a lattice-based public key cryptosystem, the key generation device comprising:
a communication circuit configured to send and receive data;
a memory; and
a processor coupled to the communication circuit and the memory, and configured to control the key generation device to perform a plurality of operations by loading instructions stored in the memory,
wherein the plurality of operations include:
obtaining a public key seed and a secret key seed;
generating a public key polynomial belonging to a first polynomial ring that is a quotient ring by a polynomial φ(X), by determining a degree and coefficients of the public key polynomial according to the public key seed;
generating a public key based on the public key polynomial;
generating a secret key polynomial belong to a second polynomial ring that is a quotient ring by the polynomial φ(X), by determining a degree and coefficients of the secret key polynomial from the secret key seed; and
generating a secret key based on the secret key polynomial;
storing the public key and the secret key,
wherein the polynomial φ(X) is defined as X p −X−1 (p is a prime number) or
X
n
-
X
n
2
+
1
(n=2 a 3 b (a and b are positive integers)) such that the public key and the secret key are secure against attacks based on decomposition of the polynomial φ(X).
2 . The key generation device of claim 1 , wherein the generating of the public key comprises:
generating a first public key polynomial defined on the first polynomial ring;
generating a secret key polynomial defined on the second polynomial ring;
generating a second public key polynomial by using the first public key polynomial and the secret key polynomial; and
generating the public key by using the first public key polynomial and the second public key polynomial.
3 . The key generation device of claim 2 , wherein the generating of the secret key further comprises:
generating a first secret key polynomial and a second secret key polynomial from the secret key polynomial; and
generating the secret key by using the first secret key polynomial and the second secret key polynomial.
4 . The key generation device of claim 3 , wherein the generating of the first secret key polynomial and the second secret key polynomial comprises:
selecting the first secret key polynomial and the second secret key polynomial among polynomials in which a maximum size of coefficients of respective terms is within a reference value among polynomials included in the second polynomial ring.
5 . The key generation device of claim 2 , wherein the generating of the public key further comprises:
generating a first part public key polynomial and a second part public key polynomial based on each of coefficients of the second public key polynomial; and
generating the public key by using any one of the first part public key polynomial and the second part public key polynomial.
6 . The key generation device of claim 1 , wherein the first polynomial ring is Z q [X]/X p −X−1) (here, q is a prime number making the first polynomial ring become a field), and
wherein the second polynomial ring is Z[X]/(X p −X−1).
7 . The key generation device of claim 1 , wherein the first polynomial ring is
ℤ
q
[
X
]
/
(
X
n
-
X
n
2
+
1
)
(here, q is a prime number making the first polynomial ring become a field), and
wherein the second polynomial ring is
ℤ
[
X
]
/
(
X
n
-
X
n
2
+
1
)
.
8 . A method for operating a key generation device of a lattice-based public key cryptosystem, the method comprising:
obtaining a public key seed and a secret key seed;
generating a public key polynomial belonging to a first polynomial ring that is a quotient ring by a polynomial φ(X), by determining a degree and coefficients of the public key polynomial according to the public key seed;
generating a secret key polynomial belong to a second polynomial ring that is a quotient ring by the polynomial φ(X), by determining a degree and coefficients of the secret key polynomial according to the secret key seed; and
generating a public key based on the public key polynomial and the secret key polynomial;
generating a secret key based on the secret key polynomial; and
storing the public key and the secret key,
wherein the polynomial φ(X) is defined as X p −X−1 (p is a prime number) or
X
n
-
X
n
2
+
1
(n=2a3b (a and b are positive integers)) such that the public key and the secret key are secure against attacks based on decomposition of the polynomial φ(X).
9 . The method of claim 8 , wherein the generating of the public key comprises:
generating a first public key polynomial defined on the first polynomial ring;
generating a secret key polynomial defined on the second polynomial ring;
generating a public key polynomial by using the first public key polynomial and the secret key polynomial; and
generating the public key by using the public key polynomials.
10 . A computer-readable non-transitory storage medium storing a program for performing the method described in claim 9 .
11 . The method of claim 8 , wherein the first polynomial ring is Z q [X]/(X p −X−1) (here, q is a prime number making the first polynomial ring become a field), and
wherein the second polynomial ring is Z[X]/X p −X−1).
12 . The method of claim 8 , wherein the first polynomial ring is
ℤ
q
[
X
]
/
(
X
n
-
X
n
2
+
1
)
(here, q is a prime number making the first polynomial ring become a field), and
wherein the second polynomial ring is
ℤ
[
X
]
/
(
X
n
-
X
n
2
+
1
)
.