Apparatus and method for generating secret key for ID-based encryption system and recording medium having program recorded thereon for causing computer to execute the method

• US 9,172,530 B2
• Filed: 05/31/2013
• Issued: 10/27/2015
• Est. Priority Date: 05/31/2012
• Status: Active Grant

• Current Assignee: Samsung SDS (China) Co., Ltd. (Samsung Group)
• Original Assignee: Samsung SDS (China) Co., Ltd. (Samsung Group)
• Inventors: Lee, Seon Young, Yoon, Hyo Jin, Kwon, Ki Sang
• Primary Examiner(s): Cervetti, David Garcia
• Application Number:
  US13/906,867
• Publication Number:
  US 20130322620A1
• Time in Patent Office: 879 Days
• Field of Search: 380/44
• US Class Current: 1/1
• CPC Class Codes: H04L 9/0816 Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
• CPC Class Codes: H04L 9/3006 underlying computational problems or public-key parameters
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves

Abstract

A private key generation apparatus for generating a private key corresponding to a user ID using the user ID as a public key is disclosed. When a user ID is input, an ID conversion unit outputs a specific element value of a discrete logarithm cyclic group having a one-to-one correspondence relationship with an input user ID. A private key calculation unit calculates a discrete logarithm result value based on the output specific element value of the discrete logarithm cyclic group and calculates a private key having a one-to-one correspondence relationship with the user ID. According to the present invention, it is possible to concretely propose a method of calculating a secret key, capable of guaranteeing a one-to-one correspondence relationship between the ID and the private key by applying a method of calculating a discrete logarithm using the pre-computation table in an ID-based encryption system.

Claims

1. A private key generation apparatus intended for use in generating a private key corresponding to a user ID using the user ID as a public key, the apparatus comprising:

an ID conversion unit configured to output a specific element value of one discrete logarithm cyclic group having a one-to-one correspondence relationship with an input user ID by using a value of a previously set length irrespective of a length of the input user ID; and

a private key calculation unit configured to;

calculate a discrete logarithm result value based on the output specific element value of the one discrete logarithm cyclic group; and

calculate a private key having a one-to-one correspondence relationship with the input user ID by using parameters set so that the input user ID as the input value and the discrete logarithm result value as the output value are in one-to-one correspondence to each other,

wherein the private key calculation unit comprises;

a setting unit configured to set parameters for one-to-one correspondence between the input user ID and the discrete logarithm result value;

a pre-computation table generation unit configured to store a value of a result of performing a multiplication operation using the set parameters in the form of a data structure to generate a lookup table, and store a chain value of a cyclic function value taking into account a time-memory trade off using the lookup table, in the form of a data structure, to generate a pre-computation table; and

a discrete logarithm calculation unit configured to receive data from the setting unit and the pre-computation table generation unit, and calculate a discrete logarithm result value using an index value of the pre-computation table,

wherein at least one of the ID conversion unit and the private key calculation unit is implemented as a hardware component.

2. The private key generation apparatus according to claim 1, wherein the ID conversion unit is further configured to:

convert an ID, using a function in which the input user ID and the output specific element value have a one-to-one correspondence relationship, so as to provide a converted value;

determine whether a jacobi value of the converted value corresponds to a previously set reference value; and

cause the input user ID and the generated private key to have a one-to-one correspondence relationship.

3. The private key generation apparatus according to claim 2, wherein the ID conversion unit is further configured to:

apply a hash function to the input user ID to generate a first conversion value of a number having a certain length;

generate a second conversion value obtained by adding data having a certain bit size to the first conversion value; and

determine whether the jacobi value of the second conversion value corresponds to the previously set reference value.

4. The private key generation apparatus according to claim 3, wherein when the jacobi value of the second conversion value does not correspond to the previously set reference value, a value of the added data is continuously changed.

5. The private key generation apparatus according to claim 1, wherein the setting unit is configured to:

set a prime number parameter P whose remainder is 1 when divided by 4, and a prime number parameter Q whose remainder is 3 when divided by 4; and

define a new parameter N (N=P*Q) using the parameters P and Q to set sizes of the respective parameters N, P and Q.

