Abstract:
There is provided in accordance with the present invention a key issuing method for being performed by a user apparatus in a group signature system including the user apparatus and an issuer apparatus connected to the user apparatus through a network.

Description:
BACKGROUND OF THE INVENTION 
     1) Field of the Invention 
     The present invention relates to a group signature system and an information processing apparatus for permitting a signature to be made by a member belonging to a group and making it possible to confirm the signature, a key issuing method for issuing a key at the time a new member is added to the group signature system, and a program for enabling a computer to carry out the key issuing method. 
     2) Description of the Related Art 
     Group signature systems of the background art are disclosed in “Jan Camenisch. Jens Groth. Group Signatures: Better Efficiency and New Theoretical Aspects. SCN 2004, vol. 3352 of LNCS. pp. 120-133, 2004” (hereinafter referred to as Non-patent document 1), and “Furukawa, Imai. An Efficient Group Signature Scheme from Bilinear Maps. ACISP 2005, vol. 3574 of LNCS, pp. 455-467” (hereinafter referred to as Non-patent document 2). In the group signature systems of the background art, a join protocol for adding a group member has the following structural features: 
     According to the join protocol of the group signature systems of the background art, a user apparatus first calculates data using a secret key. Then, the user apparatus sends the data to an issuer apparatus (referred to as group manager in Non-patent document 1 and membership manager in Non-patent document 2). Thereafter, the user apparatus proves the legitimacy of the data to the issuer apparatus. The issuer apparatus then processes the data using a secret key of the issuer apparatus. 
     BRIEF SUMMARY OF THE INVENTION 
     In the group signature systems of the background art, as described above, the user apparatus first proves the legitimacy of the data and thereafter the issuer apparatus processes the data using the secret key of the issuer apparatus. Information has been exchanged on one-on-one level between the user apparatus and the issuer apparatus until the process of issuing a key to one member is finished. If the issuing apparatus operates concurrently on the join protocol with respect to a plurality of user apparatus, then safety such as information confidentiality cannot be guaranteed. 
     The present invention has been made in order to solve the problems of the background art. It is an object of the present invention to provide a key issuing method, a group signature system, an information processing apparatus for allowing a join protocol to be operated on concurrently for adding group members, and a program for enabling a computer to carry out the key issuing method. 
     To achieve the above object, there is provided in accordance with the present invention a key issuing method for being performed by a user apparatus in a group signature system including the user apparatus and an issuer apparatus connected to the user apparatus through a network, comprising reading an issuer public key from the issuer apparatus into a user storage through the network, receiving, from the issuer apparatus through the network, first confidential data including one or plural confidential texts which are produced by confidentializing the issuer public key using element data containing information of an element of a group in the issuer apparatus, performing a second confidential data generating process for generating second confidential data of a confidential text represented by the product of modulo-exponentiated element data corresponding to the confidential texts included in the first confidential data or a confidential text represented by the sum of the element data multiplied by a constant, using the issuer public key and the first confidential data, sending the second confidential data to the issuer apparatus through the network, receiving, from the issuer apparatus through the network, information generated in the issuer apparatus and based on the element data corresponding to the second confidential data, and generating a member public key which is a public key corresponding to the user apparatus and a member secret key which is a secret key corresponding to the user apparatus, using the information based on the element data corresponding to the second confidential data, and writing the member public key and the member secret key into the user storage. 
     According to the present invention, a key issuing method for issuing a key to an additional member from an issuer apparatus in a group signature system including a user apparatus and the issuer apparatus connected to the user apparatus through a network, comprises reading an issuer public key and an issuer secret key from an issuer storage, performing a confidential text generating process for generating one or plural confidential texts by confidentializing data calculated from a part of the issuer public key using element data including information of an element of a group, sending first confidential data including the one or plural confidential texts to the user apparatus through the network, receiving, from the user apparatus through the network, second confidential data of a confidential text represented by the product of modulo-exponentiated element data corresponding to the confidential texts included in the first confidential data or a confidential text represented by the sum of the element data multiplied by a constant in the user apparatus, performing a to-be-sent data generating process for calculating g″ representing data restored from the second confidential data and generating to-be-sent data from the g″, and sending the to-be-sent data to the user apparatus through the network. 
     To achieve the above object, a group signature system according to the present invention comprises an issuer apparatus including an issuer storage for storing an issuer public key and an issuer apparatus controller for sending the issuer public key through a network, generating one or plural confidential texts which are produced by confidentializing the issuer public key using element data containing information of an element of a group, sending out first confidential data including the one or plural confidential texts through the network, and when second confidential data generated by confidentializing the first confidential data are received, generating element data of the second confidential data, and sending out information based on the element data through the network, and a user apparatus including a user storage for storing the issuer public key through the network, and a user apparatus controller for storing the issuer public key received from the issuer apparatus into the user storage, and when the first confidential data are received, generating the second confidential data of a confidential text represented by the product of modulo-exponentiated element data corresponding to the confidential texts included in the first confidential data or a confidential text represented by the sum of the element data multiplied by a constant, using the issuer public key and the first confidential data, sending the second confidential data to the issuer apparatus through the network, and when information based on the element data is received, generating a member public key which is a public key corresponding to the user apparatus and a member secret key which is a secret key corresponding to the user apparatus, and writing the member public key and the member secret key into the user storage. 
     According to the present invention, the issuer apparatus first generates data using the secret key of the issuer apparatus, and then the user apparatus processes the data into other data and proves the legitimacy of the processed data to the issuer apparatus. Since the issuer apparatus processes the data using the secret key thereof before the user apparatus proves the legitimacy of the data, the issuer apparatus is able to process data received from other user apparatus before it finishes its process of issuing a key to a single member. 
     To achieve the above object, there is provided in accordance with the present invention an information processing apparatus connected to an issuer apparatus storing an issuer public key therein through a network, comprising a storage for storing the issuer public key, and a controller for storing the issuer public key received from the issuer apparatus into the storage, and when first confidential data including one or plural confidential texts which are produced by confidentializing the issuer public key using element data containing information of an element of a group in the issuer apparatus are received from the issuer apparatus, generating the second confidential data of a confidential text represented by the product of modulo-exponentiated element data corresponding to the confidential texts included in the first confidential data or a confidential text represented by the sum of the element data multiplied by a constant, using the issuer public key and the first confidential data, sending the second confidential data to the issuer apparatus through the network, and when information based on the element data is received from the issuer apparatus, generating a member public key which is a public key corresponding to the user apparatus and a member secret key which is a secret key corresponding to the user apparatus using information based on the element data of the second confidential data, and writing the member public key and the member secret key into the storage. 
     According to the present invention, an information processing apparatus connected to a user apparatus of an additional user newly added to a group through a network, comprises a storage storing an issuer public key, and a controller for generating one or plural confidential texts by confidentializing data calculated from a part of the issuer key using element data including information of an element of a group, sending first confidential data including the one or plural confidential texts to the user apparatus, receiving, from the user apparatus, second confidential data of a confidential text represented by the product of modulo-exponentiated element data corresponding to the confidential texts included in the first confidential data or a confidential text represented by the sum of the element data multiplied by a constant in the user apparatus, calculating g″ representing data restored from the second confidential data, generating to-be-sent data from the g″, and sending the to-be-sent data to the user apparatus. 
     To achieve the above object, a program according to the present invention for being executed by a computer connected to an issuer apparatus storing an issuer public key therein through a network, enables the computer to perform a process comprising reading the issuer public key from the issuer apparatus through the network into a storage of the computer, receiving, from the issuer apparatus through the network, first confidential data including one or plural confidential texts which are produced by confidentializing the issuer public key using element data containing information of an element of a group in the issuer apparatus, generating second confidential data of a confidential text represented by the product of modulo-exponentiated element data corresponding to the confidential texts included in the first confidential data or a confidential text represented by the sum of the element data multiplied by a constant, using the issuer public key and the first confidential data, sending the second confidential data to the issuer apparatus through the network, receiving, from the issuer apparatus through the network, information generated in the issuer apparatus and based on the element data corresponding to the second confidential data, and generating a member public key which is a public key corresponding to the computer and a member secret key which is a secret key corresponding to the computer, using the information based on the element data corresponding to the second confidential data, and writing the member public key and the member secret key into the storage of the computer. 
     According to the present invention, a program for being executed by a computer connected to a user apparatus of an additional user newly added to a group through a network, enables the computer to perform a process comprising reading an issuer public key and an issuer secret key from a storage of the computer, performing a confidential text generating process for generating one or plural confidential texts by confidentializing data calculated from a part of the issuer public key using element data including information of an element of a group, sending first confidential data including the one or plural confidential texts to the user apparatus through the network, receiving, from the user apparatus through the network, second confidential data of a confidential text represented by the product of modulo-exponentiated element data corresponding to the confidential texts included in the first confidential data or a confidential text represented by the sum of the element data multiplied by a constant in the user apparatus, performing a to-be-sent data generating process for calculating g″ representing data restored from the second confidential data and generating to-be-sent data from the g″, and sending the to-be-sent data to the user apparatus through the network. 
     According to the present invention, as described above, since the issuer apparatus processes data using the secret key thereof before the user apparatus proves the legitimacy of the data, the safety of information is enhanced even when data are sent and received concurrently between a plurality of user apparatus and the issuer apparatus according to the join protocol. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram showing a configuration of a group signature system; 
         FIG. 2  is a flowchart of an issuer key generating sequence according to Exemplary Embodiment 1; 
         FIG. 3  is a flowchart of an opener key generating sequence according to Exemplary Embodiment 1; 
         FIG. 4  is a flowchart of an issuing sequence 1 according to Exemplary Embodiment 1; 
         FIG. 5  is a flowchart of a joining sequence 1 according to Exemplary Embodiment 1; 
         FIG. 6  is a flowchart of an issuing sequence 2 according to Exemplary Embodiment 1; 
         FIG. 7  is a flowchart of a joining sequence 2 according to Exemplary Embodiment 1; 
         FIG. 8  is a flowchart of a pf_α generating sequence; 
         FIG. 9  is a flowchart of a pf_α verifying sequence; 
         FIG. 10  is a flowchart of an ElGamal encrypting sequence; 
         FIG. 11  is a flowchart of an ElGamal cryptotext linear product reencrypting sequence; 
         FIG. 12  is a flowchart of an ElGamal cryptotext decrypting sequence; 
         FIG. 13  is a flowchart of a (Y, C) legitimacy proving sequence; 
         FIG. 14  is a flowchart of a (Y, C) legitimacy proof verifying sequence; 
         FIG. 15  is a flowchart of an issuer key generating sequence according to Exemplary Embodiment 2; 
         FIG. 16  is a flowchart of an opener key generating sequence according to Exemplary Embodiment 2; 
         FIG. 17  is a flowchart of an issuing sequence 1 according to Exemplary Embodiment 2; 
         FIG. 18  is a flowchart of a joining sequence 1 according to Exemplary Embodiment 2; 
         FIG. 19  is a flowchart of an issuing sequence 2 according to Exemplary Embodiment 2; 
         FIG. 20  is a flowchart of a joining sequence 2 according to Exemplary Embodiment 2; 
         FIG. 21  is a flowchart of a Linear cryptosystem key generating sequence; 
         FIG. 22  is a flowchart of a Linear encrypting sequence; 
         FIG. 23  is a flowchart of a Linear cryptotext linear sum reencrypting sequence; 
         FIG. 24  is a flowchart of a Linear cryptotext decrypting sequence; 
         FIG. 25  is a flowchart of an (Ider_U, Cipher) legitimacy proving sequence; 
         FIG. 26  is a flowchart of an (Ider_U, Cipher) legitimacy proof verifying sequence; 
         FIG. 27  is a flowchart of an issuer key generating sequence according to Exemplary Embodiment 3; 
         FIG. 28  is a flowchart of an opener key generating sequence according to Exemplary Embodiment 3; 
         FIG. 29  is a flowchart of a joining sequence 1 according to Exemplary Embodiment 3; 
         FIG. 30  is a flowchart of an issuing sequence 1 according to Exemplary Embodiment 3; 
         FIG. 31  is a flowchart of a joining sequence 2 according to Exemplary Embodiment 3; 
         FIG. 32  is a flowchart of an issuing sequence 1 according to Exemplary Embodiment 4; 
         FIG. 33  is a flowchart of a joining sequence 1 according to Exemplary Embodiment 4; 
         FIG. 34  is a flowchart of an issuing sequence 2 according to Exemplary Embodiment 4; 
         FIG. 35  is a flowchart of a (Y, C) legitimacy proving sequence; 
         FIG. 36  is a flowchart of a (Y, C) legitimacy proof verifying sequence; 
         FIG. 37  is a flowchart of an issuer key generating sequence according to Exemplary Embodiment 5; 
         FIG. 38  is a flowchart of an issuing sequence 1 according to Exemplary Embodiment 5; 
         FIG. 39  is a flowchart of a joining sequence 1 according to Exemplary Embodiment 5; 
         FIG. 40  is a flowchart of a joining sequence 2 according to Exemplary Embodiment 5; 
         FIG. 41  is a flowchart of an (Ider_U, Cipher) legitimacy proving sequence; and 
         FIG. 42  is a flowchart of an (Ider_U, Cipher) legitimacy proof verifying sequence. 
     
    
    
     DESCRIPTION OF REFERENCE CHARACTERS 
     
         
         
           
               100  issuer apparatus 
               110  issuer apparatus controller 
               120  issuer storage 
               200  user apparatus 
               210  user apparatus controller 
               220  user storage 
           
         
       
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Exemplary Embodiment 1 
     Apparatus Configuration 
     A configuration of a group signature system according to the present exemplary embodiment will be described below.  FIG. 1  is a block diagram showing a configuration of the group signature system. As shown in  FIG. 1 , the group signature system includes issuer apparatus  100  for issuing a key to a member of a group and user apparatus  200  to be operated by a member. Verifier apparatus  300  and opener apparatus  400  are connected to the group signature system. Issuer apparatus  100 , user apparatus  200 , verifier apparatus  300 , and opener apparatus  400  are information processing apparatus having memories, controllers, etc. 
     Issuer apparatus  100  comprises issuer apparatus controller  110 , issuer storage  120 , and a communicator (not shown). Issuer apparatus controller  110  comprises issuer key generating means  112  and issuing means  114 . User apparatus  200  comprises user apparatus controller  210 , user storage  220 , and a communicator (not shown). User apparatus controller  210  comprises joining means  212  and signature generating means  214 . 
     Verifier apparatus  300  comprises verifier apparatus controller  310 , verifier storage  320 , and a communicator (not shown). Verifier apparatus controller  310  comprises verifying means  314 . Opener apparatus  400  comprises opener apparatus controller  410 , opener storage  420 , and a communicator (not shown). Opener apparatus controller  410  comprises opener key generating means  412  and disclosing means  414 . 
     The controller of each of the apparatus controls the communicator and the storage and performs data processing operation. The controller comprises a CPU (Central Processing Unit) for carrying predetermined processing sequences according to programs and a memory for storing the programs. 
     Issuer apparatus  100 , user apparatus  200 , verifier apparatus  300 , and opener apparatus  400  are interconnected for mutual communications by communication networks such as the Internet and a LAN (Local Area Network). The communication networks may be wired or wireless, or the combination of these. In  FIG. 1 , the communicators of the apparatus are omitted from illustration for an easier understanding of the flow of information between the apparatus. 
     Issuer storage  120 , user storage  220 , verifier storage  320 , and opener storage  420  may be hard disks, semiconductor memories, etc. 
     It is assumed that the storages of the apparatus have been supplied with security parameters I_n, I_E, I_Q, I_c, I_e, I_s in advance. The storages may be supplied with I_n, I_E, I_Q, I_c, I_e, I_s in any ways. It is assumed that ┌ represents a cyclic group of order Q and the number of bits of Q is I_Q bits. A multiplicative group of (Z/PZ), an elliptic curve group, or the like may be used as ┌. Here, ┌ as a multiplicative group of (Z/PZ) will be described below. It is also assumed that Z or (Z/QZ) is referred to as a cyclic group. 
     Furthermore, it is assumed that the storages of the apparatus have been supplied with a parameter descriptive of ┌, and Q in advance. The storages of the apparatus may be supplied with the parameter descriptive of ┌, and Q in any ways. 
     Issuer apparatus  100  is implemented by a general computer comprising an input device, an output device, a storage, and a controller. Issuer key generating means  112  and issuing means  114  are virtually constructed in the computer when the CPU executes programs. The same holds true for user apparatus  200 , verifier apparatus  300 , and opener apparatus  400 . 
     In issuer apparatus  100 , user apparatus  200 , and opener apparatus  400 , the CPU of each of the controllers thereof executes programs to randomly select elements of multiplicative group r, elements of cyclic group (Z/QZ), and elements of (Z/nZ) as information which should be confidential. n in (Z/nZ) will be described in next [Issuer key generating sequence ISS-GEN]. One process of randomly selecting an element from a plurality of elements may use random numbers, for example. 
     A key issuing method carried out by the group signature system according to the present exemplary embodiment will be described below. In the present exemplary embodiment, the issuer apparatus encrypts information to be confidentialized to provide confidentiality. Information which has been confidentialized by a confidentializing process such as encrypting will be referred to as confidential text. Data containing information of an element are referred to as element data. According to the encrypting process, data containing information of an element correspond to plaintext. 
     [Issuer Key Generating Sequence ISS-GEN]: 
     Issuer key generating sequence ISS-GEN performed by issuer key generating means  112  will be described below.  FIG. 2  is a flowchart of the issuer key generating sequence. As shown in  FIG. 2 , issuer apparatus  100  performs the following ISS-GEN1, . . . , ISS-GEN5 sequentially: 
     ISS-GEN1: Issuer key generating means  112  reads security parameter I_n from issuer storage  120  (step  1001 ). 
     ISS-GEN2: Issuer key generating means  112  selects prime numbers p, q whose product n=pq is of I_n bits (step  1002 ). 
     ISS-GEN3: Issuer key generating means  112  randomly selects elements a, g of QR(n) and nonnegative integer α equal to or smaller than n, and calculates h=g^α mod n (step  1003 ). 
     ISS-GEN4: Issuer key generating means  112  enters (α, g, h) and performs [pf_α generating sequence] to be described later to generate proof text pf_α of the knowledge a (step  1004 ). 
     ISS-GEN5: Issuer key generating means  112  sets issuer public key ipk to (n, a, g, h, pf_α) and issuer secret key isk to (p, q, α), writes ipk, isk into issuer storage  120  (step  1005 ), whereupon issuer key generating means  112  puts issuer key generating sequence ISS-GEN to an end. 
     Issuer public key ipk is disclosed to all the apparatus in some way. For example, one way to disclose ipk may be putting it on a public bulletin board on the Internet. Any methods may be used to disclose ipk. User apparatus controller  210  of user apparatus  200  stores disclosed issuer public key ipk in user storage  220 . 
     [Opener Key Generating Sequence OPN-GEN] 
     Opener key generating sequence OPN-GEN performed by opener key generating means  412  will be described below.  FIG. 3  is a flowchart of the opener key generating sequence. As shown in  FIG. 3 , opener apparatus  400  performs the following OPN-GEN1, OPN-GEN2, OPN-GEN3 sequentially: 
     OPN-GEN1: Opener key generating means  412  reads Q from opener storage  420  (step  1011 ). 
     OPN-GEN2: Opener key generating means  412  randomly selects elements X_G, X_H of (Z/QZ) and element F of ┌, and establishes G=F^{X_G}, H=F^{X_H} (step  1012 ). 
     OPN-GEN3: Opener key generating means  412  sets opener public key opk to (F, G, H) and sets opener secret key osk to (X_G, X_H), and writes opk, osk into opener storage  420  (step  1013 ), whereupon opener key generating means  412  puts opener key generating sequence OPN-GEN to an end. 
     Opener public key opk is disclosed to all the apparatus in some way. For example, one way to disclose opk may be putting it on a public bulletin board on the Internet. Any methods may be used to disclose opk. User apparatus controller  210  of user apparatus  200  stores disclosed opener public key opk in user storage  220 . Issuer apparatus controller  110  of issuer apparatus  100  stores disclosed opener public key opk in issuer storage  120 . 
     [Issuing Sequence ISS-ISSUE and Joining Sequence USR-JOIN] 
     Issuer apparatus  100  and user apparatus  200  perform issuing sequence ISS-ISSUE and joining sequence USR-JOIN, respectively, while communicating with each other. 
     First, issuer apparatus  100  performs [Issuing sequence 1 ISS-ISSUE-1] to be described later, and then user apparatus  200  performs [Joining sequence 1 USR-JOIN-1] to be described later. Issuer apparatus  100  performs [Issuing sequence 2 ISS-ISSUE-2] to be described later, and finally user apparatus  200  performs [Joining sequence 2 USR-JOIN-2] to be described later. 
     During the above sequences, member public key upk and member secret key usk are generated. 
     Member public key upk is disclosed to all the apparatus in some way. For example, one way to disclose upk may be putting it on a public bulletin, board on the Internet. Any methods may be used to disclose upk. 
     [Signature Sequence USR-SIGN] 
     When signature generating means  214  has received message m as an input, signature generating means  214  performs Sign(m, vk, sk) according to Non-patent document 1 as vk=ipk, sk=(vk, usk) to obtain signature text σ for m. 
     [Verifying Sequence VER-VERIFY] 
     When verifying means  314  has received message m and signature text a for m, verifying means  314  performs Verify(vk, m, σ) according to Non-patent document 1 as vk=ipk. 
     [Opening Sequence OPN-OPEN] 
     When opening means  414  has received message m and signature text σ for m, opening means  414  performs Open(gusk, m, σ) according to Non-patent document 1 as gusk=(ipk, opk). 
     [Issuing Sequence 1 ISS-ISSUE-1] 
     Issuing sequence 1 ISS-ISSUE-1 performed by issuing means  114  will be described below.  FIG. 4  is a flowchart of issuing sequence 1. As shown in  FIG. 4 , issuer apparatus  100  performs the following ISS-ISSUE-1-1, . . . , ISS-ISSUE-1-4 sequentially: 
     ISS-ISSUE-1-1: Issuing means  114  reads ipk=(n, a, g, h, pf_α), opk=(F, G, H), isk=(p, q, α) from issuer storage  120  (step  1021 ). 
     ISS-ISSUE-1-2: Issuing means  114  randomly selects nonnegative integer e of I_e bits where E=2^{I_E}+e is a prime number, and calculates g′=g^{1/E} mod n, h′=h^{1/E} mod n (step  1022 ). 
     ISS-ISSUE-1-3: Issuing means  114  enters ((n, g, h), g′) and performs [ElGamal encrypting sequence] to be described later to generate C_{g′}. Similarly, issuing means  114  enters ((n, g, h), h′) and performs [ElGamal encrypting sequence] to generate C_{h′} (step  1023 ). 
     ISS-ISSUE-1-4: Issuing means  114  sends (C_{g′}, C_{h′}) to user apparatus  200  (step  1024 ). 
     [Joining Sequence 1 USR-JOIN-1] 
     Joining sequence 1 USR-JOIN-1 performed by joining means  212  will be described below.  FIG. 5  is a flowchart of joining sequence 1. As shown in  FIG. 5 , user apparatus  200  performs the following USR-JOIN-1-1, . . . , USR-JOIN-1-7 sequentially: 
     USR-JOIN-1-1: Joining means  212  receives (C_{g′}, C_{h′}) (step  1031 ). 
     USR-JOIN-1-2: Joining means  212  reads ipk=(n, a, g, h, pf_α), opk=(F, G, H) from user storage  220  (step  1032 ). 
     USR-JOIN-1-3: Joining means  212  enters (ipk, pf_α) and performs is [pf_α verifying sequence] to be described later. If [pf_α verifying sequence] outputs reject, then joining means  212  finishes the joining sequence (step  1033 ). 
     USR-JOIN-1-4: Joining means  212  randomly selects element x of (Z/QZ) and element r′ of (Z/nZ) and calculates Y=G^{x} (step  1034 ). USR-JOIN-1-5: Joining means  212  enters (ipk, x, r′, C_{g′}, C_{h′}) and performs [ElGamal cryptotext linear product reencrypting sequence] to be described later to generate (C, (step  1035 ). 
     USR-JOIN-1-6: Joining means  212  enters (n, g, h, x, r′, C_{g′}, C_{h′}, Y, C) and performs [(Y, C) legitimacy proving sequence] to be described later to generate pf_{Y, C} (step  1036 ). 
     USR-JOIN-1-7: Joining means  212  sends (Y, C, pf_{Y, C}) to issuer apparatus  100  (step  1037 ). 
     [Issuing Sequence 2 ISS-ISSUE-2] 
     Issuing sequence 2 ISS-ISSUE-2 performed by issuing means  114  will be described below.  FIG. 6  is a flowchart of issuing sequence 2. As shown in  FIG. 6 , issuer apparatus  100  performs the following ISS-ISSUE-2-1, . . . , ISS-ISSUE-2-5 sequentially: 
     ISS-ISSUE-2-1: Issuing means  114  receives (Y, C, pf_{Y, C}) (step  1041 ). 
     ISS-ISSUE-2-2: Issuing means  114  enters (n, g, h, C_{g′}, C_{h′}, Y, C, pf_{Y, C}) and performs [(Y, C) legitimacy proof verifying sequence] to be described. If [(Y, C) legitimacy proof verifying sequence] outputs reject, then issuing means  114  finishes the joining sequence (step  1042 ). 
     ISS-ISSUE-2-3: Issuing means  114  enters (ipk, ask, C) and performs [ElGamal cryptotext decrypting sequence] to be described later to generate plaintext g″. Issuing means  114  randomly selects element r″ of (Z/EZ) and calculates y=a^{1/E}g″h^{r″} mod n (step  1043 ). 
     ISS-ISSUE-2-4: Issuing means  114  sends Y paired with ID of the user to opener apparatus  400  (step  1044 ). 
     ISS-ISSUE-2-5: Issuing means  114  sends (y, r″) to user apparatus  200  (step  1045 ), and then puts the issuing sequence to an end. 
     [Joining Sequence 2 USR-JOIN-2] 
     Joining sequence 2 USR-JOIN-2 performed by joining means  212  will be described below.  FIG. 7  is a flowchart of joining sequence 2. As shown in  FIG. 7 , user apparatus  200  performs the following USR-JOIN-2-1, . . . , USR-JOIN-2-4 sequentially: 
     USR-JOIN-2-1: Joining means  212  receives (y, r″) (step  1051 ). 
     USR-JOIN-2-2: Joining means  212  calculates r=r′+r″ (step  1052 ). 
     USR-JOIN-2-3: Joining means  212  confirms whether ag^{x}h^{r}=y^E is satisfied or not. If not, then joining means  212  finishes the joining sequence (step  1053 ). 
     USR-JOIN-2-4: If satisfied, then joining means  212  sets member public key upk to (Y, y, E) and sets member secret key usk to (x, r), and writes upk, usk into user storage  220  (step  1054 ). Then, joining means  212  puts the joining sequence to an end. 
     [pf_α Generating Sequence] 
     A pf_α generating sequence performed by issuer apparatus controller  110  will be described below.  FIG. 8  is a flowchart of the pf_α generating sequence. As shown in  FIG. 8 , issuer apparatus  100  performs the following pf_α-GEN-1, . . . , pf_α-GEN-5 sequentially: 
     pf_α-GEN-1: Issuer apparatus controller  110  receives input (α, g, h) (step  1061 ). 
     pf_α-GEN-2: Issuer apparatus controller  110  selects random number α — {0, 1} of I_n+I_s bits, and calculates h — {0, 1}=g^{α — {0, 1}} mod n (step  1062 ). 
     A hash function which outputs the rows of bits that are I_c bits, is described as H_{I_c}. 
     pf_α-GEN-3: Issuer apparatus controller  110  calculates c=H_{I_c}(g, h, h — {0, 1}) (step  1063 ). 
     pf_α-GEN-4: Issuer apparatus controller  110  establishes α — {0, 2}=cα+α — {0, 1} (step  1064 ). 
     pf_α-GEN-5: Issuer apparatus controller  110  establishes pf_α=(h — {0, 1}, α — {0, 2}) (step  1065 ). 
     [pf_α Verifying Sequence] 
     A pf_α verifying sequence performed by user apparatus controller  210  will be described below.  FIG. 9  is a flowchart of the pf_α verifying sequence. As shown in  FIG. 9 , user apparatus  200  performs the following pf_α-VER-1, . . . , pf_α-GEN-3 sequentially: 
     pf_α-VER-1: User apparatus controller  210  receives input (ipk, pf_α) and parses them into ipk=(n, a, g, h, pf_α), pf_α=(h — {0, 1}, α — {0, 2}) (step  1071 ). 
     pf_α-VER-2: User apparatus controller  210  calculates c=H_{I_c}(g, h, h — {0, 1}) (step  1072 ). 
     pf_α-GEN-3: If g^{α — {0, 2}}=h^ch — {0, 1} mod n is satisfied, then user apparatus controller  210  outputs accept, and if it is not satisfied, then user apparatus controller  210  outputs reject (step  1073 ). 
     [ElGamal Encrypting Sequence] 
     An ElGamal encrypting sequence performed by issuer apparatus controller  110  will be described below.  FIG. 10  is a flowchart of the ElGamal encrypting sequence. As shown in  FIG. 10 , issuer apparatus  100  performs the following ELGAMAL-ENC-1, . . . , ELGAMAL-ENC-3 sequentially: 
     ELGAMAL-ENC-1: Issuer apparatus controller  110  receives input ((n, g, h), g′) (step  1081 ). 
     ELGAMAL-ENC-2: Issuer apparatus controller  110  randomly selects element r — 1 of I_N bits, and establishes g — 1=g^{r — 1} mod n, h — 1=g′h^{r — 1} mod n (step  1082 ). 
     ELGAMAL-ENC-3: Issuer apparatus controller  110  establishes C_{g′}=(g — 1, h — 1) (step  1083 ). 
     [ElGamal Cryptotext Linear Product Reencrypting Sequence] 
     An ElGamal cryptotext linear product reencrypting sequence performed by issuer apparatus controller  110  will be described below.  FIG. 11  is a flowchart of the ElGamal cryptotext linear product reencrypting sequence. As shown in  FIG. 11 , issuer apparatus  100  performs the following ELGAMAL-MUL-1, . . . , 3 sequentially: 
     ELGAMAL-MUL-1: Issuer apparatus controller  110  receives input (ipk, x, r′, C_{g′}, C_{h′}) (step  1091 ). 
     ELGAMAL-MUL-2: Issuer apparatus controller  110  parses them into ipk=(n, a, g, h, pf_α), C_{g′}=(g — {1, g′}, h — {1, g′}), C_{h′}=(g — {1, h′}, h — {1, h′}) (step  1092 ). 
     ELGAMAL-MUL-3: Issuer apparatus controller  110  elects natural number r′″ of I_n bits, and calculates C=(g — {1, g′}^{x}h — {1, h′}^{e} g ^{r}, h — {1, g′}^{x}g — {1, h′}^{e}h^{r′″}) (step  1093 ). 
     [ElGamal Cryptotext Decrypting Sequence] 
     An ElGamal cryptotext decrypting sequence performed by issuer apparatus controller  110  will be described below.  FIG. 12  is a flowchart of the ElGamal cryptotext decrypting sequence. As shown in  FIG. 12 , issuer apparatus controller  110  performs the following ELGAMAL-DEC-1, . . . , ELGAMAL-DEC-3 sequentially: 
     ELGAMAL-DEC-1: Issuer apparatus controller  110  receives input (ipk, isk, C) (step  1101 ). 
     ELGAMAL-DEC-2: Issuer apparatus controller  110  parses them into ipk=(n, a, g, h, pf_α), isk=(p, q, α), C=(g_C, h_C) (step  1102 ). 
     ELGAMAL-DEC-3: Issuer apparatus controller  110  calculates g″=h_C/g_C^{α} mod n (step  1103 ). 
     [(Y, C) Legitimacy Proving Sequence] 
     A (Y, C) legitimacy proving sequence performed by user apparatus controller  210  will be described below.  FIG. 13  is a flowchart of the (Y, C) legitimacy proving sequence. As shown in  FIG. 13 , user apparatus  200  performs the following PF-YC-GEN-1, . . . , PF-YC-GEN-5 sequentially: 
     PF-YC-GEN-1: User apparatus controller  210  receives (n, g, h, x, r′, r′″, C_{g′}, C_{h′}, Y, C), and parses them into C_{g′}=(g — {1, g′}, h — {1, g′}), C_{h′}=(g — {1, h′}, h — {1, h′}) (step  1111 ). 
     PF-YC-GEN-2: User apparatus controller  210  randomly selects natural number x — {0, 1} of I_q+I_s bits and natural numbers r′ — {0, 1}, r′″ — {0, 1} of I_n+I_s bits, and establishes g — {1, g, 0, 1}=g — {1, g′}^{x — {0, 1}}g — {1, h′}^{r′ — {0, 1}}g^{r′″ — {0, 1}} mod n, h — {1, h, 0, 1}=h — {1, g′}^{x — {0, 1}}g — {1, h′}^{r′{0, 1}}h^{r′″ — {0, 1}} mod n, Y — {0, 1}=G^{x — {0, 1}} (step  1112 ). 
     PF-YC-GEN-3: User apparatus controller  210  calculates c=H — {1_c}(n, g, h, C_{g′}, C_{h′}, Y, C, C_{g, 0, 1}, C_{h, 0, 1}, Y — {0, 1}) (step  1113 ). 
     PF-YC-GEN-4: User apparatus controller  210  calculates x — {0, 2}=cx+x — {0, 1}, r′ — {0, 2}=cr′+r′ — {0, 1}, r′″ — {0, 2}=cr′″+r′″ — {0, 1} (step  1114 ). 
     PF-YC-GEN-5: User apparatus controller  210  establishes pf_{Y, C}=(g — {1, g, 0, 1}, h — {1, h, 0, 1}, Y — {0, 1}, x — {0, 2}, r′ — {0, 2}, r′″ — {0, 2}) (step  1115 ). 
     [(Y, C) Legitimacy Proof Verifying Sequence] 
     A (Y, C) legitimacy proof verifying sequence performed by issuer apparatus controller  110  will be described below.  FIG. 14  is a flowchart of the (Y, C) legitimacy proof verifying sequence. As shown in  FIG. 14 , issuer apparatus  100  performs the following PF-YC-VER-1, . . . , PF-YC-VER-3 sequentially: 
     PF-YC-VER-1: Issuer apparatus controller  110  receives (n, g, h, C_{g′}, C_{h′}, Y, C, pf_{Y, C}), and parses them into C_{g′}=(g — {1, g′}, h — {1, g′}), C_{h′}=(g — {1, h′}, h — {1, h′}), C=(g — {1, g}, C — {1, h}), pf_{Y, C}=(g — {1, g, 0, 1}, h — {1, h, 0, 1}, Y — {0, 1}, x — {0, 2}, r′ — {0, 2}, r′″ — {0, 2}) (step  1121 ). 
     PF-YC-VER-2: Issuer apparatus controller  110  calculates c=H_{I_c}(n, g, h, C_{y}, C_{h′}, Y, C, C_{g, 0, 1}, C_{h, 0, 1}, Y — {0, 1}) (step  1122 ). 
     PF-YC-VER-3: If g — {1, g}^cg — {1, g, 0, 1}=g — {1, g′}^{x — {0, 2}}g — {1, h′}^{r′ — {0, 2}}g^{r′″ — {0, 2}} mod n, h — {1, h}^ch — {1, h, 0, 1}=h — {1, g′}^{x — {0, 2}}g — {1, h′}^{r′{0, 2}}h^{r′″ — {0, 2}} mod n, Y^cY — {0, 1}=G^{x — {0, 2}}, −2^{I_Q+I_c+I_s}≦x — {0, 2}≦2^{I_Q+I_c+I_s} are satisfied, then issuer apparatus controller  110  accepts them, and if not satisfied, then issuer apparatus controller  110  rejects them (step  1123 ). 
     With the method of issuing a key to an additional member and the group signature system according to the present exemplary embodiment, the issuer apparatus first generates first confidential data using the secret key of the issuer apparatus, and then the user apparatus processes the first confidential data into second confidential data and proves the processed data to the issuer apparatus. Unlike the group signature apparatus of the background art, the issuer apparatus processes the data using the secret key of the issuer apparatus before the user apparatus proves the legitimacy of the data. Therefore, the safety of information is enhanced even when data are sent and received concurrently between a plurality of user apparatus and the issuer apparatus according to the join protocol. 
     Exemplary Embodiment 2 
     Apparatus Configuration 
     A group signature system according to the present exemplary embodiment will be described below. The configuration of the system will not be described in detail below as it is the same as the system described in Exemplary Embodiment 1. Processing details which are different from those of Exemplary Embodiment 1 will be described below. 
     It is assumed that the storages of the apparatus have been supplied with security parameter k in advance. The storages may be supplied with k in any ways. 
     It is assumed that ┌ — 1, ┌ — 2, ┌_T represent cyclic groups of order p, bilinear mapping e from ┌ — 1×┌ — 2 onto ┌_T is defined, and the number of bits of p is k. It is also assumed that r represents a cyclic group of order p. 
     Furthermore, it is assumed that the storages of the apparatus have been supplied with parameters descriptive of ┌ — 1, ┌ — 2, ┌_T, and p in advance. The storages of the apparatus may be supplied with the parameters descriptive of ┌ — 1, ┌ — 2, ┌_T, and p in any ways. 
     A key issuing method carried out by the group signature system according to the present exemplary embodiment will be described below. In the present exemplary embodiment, the issuer apparatus encrypts information to be confidentialized to provide confidentiality, as with Exemplary Embodiment 1. 
     [Issuer Key Generating Sequence ISS-GEN]: 
     Issuer key generating sequence ISS-GEN performed by issuer key generating means  112  will be described below.  FIG. 15  is a flowchart of the issuer key generating sequence. As shown in  FIG. 15 , issuer apparatus  100  performs the following ISS-GEN-1, . . . , ISS-GEN-3 sequentially: 
     ISS-GEN-1: Issuer key generating means  112  randomly selects elements G — 1, H, K of ┌ — 1, element G — 2 of ┌ — 2, and element w of (Z/pZ), and establishes Y=wG — 2 (step  1201 ). 
     ISS-GEN-2: Issuer key generating means  112  enters G — 1 and performs [Linear cryptosystem key generating sequence] to be described below to generate Linear cryptosystem public key Ipk and Linear cryptosystem secret key Isk (step  1202 ). 
     ISS-GEN-3: Issuer key generating means  112  sets issuer public key ipk to (G — 1, G — 2, H, K, Y, Ipk), sets issuer secret key isk to (w, Isk), and stores ipk, isk in issuer storage  120  (step  1203 ). 
     Issuer public key ipk is disclosed to all the apparatus in some way. For example, one way to disclose ipk may be putting it on a public bulletin board on the Internet. Any methods may be used to disclose ipk. User apparatus controller  210  of user apparatus  200  stores disclosed issuer public key ipk in user storage  220 . 
     [Opener Key Generating Sequence OPN-GEN] 
     Opener key generating sequence OPN-GEN performed by opener key generating means  412  will be described below.  FIG. 16  is a flowchart of the opener key generating sequence. As shown in  FIG. 16 , opener apparatus  400  performs the following OPN-GEN-1, OPN-GEN-2 sequentially: 
     OPN-GEN-1: Opener key generating means  412  randomly selects element G of ┌, elements s, t of (Z/pZ), and establishes S=sG, T=tG (step  1211 ). 
     OPN-GEN-2: Opener key generating means  412  sets opener public key opk to (G, element G of ┌, S, T), sets opener secret key osk to (s, t), and writes opk, osk into opener storage  420  (step  1212 ). 
     Opener public key opk is disclosed to all the apparatus in some way. For example, one way to disclose opk may be putting it on a public bulletin board on the Internet. Any methods may be used to disclose opk. User apparatus controller  210  of user apparatus  200  stores disclosed opener public key opk in user storage  220 . Issuer apparatus controller  110  of issuer apparatus  100  stores disclosed opener public key opk in issuer storage  120 . 
     [Issuing Sequence ISS-ISSUE and Joining Sequence USR-JOIN] 
     Issuer apparatus  100  and user apparatus  200  perform issuing sequence ISS-ISSUE and joining sequence USR-JOIN, respectively, while communicating with each other. 
     First, issuer apparatus  100  performs [Issuing sequence 1 ISS-ISSUE-1] to be described later, and then user apparatus  200  performs [Joining sequence 1 USR-JOIN-1] to be described later. Issuer apparatus  100  performs [Issuing sequence 2 ISS-ISSUE-2] to be described later, and finally user apparatus  200  performs [Joining sequence 2 USR-JOIN-2] to be described later. 
     During the above sequences, member public key upk and member secret key usk are generated. 
     Member public key upk is disclosed to all the apparatus in some way. For example, one way to disclose upk may be putting it on a public bulletin board on the Internet. Any methods may be used to disclose upk. 
     [Signature Sequence USR-SIGN] 
     When signature generating means  214  has received message m as an input, signature generating means  214  performs Sign(m, upk, tpk, cert_U, sk_U) according to Non-patent document 2 as mpk=ipk, tpk=opk, cert_U=upk, sk_U=usk to obtain signature text gs for m. 
     [Verifying Sequence VER-VERIFY] 
     When verifying means  314  has received message m and signature text gs for m, verifying means  314  performs Verify(m, gs, mpk, tpk) according to Non-patent document 2 as mpk=ipk, tpk=opk. 
     [Opening Sequence OPN-OPEN] 
     When opening means  414  has received message m and signature text gs for m, opening means  414  performs Open(m, σ, mpk, tpk, tsk) according to Non-patent document 2 as mpk=ipk, tpk=opk, tsk=osk. 
     [Issuing Sequence 1 ISS-ISSUE-1] 
     Issuing sequence 1 ISS-ISSUE-1 performed by issuing means  114  will be described below.  FIG. 17  is a flowchart of issuing sequence 1. As shown in  FIG. 17 , issuer apparatus  100  performs the following ISS-ISSUE-1-1, ISS-ISSUE-1-4 sequentially: 
     ISS-ISSUE-1-1: Issuing means  114  reads ipk=(G — 1, G — 2, H, K, Y, Ipk), opk=(G, S, T), isk=(w, Isk) from issuer storage  120  (step  1221 ). 
     ISS-ISSUE-1-2: Issuing means  114  randomly selects element y_U of (Z/pZ), and calculates H′=(1/(w+y_U)) H, K′=(1/(w+y_U)) K (step  1222 ). 
     ISS-ISSUE-1-3: Issuing means  114  enters (G — 1, Ipk, H′) and performs [Linear encrypting sequence] to be described later to generate Cipher_{H}. Similarly, issuing means  114  enters (G — 1, Ipk, K′) and performs [Linear encrypting sequence] to generate Cipher {K′} (step  1223 ). 
     ISS-ISSUE-1-4: Issuing means  114  sends (Cipher_{H′}, Cipher_{K′}) to user apparatus  200  (step  1224 ). 
     [Joining Sequence 1 USR-JOIN-1] 
     Joining sequence 1 USR-JOIN-1 performed by joining means  212  will be described below.  FIG. 18  is a flowchart of joining sequence 1. As shown in  FIG. 18 , user apparatus  200  performs the following USR-JOIN-1-1, . . . , USR-JOIN-1-6 sequentially: 
     USR-JOIN-1-1: Joining means  212  receives (Cipher_{H′}, Cipher_{K′}) (step  1231 ). 
     USR-JOIN-1-2: Joining means  212  reads ipk=(G — 1, G — 2, H, K, Y, Ipk), opk=(G, S, T) from user storage  220  (step  1232 ). 
     USR-JOIN-1-3: Joining means  212  randomly selects elements x_U, z′_U of (Z/pZ) and calculates Ider_U=x_U G (step  1233 ). 
     USR-JOIN-1-4: Joining means  212  enters (G — 1, x_U, z′_U, Cipher_{H′}, Cipher {K′}) and performs [Linear cryptotext linear product reencrypting sequence] to be described later to generate (Cipher, β, β′) (step  1234 ). 
     USR-JOIN-1-5: Joining means  212  enters (G, Ipk, x_U, β, β′, Cipher_{H′}, Cipher_{K′}, Ider_U, Cipher) and performs [(Ider_U, Cipher) legitimacy proving sequence] to be described later to generate pf_{Ider_U, Cipher} (step  1235 ). 
     USR-JOIN-1-6: Joining means  212  sends (Ider_U, Cipher, pf_{Ider_U, Cipher}) to issuer apparatus  100  (step  1236 ). 
     [Issuing Sequence 2 ISS-ISSUE-2] 
     Issuing sequence 2 ISS-ISSUE-2 performed by issuing means  114  will be described below.  FIG. 19  is a flowchart of issuing sequence 2. As shown in  FIG. 19 , issuer apparatus  100  performs the following ISS-ISSUE-2-1, . . . , ISS-ISSUE-2-5 sequentially: 
     ISS-ISSUE-2-1: Issuing means  114  receives (Ider_U, Cipher, pf_{Ider_U, Cipher}) (step  1241 ). 
     ISS-ISSUE-2-2: Issuing means  114  enters (G, Ipk, Cipher_{H′}, Cipher_{K′}, Ider_U, Cipher, pf_{Ider_U, Cipher}) and performs [(Ider_U, Cipher) legitimacy proof verifying sequence] to be described. If [(Ider_U, Cipher) legitimacy proof verifying sequence] outputs reject, then issuing means  114  finishes the joining sequence (step  1242 ). 
     ISS-ISSUE-2-3: Issuing means  114  enters (G — 1, Ipk, Isk, Cipher) and performs [Linear cryptotext decrypting sequence] to be described later to generate plaintext G — 1″. Issuing means  114  randomly selects element z″_U of (Z/eZ) and calculates A_U=(1/(w+y_U)) G — 1−G — 1″−z″_UK (step  1243 ). Plaintext G — 1″ corresponds to plaintext g″ according to Exemplary Embodiment 1. 
     ISS-ISSUE-2-4: Issuing means  114  sends Ider_U paired with ID of the user to opener apparatus  400  (step  1244 ). 
     ISS-ISSUE-2-5: Issuing means  114  sends (A_U, z″_U) to user apparatus  200  (step  1245 ), and then puts the issuing sequence to an end. 
     [Joining Sequence 2 USR-JOIN-2] 
     Joining sequence 2 USR-JOIN-2 performed by joining means  212  will be described below.  FIG. 20  is a flowchart of joining sequence 2. As shown in  FIG. 20 , user apparatus  200  performs the following USR-JOIN-2-1, . . . , USR-JOIN-2-4 sequentially: 
     USR-JOIN-2-1: Joining means  212  receives (A_U, z″_U) (step  1251 ). 
     USR-JOIN-2-2: Joining means  212  calculates z_U=+z″_U mod p (step  1252 ). 
     USR-JOIN-2-3: Joining means  212  confirms whether e(A_U, Y+y_UG — 1)e(x_UH, G — 2)e(z_UK, G — 2)=e(G — 1, G — 2) is satisfied or not. If not, then joining means  212  finishes the joining sequence (step  1253 ). 
     USR-JOIN-2-4: If satisfied, then joining means  212  sets member public key upk to (A_U, y_U, z_U) and sets member secret key usk to (x_U, z_U), and writes upk, usk into user storage  220  (step  1254 ). Then, joining means  212  puts the joining sequence to an end. 
     [Linear Cryptosystem Key Generating Sequence] 
     A Linear cryptosystem key generating sequence performed by issuer apparatus controller  110  will be described below.  FIG. 21  is a flowchart of the Linear cryptosystem key generating sequence. As shown in  FIG. 21 , issuer apparatus  100  performs the following LIN-GEN-1, . . . , LIN-GEN-3 sequentially: 
     LIN-GEN-1: Issuer apparatus controller  110  reads input G — 1 (step  1261 ). 
     LIN-GEN-2: Issuer apparatus controller  110  randomly selects α, α′ of (Z/pZ) and establishes L=(1/α)G — 1, L′=(1/α′)G — 1 (step  1262 ). 
     LIN-GEN-3: Issuer apparatus controller  110  sets Linear cryptosystem public key Ipk to (L, L′) and sets Linear cryptosystem secret key Isk to (α, α′) (step  1263 ). 
     [Linear Encrypting Sequence] 
     An Linear encrypting sequence performed by issuer apparatus controller  110  will be described below.  FIG. 22  is a flowchart of the Linear encrypting sequence. As shown in  FIG. 22 , issuer apparatus  100  performs the following LIN-ENC-1, LIN-ENC-2 sequentially: 
     LIN-ENC-1: Issuer apparatus controller  110  receives input (G — 1, Ipk, H′) and parses them into Ipk=(L, L′) (step  1271 ). 
     LIN-ENC-2: Issuer apparatus controller  110  randomly selects elements r, r′ of (Z/pZ) and establishes (G_{Cipher, H′}, L_{Cipher, H′}, L′_{Cipher, H′})=(H′+(r+r′)G, rL, r′L′) and Cipher_{H′}=(G_Cipher_{H′}, L_{Cipher, H′}, L′_{Cipher, H′}) (step  1272 ). 
     [Linear Cryptotext Linear Sum Reencrypting Sequence] 
     A Linear cryptotext linear sum reencrypting sequence performed by user apparatus controller  210  will be described below.  FIG. 23  is a flowchart of the Linear cryptotext linear sum reencrypting sequence. As shown in  FIG. 23 , user apparatus  200  performs the following LIN-SUM-1, LIN-SUM-2 sequentially: 
     LIN-SUM-1: User apparatus controller  210  receives (G — 1, x_U, z′_U, Cipher_{H′}, Cipher_{K′}) and parses them into Ipk=(L, L′), Cipher_{H′} (G_{Cipher, H′}, L_{Cipher, H′}, L′_{Cipher, H′}), and Cipher {K′}=(G_{Cipher, K′}, L_{Cipher, K′}, L′_{Cipher, K′}) (step  1281 ). 
     LIN-SUM-2: User apparatus controller  210  randomly selects elements β, β′ of (Z/pZ) and establishes (G_{Cipher}, L_{Cipher}, L′_{Cipher})=(x_UG_{Cipher, H′}+z′_UG_{Cipher, K′}+(β+β′)G — 1, x_UL_{Cipher, H′}+z′_UL_{Cipher, K′}+βL, x_UL′_{Cipher, H′}+z′_UL′_{Cipher, K′}+β′L′), and Cipher=(G_{Cipher}, L_{Cipher}, L′_{Cipher}) (step  1282 ). 
     In this manner, user apparatus controller  210  generates a cryptotext from the sum of plaintexts multiplied by a constant. According to Exemplary Embodiment 1, a cryptotext is generated from the product of modulo-exponentiated plaintexts. The reencrypting sequence according to Exemplary Embodiment 1 may be applied to the present exemplary embodiment, and the reencrypting sequence according to the present exemplary embodiment may be applied to Exemplary Embodiment 1. 
     [Linear Cryptotext Decrypting Sequence] 
     A Linear cryptotext decrypting sequence performed by issuer apparatus controller  110  will be described below.  FIG. 24  is a flowchart of the Linear cryptotext decrypting sequence. As shown in  FIG. 24 , issuer apparatus  100  performs the following LIN-DEC-1, LIN-DEC-2 sequentially: 
     LIN-DEC-1: Issuer apparatus controller  110  receives input (G — 1, Ipk, Isk, Cipher) and parses them into Ipk=(L, L′), Isk=(α, α′), and Cipher=(G_{Cipher}, L_{Cipher}, L′_{Cipher}) (step  1291 ). 
     LIN-DEC-2: Issuer apparatus controller  110  establishes G — 1″=G_{Cipher}−αL_{Cipher}−α′L′_{Cipher} (step  1292 ). 
     [(Ider_U, Cipher) Legitimacy Proving Sequence ID-CI-PF-GEN] 
     An (Ider_U, Cipher) legitimacy proving sequence performed by user apparatus controller  210  will be described below.  FIG. 25  is a flowchart of the (Ider_U, Cipher) legitimacy proving sequence. As shown in  FIG. 25 , user apparatus  200  performs the following ID-CI-PF-GEN-1, . . . , ID-CI-PF-GEN-5 sequentially: 
     ID-CI-PF-GEN-1: User apparatus controller  210  receives input (G, Ipk, x_U, β, β′, Cipher_{H′}, Cipher_{K′}, Ider_U, Cipher), parses Ipk into (L, L′), parses Cipher_{H′} into (G_{Cipher, H′}, L_{Cipher, H′}, L′_{Cipher, H′}), and parses Cipher_{K′} into (G_{Cipher, K′}, L_{Cipher, K′}, L′_{Cipher, K′}) (step  1301 ). 
     ID-CI-PF-GEN-2: User apparatus controller  210  randomly selects elements x_{U, 0, 1}, z′_{U, 0, 1}, β_{U, 0, 1}, β′_{U, 0, 1} of (Z/pZ) and establishes (G_{Cipher, 0, 1}, L_{Cipher, 0, 1}, L′_{Cipher, 0, 1})=(x_{U, 0, 1}G_{Cipher, H′}+z′_{U, 0, 1}G_{Cipher, K′}+(α — {0, 1}+β′ — {0, 1})G — 1, x_{U, 0, 1}L_{Cipher, H′}+z′_{U, 0, 1}L_{Cipher, K′}+β — {0, 1}L, x_{U, 0, 1}L′_{Cipher, H′}+z′_{U, 0, 1}L′_{Cipher, K}+β′ — {0, 1}L′), and Ider_{U, 0, 1}=x_{U, 0, 1}G (step  1302 ). 
     User apparatus controller  210  sets H_{Z/pZ} as a hash function that takes it value at (Z/pZ). 
     ID-CI-PF-GEN-3: User apparatus controller  210  establishes c=H_{Z/pZ}(G, Ipk, Cipher_{H′}, Cipher_{K}, Ider_U, Cipher G_{Cipher, 0, 1}, L_{Cipher, 0, 1}, L′_{Cipher, 0, 1}, Ider_{U, 0, 1}) (step  1303 ). 
     ID-CI-PF-GEN-4: User apparatus controller  210  establishes x_{U, 0, 2}=cx_U+x_{U, 0, 1} mod p, z′_{U, 0, 2}=cz′_U+z′_{U, 0, 2} mod p, β — {0, 2}=cβ+β — {0, 1} mod p, β′ — {0, 2}=cβ′+β′ — {0, 1} mod p (step  1304 ). 
     ID-CI-PF-GEN-5: User apparatus controller  210  establishes pf_{Ider_U, Cipher}=(G_{Cipher, 0, 1}, L_{Cipher, 0, 1}, L′_{Cipher, 0, 1}, Ider_{U, 0, 1}, x_{U, 0, 2}, z′_{U, 0, 2}, β — {0, 2}, β′ — {0, 2}) (step  1305 ). 
     [(Ider_U, Cipher) Legitimacy Proof Verifying Sequence ID-CI-PF-VER] 
     An (Ider_U, Cipher) legitimacy proof verifying sequence performed by issuer apparatus controller  110  will be described below.  FIG. 26  is a flowchart of the (Ider_U, Cipher) legitimacy proof verifying sequence. As shown in  FIG. 26 , user apparatus  100  performs the following ID-CI-PF-VER-1, . . . , ID-CI-PF-VER-3 sequentially: 
     ID-CI-PF-VER-1: Issuer apparatus controller  110  receives input (G, Ipk, Cipher_{H′}, Cipher_{K}, Ider_U, Cipher, pf_{Ider_U, Cipher}), parses them into Ipk=(L, L′), Cipher=(G_{Cipher}, L_{Cipher}, L′{Cipher}), Cipher_{H′}=(G_{Cipher, H′}, L_{Cipher, H′}, L′_{Cipher, H′}), Cipher_{K}=(G_{Cipher, K′}, L_{Cipher, K′}, L′_{Cipher, K′}), pf_{Ider_U, Cipher}=(G_{Cipher, 0, 1}, L_{Cipher, 0, 1}, L′_{Cipher, 0, 1}, Ider_{U, 0, 1}, x_{U, 0, 2}, z′_{U, 0, 2}, β — {0, 2}, β′ — {0, 2}) (step  1311 ). 
     ID-CI-PF-VER-2: Issuer apparatus controller  110  establishes c=H_{Z/pZ}(G, Ipk, Cipher_{H′}, Cipher_{K′}, Ider_U, Cipher G_{Cipher, 0, 1}, L_{Cipher, 0, 1}, L′_{Cipher, 0, 1}, Ider_{U, 0, 1}) (step  1312 ). 
     ID-CI-PF-VER-3: If (cG_{Cipher}+G_{Cipher, 0, 1}, cL_{Cipher}+L_{Cipher, 0, 1}, cL′_{Cipher}+L′_{Cipher, 0, 1})=(x_{U, 0, 2}G_{Cipher, H′}+z′_{U, 0, 2}G_{Cipher, K′}+(β — {0, 2}+β′ — {0, 2})G — 1, x_{U, 0, 2}L_{Cipher, H′}+z′_{U, 0, 2}L_{Cipher, K′}+β — {0, 2}L, x_{U, 0, 2}L′_{Cipher, H′}+z′_{U, 0, 2}L′_{Cipher, K′}+β′ — {0, 2}L′), and c.Ider_{U, 0, 1}+Ider_{U, 0, 2}=x_{U, 0, 2}G, then issuer apparatus controller  110  outputs accept, and if not, then issuer apparatus controller  110  outputs reject (step  1313 ). 
     The key issuing method and the group signature system according to the present exemplary embodiment offer the same advantages as Exemplary Embodiment 1. 
     Exemplary Embodiment 3 
     Apparatus Configuration 
     A group signature system according to the present exemplary embodiment will be described below. The configuration of the system will not be described in detail below as it is the same as the system described in Exemplary Embodiment 1. Processing details which are different from those of Exemplary Embodiment 1 will be described below. 
     It is assumed that the storages of the apparatus have been supplied with security parameters I_n, I_E, I_Q, I_c, I_e, I_s in advance. The storages may be supplied with I_n, I_E, I_Q, I_c, I_s in any ways. It is assumed that r represents a cyclic group of order Q and the number of bits of Q is I_Q bits. A multiplicative group of (Z/PZ) or an elliptic curve group, for example, may be used as ┌. Here, ┌ as a multiplicative group of (Z/PZ) will be described below. 
     Furthermore, it is assumed that the storages of the apparatus have been supplied with a parameter descriptive of r, and Q in advance. The storages of the apparatus may be supplied with the parameter descriptive of ┌, and Q in any ways. 
     A key issuing method carried out by the group signature system according to the present exemplary embodiment will be described below. 
     [Issuer Key Generating Sequence ISS-GEN]: 
     Issuer key generating sequence ISS-GEN performed by issuer key generating means  112  will be described below.  FIG. 27  is a flowchart of the issuer key generating sequence. As shown in  FIG. 27 , issuer apparatus  100  performs the following ISS-GEN1, . . . , ISS-GEN5 sequentially: 
     ISS-GEN1: Issuer key generating means  112  reads security parameter I_n from issuer storage  120  (step  1401 ). 
     ISS-GEN2: Issuer key generating means  112  selects prime numbers p, q whose product n=pq is of I_n bits (step  1402 ). 
     ISS-GEN3: Issuer key generating means  112  randomly selects elements a, g of QR(n) and nonnegative integer a equal to or smaller than n, and calculates h=g^α mod n (step  1403 ). 
     ISS-GEN4: Issuer key generating means  112  enters (α, g, h) and performs [pf_α generating sequence] described in Exemplary Embodiment 1 to generate proof text pf_α of the knowledge a (step  1404 ). 
     ISS-GEN5: Issuer key generating means  112  sets issuer public key ipk to (n, a, g, h, pf_α) and issuer secret key isk to (p, q, a), writes ipk, isk into issuer storage  120 , whereupon issuer key generating means  112  puts issuer key generating sequence ISS-GEN to an end (step  1405 ). 
     Issuer public key ipk is disclosed to all the apparatus in some way. For example, one way to disclose ipk may be putting it on a public bulletin board on the Internet. Any methods may be used to disclose ipk. User apparatus controller  210  of user apparatus  200  stores disclosed issuer public key ipk in user storage  220 . 
     [Opener Key Generating Sequence OPN-GEN] 
     Opener key generating sequence OPN-GEN performed by opener key generating means  412  will be described below.  FIG. 28  is a flowchart of the opener key generating sequence. As shown in  FIG. 28 , opener apparatus  400  performs the following OPN-GEN1, OPN-GEN2, OPN-GEN3 sequentially: 
     OPN-GEN1: Opener key generating means  412  reads Q from opener storage  420  (step  1411 ). 
     OPN-GEN2: Opener key generating means  412  randomly selects elements X_G, X_H of (Z/QZ) and element F of r, and establishes G=F^{X_G}, H=F^{X_H} (step  1412 ). 
     OPN-GEN3: Opener key generating means  412  sets opener public key opk to (F, G, H) and opener secret key osk to (X_G, X_H), writes opk, osk into opener storage  420  (step  1413 ), whereupon opener key generating means  412  puts opener key generating sequence OPN-GEN to an end. 
     Opener public key opk is disclosed to all the apparatus in some way. For example, one way to disclose opk may be putting it on a public bulletin board on the Internet. Any methods may be used to disclose opk. User apparatus controller  210  of user apparatus  200  stores disclosed opener public key opk in user storage  220 . Issuer apparatus controller  110  of issuer apparatus  100  stores disclosed opener public key opk in issuer storage  120 . 
     [Issuing Sequence ISS-ISSUE and Joining Sequence USR-JOIN] 
     Issuer apparatus  100  and user apparatus  200  perform issuing sequence ISS-ISSUE and joining sequence USR-JOIN, respectively, while communicating with each other. 
     First, user apparatus  200  performs [Joining sequence 1 USR-JOIN-1] to be described later, and then issuer apparatus  100  performs [Issuing sequence 1 ISS-ISSUE-1] to be described later. Furthermore, user apparatus  200  performs [Joining sequence 2 USR-JOIN-2] to be described later. 
     During the above sequences, member public key upk and member secret key usk are generated. 
     Member public key upk is disclosed to all the apparatus in some way. For example, one way to disclose upk may be putting it on a public bulletin board on the Internet. Any methods may be used to disclose upk. 
     [Signature Sequence USR-SIGN] 
     When signature generating means  214  has received message m as an input, signature generating means  214  parses it into upk=(x, e, y), randomly selects element β of (Z/NZ), calculates (F′, G′, H′)=(F^β, F^β, F^xG^β, F^xH^β), and calculates legitimacy proof text pf_{(G′, H′)} of (G′, H′). 
     [Verifying Sequence VER-VERIFY] 
     Verifying means  314  verifies the legitimacy of pf_{(G′, H′)}. 
     [Opening Sequence OPN-OPEN] 
     Opening means  414  calculates G′/F′^{X_G} and outputs ID of the user where member public key upk=(x, e, y) satisfies G′/F′^{X_G}=G^x. 
     [Joining Sequence 1 USR-JOIN-1] 
     Joining sequence 1 USR-JOIN-1 performed by joining means  212  will be described below.  FIG. 29  is a flowchart of joining sequence 1. As shown in  FIG. 29 , user apparatus  200  performs the following USR-JOIN-1-1, . . . , USR-JOIN-1-3 sequentially: 
     USR-JOIN-1-1: Joining means  212  reads ipk=(n, a, g, pf_α), opk=(F, G, H) from user storage  220  (step  1421 ). 
     USR-JOIN-1-2: Joining means  212  selects prime numbers X — 1, X — 2 whose product x=X — 1X — 2 is of I_n bits (step  1422 ). 
     USR-JOIN-1-3: Joining means  212  sends x to issuer apparatus  100  (step  1423 ). 
     [Issuing Sequence 1 ISS-ISSUE-1] 
     Issuing sequence 1 ISS-ISSUE-1 performed by issuing means  212  will be described below.  FIG. 30  is a flowchart of issuing sequence 1. As shown in  FIG. 30 , issuer apparatus  100  performs the following ISS-ISSUE-1-1, . . . , ISS-ISSUE-1-5 sequentially: 
     ISS-ISSUE-1-1: Issuing means  114  reads ipk=(n, a, g, h, pf_α), opk=(F, G, H), isk=(p, q, α) from issuer storage  120  (step  1431 ). 
     ISS-ISSUE-1-2: Issuing means  114  checks if x is less than I_n bits or not. If not, issuing means  114  finishes issuing sequence ISS-ISSUE (step  1432 ). 
     ISS-ISSUE-1-3: Issuing means  114  randomly selects nonnegative integer e of I_e bits where E=2^{I_E}+e is a prime number, and calculates y=(ag^x)^{1/E} mod n (step  1433 ). In other words, issuing means  114  determines a value remaining when RSA modulus n acts as a modulus for (ag^x)^{1/E}. 
     ISS-ISSUE-1-4: Issuing means  114  sends x paired with ID of the user to opener apparatus  400  (step  1434 ). 
     ISS-ISSUE-1-5: Issuing means  114  sends (E, y) to user apparatus  200  (step  1435 ). 
     [Joining Sequence 2 USR-JOIN-2] 
     Joining sequence 2 USR-JOIN-2 performed by joining means  212  will be described below.  FIG. 31  is a flowchart of joining sequence 2. As shown in  FIG. 31 , user apparatus  200  performs the following USR-JOIN-2-1, USR-JOIN-2-2 sequentially: 
     USR-JOIN-2-1: Joining means  212  confirms whether ag^ x=y^E is satisfied or not. If not, then joining means  212  finishes the joining sequence (step  1441 ). In other words, joining means  212  determines whether an RSA modulus which is the product of two prime numbers is equal to the modulus or not. 
     USR-JOIN-2-2: If ag^ x=y^E is satisfied, then joining means  212  sets member public key upk to (Y, y, E) and member secret key usk to (x, r), and writes upk, usk into user storage  220  (step  1442 ). Then, joining means  212  puts the joining sequence to an end. 
     With the key issuing method and the group signature system according to the present exemplary embodiment, the safety of information is enhanced even when data are sent and received concurrently between a plurality of user apparatus and the issuer apparatus according to the join protocol. In addition, as issuing sequence 2 performed by the issuer apparatus can be omitted, the process is made simpler than with Exemplary Embodiment 1 and Exemplary Embodiment 2. 
     Exemplary Embodiment 4 
     Apparatus Configuration 
     A group signature system according to the present exemplary embodiment will be described below. The configuration of the system will not be described in detail below as it is the same as the system described in Exemplary Embodiment 1. A key issuing method performed by the group signature system according to the present exemplary embodiment will be described below. According to the present exemplary embodiment, the issuer apparatus confidentializes data in a process different from the processes according to Exemplary Embodiments 1 through 4. 
     [Issuer key generating sequence ISS-GEN] and [Opener Key generating sequence OPN-GEN] are performed in the same manner as with Exemplary Embodiment 1. 
     [Issuing Sequence ISS-ISSUE and Joining Sequence USR-JOIN] 
     Issuer apparatus  100  and user apparatus  200  perform issuing sequence ISS-ISSUE and joining sequence USR-JOIN, respectively, while communicating with each other. First, issuer apparatus  100  performs [Issuing sequence 1 ISS-ISSUE-1] to be described later, and then user apparatus  200  performs [Joining sequence 1 USR-JOIN-1] to be described later. Issuer apparatus  100  performs [Issuing sequence 2 ISS-ISSUE-2] to be described later, and finally user apparatus  200  performs [Joining sequence 2 USR-JOIN-2] to be described later. 
     During the above sequences, member public key upk and member secret key usk are generated. 
     Member public key upk is disclosed to all the apparatus in some way. For example, one way to disclose upk may be putting it on a public bulletin board on the Internet. Any methods may be used to disclose upk. 
     [Signature sequence USR-SIGN], [Verifying sequence VER-VERIFY], and [Opening sequence OPN-OPEN] are performed in the same manner as with Exemplary Embodiment 1. 
     [Issuing Sequence 1 ISS-ISSUE-1] 
     Issuing sequence 1 ISS-ISSUE-1 performed by issuing means  114  will be described below.  FIG. 32  is a flowchart of issuing sequence 1. As shown in  FIG. 32 , issuer apparatus  100  performs the following ISS-ISSUE-1-1, . . . , ISS-ISSUE-1-4 sequentially: 
     ISS-ISSUE-1-1: Issuing means  114  reads ipk=(n, a, g, h, pf_α), opk=(F, G, H), isk=(p, q, α) from issuer storage  120  (step  1451 ). 
     ISS-ISSUE-1-2: Issuing means  114  randomly selects nonnegative integer e of I_e bits where E=2^{I_E}+e is a prime number. Issuing means  114  also randomly selects nonnegative integer p of I_n+I_s bits, and calculates g′=g^{p/E} mod n, h′=h^{p/E} mod n (step  1452 ). 
     ISS-ISSUE-1-3: Issuing means  114  sends (g′, h′) to user apparatus  200  (step  1453 ). 
     [Joining Sequence 1 USR-JOIN-1] 
     Joining sequence 1 USR-JOIN-1 performed by joining means  212  will be described below.  FIG. 33  is a flowchart of joining sequence 1. As shown in  FIG. 33 , user apparatus  200  performs the following USR-JOIN-1-1, . . . , USR-JOIN-1-7 sequentially: 
     USR-JOIN-1-1: Joining means  212  receives (g′, h′) (step  1461 ). 
     USR-JOIN-1-2: Joining means  212  reads ipk=(n, a, g, h, pf_α), opk=(F, G, H) from user storage  220  (step  1462 ). 
     USR-JOIN-1-3: Joining means  212  enters (ipk, pf_α) and performs [pf_α verifying sequence] to be described later. If [pf_α verifying sequence] outputs reject, then joining means  212  finishes the joining sequence (step  1463 ). 
     USR-JOIN-1-4: Joining means  212  randomly selects element x of (Z/QZ) and element r′ of (Z/nZ) and calculates Y=G^{x} (step  1464 ). 
     USR-JOIN-1-5: Joining means  212  calculates C=g′^{x}h′^{r′} mod n (step  1465 ). 
     USR-JOIN-1-6: Joining means  212  enters (n, g, h, x, r′, g′, h′, Y, C) and performs [(Y, C) legitimacy proving sequence] to be described to generate pf_{Y, C} (step  1466 ). 
     USR-JOIN-1-7: Joining means  212  sends (Y, C, pf_{Y, C}) to issuer apparatus  100  (step  1467 ). 
     [Issuing Sequence 2 ISS-ISSUE-2] 
     Issuing sequence 2 ISS-ISSUE-2 performed by issuing means  114  will be described below.  FIG. 34  is a flowchart of issuing sequence 2. As shown in  FIG. 34 , issuer apparatus  100  performs the following ISS-ISSUE-2-1, . . . , ISS-ISSUE-2-5 sequentially: 
     ISS-ISSUE-2-1: Issuing means  114  receives (Y, C, pf_{Y, C}) (step  1471 ). 
     ISS-ISSUE-2-2: Issuing means  114  enters (n, g, h, g′, h′, Y, C, pf_{Y, C}) and performs [(Y, C) legitimacy proof verifying sequence] to be described. If [(Y, C) legitimacy proof verifying sequence] outputs reject, then issuing means  114  finishes the joining sequence (step  1472 ). 
     ISS-ISSUE-2-3: Issuing means  114  calculates g″=g′^{1/p}, randomly selects element r″ of (Z/EZ), and calculates y=a^{1/E}g″h″^{r″} mod n (step  1473 ). 
     ISS-ISSUE-2-4: Issuing means  114  sends Y paired with ID of the user to opener apparatus  400  (step  1474 ). 
     ISS-ISSUE-2-5: Issuing means  114  sends (y, r″) to user apparatus  200  (step  1475 ), and then puts the issuing sequence to an end. 
     [Joining sequence 2 USR-JOIN-2], [pf_α generating sequence], and [pf_α verifying sequence] are performed in the same manner as with Exemplary Embodiment 1. 
     [(Y, C) Legitimacy Proving Sequence] 
     A (Y, C) legitimacy proving sequence performed by user apparatus controller  210  will be described below.  FIG. 35  is a flowchart of the (Y, C) legitimacy proving sequence. As shown in  FIG. 35 , user apparatus  200  performs the following PF-YC-GEN-1, . . . , PF-YC-GEN-5 sequentially: 
     PF-YC-GEN-1: User apparatus controller  210  receives (n, g, h, x, r′, g′, h′, Y, C) (step  1481 ). 
     PF-YC-GEN-2: User apparatus controller  210  randomly selects natural number x — {0, 1} of I_q+I_s bits and natural number r′ — {0, 1} of I_n+I_s bits, and calculates Y — {0, 1}=G^{x — {0, 1}}, C — {0, 1}=g′^{x — {0, 1}}h′^{r′ — {0, 1}} (step  1482 ). 
     PF-YC-GEN-3: User apparatus controller  210  calculates c=H_{I_c} (n, g, h, g′, h′, Y, C, Y — {0, 1}, C — {0, 1}) (step  1483 ). 
     PF-YC-GEN-4: User apparatus controller  210  calculates x — {0, 2}=cx+x — {0, 1}, r′ — {0, 2}=cr′+r′ — {0, 1} (step  1484 ). 
     PF-YC-GEN-5: User apparatus controller  210  establishes pf_{Y, C}=(c, x — {0, 2}, r′ — {0, 2}) (step  1485 ). 
     [(Y, C) Legitimacy Proof Verifying Sequence] 
     A (Y, C) legitimacy proof verifying sequence performed by issuer apparatus controller  110  will be described below.  FIG. 36  is a flowchart of the (Y, C) legitimacy proof verifying sequence. As shown in  FIG. 36 , issuer apparatus  100  performs the following PF-YC-VER-1, PF-YC-VER-3 sequentially: 
     PF-YC-VER-1: Issuer apparatus controller  110  receives (n, g, h, g′, h′, Y, C, pf_{Y, C}), and parses them into pf_{Y, C}=(c, x — {0, 2}, r′ — {0, 2}) (step  1491 ). 
     PF-YC-VER-2: Issuer apparatus controller  110  calculates Y′ — {0, 1}=Y^{−c} G^{x — {0, 2} and C′ — {0, 1}=C^{−c} g′^{x — {0, 2}}h′^{r′ — {0, 2}} (step  1492 ). 
     PF-YC-VER-3: If c=H_{I_c}(n, g, h, g′, h′, Y, C, Y′ — {0, 1}, C′ — {0, 1}) is satisfied, then issuer apparatus controller  110  accepts it, and if not satisfied, then issuer apparatus controller  110  rejects it (step  1493 ). 
     With the method of issuing a key to an additional member and the group signature system according to the present exemplary embodiment, the issuer apparatus first generates first confidential data using the secret key of the issuer apparatus, and then the user apparatus processes the first confidential data into second confidential data and proves the processed data to the issuer apparatus. Unlike the group signature apparatus of the background art, the issuer apparatus processes the data using the secret key of the issuer apparatus before the user apparatus proves the legitimacy of the data. Therefore, the safety of information is enhanced even when data are sent and received concurrently between a plurality of user apparatus and the issuer apparatus according to the join protocol. 
     The information confidentializing process according to the present exemplary embodiment has a higher information processing rate than with Exemplary Embodiment 1 as it does not need a data encrypting process and a data decrypting process. 
     Exemplary Embodiment 5 
     Apparatus Configuration 
     A group signature system according to the present exemplary embodiment will be described below. The configuration of the system will not be described in detail below as it is the same as the system described in Exemplary Embodiment 1. Configurational details which are different from those of Exemplary Embodiment 1 will be described below. 
     It is assumed that the storages of the apparatus have been supplied with security parameter k in advance. The storages may be supplied with k in any ways. 
     It is assumed that ┌ — 1, ┌ — 2, ┌_T represent cyclic groups of order p, bilinear mapping e from ┌ — 1 X ┌ — 2 onto ┌_T is defined, and the number of bits of p is k. It is also assumed that r represents a cyclic group of order p. 
     Furthermore, it is assumed that the storages of the apparatus have been supplied with parameters descriptive of ┌ — 1, ┌_T, and p in advance. The storages of the apparatus may be supplied with the parameters descriptive of ┌ — 1, ┌ — 2, ┌_T, and p in any ways. 
     A key issuing method carried out by the group signature system according to the present exemplary embodiment will be described below. The key issuing method according to the present exemplary embodiment is similar to the method described in Exemplary Embodiment 2 except that the information confidentializing process performed by the issuer apparatus is different from the process according to Exemplary Embodiment 2. Therefore, details which are different from those according to Exemplary Embodiment 2 will be described below. 
     [Issuer Key Generating Sequence ISS-GEN]: 
     Issuer key generating sequence ISS-GEN performed by issuer key generating means  112  will be described below.  FIG. 37  is a flowchart of the issuer key generating sequence. As shown in  FIG. 37 , issuer apparatus  100  performs the following ISS-GEN-1 and ISS-GEN-2 sequentially: 
     ISS-GEN-1: Issuer key generating means  112  randomly selects elements G — 1, H, K of ┌ — 1, element G — 2 of ┌ — 2, and element w of (Z/pZ), and establishes Y=wG — 2 (step  1501 ). 
     ISS-GEN-2: Issuer key generating means  112  sets issuer public key ipk to (G — 1, G — 2, H, K, Y), sets issuer secret key isk to w, and stores ipk and isk in issuer storage  120  (step  1502 ). 
     Opener apparatus  400  performs [Opener key generating sequence OPN-GEN] in the same manner as with Exemplary Embodiment 2. 
     [Issuing Sequence ISS-ISSUE and Joining Sequence USR-JOIN] 
     Issuer apparatus  100  and user apparatus  200  perform issuing sequence ISS-ISSUE and joining sequence USR-JOIN, respectively, while communicating with each other. 
     First, issuer apparatus  100  performs [Issuing sequence 1 ISS-ISSUE-1] to be described later, and then user apparatus  200  performs [Joining sequence 1 USR-JOIN-1] to be described later. Furthermore, issuer apparatus  100  performs [Issuing sequence 2 ISS-ISSUE-2] to be described later, and finally user apparatus  200  performs [Joining sequence 2 USR-JOIN-2] to be described later. 
     During the above sequences, member public key upk and member secret key usk are generated. 
     Member public key upk is disclosed to all the apparatus in some way. For example, one way to disclose upk may be putting it on a public bulletin board on the Internet. Any methods may be used to disclose upk. 
     [Signature sequence USR-SIGN], [Verifying sequence VER-VERIFY], and [Opening sequence OPN-OPEN] are performed in the same manner as with Exemplary Embodiment 2. 
     [Issuing Sequence 1 ISS-ISSUE-1] 
     Issuing sequence 1 ISS-ISSUE-1 performed by issuing means  114  will be described below.  FIG. 38  is a flowchart of issuing sequence 1. As shown in  FIG. 38 , issuer apparatus  100  performs the following ISS-ISSUE-1-1, ISS-ISSUE-1-2 sequentially: 
     ISS-ISSUE-1-1: Issuing means  114  reads ipk=(G — 1, G — 2, H, K, Y), opk=(G, S, T), isk=(w, Isk) from issuer storage  120  (step  1511 ). 
     ISS-ISSUE-1-2: Issuing means  114  randomly selects element y_U of (Z/pZ) and ρ, calculates H′=(ρ/(w+y_U))H, K′=(ρ/(w+y_U))K, and sends H′, K′ to user apparatus  200  (step  1512 ). 
     [Joining Sequence 1 USR-JOIN-1] 
     Joining sequence 1 USR-JOIN-1 performed by joining means  212  will be described below.  FIG. 39  is a flowchart of joining sequence 1. As shown in  FIG. 39 , user apparatus  200  performs the following USR-JOIN-1-1, . . . , USR-JOIN-1-6 sequentially: 
     USR-JOIN-1-1: Joining means  212  receives (H′, K′) (step  1521 ). 
     USR-JOIN-1-2: Joining means  212  reads ipk=(G — 1, G — 2, H, K, Y), opk=(G, S, T) from user storage  220  (step  1522 ). 
     USR-JOIN-1-3: Joining means  212  randomly selects elements x_U, z′_U of (Z/pZ) and calculates Ider_U=x_U G (step  1523 ). 
     USR-JOIN-1-4: Joining means  212  calculates C=H′^{x_U}K′^{z′_U} (step  1524 ). 
     USR-JOIN-1-5: Joining means  212  enters (G, H′, K′, x_U, z′_U, Ider_U, C) and performs [(Ider_U, C) legitimacy proving sequence] to be described later to generate pf_{Ider_U, C} (step  1525 ). 
     USR-JOIN-1-6: Joining means  212  sends (Ider_U, Cipher, pf_{Ider_U, C}) to issuer apparatus  100  (step  1526 ). 
     [Issuing Sequence 2 ISS-ISSUE-2] 
     Issuing sequence 2 ISS-ISSUE-2 performed by issuing means  114  will be described below.  FIG. 40  is a flowchart of issuing sequence 2. As shown in  FIG. 40 , issuer apparatus  100  performs the following ISS-ISSUE-2-1, . . . , ISS-ISSUE-2-5 sequentially: 
     ISS-ISSUE-2-1: Issuing means  114  receives (Ider_U, Cipher, pf_{Ider_U, C}) (step  1531 ). 
     ISS-ISSUE-2-2: Issuing means  114  enters (G, H′, K′, Ider_U, C, pf_{Ider_U, C}) and performs [(Ider_U, C) legitimacy proof verifying sequence] to be described later. If [(Ider_U, C) legitimacy proof verifying sequence] outputs reject, then issuing means  114  finishes the joining sequence (step  1532 ). 
     ISS-ISSUE-2-3: Issuing means  114  calculates G — 1″=C″^{1/ρ}, randomly selects element z″_U of (Z/eZ), and calculates A_U=(1/(w+y_U)) G — 1-G — 1″-z″_UK (step  1533 ). G — 1″ corresponds to g″ according to Exemplary Embodiment 4, and represents unconfidentialized data. 
     ISS-ISSUE-2-4: Issuing means  114  sends Ider_U paired with ID of the user to opener apparatus  400  (step  1534 ). 
     ISS-ISSUE-2-5: Issuing means  114  sends (A_U, z″_U) to user apparatus  200  (step  1535 ), and then puts the issuing sequence to an end. 
     [Joining sequence 2 USR-JOIN-2] is performed in the same manner as with Exemplary Embodiment 2. 
     [(Ider_U, C) Legitimacy Proving Sequence] 
     A (Ider_U C) legitimacy proving sequence performed by joining means  212  will be described below.  FIG. 41  is a flowchart of the (Ider_U, C) legitimacy proving sequence. As shown in  FIG. 41 , user apparatus  200  performs the following USR-PF-1, . . . , USER-P-5 sequentially: 
     USR-PF-1: Joining means  212  receives (G, H′, K′, x_U, Ider_U, C) (step  1541 ). 
     USR-PF-2: Joining means  212  randomly selects elements x_{U, 0, 1}, z′_{U, 0, 1} of (Z/qZ), and calculates C — {0, 1}=H′^{x_{U, 0, 1}}K′^{z′_{U, 0, 1}} (step  1542 ). 
     USR-PF-3: Joining means  212  calculates c=H_{Z/qZ}(G, H′, K′, x_U, z′_U, Ider_U, C, C — {0, 1}) (step  1543 ). 
     USR-PF-4: Joining means  212  calculates x_{U, 0, 2}=cx_U+x_{U, 0, 2}, z_{U, 0, 2}=cz_U+z_{U, 0, 2} (step  1544 ). 
     USR-PF-5: Joining means  212  establishes pf_{Ider_U, C}=(c, x_{U, 0, 2}, z_{U, 0, 2}) (step  1545 ). 
     [(Ider_U, C) Legitimacy Proof Verifying Sequence] 
     An (Ider_U, C) legitimacy proof verifying sequence performed by issuing means  114  will be described below.  FIG. 42  is a flowchart of the (Ider_U, C) legitimacy proof verifying sequence. As shown in  FIG. 42 , issuer apparatus  100  performs the following USR-VER-1, USR-VER-4 sequentially: 
     USR-VER-1: Issuing means  114  receives (G, H′, K′, Ider_U, C, pf_{Ider_U, C}) (step  1551 ). 
     USR-VER-2: Issuing means  114  parses it into pf_{Ider_U, C}=(c, x_{U, 0, 2}, z_{U, 0, 2}) (step  1552 ). 
     USR-VER-3: Issuing means  114  calculates C′ — {0, 1}=H′^{x_{U, 0, 2}}K′^{z′_{U, 0, 2}}C^{-c} (step  1553 ). 
     USR-VER-3: If c=H_{Z/qZ}(G, H′, K′, x_U, z′_U, Ider_U, C, C′ — {0, 1}) is satisfied, then issuing means  114  outputs accept, and if not satisfied, then issuing means  114  outputs reject (step  1554 ). 
     The key issuing method and the group signature system according to the present exemplary embodiment have a higher information processing rate than with Exemplary Embodiment 2 as they do not need a data encrypting process and a data decrypting process. 
     The key issuing methods according to the above exemplary embodiments may be applied to a program to be executed by a computer. The program may be recorded in a recording medium readable by a computer. 
     The present invention is not limited to the above embodiments, but various modifications may be made within the scope of the invention as falling within the scope of the invention.