MEMBER CERTIFICATE ACQUIRING DEVICE, MEMBER CERTIFICATE ISSUING DEVICE, GROUP SIGNING DEVICE, AND GROUP SIGNATURE VERIFYING DEVICE

• US 20090074188A1
• Filed: 01/16/2006
• Published: 03/19/2009
• Est. Priority Date: 02/10/2005
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Furukawa, Jun
• Granted Patent: US 8,074,067 B2
• Time in Patent Office: Days
• US Class Current: 380/277
• CPC Class Codes: G06Q 20/3678 e-cash details, e.g. blinded, divisible or detecting double spending
• CPC Class Codes: G06Q 20/383 Anonymous user system
• CPC Class Codes: H04L 9/3073 involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3255 using group based signatures, e.g. ring or threshold signatures

Abstract

It is an object of the present invention to enhance the security and reduce the data amount of data to be handled in a group signing system, in which when the group public key which includes: a description for four groups: group 1, group 2, group T, and group E of the same order number; a description of bilinear mapping from group 1 and group 2 to group T; each generator of group 1, group 2, group T, and group E; and a signature public key of a signature scheme using group 1, group 2, and group T, is input, the member secret key including an integer not larger than the order number, member evidence which is a value given by multiplying the generator of group E by the member secret key, and an element of group 1 or group 2 which is a value given by multiplying the generator of the group 1 or the group 2 by the member secret key are sent to the member-certificate issuing device, and thereafter upon receipt of a signature for the member secret key, which is verifiable by the signature public key, from the member-certificate issuing device, the signature is used as the member certificate.

Claims

1. A member-certificate acquiring device, which is input with a group public key and a random number and outputs a member certificate and a member secret key by communicating with a member-certificate issuing device, characterized in that

when input with said group public key which includes:

a description for four groups;

group 1, group 2, group T, and group E, of the same order number;

a description of bilinear mapping from group 1 and group 2 to group T;

each generator of group 1, group 2, group T, and group E; and

a signature public key of a signature scheme using said group 1, said group 2, and said group T, said member-certificate acquiring device sends;

said member secret key including an integer not larger than said order number;

a member evidence which is a value given by multiplying said generator of said group E by said member secret key; and

an element of said group 1 or group 2 which is a value given by multiplying said generator of said group 1 or group 2 by said member secret key, to said member-certificate issuing device, and thereafter upon receipt of a signature for said member secret key, which is verifiable by said signature public key, from said member-certificate issuing device, uses said signature as said member certificate;

and especially group E is a group different from group 1, group 2, and group T, in which solving the Diffie-Hellman discrimination problem is difficult.

13. A group signing system, comprising the member-certificate acquiring device according to claim 1, characterized in that

said member-certificate acquiring device communicates with said member-certificate issuing device to acquire a member certificate and a member secret key;

inputs the acquired said member certificate, the acquired said member secret key, a message, a group public key, and a tracking public key into said group signing device to acquire a group signature for said message; and

inputs said message and the acquired group signature into said group-signature verifying device to verify that the acquired group signature is a valid group signature for said message and to input said group signature into said tracking device thereby outputting a member evidence representing the member which has generated the group signature.

2. A member-certificate issuing device, which is input with a group public key, a group secret key and a random number and which outputs a member evidence for use in identifying a member by communicating with a member-certificate acquiring device, characterized in that

the member-certificate issuing device is input with said group public key which includes:

a description for four groups;

group 1, group 2, group T, and group E, of the same order number;

a description of bilinear mapping from group 1 and group 2 to group T;

each generator of group 1, group 2, group T, and group E; and

a signature public key of a signature scheme using said group 1, said group 2, and said group T, and said group secret key which includes a signature secret key corresponding to said signature public key of a signature scheme using said group 1, said group 2, and said group T, and upon receipt of a member evidence which is a value given by multiplying said generator of said group E by the member secret key, and an element of said group 1 or said group 2 which is a value given by multiplying the generator of said group 1 or group 2 by the member secret key from said member-certificate acquiring device, generates a signature for said member secret key using said signature secret key to send said signature to the member-certificate acquiring device as said member certificate;

and especially group E is a group different from group 1, group 2, and group T, in which solving the Diffie-Hellman discrimination problem is difficult.

14. A group signing system, comprising the member-certificate acquiring device according to claim 2, characterized in that said member-certificate acquiring device communicates with said member-certificate issuing device to acquire a member certificate and a member secret key;

inputs the acquired said member certificate, the acquired said member secret key, a message, a group public key, and a tracking public key into said group signing device to acquire a group signature for said message; and

inputs said message and the acquired group signature into said group-signature verifying device to verify that the acquired group signature is a valid group signature for said message and to input said group signature into said tracking device thereby outputting a member evidence representing the member which has generated the group signature.

3. A group signing device, which is input with a group public key, a tracking public key, a member certificate, a member secret key, and a message and which outputs a group signature for said message, characterized in that

said group signing device comprises an encryption device for creating an encrypted text in which part of the member evidence generated from the said member secret key is encrypted by a tracking public key from:

said group public key including a description for four groups;

group 1, group 2, group T, and group E, of the same order number, a description of bilinear mapping from group 1 and group 2 to group T, each generator of group 1, group 2, group T, and group E, and a signature public key of a signature scheme utilizing said group 1, said group 2, and said group T;

said tracking public key comprising an element of said group E; and

said member secret key;

and especially group E is a group different from group 1, group 2, and group T, in which solving the Diffie-Hellman discrimination problem is difficult.

