Patent ID: 8074067

Claim:
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, said group signing device comprising: an encryption device for creating an encrypted text in which part of member evidence generated from said member secret key is encrypted by said tracking public key from: a) said group public key including a description for four groups: (1) group 1, group 2, group T, and group E, of a same order number, (2) a description of bilinear mapping from said group 1 and said group 2 to said group T, (3) respective generators of said group 1, said group 2, said group T, and said group E, and (4) a signature public key of a signature scheme utilizing said group 1, said group 2, and said group T; b) said tracking public key comprising an element of said group E; and c) said member secret key; and a knowledge-proof-statement generating device comprising a processor 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 said knowledge proof statement generated by said knowledge-proof-statement generating device, and wherein said group E is a group different from said group 1, said group 2, and said group T for solving a Diffie-Hellman discrimination problem.