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 20130322620A1
• Filed: 05/31/2013
• Published: 12/05/2013
• 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: YOON, Hyo Jin, LEE, Seon Young, KWON, Ki Sang
• Granted Patent: US 9,172,530 B2
• Time in Patent Office: Days
• US Class Current: 380/44
• 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 a discrete logarithm cyclic group having a one-to-one correspondence relationship with an input user ID; and

a private key calculation unit configured to;

calculate a discrete logarithm result value based on the output specific element value; and

calculate a private key having a one-to-one correspondence relationship with the input user ID.

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 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.

6. The private key generation apparatus according to claim 5, 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.

7. The private key generation apparatus according to claim 6, 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.

8. The private key generation apparatus according to claim 6, 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.

9. The private key generation apparatus according to claim 5, 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.

10. 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 a discrete logarithm cyclic group having a one-to-one correspondence relationship with an input user ID; and

(b) calculating a discrete logarithm result value based on the output specific element value and calculating a private key having a one-to-one correspondence relationship with the input user ID.

11. The private key generation method according to claim 10, 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.

12. The private key generation method according to claim 11, 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.

13. The private key generation method according to claim 12, 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.

14. The private key generation method according to claim 10, 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.

15. The private key generation method according to claim 14, 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.

16. The private key generation method according to claim 15, 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.

17. The private key generation method according to claim 15, 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.

18. The private key generation method according to claim 14, 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.

19. 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; and

using the predetermined parameters, obtaining the one-to-one correspondence between the input user ID and the discrete logarithm result value.

20. The private key generation method according to claim 19, 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.

21. The private key generation method according to claim 20, 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.

22. 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;

then

outputting a specific element value of a discrete logarithm cyclic group having a one-to-one correspondence relationship with the input user ID, based on the previously set jacobi value.

23. The private key generation method according to claim 22, 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.

24. The private key generation method according to claim 22, 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.

25. 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 a discrete logarithm cyclic group having a one-to-one correspondence relationship with an input user ID; and

(b) calculating a discrete logarithm result value based on the output specific element value and calculating a private key having a one-to-one correspondence relationship with the input user ID.