PRIVATE KEY GENERATION APPARATUS AND METHOD, AND STORAGE MEDIA STORING PROGRAMS FOR EXECUTING THE METHODS

• US 20130322621A1
• 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), SNU R&DB Foundation (Seoul National University)
• Original Assignee: Samsung SDS (China) Co., Ltd. (Samsung Group), SNU R&DB Foundation (Seoul National University)
• Inventors: YOON, Hyo Jin, CHEON, Jung Hee, SOHN, Jung Hoon
• Granted Patent: US 9,036,818 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/0836 using tree structure or hierarchical structure
• 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

Disclosed herein are a private key generation apparatus and method, and storage media storing programs for executing the methods on a computer. The private key generation apparatus includes a root private key generation unit and a sub-private key generation unit. The root private key generation unit sets a root master key and predetermined parameters capable of generating private keys, and generates a first sub-master key set capable of generating a number of private keys equal to or smaller than a preset limited number. The sub-private key generation unit generates private keys with the root private key generation unit by receiving the first sub-master key set from the root private key generation unit, to generate a private key corresponding to a user ID using the first sub-master key set, and issues the private key to a user.

Claims

1. A private key generation apparatus, comprising:

a root private key generation unit configured to set a root master key and predetermined parameters capable of generating private keys, and to generate a first sub-master key set capable of generating a number of private keys equal to or smaller than a preset limited number; and

a sub-private key generation unit configured to share authority to generate private keys with the root private key generation unit by receiving the first sub-master key set from the root private key generation unit, to generate a private key corresponding to a user ID using the first sub-master key set, and to issue the private key to a user;

wherein the root private key generation unit receives a sub-private key generation unit ID from the sub-private key generation unit, authenticates the sub-private key generation unit ID, and transmits the first sub-master key set to the sub-private key generation unit if the authentication is successful.

2. The private key generation apparatus of claim 1, wherein the sub-private key generation unit generates the private key corresponding to the user ID by linearly combining a bit representation value obtained by applying a hash function to the user ID and the first sub-master key set.

3. The private key generation apparatus of claim 1, wherein the root private key generation unit, if a request for issuance of an additional sub-master key set is input by the sub-private key generation unit so as to provide a number of private keys larger than the preset limited number, generates a second sub-master key set capable of generating a number of private keys equal to a number of additionally requested users and provides the second sub-master key set to the sub-private key generation unit.

4. The private key generation apparatus of claim 3, further comprising a charging unit configured to charge for the second sub-master key set.

5. The private key generation apparatus of claim 1, wherein the root private key generation unit directly generates a private key corresponding to a user ID using the root master key and issues the private key to a user who does not fall within a preset range of private key issuance target users.

6. The private key generation apparatus of claim 1, wherein the first sub-master key is provided to the sub-private key generation unit via a first private channel, and the private key corresponding to the user ID is issued to the user via a second private channel.

7. The private key generation apparatus of claim 1, wherein the root private key generation unit issues the first sub-master key set mk_GID using discrete log values for a base g that belong to sub-parameters of the predetermined parameters;

wherein mk_GID=(x₁, x₂, . . . , x_n) (where g_i=g^xi, and x_i=log_gg_i (1≦

i≦

n)).

8. The private key generation apparatus of claim 1, wherein the sub-private key generation unit computes the private key

9. A private key generation method, the private key generation method being performed by a private key generation apparatus that generates private keys corresponding to user IDs using the user IDs as public keys, the method comprising:

(a) setting, by a root-private key generation unit, a root master key and predetermined root parameters capable of generating private keys;

(b) setting, by a sub-private key generation unit, a number of private key issuance target users and setting predetermined sub-parameters based, and transmitting, by the sub-private key generation unit, the number of private key issuance target users and an ID of the sub-private key generation unit to the root private key generation unit;

(c) authenticating, by the root-private key generation unit, the ID of the sub-private key generation unit;

(d) if the authentication is successful at step (c), generating, by the root-private key generation unit, a first sub-master key set capable of generating a number of private keys equal to the set number of users using the root parameters and the sub-parameters, and transmitting, by the root-private key generation unit, the first sub-master key to the sub-private key generation unit; and

(e) generating, by the sub-private key generation unit, a secret key corresponding to the user ID using the first sub-master key set, and providing, by the sub-private key generation unit, the private key to a user;

wherein the sub-private key generation unit shares authority to generate private keys with the root private key generation unit by receiving the first sub-master key set from the root private key generation unit.

10. The private key generation method of claim 9, wherein at step (a):

the root master key mk_Root is a prime number pair (p, q) that are B-smooth; and

the root parameters comprises a composite number N(=p*q), that is, p×

q, a largest cyclic subgroup G of Zn, a generator g of G, a first hash function H₁, and a second hash function H₂;

wherein p≡

1(mod

     4), q≡

3(mod

     4), Z_N={0, 1, . . . , N−

1}, that is, a finite ring, H₁ is a full domain hash function defined as {0,1}*→

G, and H₂ is a random hash function defined as {0,1}*→

Z_N.

11. The private key generation method of claim 9, wherein at step (b):

the sub-parameters are g_i that is defined using a predetermined hash function based on the preset number of private key issuance target users and service IDs generating the private keys;

wherein g_i=H₁(G_ID,i ), n is the preset number of private key issuance target users (1≦

i≦

n), H₁ is a full domain hash function defined as {0,1}*→

G, G is a largest cyclic subgroup of Zn, Z_N={0, 1, . . . , N−

1}, that is, a finite ring, and G_ID is a private key generation service ID.

12. The private key generation method of claim 9, wherein at step (d):

the first sub-master key set mk_GID is issued using discrete log values for a base g of the sub-parameters;

wherein mk_GID=(x₁, x₂, . . . , x_n) (where g_i=g^xi, and x_i=log_gg_i(1≦

i≦

n)).

13. The private key generation method of claim 9, wherein at step (e):

the private key

14. The private key generation method of claim 13, wherein resulting values of the random hash function H₃ are in a w-sparse form in which only w values (1≦

w≦

n) of b_i (1≦

i≦

n) are set to “

1.”

15. The private key generation method of claim 9, further comprising generating a second sub-master key set capable of generating a number of private keys equal to a number of additional users so as to provide a number of private keys larger than the preset limited number.

16. A computer-readable storage medium storing a program for executing the private key generation method of claim 9 on a computer.