Group Signature Scheme

• US 20080152130A1
• Filed: 12/13/2005
• Published: 06/26/2008
• Est. Priority Date: 01/21/2005
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Teranishi, Isamu
• Granted Patent: US 8,127,140 B2
• Time in Patent Office: Days
• US Class Current: 380/30
• 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/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3255 using group based signatures, e.g. ring or threshold signatures

Abstract

An efficient and safe group signature scheme is provided. According to the present invention, an open unit is provided to not an issuer but an opener, and a data required for operating the open unit does not include a key pair of the issuer, so that it is possible to accurately operate the open unit even if the issuer generates the public key in an illegal manner. In addition, it is possible to prove that a key pair of a member cannot be counterfeited. It is possible to implement from a discrete logarithm assumption a feature that a cipher text, that is, a portion of a signature text can be decrypted only by the opener in a method which is the same as a method representing that an ElGamal crypto scheme is safe. In addition, it is possible to implement from a random oracle assumption a feature that a knowledge signature has an extractability in a method which is the same as a method proving that a Schnorr signature is safe.

Claims

1. A group signature scheme of a proving apparatus having an input means, a calculating means, and an output means, comprising:

a step where the input means reads a data required for calculation;

a step where, when N is set to one of security parameters and a knowledge of a discrete logarithm of (a, C) is proven, the calculating means selects at random N integers X_—

{1j} and calculates X_—

{1j} for each j by using secret information x′ and

the X_—

{0j};

a step where the calculating means selects r_{ij} for each j and calculating a hash value C_{ij} of a data including the X_{ij} and the r_{ij};

a step where the calculating means calculates L_{j} for each j by raising the a to the power X_—

{0j};

a step where the calculating means selects a challenge c_j for each j and setting ξ

_{j} for each j to the X_{c_jj}; and

a step where the output means outputs a data including the {C_{ij}} and the {ξ

_{j}}.

2. A group signature scheme of a verifying apparatus having an input means, a calculating means, and an output means, comprising:

a step where the input means reads a data required for calculation;

a step where, when a knowledge of a discrete logarithm of (a, C) is proven, the calculating means acquires a challenge c_j for each j;

a step where the calculating means calculates L_{j}̂

* by multiplying a value obtained by raising the C to the power a sign-inverted c_j with a value obtained by raising the a to the power a portion ξ

_{j} of the input data;

a step where the calculating means checks whether or not a hash value of a data including the L_{j}̂

* is equal to the challenge c_j; and

a step where, if the hash value of the data including the L_{j}̂

* is not equal to the challenge c_j, the output means outputs a message indicating that the proving of the knowledge of the discrete logarithm of the (a, C) is not valid.

3. A group signature scheme of a user apparatus which communicates with an issuer apparatus to generate a member secret key, a member public key, and user-specified information, comprising:

a first step of reading a required data including a public key of an issuer;

a second step of generating at random an integer x′

, calculating power residue, and transmitting a calculation results C of the power residue to the issuer apparatus;

a third step of receiving a number x″

generated by the issuer apparatus, calculating x by using the x′ and

the x″

, setting the x to the member secret key or a portion thereof, calculating at least two-times power residue, transmitting at least β

of calculation results β and

B of the two-times power residue to the issuer apparatus, and setting the B to the user-specified information, wherein the β

is obtained by calculating the power residue using a portion G of the public key of the issuer apparatus as a base and the x as an exponent;

a fourth step of receiving an integer e and an element b of a quadratic residue group with an RSA modulus from the issuer apparatus;

a step where the output means adds the (b, e) to the member public key or a portion thereof and outputs the member public key and the member secret key,

wherein the power residue calculation is performed by setting a portion a of the public key of the issuer apparatus to a base and setting the x′

to an exponent,

wherein the B is calculated by using power residue with the a as a base and the x as an exponent,

wherein the G is an element of a group of which order is publicized, and

wherein the a is an element of a quadratic residue group with an RSA modulus.

4. The group signature scheme according to claim 3,

wherein the second step comprises:

a step of calculating a straight-line extractable validity proof text of the C and a proof text for proving that a discrete logarithm of the C with the a as a base is included in a predetermined interval; and

