Digital signature method based on identification information of group members, and methodof acquiring identification information of signed-group member, and digital signature system for performing digital signature based on identification information of group members

• US 20050097316A1
• Filed: 11/01/2004
• Published: 05/05/2005
• Est. Priority Date: 11/01/2003
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kim, Dae-youb
• Granted Patent: US 7,590,850 B2
• Time in Patent Office: Days
• US Class Current: 713/163
• CPC Class Codes: H04L 9/3255 using group based signatures, e.g. ring or threshold signatures

Abstract

A digital signature method based on identification information of one or more group members who belong to a group includes: a) a group parameter generating operation generating group public key information and group secret key information corresponding to the group; b) a member registering operation generating member secret key information using identification information of the group members who belong to the group and an identification information digest value obtained by applying a predetermined hash function to the identification information, and transmitting the member secret key information to the group members; c) a digital signing operation generating a digital signature by applying a predetermined signature algorithm to the identification information and the identification information digest value, and transmitting the generated digital signature and a message; and d) an authentication operation verifying a validity of the digital signature by applying a predetermined authentication algorithm to the message and the digital signature.

Claims

1. A digital signature method based on identification information of one or more group members who belong to a group, the method comprising:

a) a group parameter generating operation including generating group public key information and group secret key information corresponding to the group;

b) a member registering operation including generating member secret key information using identification information of the group members who belong to the group and an identification information digest value obtained by applying a predetermined hash function on the identification information, and transmitting the member secret key information to the group members;

c) a digital signing operation including generating a digital signature by applying a predetermined signature procedure to the identification information and the identification information digest value, and transmitting the generated digital signature and a message; and

d) an authentication operation including verifying a validity of the digital signature by applying a predetermined authentication procedure to the message and the digital signature.

2. The method as claimed in claim 1, wherein the predetermined signature procedure uses different random numbers every time a digital signature is generated.

3. The method as claimed in claim 2, wherein the group parameter generating operation comprises:

a1) selecting prime numbers p and q as first and second group manager secret key information, and calculating a first group manager public key information m=p×

q (where, Z_m={0, 1, . . . , m−

1} and Z_m*=(aε

Z_m/gcd(m, a)=1});

a2) selecting g, which satisfies g<

min(p, q), as a second group manager public key information;

a3) selecting a third group manager secret key information x, which satisfies xε

{aε

Z_m/gcd(a, Φ

(m))=1}, selecting an arbitrary number hε

Z_m*, and calculating y≡

h^x mod m;

a4) calculating a third group manager public key information u, which satisfies x·

u≡

1 mod Φ

(m);

a5) selecting a fourth group manager public key information e, and calculating a fourth group manager secret key information d, which satisfies e·

d≡

1 mod Φ

(m), (where, gcd(e, Φ

(m))=1); and

a6) laying open the first through fourth group manager public key information m, g, u, e as a group manager public key information and storing the first through the fourth group manager secret key information p, q, x, d as a group manager secret key information.

4. The method as claimed in claim 3, wherein the member registering operation comprises:

b1) with respect to identification information ID_i of group members U_i, calculating a first group member secret key information x_i, which satisfies H(ID_i)≡

g^xi mod m, using the second group manager public key information g (where, H is a unidirectional hash function and H(ID_i) is an identification information digest value);

b2) calculating a second group member secret key information z_i, which satisfies ID_i≡

z_i^e mod m, using the fourth group manager public key information e; and

b3) transmitting the first and second group member secret key information (x_i, z_i) to the group members.

5. The method as claimed in claim 4, wherein the digital signing operation comprises:

c1) selecting first through fifth random numbers β

, ω

, ε

, T, π

, (where, β

, ω

, ε

, T, π

ε

Z_m);

c2) generating a first digital signature information A, which satisfies A=(ε

·

T·

z_i) mod m, using the second group member secret key information

c3) generating a second digital signature information B, which satisfies B=ε

^e.u.·

h^ω

mod m, using the fourth group manager public key information e;

c4) generating a third digital signature information C, which satisfies C=ε

^e·

y^ω

·

ID_i, using the identification information ID_i;

c5) generating fourth digital signature information D, which satisfies D=T·

g^ω

·

H(ID_i), using the identification information digest value H(ID_i);

c6) generating a fifth digital signature information E, which satisfies E=H(y ∥

g ∥

A ∥

B ∥

C ∥

D ∥

t ∥

M), (where, ∥

is a concatenation operator, t=(y^β

·

g^π

) mod m, and M is a message);

c7) generating a sixth digital signature information F, which satisfies F=β

−

E·

ω

;

c8) generating a seventh digital signature information G, which satisfies G=π

−

E·

e·

(ω

+x_i); and

c9) transmitting the first through seventh digital signature information A, B, C, D, E, F, G and the message M.

6. The method as claimed in claim 5, wherein the authentication operation comprises:

d1) calculating a parametric value

