Group signature system, device, and program

• US 8,200,977 B2
• Filed: 01/08/2010
• Issued: 06/12/2012
• Est. Priority Date: 07/11/2007
• Status: Active Grant

• Current Assignee: Toshiba Solutions Corporation (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation), Toshiba Solutions Corporation (Toshiba Corporation)
• Inventors: Okada, Koji, Yoshida, Takuya
• Primary Examiner(s): Homayounmehr, Farid
• Application Number:
  US12/684,606
• Publication Number:
  US 20100169656A1
• Time in Patent Office: 886 Days
• Field of Search: 713/180, 380/44
• US Class Current: 713/180
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• 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

A group signature system includes a group manager device, a signer device and a verifier device capable of communicating with each other, each device using a group signature scheme. The group manager device generates a group secret key, a group public key, a member secret key and a signer tracing information. The signer device generates an encrypted text data of the signer tracing information, and a zero-knowledge proof showing that the signer device knows the member secret key and the encrypted text data is correctly generated based on the signer tracing information. The signer device transmits, to the verifier device, a group signature composed of the encrypted text data and the zero knowledge proof, and the message. The verifier device verifies correctness of the group signature and transmits the verified result to the signer device.

Claims

1. A group signature system comprising a group manager device, a signer device and a verifier device capable of communicating with each other, each device using a group signature scheme, wherein

the group manager device comprises:

a parameter storing module configured to store a public parameter including a prime order q and a generator g₁ of a multiplicative cyclic group G of the prime order q used in the group signature scheme;

a group key generating module configured to generate a group secret key including values a, bε

Z_q, and a group public key including values g₂, f and the generator g₁ satisfying a first relational expression g₂=g₁^a and a second relational expression f=g₁^b, based on the public parameter in the parameter storing module;

a member secret key generating module configured to calculate a member secret key composed of representation (k_i1, k_i2) satisfying a fourth relational expression f=g₁^{k_i1}g₂^{k_i2}, based on the group secret key, the group public key and a third relational expression k_i1=b−

ak_i2 mod q (^ is a symbol representing exponentiation); and

a signer tracing information calculating module configured to calculate signer tracing information T_i=g₁^{k_i1} based on the member secret key and the generator g₁,

the signer device comprises;

a signer storing module configured to store the public parameter including the prime order q and the generator g₁ of the multiplicative cyclic group G of the prime order q used in the group signature scheme, the group public key, the member secret key, the signer tracing information T_i, and a message;

an encrypted text generating module configured to generate encrypted text data of the signer tracing information T_i by encrypting the signer tracing information T_i based on the public parameter and the group public key in the signer storing module;

a zero-knowledge proof generating module configured to generate a zero-knowledge proof showing that the signer device knows the member secret key and the encrypted text data is correctly generated based on the signer tracing information T_i, based on the public parameter, the group public key, the member secret key and the message in the signer storing module, and the encrypted text data of the signer tracing information T_i; and

a module that transmits, to the verifier device, a group signature composed of the encrypted text data and the zero knowledge proof, and the message, and

the verifier device comprises;

a verifier storing module configured to store the public parameter including the prime order q and the generator g₁ of the multiplicative cyclic group G of the prime order q used in the group signature scheme, and the group public key,

a module that receives the group signature and the message from the signer device;

a verifying module configured to verify correctness of the group signature, based on the received group signature and message, the public parameter and the group public key in the verifier storing module; and

a module that transmits the verified result to the signer device.

2. A group manager device capable of communicating with a signer device and a verifier device, the group manager device comprising:

a parameter storing module configured to store a public parameter including a prime order q and a generator g₁ of a multiplicative cyclic group G of the prime order q used in a group signature scheme;

a group key generating module configured to generate a group secret key including values a, bε

Z_q, and a group public key including values g₂, f and the generator g₁ satisfying a first relational expression g₂=g₁^a and a second relational expression f=g₁^b, based on the public parameter in the parameter storing module;

a member secret key generating module configured to calculate a member secret key composed of representation (k_i1, k_i2) satisfying a fourth relational expression f=g₁^{k_i1}g₂^{k_i2}, based on the group secret key, the group public key and a third relational expression k_i1=b−

ak_i2 mod q (^ is a symbol representing exponentiation);

a signer tracing information calculating module configured to calculate signer tracing information T_i=g₁^{k_i1} based on the member secret key and the generator g₁;

a module that transmits, to the signer device, the public parameter, the group public key, the member secret key and the signer tracing information T_i to generate a group signature in the group signature scheme; and

a module that transmits, to the verifier device, the public parameter and the group public key to verify the group signature in the group signature scheme.

3. The group manager device according to claim 2, further comprising:

a user information storing module configured to store the signer tracing information T_i and user identification information ID(i) associated with each other,

a module that receives, from the signer device, the group signature and a message, the group signature being composed of the zero-knowledge proof and the encrypted text data of the signer tracing information T_i, and the zero-knowledge proof showing that, regarding the signer tracing information T_i=g₁^{k_i1}, the member secret key is known and the encrypted text data is correctly generated based on the signer tracing information T_i;