a step of transmitting the C, the straight-line extractable validity proof text, and the proof text for proving that the discrete logarithm is included in the predetermined interval to the issuer apparatus, and

wherein the third step comprises a step of generating a validity proof text of the (β

, B) and transmitting the validity proof text of the (β

, B) to the issuer apparatus.

5. The group signature scheme according to claim 4,

wherein the step of generating the straight-line extractable validity proof text comprises:

a step of reading a required data and selecting at random X_—

{01}, . . . , X_—

{0N};

a step of calculating X_—

{1j} for each j obtained by adding the x′

to the X_—

{0j}, selecting at random number r, calculating a hash value C_{ij} of a bit column including X_{ij} and r for each ij, and a hash value V of a bit column including the hash value C_{ij};

a step of calculating an inner product X of the V and a vector of X_—

{01}, . . . , X_—

{0N};

a step of generating c_—

1, . . . , c_N from hash values of a data including L obtained by raising the data a which is a portion of publicized information of an issuer to the power of X; and

a step of outputting a data including r, {C_{ij}}, L, and Ξ

as the straight-line extractable validity proof text, and

wherein the X_{c_jj} is ξ

_j, and the ξ

_—

1, . . . , ξ

_N is the Ξ

.

6. The group signature scheme according to claim 5, wherein the straight-line extractable validity proof text is generated.

7. A group signature scheme of an issuer apparatus for communicating with a user apparatus to generate a member secret key, a member public key, and a user-specified information, comprising:

a first step of reading a data including a public key and a secret key;

a second step of generating at random a number x″ and

transmitting the x″

to the user apparatus; and

a third step of calculating (b, e) by using a data received from the user apparatus or a portion β

thereof,

wherein the β

is an element of a quadratic residue group with an RSA modulus n,

wherein the β

is selected at random,

wherein the b is generated by raising the β

to the power 1/e as a modulus of the n.

8. The group signature scheme according to claim 7,

wherein the second step comprises:

receiving from the user apparatus a data C, a straight-line extractable validity proof text of the data C, and a proof text for proving that a discrete logarithm of the data C with a portion a of the public key of the issuer as a base is included in a predetermined interval; and

verifying a validity of the straight-line extractable validity proof text and a validity of the proof text for proving that the discrete logarithm is included in the interval, and

wherein the third step comprises;

receiving the data B and a validity proof text of the (β

, B); and

verifying a validity of the validity proof text of the (β

, B).

9. The group signature scheme according to claim 8,

the verifying of the validity of the straight-line extractable validity proof text comprises:

reading a required data including the straight-line extractable validity proof text;

generating K=(c_—

1, . . . , C_N) from a hash value of a data including {C_{ij}}, L, and r, wherein the read straight-line extractable validity proof text includes r, {C_{ij}}, L, and Ξ

, and a hash value of a data including the {C_{ij}} is set to V; and

accepting the validity proof text if C_{c_jj} for all j is a hash value of a data including ξ

_j, c_j, and r, and if a value obtained by raising a portion a of the public key of the issuer apparatus to the power of an inner product of V and Ξ

is equal to a value obtained by multiplying L with a value obtained by raising the data C to the power of an inner product of V and K.

10. The group signature scheme according to claim 8, where the verifying of the straight-line extractable validity proof text is performed.

11. A group signature scheme comprising:

a step of selecting a random number p and generating a Cipher where user-specified information B is encrypted by using a public key of an opener apparatus or a portion thereof and the p;

a step where an input means reads a data required for calculation;

a step where a commitment means selects at random u and e′ and

acquires a commitment χ

_b of a portion b of a public key of the user apparatus, a commitment χ

_e of a portion e of the public key of the user apparatus, a commitment χ

_u of u, a commitment (d_—

1, d_—

2) used for verifying a satisfaction of a verification equation associated with an RSA modulus, a commitment d_e of e′

, and a commitment ComCipher used for verifying that the Cipher is a valid cipher text;

a step where a challenge means acquires a challenge 1;

a step where a response means acquires a response x″

representing a knowledge of a secret key x of the user apparatus, a response e″