$T={\left({\left(\frac{D}{A}\right)}^e·<br><br>C\right)}^E·<br><br>y^F·<br><br>g^G<br><br>\mathrm{mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>m,$

mod m,

using the received first through seventh digital signature information A, B, C, D, E, F, G and the group manager public key information m, g, u, e;

d2) calculating an authentication value E′

=H(y ∥

g ∥

h ∥

A ∥

B ∥

C ∥

D ∥

T ∥

M), using the parametric value T;

d3) comparing the authentication value E′ and

the received fifth digital signature information E; and

d4) determining that the digital signature is valid when the authentication value E′ and

the fifth digital signature information E are identical, and determining that the digital signature is not valid when the authentication value E′ and

the fifth digital signature information E are not identical.

7. A computer-readable medium having recorded thereon a computer program for performing the method according to claim 1.

8. A method for acquiring identification information of signed-group member in data encryption using public key encryption based on identification information of one or more group members who belong to a group, the method comprising:

a) a group parameter generating operation including generating group public key information and group secret key information corresponding to the group;

b) a member registering operation including generating member secret key information using identification information of the group members who belong to the group and an identification information digest value which results from application of predetermined hash function to the identification information, and transmitting the member secret key information to group members;

c) a digital signing operation including generating a digital signature by applying a predetermined signature procedure to the identification information and the identification information digest value, and transmitting the generated digital signature and a message; and

d) an identification information acquiring operation including acquiring the identification information of group members who have performed the digital signature using the group secret key information.

9. The method as claimed in claim 8, wherein the predetermined signature procedure uses different random numbers every time a digital signature is generated.

10. The method as claimed in claim 9, wherein the group parameter generating operation comprises:

a1) selecting prime numbers p and q as first and second group manager secret key information, and calculating a first group manager public key information m=p×

q (where, Z_m={0, 1, . . . , m−

1} and Z_m*={aε

Z_m/gcd(m, a)=1));

a2) selecting g, which satisfies g<

min(p, q), as a second group manager public key information;

a3) selecting a third group manager secret key information x, which satisfies xε

{aε

Z_m/gcd(a, Φ

(m))=1}, selecting an arbitrary number hε

Z_m*, and calculating y≡

h^x mod m;

a4) calculating a third group manager public key information u, which satisfies x·

u≡

1 mod Φ

(m);

a5) selecting a fourth group manager public key information e, and calculating a fourth group manager secret key information d, which satisfies e·

d≡

1 mod Φ

(m) (where, gcd(e, Φ

(m))=1); and

a6) laying open the first through fourth group manager public key information m, g, u, e as a group manager public key information and storing the first through the fourth group manager secret key information p, q, x, d as a group manager secret key information.

11. The method as claimed in claim 10, wherein the member registering operation comprises:

b1) with respect to identification information ID_i of group members U_i, calculating a first group member secret key information x_i, which satisfies H(ID_i)≡

g^xi mod m, using the second group manager public key information g (where, H is a unidirectional hash function and H(ID_i) is an identification information digest value);

b2) calculating a second group member secret key information z_i, which satisfies ID_i≡

z_i^e mod m, using the fourth group manager public key information e; and

b3) transmitting the first and second group member secret key information x_i, z_i to the group members.

12. The method as claimed in claim 11, wherein the digital signing operation comprises:

c1) selecting first through fifth random numbers β

, ω

, ε

, T, π

, (where, β

, ω

, ε

, T, π

ε

Z_m);

c2) generating a first digital signature information A, which satisfies A=(ε

·

T·

z_i) mod m, using the second group member secret key information z_i;

c3) generating a second digital signature information B, which satisfies B=ε

^e.u.·

h^ω

mod m, using the fourth group manager public key information e;

c4) generating a third digital signature information C, which satisfies C=ε

^e·

y^ω

·

ID_i, using the identification information ID_i;

c5) generating a fourth digital signature information D, which satisfies D=T·

g^ω

·

H(ID_i), using the identification information digest value H(ID_i);

c6) generating a fifth digital signature information E, which satisfies E=H(y ∥

g ∥

h ∥

A ∥

B ∥

C ∥

D ∥

t ∥

M), (where, ∥

is a concatenation operator, t=(y^β

·

g^π

) mod m, and M is a message);

c7) generating a sixth digital signature information F, which satisfies F=β

−

E·

ω

;

c8) generating a seventh digital signature information G, which satisfies G=π

−

E·

e·

(ω

+x_i); and

c9) transmitting the first through seventh digital signature information A, B, C, D, E, F, G and the message M.

13. The method as claimed in claim 12, wherein the identification information acquiring operation comprises:

d1) calculating C/B^x, using the third group manager secret key information x; and

d2) providing the result from d1) as identification information of members.

14. A computer-readable medium having recorded thereon a computer program for performing the method according to claim 8.

15. A digital signature system performing digital signature based on identification information of one or more group members who belong to a group, the system comprising:

a group parameter generator generating group public key information and group secret key information corresponding to the group;

