Group Signature Scheme
First Claim
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}}.
1 Assignment
0 Petitions
Accused Products
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.
20 Citations
20 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}; anda 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; anda 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. - View Dependent Claims (4, 5, 6)
-
-
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; anda 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. - View Dependent Claims (8, 9, 10)
-
-
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 ρ
; anda step where an output means outputs the responses. - View Dependent Claims (12, 13, 14, 15, 16)
-
-
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, andwherein the interval verifying means verifies whether or not, the x″ and
the e″
are included in a predetermined interval. - View Dependent Claims (18, 19, 20)
- _b, χ
Specification