representing a knowledge of the e, a response u″

representing a knowledge of the u, a response u″

_e representing a knowledge of a product of the u and the e, and a response ρ

″

representing a a knowledge of the ρ

; and

a step where an output means outputs the responses.

12. The group signature scheme according to claim 11,

wherein the public key of the opener apparatus used for calculating the Cipher or a portion thereof include P, Q_—

1, and Q_—

2,

wherein the Cipher includes G′

, H′

_—

1, and H′

_—

2,

wherein the ComCipher includes the U calculated by performing a scalar product of the G and the ρ

′

, the V_—

1 obtained by adding the scalar product of the G and the x′

to a scalar product of the H_—

1 and the ρ

′

, and the V_—

2 obtained by adding the scalar product of the G and the x′

to a scalar product of the H_—

2 and the ρ

′

,

wherein, when the G′

, H′

_—

1, and H′

_—

2 are generated, the user apparatus selects at random a number ρ and

calculates G′

that is a scalar product of P and ρ

, H′

_—

1 that is a scalar product of Q_—

1 and ρ

, and H′

_—

2 that is a scalar product of Q_—

2 and ρ

,

wherein the commitment means selects at random numbers s, t, x′

, t′

, u′

_e, t′

_e, and ρ

′ and

calculates a commitment d_u of u′

,

wherein the χ

_b is calculated by multiplying a value obtained by raising a portion h of the public key of the issuer to the power of u with a portion b of a public key of a user,

wherein the χ

_e is calculated by subtracting e with a value obtained by raising 2 to the power of a value γ

determined based on a security parameter to calculate E, and by multiplying a value obtained by raising a portion g of the public key of the issuer to the power of the E with a value obtained by raising the h to the power of s,

wherein the χ

#u is calculated by multiplying a value obtained by raising the g to the power of u with a value obtained by raising the h to the power of the t,

wherein the d_—

1 is calculated by multiplying a value obtained by raising a portion a of the public key of the issuer to the power of −

x′

with a value obtained by raising the χ

_b to the power of e′ and

a value obtained by raising the h to the power of a number U,

wherein the U is calculating by inverting a sign of a value obtained by adding the u′

_e to a value obtained by multiplying a value obtained by raising 2 to the power of the γ

with the u′

,

wherein the d_—

2 is calculated by multiplying a value obtained by raising the χ

_u to the power of −

e′

with a value obtained by raising the g to the power of the u′

_e and a value obtained by raising the h to the power of the t′

_e,

wherein the d_e is calculated by multiplying a value obtained by raising the g to the power of the e′

with a value obtained by raising the h to the power of the s′

,

wherein the d_u is calculated by multiplying a value obtained by raising the g to the power of the u′

with a value obtained by raising the h to the power of the t′

.

13. The group signature scheme according to claim 12, comprising

a step of calculating a response s″

representing a knowledge of the s, a response t″

representing a knowledge of the t, and a response t″

_e representing a knowledge of a product of the t and the e,

wherein the x″

is a value obtained by adding the x′

to a product of the x and the 1,

wherein the e″

is a value obtained by adding the e′

to a product of the 1 and a value obtained by subtracting the e with a value obtained by raising 2 to the power of the λ

,

wherein the u″

is a value obtained by adding the u′

to a product of the u and the 1,

wherein the s″

is a value obtained by adding the s′

to a product of the s and the 1,

wherein the t″

is a value obtained by adding the t′

to a product of the t and the 1,

wherein the u″

_e is a value obtained by adding the u′

e to a product of the 1 and u and a value obtained by subtracting the e with a value obtained by raising 2 to the power of the λ

,

wherein the t″

_e is a value obtained by adding the t′

_e to a product of the t and 1 and a value obtained by subtracting the e with a value obtained by raising 2 to the power of the λ

,

wherein the ρ

″

is a value obtained by adding the ρ

′

to a product of the p and the 1,

wherein the χ

_b, the χ

_e, the χ

_u, the x″

, the e″

, the u″

, the s″

, the t″

, the u″

_e, the t″

_e, and the ρ

″

are output as a portion of a data.

