Private key generation apparatus and method, and storage media storing programs for executing the methods

• US 9,036,818 B2
• Filed: 05/31/2013
• Issued: 05/19/2015
• 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, Sohn, Jung Hoon, Cheon, Jung Hee
• Primary Examiner(s): Cervetti, David Garcia
• Application Number:
  US13/907,139
• Publication Number:
  US 20130322621A1
• Time in Patent Office: 718 Days
• Field of Search: 380/44, 380/277, 380/30, 380/282, 380/278, 380/28, 380/259, 380/286, 380/285, 380/46
• 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 and information about the number of service users 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,

wherein at least one of the root private key generation unit and the sub-private key generation unit is implemented as a hardware component.

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 and information about the number of service users 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 non-transitory computer-readable storage medium storing a program for executing the private key generation method of claim 9 on a computer.