a signature verifying module configured to verify correctness of the group signature, based on the group signature and the message that are received, the public parameter in the parameter storing module, and the group secret key and the group public key that are generated; and

a signer tracing module configured to calculate the signer tracing information T_i from the encrypted text data based on the group secret key when the verified result shows the correctness, and to trace the user identification information ID(i) corresponding to the obtained signer tracing information T_i from the user information storing module, wherein

the encrypted text data is data provided by encrypting the signer tracing information T_i by the signer device based on the public parameter and the group public key, and

the zero-knowledge proof is data generated by the signer device based on the public parameter, the group public key, the member secret key and the message, and the encrypted text data of the signer tracing information T_i.

4. A signer device capable of communicating with a group manager device and a verifier device using a group signature scheme, the signer device comprising:

a module that receives, from the group manager device, a public parameter including a prime order q and a generator g₁ of a multiplicative cyclic group G of the prime order q used in the group signature scheme;

a group public key including values g₂, f and the generator g₁ generated, based on the public parameter, to satisfy values a, bε

Z_q, a first relational expression g₂=g₁^a and a second relational expression f=g₁^b;

a member secret key composed of representation (k_i1, k_i2) generated, based on the values a, bε

Z_q, the group public key and a third relational expression k_i1=b−

ak_i2 mod q, to satisfy a fourth relational expression f=g₁^{k_i1}g₂^{k_i2} (^ is a symbol representing exponentiation); and

the signer tracing information T_i=g₁^{k_i1} generated based on the member secret key and the generator g₁,

a signer storing module configured to store the public parameter, the group public key, the member secret key and the signer tracing information T_i that are received, and a message;

a module configured to generate the message and to store the message in the signer storing module;

an encrypted text generating module configured to generate encrypted text data of the signer tracing information T_i by encrypting the signer tracing information T_i based on the public parameter and the group public key in the signer storing module;

a zero-knowledge proof generating module configured to generate a zero-knowledge proof showing that the member secret key is known and the encrypted text data is correctly generated based on the signer tracing information T_i, based on the public parameter, the group public key, the member secret key and the message in the signer storing module, and the encrypted text data of the signer tracing information T_i, and

a module that transmits, to the verifier device, the group signature composed of the encrypted text data and the zero-knowledge proof, and the message.

5. A verifier device capable of communicating with a group manager device and a signer device used in a group signature scheme, the verifier device comprising:

a module that receives, from the group manager device, a public parameter including a prime order q and a generator g₁ of a multiplicative cyclic group G of the prime order q used in the group signature scheme, and a group public key including values g₂, f and the generator g₁ generated, based on the public parameter, to satisfy values a, bε

Z_q, a first relational expression g₂=g₁^a and a second relational expression f=g₁^b;

a verifier storing module configured to store the public parameter and the group public key that are received;

a module that receives, from the signer device, a member secret key composed of representation (k_i1, k_i2) generated, based on the values a, bε

Z_q, the group public key and a third relational expression k_i1=b−

ak_i2 mod q, to satisfy a fourth relational expression f=g₁^{k_i1}g₂^{k_i2} (^ is a symbol representing exponentiation), a group signature, and a message, the group signature being composed of the zero-knowledge proof and the encrypted text data of the signer tracing information T_i, and the zero-knowledge proof showing that, regarding the signer tracing information T_i=g₁^{k_i1}, the member secret key is known and the encrypted text data is correctly generated based on the signer tracing information T_i;

a verifying module configured to verify correctness of the group signature, based on the group signature and the message that are received, the public parameter, and the group public key in the verifier storing module; and

a module that transmits the verified result to the signer device, wherein the encrypted text data is data provided by encrypting the signer tracing information T_i by the signer device based on the public parameter and the group public key, and

the zero-knowledge proof is data generated by the signer device based on the public parameter, the group public key, the member secret key and the message, and the encrypted text data of the signer tracing information T_i.

6. A non-transitory computer-readable storage medium storing a program used for a group manager device capable of communicating with a signer device and a verifier device using a group signature scheme, the program comprising:

first program code that allows the computer to execute processing of storing a public parameter including a prime order q and a generator g₁ of a multiplicative cyclic group G of the prime order q used in the group signature scheme in a memory of the computer;

second program code that allows the computer to execute processing of generating, based on the public parameter in the memory, a group secret key including values a, bε

Z_q, and a group public key including values g₂, f and the generator g₁ satisfying a first relational expression g₂=g₁^a and a second relational expression f=g₁^b;

third program code that allows the computer to execute processing of calculating a member secret key composed of representation (k_i1, k_i2) satisfying a fourth relational expression f=based on the group secret key, the group public key and a third relational expression k_i1=b−

ak_i2 mod q (^ is a symbol representing exponentiation);

fourth program code that allows the computer to execute processing of calculating signer tracing information T_i=g₁^{k_i1} based on the member secret key and the generator g₁;