14. The group signature scheme according to claim 13,

wherein the 1 is a hash value of a data including the (χ

_b, (χ

_e, χ

_u), d_—

1, d_—

2, (d_e, d_u), (U, V_—

1, V_—

2)).

15. The group signature scheme according to claim 14,

wherein the 1 is included in a portion of an output data.

16. The group signature scheme according to claim 14,

wherein the (χ

_b, (χ

_e, χ

_u), d_—

1, d_—

2, (d_e, d_u), (U, V_—

1, V_—

2)) is included in a portion of an output data.

17. A group signature scheme of a verifying apparatus having an input means for inputting a data, a verifying means for verifying the data, and an output means for outputting a verification result of the verifying means,

wherein the input means inputs publicized information and a data output by a user apparatus and a challenge 1,

wherein the data includes χ

_b, χ

_e, χ

_u, x″

, e″

, u″

, s″

, t″

, u″

_e, t″

_e, and ρ

″

,

wherein the output means outputs a data representing whether or not a signature text is a valid signature text of a message,

wherein the verifying means comprises a commitment calculating means, a validity verifying means, and a interval verifying means,

wherein the commitment calculating means calculates d_—

1̂

*, d_—

2̂

* d_ê

* d_û

*, Û

* V_—

1̂

*, and V_—

2̂

*,

wherein the d_—

1̂

* is a value obtained by multiplying a value obtained by raising a portion a_—

0 of a public key of an issuer apparatus to the power of a sign-inverted value of the 1 with a value obtained by raising a portion a of a public key of an issuer apparatus to the power of a sign-inverted value of the x″

, a value obtained by raising χ

_b to the power of a value obtained by adding e″

to a product of 1 and a value obtained by raising 2 to the power of a value γ

determined based on a security parameter, and a value obtained by adding u″

_e to a product of the u″ and

a value obtained by raising 2 to the power of the γ

,

wherein the d_—

2̂

* is obtained by multiplying a value obtained by raising the χ

_u to the power of −

e″

with a value obtained by raising a portion g of the public key of the issuer apparatus to the power of the u″

_e and a value obtained by raising a portion h of the public key of the issuer apparatus to the power of the t″

_e,

wherein the d_ê

* is obtained by multiplying a value obtained by raising the X_e to the power of a sign-inverted value of the 1 with a value obtained by raising the g to the power of the u″

_e and a value obtained by raising the h to the power of the s″

,

wherein the d_û

* is obtained by multiplying a value obtained by raising the χ

_u to the power of a sign-inverted value of the 1 with a value obtained by raising the g to the power of the u″ and

a value obtained by raising the h to the power of the t″

,

wherein the Û

* is a value obtained by adding a scalar product of a sign-inverted value of the 1 and P to a scalar product of the ρ

″ and

the G,

wherein the V_—

1̂

* is a value obtained by adding a scalar product of a sign-inverted value of the 1 and Q_—

1 to a scalar product of the x″ and

the G and a scalar product of the ρ

″ and

the H_—

1,

wherein the V_—

2̂

* is a value obtained by adding a scalar product of a sign-inverted value of the 1 and Q_—

2 to a scalar product of the x″ and

the G and a scalar product of the ρ

″ and

the H_—

2, and

wherein the interval verifying means verifies whether or not, the x″ and

the e″

are included in a predetermined interval.

18. The group signature scheme according to claim 17,

wherein the 1 is included in the data output by the user apparatus.

19. The group signature scheme according to claim 18,

wherein the 1 is a hash value of a data including the (χ

_i, (χ

_e, χ

_u), d_—

1*, d_—

2̂

*, (d_ê

* d_û

*), (Û

*, V_—

1̂

* V_—

2̂

*)).

20. The group signature scheme according to claim 17,

wherein the data output by the user apparatus includes seven types of data,

wherein the verifying means uses a hash value of a data including the seven types of data as the 1, and

wherein the verifying apparatus verifies whether or not the seven types of data are equal to the d_—

1̂

*, the d_—

2̂

*, the d_ê

*, the d_û

*, the Û

*, the V_—

1̂

* and the V_—

2̂

*.