6. The private key generation apparatus according to claim 5, wherein the private key generation apparatus is further configured to confirm:

whether the greatest common divisor of (P−

1)/2 and (Q−

1)/2 is 1 using the parameters P and Q; and

whether the sizes of the parameters N, P and Q meet the set values.

7. The private key generation apparatus according to claim 5, wherein the private key generation apparatus is further configured to adjust one or more of the sizes and the numbers of the prime factors constituting the parameters P and Q according to the set values of the parameters in the setting unit.

8. The private key generation apparatus according to claim 1, wherein the private key generation apparatus is further configured to adjust one or more of a condition of the chains and a total number of necessary chains according to:

the set values of the parameters of the pre-computation table generation unit, and

set values that take into consideration the time-memory trade off.

9. A private key generation method performed by a private key generation apparatus, intended for use in generating a private key corresponding to a user ID using the user ID as a public key, the method comprising:

(a) outputting a specific element value of one discrete logarithm cyclic group having a one-to-one correspondence relationship with an input user ID by using a value of a previously set length irrespective of a length of the input user ID; and

(b) calculating a discrete logarithm result value based on the output specific element value of the one discrete logarithm cyclic group and calculating a private key having a one-to-one correspondence relationship with the input user ID by using parameters which are set so that the input user ID that is the input value and the discrete logarithm result value that is the output value correspond to each other in one to one,

wherein step (b) comprises;

(b1) setting parameters for one-to-one correspondence between the input user ID and the discrete logarithm result value;

(b2) storing a value of a result of performing a multiplication operation using the set parameters in the form of a data structure to generate a lookup table, and storing a chain value of a cyclic function value taking into account a time-memory trade off (TMTO) using the lookup table, in the form of a data structure, to generate a pre-computation table; and

(b3) receiving data from the pre-computation table, and calculating a discrete logarithm result value using an index value of the pre-computation table.

10. The private key generation method according to claim 9, wherein step (a) includes:

converting an ID using a function in which the input user ID and the output specific element value have a one-to-one correspondence relationship, so as to provide a converted value;

determining whether a jacobi value of the converted value corresponds to a previously set reference value; and

causing the input user ID and the generated private key to have a one-to-one correspondence relationship.

11. The private key generation method according to claim 10, wherein step (a) further includes:

applying a hash function to the input ID to generate a first conversion value of a number having a certain length;

generating a second conversion value obtained by adding data having a certain bit size to the first conversion value; and

determining whether the jacobi value of the second conversion value corresponds to the previously set reference value.

12. The private key generation method according to claim 11, wherein when the jacobi value of the second conversion value does not correspond to the previously set reference value, a value of the added data is continuously changed.

13. The private key generation method according to claim 9, wherein step (b) includes:

setting a prime number parameter P whose remainder is 1 when divided by 4, and a prime number parameter Q whose remainder is 3 when divided by 4; and

defining a new parameter N (N=P*Q) using the parameters P and Q to set sizes of the respective parameters N, P and Q.

14. The private key generation method according to claim 13, further comprising:

confirming whether the greatest common divisor of (P−

1)/2 and (Q−

1)/2 is 1 using the parameters P and Q; and

confirming whether the sizes of the parameters N, P and Q meet the set values.

15. The private key generation method according to claim 13, further comprising adjusting the sizes and the numbers of the prime factors constituting the parameters P and Q, according to the set values of the parameters.

16. The private key generation method according to claim 9, further comprising adjusting a condition of the chains and a total number of necessary chains according to:

the set values of the parameters of the pre-computation table; and

set values that take into consideration the time-memory trade off.

17. A private key generation method performed by a private key generation apparatus, intended for use in generating a private key corresponding to a user ID using the user ID as a public key, the method comprising:

setting predetermined parameters, in advance, for use in obtaining a one-to-one correspondence between a user ID to be received in the future, and a discrete logarithm result value;

then

receiving the user ID as an input user ID;

using the predetermined parameters which are set so that the input user ID that is the input value and the discrete logarithm result value that is the output value correspond to each other in one to one, obtaining the one-to-one correspondence between the input user ID and the discrete logarithm result value; and