a member secret key information generator generating member secret key information using identification information of the group members who belong to the group and an identification information digest value obtained by applying a predetermined hash function to the identification information, and transmitting the member secret key information to the group members;

a digital signing unit generating digital signature by applying a predetermined signature procedure to the identification information and the identification information digest value, and transmitting the generated digital signature and a message; and

a digital signature authenticator verifying a validity of the digital signature by applying a predetermined authentication procedure to the message and the digital signature.

16. The digital signature system as claimed in claim 15, wherein the digital signing unit uses different random numbers every time a digital signature is generated.

17. The digital signature system as claimed in claim 16, the digital signature system further comprising an identification information acquiring unit acquiring the identification information of group members performing digital signatures using the group secret key information.

18. The digital signature system as claimed in claim 16, wherein the group parameter generator comprises:

a first calculator selecting prime numbers p and q as first and second group manager secret key information, and calculating a first group manager public key information m=p×

q (where, Z_m={0, 1, . . . , m−

1} and Z_m*={aε

Z_m/gcd(m, a)=1});

a second calculator selecting g, which satisfies g<

min(p, q), as a second group manager public key information;

a third calculator selecting a third group manager secret key information x, which satisfies xε

{aε

Z_m/gcd(a, Φ

(m))=1}, selecting an arbitrary number hε

Z_m*, and calculating y≡

h^x mod m;

a fourth calculator calculating a third group manager public key information u, which satisfies x·

u≡

1 mod Φ

(m);

a fifth calculator selecting a fourth group manager public key information e and calculating a fourth group manager secret key information d, which satisfy e·

d≡

1 mod Φ

(m) (where, gcd(e, Φ

(m))=1); and

a group manager laying open the first through fourth group manager public key information m, g, u, e as a group manager public key information and storing the first through the fourth group manager secret key information p, q, x, d as a group manager secret key information.

19. The digital signature system as claimed in claim 18, wherein the member secret key information generator comprises:

a first generator calculating a first group member secret key information x_i, which satisfies H(ID_i)≡

g^xi mod m with respect to the identification information ID_i of group members U_i, using the second group manager public key information g, (where, H is a unidirectional hash function and H(ID_i) is an identification information digest value);

a second generator calculating a second group member secret key information z_i, which satisfies ID_i≡

z_i^e mod m, using the fourth group manager public key information e; and

a group member secret key transmitter transmitting the first and second group member secret key information x_i, z_i to the group members.

20. The digital signature system as claimed in claim 19, wherein the digital signature system comprises:

a random number selector selecting first through fifth random numbers β

, ω

, ε

, T, π

(where, β

, ω

, ε

, T, π

ε

Z_m);

a first signature information generator generating a first digital signature information A, which satisfies A=(ε

·

T·

z_i) mod m, using the second group members secret key information z_i;

a second signature information generator generating a second digital signature information B, which satisfies B=ε

^e.u.·

h^ω

mod m, using the fourth group manager public key information e;

a third signature information generator generating a third digital signature information C, which satisfies C=ε

^e·

y^ω

·

ID_i, using the identification information ID_i;

a fourth signature information generator generating a fourth digital signature information D which satisfies D=T·

g^ω

·

H(ID_i), using the identification information digest value H(ID_i);

a fifth signature information generator generating a fifth digital signature information E, which satisfies E=H(y ∥

g ∥

h ∥

A ∥

B ∥

C ∥

D ∥

t∥

M), (where, ∥

is a concatenation operator, t=(y^β

·

g^π

) mod m, and M is a message);

a sixth signature information generator generating a sixth digital signature information F, which satisfies F=β

−

E·

ω

;

a seventh signature information generator generating a seventh digital signature information G, which satisfies G=π

−

E·

e·

(ω

+x_i); and

a signature information transmitter transmitting the first through seventh digital signature information A, B, C, D, E, F, G and the message M.

21. The digital signature system as claimed in claim 20, wherein the digital signature authenticator comprises:

a parametric value calculator calculating parametric value

$T={\left({\left(\frac{D}{A}\right)}^e·<br><br>C\right)}^E·<br><br>y^F·<br><br>g^G<br><br>\mathrm{mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>m,$

mod m, using the received first through seventh digital signature information A, B, C, D, E, F, G and the group manager public key information m, g, u, e;

an authentication value calculator calculating an authentication value E′

=H(y ∥

g ∥

h ∥

A ∥

B ∥

C ∥

D ∥

T ∥

M), using the parametric value T;

a comparator comparing the authentication value E′ and

the received fifth digital signature information E; and

a determining unit determining that the digital signature is valid when the authentication value E′ and

the fifth digital signature information E are identical, and determining that the digital signature is not valid when the authentication value E′ and

the fifth digital signature information E are not identical.

22. The digital signature system as claimed in claim 21, wherein the identification acquiring unit comprises:

an identification information calculator calculating C/B^x using the third group manager secret key information x; and

an identification information provider providing an output of the identification information calculator as identification information of members.