4. The group signing device according to claim 3, characterized in that said group signing device comprises a knowledge-proof-statement generating device which generates a knowledge proof statement which is data for proving that a secret key encrypted into said encrypted text and a signature for said secret key can be calculated from input data, wherein said group signature to be output includes a knowledge proof statement generated by said knowledge-proof-statement generating device.

5. The group signing device according to claim 4, characterized in that

said knowledge-proof-statement generating device comprises:

a commitment generating device which is input with said group public key, said tracking public key, said member secret key, said member certificate, and said random number and generates a commitment to encryption which is data for proving knowledge of a random number for encryption, and a commitment to a member certificate which is data for proving knowledge of a signature and member secret key, to output said commitment to encryption and said commitment to a member certificate as a commitment;

a challenge-value generating device which is input with said group public key, said tracking public key, said encrypted text, and said commitment and outputs a hash value of the foregoing values as a challenge value; and

a response generating device which is input with said group public key, said member secret key, said member certificate, said random number, and said challenge value, and outputs a response of encryption and a response of member certification as a response.

6. The group signing device according to claim 5, characterized in that said group signature comprises said encrypted text, said commitment, and said response.

7. The group signing device according to claim 5, characterized in that said group signature comprises said encrypted text, said challenge value, and said response.

15. A group signing system, comprising the group signing device according to claim 3, characterized in that

said member-certificate acquiring device communicates with said member-certificate issuing device to acquire a member certificate and a member secret key;

inputs the acquired said member certificate, the acquired said member secret key, a message, a group public key, and a tracking public key into said group signing device to acquire a group signature for said message; and

inputs said message and the acquired group signature into said group-signature verifying device to verify that the acquired group signature is a valid group signature for said message and to input said group signature into said tracking device thereby outputting a member evidence representing the member which has generated the group signature.

8. A group-signature verifying device, which is input with a group public key, a tracking public key, a message, and a group signature, and judges whether said group signature is a valid group signature for said message to output “

valid”

or “

invalid,”

characterized in that

when input with;

a group public key which includes a description for four groups;

group 1, group 2, group T, and group E, of the same order number;

a description of bilinear mapping from group 1 and group 2 to group T;

each generator of group 1, group 2, group T, and group E; and

a signature public key of a signature scheme using said group 1, said group 2, and said group T;

a tracking public key comprising an element of group E; and

a group signature including an encrypted text in which part of member evidence generated by a member secret key is encrypted by the tracking public key, said group-signature verifying device judges whether said group signature is a valid group signature for said message to output “

valid”

or “

invalid”

;

and especially group E is a group different from group 1, group 2, and group T, in which solving the Diffie-Hellman discrimination problem is difficult.

9. The group-signature verifying device according to claim 8, characterized in that

said group-signature verifying device comprises a knowledge-proof-statement verifying device which verifies that a knowledge proof statement is data to prove that a secret key which is used to generate part of member evidence encrypted into said encrypted text, and a signature for the secret key can be calculated from data input into the group signing device and from data included in the group signing device, and

said group signature includes a knowledge proof statement which has been verified by said proof-statement verifying device.

10. The group signing device according to claim 9, characterized in that said group signature comprises said encrypted text, said commitment, and said response, and

said knowledge-proof-statement verifying device comprises:

a challenge-value generating device which is input with said group public key, said tracking public key, said encrypted text, and said commitment, and outputs a hash value of the foregoing values as a challenge value; and

a response verifying device which is input with said group public key, said tracking public key, said encrypted text, said commitment, said challenge value and said response, and outputs “

valid”

or “

invalid”

depending on whether or not these inputs satisfy a given equation, wherein

the output of said response verifying device is output as the output of said group-signature verifying device.

11. The group-signature verifying device according to claim 9, characterized in that:

said group signature comprises said encrypted text, said challenge value, and said response; and

said knowledge-proof-statement verifying device comprises;

a commitment generating device which is input with said group public key, said tracking public key, said response, and said challenge value, and outputs a commitment to encryption and a commitment to member certificate as a commitment; and

a response verifying device which is input with said public key, said tracking public key, said encrypted text, and said commitment, and outputs “

valid”

or “

invalid”

depending on whether or not a hash value of the foregoing values corresponds to said challenge value, wherein

the output of said response verifying device is output as the output of the group-signature verifying device.

16. A group signing system, comprising the group-signature verifying device according to claim 8, characterized in that

said member-certificate acquiring device communicates with said member-certificate issuing device to acquire a member certificate and a member secret key;

inputs the acquired said member certificate, the acquired said member secret key, a message, a group public key, and a tracking public key into said group signing device to acquire a group signature for said message; and

inputs said message and the acquired group signature into said group-signature verifying device to verify that the acquired group signature is a valid group signature for said message and to input said group signature into said tracking device thereby outputting a member evidence representing the member which has generated the group signature.

12. A tracking device, which is input with a group public key, a tracking public key, a group signature, and a tracking secret key, and which decrypts the encrypted text of part of the member evidence generated from a member secret key contained in the group signature to output the part of member evidence which is a value uniquely determined from the member secret key, the encrypted text of part of the member certificate being an ElGamal encrypted text.

17. A group signing system, comprising the tracking device according to claim 12, characterized in that

said member-certificate acquiring device communicates with said member-certificate issuing device to acquire a member certificate and a member secret key;

inputs the acquired said member certificate, the acquired said member secret key, a message, a group public key, and a tracking public key into said group signing device to acquire a group signature for said message; and

inputs said message and the acquired group signature into said group-signature verifying device to verify that the acquired group signature is a valid group signature for said message and to input said group signature into said tracking device thereby outputting a member evidence representing the member which has generated the group signature.