calculating a discrete logarithm result value based on the output specific element value of the one discrete logarithm cyclic group and calculating a private key having a one-to-one correspondence relationship with the input user ID by using parameters which are set so that the input user ID that is the input value and the discrete logarithm result value that is the output value correspond to each other in one to one,

wherein the calculating comprises setting parameters for one-to-one correspondence between the input user ID and the discrete logarithm result value;

storing a value of a result of performing a multiplication operation using the set parameters in the form of a data structure to generate a lookup table, and storing a chain value of a cyclic function value taking into account a time-memory trade off (TMTO) using the lookup table, in the form of a data structure, to generate a pre-computation table; and

receiving data from the pre-computation table, and calculating a discrete logarithm result value using an index value of the pre-computation table.

18. The private key generation method according to claim 17, wherein the predetermined parameters include a prime number parameter P whose remainder is 1 when divided by 4, and a prime number parameter Q whose remainder is 3 when divided by 4.

19. The private key generation method according to claim 18, further comprising defining a new parameter N (N=P*Q) using the parameters P and Q to set sizes of the respective parameters N, P and Q.

20. A private key generation method performed by a private key generation apparatus, intended for use in generating a private key corresponding to a user ID using the user ID as a public key, the method comprising:

setting a jacobi value based on the user ID;

outputting a specific element value of one discrete logarithm cyclic group having a one-to-one correspondence relationship with the input user ID, based on the previously set jacobi value by using a value of a previously set length irrespective of a length of the input user ID; and

calculating a discrete logarithm result value based on the output specific element value of the one discrete logarithm cyclic group and calculating a private key having a one-to-one correspondence relationship with the input user ID by using parameters which are set so that the input user ID that is the input value and the discrete logarithm result value that is the output value correspond to each other in one to one,

wherein the calculating comprises setting parameters for one-to-one correspondence between the input user ID and the discrete logarithm result value;

storing a value of a result of performing a multiplication operation using the set parameters in the form of a data structure to generate a lookup table, and storing a chain value of a cyclic function value taking into account a time-memory trade off (TMTO) using the lookup table, in the form of a data structure, to generate a pre-computation table; and

receiving data from the pre-computation table, and calculating a discrete logarithm result value using an index value of the pre-computation table.

21. The private key generation method according to claim 20, further comprising:

converting an ID using a function in which the user ID that is an input value and the output specific element value have a one-to-one correspondence relationship;

making a determination as to whether a jacobi value of the converted value corresponds to a previously set reference value; and

causing the user ID and the generated private key to have a one-to-one correspondence relationship in accordance with the determination.

22. The private key generation method according to claim 20, further comprising:

applying a predetermined hash function to the user ID to generate a first conversion value of a number having a certain length;

generating a second conversion value obtained by adding data having a certain bit size to the first conversion value; and

determining whether the jacobi value of the second conversion value corresponds to the previously set reference value.

23. A non-transitory computer-readable recording medium storing instructions configured to enable a computer processor to execute operations implementing a private key generation method comprising:

(a) outputting a specific element value of one discrete logarithm cyclic group having a one-to-one correspondence relationship with an input user ID by using a value of a previously set length irrespective of a length of the input user ID; and

(b) calculating a discrete logarithm result value based on the output specific element value of the one discrete logarithm cyclic group and calculating a private key having a one-to-one correspondence relationship with the input user ID by using parameters which are set so that the input user ID that is the input value and the discrete logarithm result value that is the output value correspond to each other in one to one,

wherein step (b) comprises;

(b1) setting parameters for one-to-one correspondence between the input user ID and the discrete logarithm result value;

(b2) storing a value of a result of performing a multiplication operation using the set parameters in the form of a data structure to generate a lookup table, and storing a chain value of a cyclic function value taking into account a time-memory trade off (TMTO) using the lookup table, in the form of a data structure, to generate a pre-computation table; and

(b3) receiving data from the pre-computation table, and calculating a discrete logarithm result value using an index value of the pre-computation table.