fifth program code that allows the computer to execute processing of transmitting, to the signer device, the public parameter, the group public key, the member secret key and the signer tracing information T_i to generate a group signature in the group signature scheme; and

sixth program code that allows the computer to execute processing of transmitting, to the verifier device, the public parameter and the group public key to verify the group signature in the group signature scheme.

7. The program according to claim 6, further comprising:

seventh program code that allows the computer to execute processing of storing the signer tracing information T_i and user identification information ID(i) associated with each other in the memory;

eighth program code that allows the computer to execute processing of receiving, from the signer device, the group signature and a message, the group signature being composed of the zero-knowledge proof and the encrypted text data of the signer tracing information T_i, and the zero-knowledge proof showing that, regarding the signer tracing information T_i=g₁^{k_i1}, the member secret key is known and the encrypted text data is correctly generated based on the signer tracing information T_i;

ninth program code that allows the computer to execute processing of verifying correctness of the group signature, based on the group signature and the message that are received, the public parameter in the parameter storing means, and the group secret key and the group public key that are generated; and

tenth program code that allows the computer to execute processing of calculating the signer tracing information T_i from the encrypted text data based on the group secret key when the verified result shows the correctness, and tracing user identification information ID(i) corresponding to the obtained signer tracing information T_i from the memory, wherein

the encrypted text data is data provided by encrypting the signer tracing information T_i by the signer device based on the public parameter and the group public key, and

the zero-knowledge proof is data generated by the signer device based on the public parameter, the group public key, the member secret key and the message, and the encrypted text data of the signer tracing information T_i.

8. A non-transitory computer-readable storage medium storing a program used for a signer device capable of communicating with a group manager device and a verifier device using a group signature scheme, the program comprising:

first program code that allows the computer to execute processing of receiving, from the group manager device, a public parameter including a prime order q and a generator g₁ of a multiplicative cyclic group G of the prime order q used in the group signature scheme;

a group public key including values g₂, f and the generator g₁ generated, based on the public parameter, to satisfy values a, bε

Z_q, a first relational expression g₂=g₁^a and a second relational expression f=g₁^b;

a member secret key composed of representation (k_i1, k_i2) generated, based on the values a, bε

Z_q, the group public key, and a third relational expression k_i1=b−

ak_i2 mod q, to satisfy a fourth relational expression f=g₁^{k_i1}g₂^{k_i2} (^ is a symbol representing exponentiation); and

signer tracing information T_i=g₁^{k_i1} generated based on the member secret key and the generator g₁,

second program code that allows the computer to execute processing of storing the public parameter, the group public key, the member secret key and the signer tracing information T_i that are received, and a message;

third program code that allows the computer to execute processing of generating the message and storing the message in the memory;

fourth program code that allows the computer to execute processing of generating encrypted text data of the signer tracing information T_i by encrypting the signer tracing information T_i based on the public parameter and the group public key in the memory;

fifth program code that allows the computer to execute processing of generating a zero-knowledge proof showing that the member secret key is known and the encrypted text data is correctly generated based on the signer tracing information T_i, based on the public parameter, the group public key, the member secret key and the message in the memory, and the encrypted text data of the signer tracing information T_i, and

sixth program code that allows the computer to execute processing of transmitting, to the verifier device, the group signature composed of the encrypted text data and the zero-knowledge proof, and the message.

9. A non-transitory computer-readable storage medium storing a program used for a verifier device capable of communicating with a group manager device and a signer device used in a group signature scheme, the program comprising:

first program code that allows the computer to execute processing of receiving, from the group manager device, a public parameter including a prime order q and a generator g₁ of a multiplicative cyclic group G of the prime order q used in the group signature scheme, and a group public key including values g₂, f and the generator g₁ generated, based on the public parameter, to satisfy values a, bε

Z_q, a first relational expression g₂=g₁^a and a second relational expression f=g₁^b;

second program code that allows the computer to execute processing of storing the public parameter and the group public key that are received in a memory of the computer;

third program code that allows the computer to execute processing of receiving, from the signer device, a member secret key composed of representation (k_i1, k_i2) generated, based on the values a, bε

Z_q, the group public key and a third relational expression k_i1=b−

ak_i2 mod q, to satisfy a fourth relational expression f=g₁^{k_i1}g₂^{k_i2} (^ is a symbol representing exponentiation), a group signature, and a message, the group signature being composed of the zero-knowledge proof and the encrypted text data of the signer tracing information T_i, and the zero-knowledge proof showing that, regarding the signer tracing information T_i=g₁^{k_i1}, the member secret key is known and the encrypted text data is correctly generated based on the signer tracing information T_i;

fourth program code that allows the computer to execute processing of verifying correctness of the group signature, based on the group signature and the message that are received, the public parameter, and the group public key in the memory; and

fifth program code that allows the computer to execute processing of transmitting the verified result to the signer device, wherein

the encrypted text data is data provided by encrypting the signer tracing information T_i by the signer device based on the public parameter and the group public key, and

the zero-knowledge proof is data generated by the signer device based on the public parameter, the group public key, the member secret key and the message, and the encrypted text data of the signer tracing information T_i.