Methods of generating encryption key and digital signature based on lattices

1. A method of generating a digital signature comprising:

receiving a message;

computing a particular solution in which a result of calculating the particular solution in a public key becomes a function-processed output value predetermined in the received message;

generating digital signature information for the message using the computed particular solution,

wherein the public key is computed using a ring having a dimension (d) represented by a power of 2 and an integer multiplication of 3 or more; and

computing a first random matrix (S) in which the number of columns is smaller than the dimension by 1 and the number of rows is equal to the number of the dimension by sampling elements ({right arrow over (f)} l ) linearly independent from each other in the ring;

computing a second random matrix (A) in which the number of columns is equal to the number of the dimension and the number of rows is 1; and

computing the public key based on the second random matrix (A).

2. The method of claim 1 , wherein in the generating of the digital signature information, the digital signature information is generated by reducing the computed particular solution using a secret key.

3. The method of claim 1 , further comprising:

computing a trapdoor (T); and

determining the computed trapdoor (T) as a secret key.

4. The method of claim 1 , wherein in the computing of the second random matrix, a d×d matrix (M i ) is computed by excluding an i-th row from a matrix [{right arrow over (f 1 )} . . . {right arrow over (f d−1 )}]∈R q d×(d−1) , and (−1) i−1 ·det (M i ) is determined as a determinant (a i ), thereby computing a 1 −1 ·(a 1 , a 2 , . . . , a d ) as the second random matrix.

5. The method of claim 4 , wherein the computing of the trapdoor (T) includes sampling of vector ({right arrow over (F)}∈R q d ) that satisfies the relationship of det[{right arrow over (f 1 )}∥ . . . ∥{right arrow over (f d−1 )}∥{right arrow over (F)}]∈=q, in which [{right arrow over (f 1 )}∥ . . . ∥{right arrow over (f d−1 )}∥{right arrow over (F)}] is computed as the trapdoor (T).

6. The method of claim 5 , wherein in the sampling of the vector, a result vector value is output after reducing elements of the vector by using the elements ({right arrow over (f)} l ).

7. The method of claim 6 , wherein in the sampling of the vector, the elements of the vector are reduced by removing a direction component of the elements by subtracting a constant multiple of the elements ({right arrow over (f)} l ) from the elements ({right arrow over (F)}=(F 1 , . . . , F d )) of the vector.

8. The method of claim 6 , wherein in the sampling of the vector, the elements of the vector are reduced using an extended Euclidean algorithm.

9. The method of claim 1 , wherein the predetermined function-processing is a hash processing.

10. A method of verifying a message comprising:

receiving a message and digital signature information;

checking whether a result of calculating the digital signature information received in a public key becomes a function-processed output value predetermined in the message;

determining whether the received digital signature information has a value smaller than a predetermined parameter;

verifying the received message based on the check result and the determination result,

wherein the public key is computed using a ring having a dimension (d) represented by a power of 2 and an integer multiplication of 3 or more; and

computing a first random matrix (S) in which the number of columns is smaller than the dimension by 1 and the number of rows is equal to the number of the dimension by sampling elements ({right arrow over (f)} l ) linearly independent from each other in the ring;

computing a second random matrix (A) in which the number of columns is equal to the number of the dimension and the number of rows is 1; and

computing the public key based on the second random matrix (A).

11. The method of claim 10 , wherein the predetermined function-processing is a hash processing.

12. A calculation device comprising:

a memory storing at least one instruction; and

a processor performing the at least one instruction,

wherein the processor computes a particular solution in which a result of calculating the particular solution in a public key becomes a function-processed output value predetermined in a message, and generates digital signature information for the message using the computed particular solution,

the public key is computed using a ring having a dimension (d) represented by a power of 2 and an integer multiplication of 3 or more, and

the processor computes a first random matrix (S) in which the number of columns is smaller than the dimension by 1 and the number of rows is equal to the number of the dimension by sampling elements ({right arrow over (f)} l )linearly independent from each other in the ring;

the processor computes a second random matrix (A) in which the number of columns is equal to the number of the dimension and the number of rows is 1; and

the processor computes the public key based on the second random matrix (A).

13. The calculation device of claim 12 , wherein the processor reduces the computed particular solution using a secret key, and generates the digital signature information by using the reduced particular solution.

14. The calculation device of claim 12 , wherein receiving the message and the digital signature information, the processor checks whether a result of calculating the digital signature information received in a public key becomes a function-processed output value predetermined in the message, determines whether the received digital signature information has a value smaller than a predetermined parameter, and verifies the received message based on the check result and the determination result.

15. A non-transitory computer-readable recording medium comprising a program performing a method of generating a digital signature, wherein the method comprising:

receiving a message;

computing a particular solution in which a result of calculating the particular solution in a public key becomes a function-processed output value predetermined in the received message;

generating digital signature information for the message using the computed particular solution,

wherein the public key is computed using a ring having a dimension (d) represented by a power of 2 and an integer multiplication of 3 or more; and

computing a first random matrix (S) in which the number of columns is smaller than the dimension by 1 and the number of rows is equal to the number of the dimension by sampling elements ( )linearly independent from each other in the ring;

computing a second random matrix (A) in which the number of columns is equal to the number of the dimension and the number of rows is 1; and

computing the public key based on the second random matrix (A).