Anonymous authentication system and anonymous authentication method

The present invention relates to an anonymous authentication system and an anonymous authentication method.

In recent years, the importance of network security has been widely recognized. To achieve security, various services on the network are configured to provide services only to specific people. Therefore, these services perform personal authentication of the service user when using the service. However, by collecting a plurality of histories in this authentication, personal information about when, where, and what the same service user did becomes clear, and the privacy of that individual is infringed. Therefore, from the viewpoint of privacy, it is desirable that personal authentication is not performed as much as possible.

As a measure to increase the anonymity of the person to be authenticated, a method of issuing the same ID and password to all members of the service can be considered. In this method, all members authenticate using the same ID and password, so it is possible to authenticate without identifying an individual. However, if one of the members leaks the password to someone other than the member, the password must be reissued and the new password must be given to all members in order to provide services only to the member. It doesn't become. In addition, even if the behavior of the person to be authenticated is an act that should identify an individual according to the rules, the administrator cannot identify the person to be authenticated.

Further, Patent Document 1 describes an anonymous authentication method. This anonymous authentication method is an authentication method in which the administrator can identify and exclude the person to be authenticated as necessary while maintaining the anonymity of the person to be authenticated. Further, this authentication method can identify whether it is the act of the same subject or the act of a different subject for a plurality of authentications. This may have the advantage that the administrator can obtain information about repeaters in commercial membership services, etc. However, if the person to be authenticated is identified for some reason, the person to be authenticated in the past. There is a problem that all the authentication history is revealed. In addition, the anonymous authentication method of Patent Document 1 has a problem that the administrator can impersonate the member because the administrator knows the IDs and passwords of all the members.

Further, Non-Patent Document 1 describes an anonymous authentication method using a group signature. These anonymous authentication methods cannot identify whether it is the act of the same subject or the act of a different subject for multiple authentications, and the member is an administrator. Impersonation is impossible. However, these methods have a problem that the calculation cost for the person to be authenticated to generate the data necessary for authentication (hereinafter referred to as authentication data) is large.<patcit num="1"><text>Japanese Unexamined Patent Publication No. 2006-235661</text></patcit><nplcit num="1"><text>J. Camenisch and J. Groth. Group signatures: better efficiency and new theoretical aspects. Forth Int. Conf. On Security in Communication Networks --SCN 2004, LNCS 3352, Springer, 2005.</text></nplcit>

<p num="0006"> An object of the present invention is to ensure the anonymity of the person to be authenticated, and to deprive the person of the anonymity as necessary. It provides an anonymous authentication system and an anonymous authentication method that cannot determine whether the person is acting, prevents the group administrator who manages the group from spoofing the member, and requires less calculation cost to generate the authentication data of the authenticated person. There is.</p>

<p num="0007"> According to one aspect of the present invention, the anonymous authentication system is operated by a group management device that manages a group of users and a person to be authenticated who belongs to a group managed by the group management device and requests authentication. It has a device, a verification device that verifies that the user who is trying to authenticate belongs to a group, a verification assist device that assists the verification act, and a person identification device that identifies the person to be authenticated. .. The authenticated person device generates unlinkable authentication data for multiple authentications, in which no one can identify whether it is the act of the same authenticated person or the act of a different authenticated person. It has an unlinkable authentication data generator. The verification device receives the verification auxiliary data from the verification auxiliary request unit that outputs the verification auxiliary request for requesting the verification auxiliary action to the verification auxiliary device and the verification auxiliary device that responds to the verification auxiliary request, and also receives the verification auxiliary data. It has a verification unit that inputs unlinkable authentication data from the certifier device and outputs the verification result. The authenticated person identification device has an authenticated person identification unit that identifies the authenticated person by inputting the unlinkable authentication data and the private key of the group. According to another aspect of the present invention, the anonymous authentication system is operated by a group management device that manages a group of users and a person to be authenticated belonging to the group managed by the group management device, and is authenticated to request authentication. A person device, an authentication assist device that assists the authentication act, a verification device that verifies that the user who is trying to authenticate belongs to a group, and a person identification device that identifies the person to be authenticated. Have. The authenticated person device receives the authentication assist data from the authentication assist request unit that outputs the authentication assist request requesting the authentication assist act to the authentication assist device and the authentication assist device that responds to the authentication assist request. Unlinkable authentication data generator that generates unlinkable authentication data that makes it impossible for anyone to identify whether it is the act of the same subject or the act of a different subject for multiple authentications. And have. The verification device has a verification unit that inputs unlinkable authentication data and performs verification. The authenticated person identification device has an authenticated person identification unit that identifies an authenticated person by inputting unlinkable authentication data and a group private key.</p><p num="0008"> According to still another aspect of the present invention, the anonymous authentication system is a group management device that manages a group of users, a subject device for a member of the group to request authentication, and a user who is trying to authenticate. It has a verification device that verifies that it belongs to a group, an authentication assist device that assists the authentication, a verification assist device that assists the verification, and a subject identification device that identifies the person to be authenticated. The authenticated person device receives the authentication assist data from the authentication assist request unit that outputs the authentication assist request requesting the authentication assist act to the authentication assist device and the authentication assist device that responds to the authentication assist request. Unlinkable authentication data generator that generates unlinkable authentication data that makes it impossible for anyone to identify whether it is the act of the same subject or the act of a different subject for multiple authentications. And have. The verification device receives verification auxiliary data from the verification auxiliary request unit that outputs the verification auxiliary request for requesting the verification auxiliary action to the verification auxiliary device and the verification auxiliary device that responds to the verification auxiliary request, and also unlinkable authentication. It has a verification unit that inputs data and outputs verification results. The authenticated person identification device has an authenticated person identification unit that identifies an authenticated person by inputting unlinkable authentication data and a group private key.</p><p num="0009"> The present invention has the following effects.</p><p num="0010"> First, while ensuring the anonymity of the person to be authenticated, the anonymity can be deprived as necessary, and for multiple authentications, it is the same person's act or another person to be authenticated. It is not possible to determine whether it is an act. As a result, the privacy of the users belonging to the group can be protected.</p><p num="0011"> Second, it is possible to prevent user spoofing by the group administrator who manages the group. As a result, for example, in a pay-as-you-go service, it is possible to prevent excessive billing to users due to fraudulent group administrator. Further, since the authentication data of a certain user can be generated only by that user, it is possible to make it impossible for the user to deny the authentication result.</p><p num="0012"> Thirdly, it is possible to reduce the load on the user during authentication. As a result, it is possible to handle the case where the user has only a device with few computing resources.</p>

<figref num="1">FIG. 1 is a block diagram of an anonymous authentication system according to the first embodiment of the present invention.</figref><figref num="2">FIG. 2 is a block diagram of the group management device 10.</figref><figref num="3">FIG. 3 is a block diagram of the authenticated person device 20.</figref><figref num="4">FIG. 4 is a block diagram of the verification device 30.</figref><figref num="5">FIG. 5 is a block diagram of the verification auxiliary device 40.</figref><figref num="6">FIG. 6 is a block diagram of the authenticated person identification device 50.</figref><figref num="7">FIG. 7 is a flowchart of the membership registration process in the first embodiment.</figref><figref num="8">FIG. 8 is a flowchart of the authentication process according to the first embodiment.</figref><figref num="9">FIG. 9 is a flowchart of the authenticated person identification process in the first embodiment.</figref><figref num="10">FIG. 10 is a block diagram of an anonymous authentication system according to the second embodiment of the present invention.</figref><figref num="11">FIG. 11 is a block diagram of the authenticated person device 21.</figref><figref num="12">FIG. 12 is a block diagram of the authentication assist device 61.</figref><figref num="13">FIG. 13 is a block diagram of the verification device 31.</figref><figref num="14">FIG. 14 is a sequence of authentication processing in the second embodiment.</figref><figref num="15">FIG. 15 is a block diagram of an anonymous authentication system according to a third embodiment of the present invention.</figref><figref num="16">FIG. 16 is a block diagram of the authentication assist device 62.</figref><figref num="17">FIG. 17 is a block diagram of the verification auxiliary device 42.</figref><figref num="18">FIG. 18 is a flowchart of the authentication process according to the third embodiment.</figref><figref num="19">FIG. 19 is a flowchart of the authentication process according to the third embodiment.</figref>

Code description

10 Group management device 20, 21 Authenticated person equipment 30, 31 Verification device 40, 42 Verification aid 50 Authenticated person identification device 61, 62 Authentication aid 10-1 Registration Processing Department 10-2 Member registration information storage device 20-1 Registration Request Department 20-2 ID / key pair storage device 20-3 Certification Request Department 20-4 Signature generator 20-5 Unlinkable authentication data generator 30-1 Challenge Generation Department 30-2 Verification Assistance Request Department 30-3 Verification Department 30-4 Unlinkable Authentication Data Storage 30-5 Authenticated person identification request department 40-1 Authentication data decryption unit 40-2 Signature Verification Department 50-1 Authentication data decryption unit 50-2 Authenticated person identification department 101-105, 201-208 steps 301-305, 401-409, 501-511 steps

Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

The present invention is characterized in that public key encryption is used in order to obtain the anonymity of the person to be authenticated in anonymous authentication. In public key cryptography, a user has a private key and a public key corresponding to the private key. When user A sends a message to user B using public key cryptography, user A encrypts the message using the public key published by user B and sends a ciphertext to user B. The user B who receives the ciphertext decrypts the ciphertext using his / her own private key and generates a message.

Further, the present invention is characterized in that, in anonymous authentication, a digital signature technology is used in order to prevent the group administrator from impersonating an existing user. Digital signature technology is based on public key cryptography. The signer has a signing key (private key) and a verification key (public key) corresponding to the signing key. The signer uses the signing key to sign the message. The verifier can confirm that the signature was made by the signer by using the verification key published by the signer. By using the ciphertext as the authentication data, the information regarding the ID of the authenticated person is not given to the verifier who does not have the decryption key used for the decryption.

In the following description, a ^ {b} means a to the bth power, and a_b indicates that a is subscripted b. In addition, the bit concatenation is expressed as "The" (for example, when a = 10 (binary notation) and b = 01, aTheb = 1001).

[First Embodiment] As shown in FIG. 1, the anonymous authentication system according to the first embodiment of the present invention has a group management device 10, a subject device 20, a verification device 30, a verification auxiliary device 40, and a subject identification device 50. There is. The group management device 10 manages a group of users. The authenticated person device 20 is operated by a person who belongs to a group managed by the group management device 10 and requests authentication. The verification device 30 verifies that the user who is trying to authenticate belongs to the group. The verification assist device 40 assists the above verification act. The authenticated person identification device 50 deprives the authenticated person of anonymity in the event of any problem.

Group management device 10 and authenticated person device 20, group management device 10 and verification auxiliary device 40, group management device 10 and authenticated person identification device 50, authenticated person device 20 and verification device 30, verification device 30 and verification auxiliary device 40, the verification device 40 and the authenticated person identification device 50 are each connected to each other through a network such as the Internet.

The group management device 10 exists for each group, and a plurality of authenticated person devices 20 and verification devices 30 may exist in each group. In addition, the encryption key enc_g of the group corresponding to the group is input to the authenticated person device 20. The group decryption key dec_g corresponding to the group encryption key enc_g is input to the verification auxiliary device 40 and the authenticated person identification device 50. These encryption keys / decryption keys exist for each group.

2 to 6 are block diagrams of the group management device 10 to the authenticated person identification device 50, respectively.

As shown in FIG. 2, the group management device 10 stores a registration processing unit 10-1 that performs a user registration process for joining a group, and a member that stores a registration information list (hereinafter referred to as a member list) of members belonging to the group. It has a registration information storage device 10-2.

As shown in FIG. 3, the authenticated person device 20 has a registration request unit 20-1 that sends a registration request message to the group management device 10, a user ID and a user signature key assigned by the group management device 10. -Has an ID / key pair storage device 20-2 that stores the verification key pair. The authenticated person device 20 further includes an authentication request unit 20-3 that sends a request message for authentication to the verification device 30, and a signature generation unit 20-3 that generates a signature using the user's signature key when generating authentication data. It also has an unlinkable authentication data generation unit 20-5 that receives the encryption key of the group and generates unlinkable authentication data (unlinkable authentication data). Here, "unlinkable" means that it is impossible for anyone to identify whether it is the act of the same subject or the act of a different subject for multiple authentications. It means to say.

As shown in FIG. 4, the verification device 30 receives the challenge generation unit 30-1 that receives the authentication request and generates the challenge, and the verification assist device 30 that receives the unlinkable authentication data and sends the verification assist request to the verification assist device 40. It has a request unit 30-2 and a verification unit 30-3 that receives verification assistance results and performs verification. The verification device 30 further deprives the unlinkable authentication data storage device 30-4, which stores the unlinkable authentication data, and the unlinkable authentication data stored in the unlinkable authentication data storage device 30-4, as the authentication history. It has a subject identification request unit 30-5 that transmits a request to the subject identification device 50.

As shown in FIG. 5, the verification auxiliary device 40 receives the verification auxiliary request and the decryption key of the group, receives the authentication data decryption unit 40-1 that decrypts the authentication data, and receives the member list, and verifies the signature. It has a signature verification unit 40-2 to perform.

As shown in FIG. 6, the authenticated person identification device 50 receives the anonymity deprivation request and the decryption key of the group, receives the authentication data decryption unit 50-1 that decrypts the authentication data, and receives the member list, and receives the subject. It has a certified person identification unit 50-2 that identifies the certifier.

First, the pre-processing (membership registration process) at the time of authentication will be described with reference to FIG. 7.

Here, as an example, the user U having the signature key sk_u and the verification key vk_u will be described as registering. The user U stores the signature key / verification key pair (sk_u, vk_u) in the IC card or flash memory in advance, and the authenticated person device 20 has an interface that can access the IC card or flash memory.

First, the user U inputs the signature key / verification key pair (sk_u, vk_u) into the authenticated person device 20 (step 101). Upon receiving the verification key vk_u, the registration request unit 20-1 sends a registration request req_r to the group management device 10 (step 102). At this time, the registration request req_r contains the verification key vk_u of user U and personal information necessary for registration such as address, name, and age. Upon receiving the registration request req_r, the registration processing unit 10-1 issues a unique ID ID_u for the user U and sends the ID_u to the authenticated person device 20 (step 103). However, if there are some conditions (gender restriction, age restriction, double registration prohibition, etc.) in the registration, the registration processing department 10-1 will examine according to the registration request req_r, and the registration request from the user U who does not meet the conditions If so, the non-registration may be sent to the authenticated person device 20. If the user cannot be registered, the subsequent communication with the user is stopped. The registration processing unit 10-1 reads the member list List from the member registration information storage device 10-2, and (ID_u, (req_r) is added to the member list List, and the updated member list List is stored in the member registration information storage device 10-2 (step 104). The authenticated person device 20 that has received the ID_u stores (ID_u, (sk_u, vk_u)) in the ID / key pair storage device 20-2 (step 105).

Next, the flow of the authentication process will be described with reference to FIG.

Here, as an example, it is assumed that the user U having the signature key sk_u and the verification key vk_u has completed registration, and (ID_u, (sk_u, vk_u)) is stored in the ID / key pair storage device 20-2. explain.

First, the authentication request unit 20-3 of the authenticated person device 20 sends an authentication request req_a to the verification device 30 (step 201). Upon receiving the authentication request req_a, the challenge generator 30-1 sends a random message, the challenge nonce, to the authenticated person device 20 (step 202). Upon receiving the challenge nonce, the signature generator 20-4 generates the user U's signature σ for the challenge nonce using the sk_u stored in the ID / key pair storage device 20-2 (step 203). Next, the unlinkable authentication data generation unit 20-5 that has received the group encryption key enc_g encrypts the ID_u || σ and generates the ciphertext C. Further, the unlinkable authentication data response including the ciphertext C is transmitted to the verification device 30 (step 204). Upon receiving the unlinkable authentication data response, the verification auxiliary request unit 30-2 transmits the verification auxiliary request data req_v including the ciphertext C to the verification auxiliary device 40 (step 205). Validation assistance request data req_v and group decryption key Upon receiving the dec_g, the authentication data decryption unit 40-1 decrypts the ciphertext C included in the verification auxiliary request data req_v, and parses the decrypted data obtained as a result of the decryption with ID || σ (step 206). That is, the decoded data is decomposed into ID and σ. Next, the signature verification unit 40-2, which has received the member list list stored in the member registration information storage device 10-2 of the group management device 10, confirms whether the ID is described in the member list list. If it is not described, the fact that it is not accepted is transmitted to the verification device 30 as verification auxiliary data ans_v. If so, verify σ using the verification key vk corresponding to the ID. The signature verification result (accepted or rejected) is transmitted to the verification device 30 as verification auxiliary data ans_v (step 207). Upon receiving the verification auxiliary data ans_v, the verification unit 30-3 generates and outputs the authentication result result. That is, if the verification auxiliary data ans_v is accepted, the authentication result result is the data indicating the authentication success. Also, verification auxiliary data If ans_v is not accepted, the authentication result result will be the data indicating the authentication failure. In addition, the unlinkable authentication data response that was successfully authenticated is stored in the unlinkable authentication data storage device 30-4 (step 208). However, the unlinkable authentication data for which authentication has failed may also be stored in the unlinkable authentication data storage device 30-4.

Here, since the information regarding the ID of the authenticated person device 20 is encrypted by the group encryption key enc_g, the verification device 30 that does not have the group decryption key dec_g as an input has the ID of the authenticated person device 20. The information about is not even transmitted whether the two unlinkable authentication data are from the same subject or different subjects. The verification auxiliary device 40 that receives the group decryption key dec_g as an input decrypts the ciphertext C contained in the verification auxiliary request data req_v received from the verification device 30 using the group decryption key dec_g, and obtains the ID and signature data σ. obtain. The verification auxiliary device 40 confirms that the ID is included in the member list list and that it is accepted when the signature data σ is verified using the verification key corresponding to the ID. Therefore, an unregistered user, that is, a user who does not have a signing key corresponding to a verification key registered in the member list list, is a member list list. Since it is impossible to generate the signature data to be accepted using the verification key included in, it is impossible to succeed in the authentication. Furthermore, even the administrator who manages the group does not know the signing key corresponding to the verification key registered in the member list, so that the authentication cannot be successful.

Next, the process of identifying the authenticated person from the unlinkable authentication data will be described with reference to FIG.

Here, as an example, a case where the ID of the authenticated person who generated the unlinkable authentication data response_i stored in the unlinkable authentication data storage device 30-4 provided in the verification device 30 is specified will be described.

First, the authenticated person identification request unit 30-5 of the verification device 30 that has received the unlinkable authentication data response_i stored in the unlinkable authentication data storage device 30-4 sets the authenticated person identification request data req_t to the authenticated person identification device. Send to 50 (step 301). Here, the authenticated person identification request data req_t includes the unlinkable authentication data response_i. Upon receiving the authenticated person identification request data req_t and the group decryption key dec_g, the authentication data decryption unit 50-1 decrypts the ciphertext C_i contained in the unlinkable authentication data response_i and parses the decrypted data with ID_i || σ_i ( Step 302). Next, the authenticated person identification unit 50-2 that has received the member list list stored in the member registration information storage device 10-2 provided by the group management device 10 has ID_i listed in the member list list. If ID_i is listed in the member list, use the verification key vk_i corresponding to ID_i. Verify σ_i (step 303). If the verification result is accepted, the unlinkable authentication data response_i outputs that the authentication data is created by the user with ID ID_i (step 304). If ID_i is not listed in the member list or the verification result of σ_i is not accepted, the unlinkable authentication data response_i requested to identify the authenticated person is output as unaccepted authentication data (step 305). ).

The following configuration is possible as a modification of the first embodiment. The authenticated person device 20 has at least an unlinkable authentication data generation unit 20-5 that generates unlinkable authentication data. The verification device 30 outputs verification auxiliary data to the verification auxiliary device 40 from the verification auxiliary request unit 30-2 that outputs a verification auxiliary request requesting the verification auxiliary action and the verification auxiliary device 40 that responds to the verification auxiliary request. It also has at least a verification unit 30-3 that receives and inputs unlinkable authentication data from the subject device 20 and outputs the verification result. The authenticated person identification device 50 has at least the authenticated person identification unit 50-2 for inputting the unlinkable authentication data and the private key of the group and identifying the authenticated person.

[Second Embodiment] As shown in FIG. 10, the anonymous authentication system according to the second embodiment of the present invention includes a group management device 10, an authenticated person device 21, an authentication assisting device 61, a verification device 31, and an authenticated person identifying device 50. The group management device 10 manages a group. The authenticated person device 21 is operated by an authenticated person who belongs to a group managed by the group management device 10. The authentication assist device 61 assists the above-mentioned authentication data generation act. The verification device 31 verifies that the user who is trying to authenticate belongs to the group. The authenticated person identification device 50 deprives the authenticated person of anonymity in the event of any problem.

Group management device 10 and authenticated person device 21, group management device 10 and authentication auxiliary device 41, group management device 10 and authenticated person identification device 50, authenticated person device 21 and verification device 31, certified person device 21 and authentication The auxiliary device 41, the verification device 41, and the authenticated person identification device 50 are each connected to each other through a network such as the Internet.

When a plurality of groups exist, a group management device exists for each group, and a plurality of authenticated person devices and a verification device may exist in each group. In addition, the encryption key enc_g of the group corresponding to the group is input to the authenticated person device 21. The group decryption key dec_g corresponding to the group encryption key enc_g is input to the authentication auxiliary device 61 and the authenticated person identification device 50. These encryption keys / decryption keys exist for each group.

FIG. 11 is a block diagram of the authenticated person device 21, FIG. 12 is a block diagram of the authentication assisting device 61, and FIG. 13 is a block diagram of the verification device 31. Since the group management device 10 and the authenticated person identification device 50 are the same as those in the first embodiment, their illustrations are omitted.

As shown in FIG. 11, the authenticated person device 21 has a registration request unit 21-1 that sends a registration request message to the group management device 10, and a user ID and a user signature key assigned by the group management device 10. -It has an ID / key pair storage device 21-2 that stores the verification key pair, and an authentication request unit 21-3 that sends a request message for authentication to the verification device 31. The authenticated person device 21 further receives the signature generation unit 21-4 that generates a signature using the user's signature key when generating the authentication data, and the encryption key of the group, generates an encryption text, and assists the authentication. It has an authentication auxiliary request unit 21-5 that transmits authentication auxiliary request data to the device 61, and an unlinkable authentication data generation unit 21-6 that receives authentication auxiliary data and generates unlinkable authentication data.

As shown in FIG. 12, the authentication assist device 61 receives the authentication assist request and the decryption key of the group, the decryption unit 61-1 that decrypts the ciphertext, and the signature that receives the member list and verifies the signature. It has a verification unit 61-2 and a group signature generation unit 61-3 that receives the group signature key and signs the ciphertext with the group.

As shown in FIG. 13, the verification device 31 receives the challenge generation unit 31-1 that receives the authentication request and generates the challenge, and the verification unit 31-2 that receives the unlinkable authentication data and the verification key of the group and performs verification. Has. The verification device 31 further deprives the unlinkable authentication data storage device 31-3, which stores the unlinkable authentication data, and the unlinkable authentication data stored in the unlinkable authentication data storage device 31-3, as the authentication history. It has a subject identification request unit 31-4 that sends a request to the subject identification device.

Since the pre-processing (admission registration process) in the present embodiment is the same as the pre-processing (admission registration process) in the first embodiment, the description thereof will be omitted.

The flow of the authentication process will be described with reference to FIG.

Here, as an example, it is assumed that the user U having the signature key sk_u and the verification key vk_u has completed registration, and (ID_u, (sk_u, vk_u)) is stored in the ID / key pair storage device 21-2. explain.

First, the authentication request unit 21-3 of the authenticated person device 21 sends an authentication request req_a to the verification device 31 (step 401). Upon receiving the authentication request req_a, the challenge generator 31-1 generates a random message, the challenge nonce, and sends it to the authenticated person device 21 (step 402). Upon receiving the challenge nonce, the signature generator 21-4 uses the sk_u stored in the ID / key pair storage device 21-2 to generate the signature σ of the user U for the challenge nonce (step 403). Next, the authentication auxiliary request unit 21-5 that has received the group encryption key enc_g encrypts the ID_u || σ and generates the ciphertext C. Further, the authentication auxiliary request data req_h including the ciphertext C is transmitted to the authentication auxiliary device 61 (step 404). Upon receiving the authentication auxiliary request data req_h and the group decryption key dec_g, the decryption unit 61-1 decrypts the ciphertext C included in the authentication auxiliary request data req_h and decrypts the decrypted data. Parse with ID || σ (step 405). Next, the signature verification unit 61-2, which has received the member list list stored in the member registration information storage device 10-2 of the group management device 10, confirms whether the ID is described in the member list list. If the ID is listed in the member list, verify σ using the verification key vk corresponding to the ID (step 406). If the ID is not listed in the member list, or if the verification result of σ is not accepted, the subsequent operation is stopped. If the ID is listed in the member list and σ is accepted using the verification key vk corresponding to the ID, the signature generator 61-3 of the group that received the group signature key sk_g is ciphertext. Sign C with the group's signature key sk_g to generate the signature σ_g. In addition, the authentication auxiliary data ans_h containing the signature σ_g is transmitted to the authenticated person device 21 (step 407). Authentication auxiliary data ans_h The unlinkable authentication data generator 21-6 that received the message sends the unlinkable authentication data response including the signature σ_g included in the authentication auxiliary data ans_h to the verification device 31 (step 408). Upon receiving the unlinkable authentication data response and the group verification key vk_g, the verification unit 31-2 verifies the signature σ_g included in the unlinkable authentication data response. If the verification result is accepted, the authentication result result is output as authentication success. In addition, the unlinkable authentication data response is stored in the unlinkable authentication data storage device 31-3. If the verification result is not accepted, the authentication result result is output as an authentication failure (step 409). However, the unlinkable authentication data for which authentication has failed may also be stored in the unlinkable authentication data storage device 31-3. Since the process of identifying the person to be authenticated from the unlinkable authentication data is the same as that of the first embodiment, the description thereof will be omitted.

The following configuration is possible as a modification of the second embodiment. The authenticated person device 21 receives the encryption key of the group, generates an encryption text, and sends the authentication assist request data to the authentication assist device 61. The authentication assist request unit 21-5 and the authentication assist device 61 assist the authentication. It has at least an unlinkable authentication data generator 21-6 that receives data and generates unlinkable authentication data. The verification device 31 has at least a verification unit 31-2 that receives the unlinkable authentication data and the verification key of the group and performs verification. The authenticated person identification device 50 has at least the authenticated person identification unit 50-2 for inputting the unlinkable authentication data and the private key of the group and identifying the authenticated person.

[Third Embodiment] As shown in FIG. 15, the anonymous authentication system according to the third embodiment of the present invention includes the group management device 10, the authenticated person device 21, the authentication assisting device 62, the verification device 30, the verification assisting device 42, and the authenticated person identification device. Has 50 and. The group management device 10 manages a group. The authenticated person device 21 is operated by an authenticated person who belongs to a group managed by the group management device 10. The authentication assist device 62 assists in the act of generating authentication data. The verification device 30 verifies that the user who is trying to authenticate belongs to the group. The verification assist device 42 assists the above verification act. The authenticated person identification device 50 deprives the authenticated person of anonymity in the event of any problem.

Group management device 10 and authenticated person device 21, group management device 10 and verification auxiliary device 42, group management device 10 and authenticated person identification device 50, authenticated person device 21 and verification device 30, certified person device 21 and authentication The auxiliary device 62, the verification device 30, the verification auxiliary device 42, the verification device 42, and the authenticated person identification device 50 are each connected via a network such as the Internet.

When a plurality of groups exist, a group management device exists for each group, and a plurality of authenticated person devices and a verification device may exist in each group. In addition, the encryption key enc_g of the group corresponding to the group is input to the authenticated person device 22. The group decryption key dec_g corresponding to the group encryption key enc_g is input to the authentication auxiliary device 62 and the authenticated person identification device 52. These encryption / decryption keys exist for each group. Further, the authentication shared key ck_g is input to the authentication auxiliary device 62 and the verification auxiliary device 42.

FIG. 16 is a block diagram of the authentication auxiliary device 62, and FIG. 17 is a block diagram of the verification auxiliary device 42. Since the group management device 10, the verification device 30, and the authenticated person identification device 50 are the same as those in the first embodiment, they are not shown. Further, since the authenticated person device 21 is the same as that of the second embodiment, the illustration is omitted.

As shown in FIG. 16, the authentication assist device 62 receives the authentication assist request and the decryption key of the group, the decryption unit 62-1 that decrypts the encrypted text, and the signature that receives the member list and verifies the signature. It has a verification unit 62-2 and a message authenticator generation unit 62-3 that receives a shared key for authentication and attaches a message authenticator to the encrypted text.

As shown in FIG. 17, the verification auxiliary device 42 has a message authenticator verification unit 42-1 that receives the verification auxiliary request and verifies the message authenticator attached to the ciphertext included in the verification auxiliary request.

Since the pre-processing (admission registration process) in the present embodiment is the same as the pre-processing (admission registration process) in the first embodiment, the description thereof will be omitted.

The flow of the authentication process will be described with reference to FIGS. 18 and 19. Here, as an example, it is assumed that the user U having the signature key sk_u and the verification key vk_u has completed registration, and (ID_u, (sk_u, vk_u)) is stored in the ID / key pair storage device 21-2. explain.

First, the authentication request unit 21-3 of the authenticated person device 21 sends an authentication request req_a to the verification device 30 (step 501). Upon receiving the authentication request req_a, the challenge generator 30-1 sends a random message, the challenge nonce, to the authenticated person device 21 (step 502). Upon receiving the challenge nonce, the signature generator 21-4 uses the sk_u stored in the ID / key pair storage device 21-2 to generate the signature σ of the user U for the challenge nonce (step 503). Next, the authentication auxiliary request unit 21-5 that has received the group encryption key enc_g encrypts the ID_u || σ and generates the ciphertext C. Further, the authentication auxiliary request data req_h including the ciphertext C is transmitted to the authentication auxiliary device 62 (step 504). Upon receiving the authentication auxiliary request data req_h and the group decryption key dec_g, the decryption unit 62-1 decrypts the ciphertext C contained in the authentication auxiliary request data req_h and decrypts the decrypted data. Parse with ID || σ (step 505). Next, the signature verification unit 62-2, which has received the member list list stored in the member registration information storage device 10-2 of the group management device 10, confirms whether the ID is described in the member list list. If the ID is listed in the member list, verify σ using the verification key vk corresponding to the ID (step 506). If the ID is not listed in the member list, or if the verification result of σ is not accepted, the subsequent operation is stopped. If the ID is listed in the member list and σ is accepted using the verification key vk corresponding to the ID, the message authenticator generator 62-3 that received the authentication shared key ck_g sends the ciphertext. Generate a C message authenticator MAC_C. In addition, (C, The authentication auxiliary data ans_h including MAC_C) is transmitted to the authenticated person device 21 (step 507). Upon receiving the authentication auxiliary data ans_h, the unlinkable authentication data generator 21-6 transmits an unlinkable authentication data response including (C, MAC_C) included in the authentication auxiliary data ans_h to the verification device 30 (step 508). Upon receiving the unlinkable authentication data response, the verification auxiliary request unit 30-2 sends the verification auxiliary request data req_v including (C, MAC_C) included in the unlinkable authentication data response to the verification auxiliary device 42 (step 509). The message authenticator verification unit 42-1 that received the verification auxiliary request data req_v and the authentication shared key ck_g is included in the verification auxiliary request data req_v (C, Verify MAC_C). The verification result (accepted or rejected) is transmitted to the verification device 30 as verification auxiliary data ans_v (step 510). Upon receiving the verification auxiliary data ans_v, the verification unit 30-3 generates and outputs the authentication result result. However, if the verification auxiliary data ans_v is accepted, the verification result result is the authentication success, and if the verification auxiliary data ans_v is not accepted, the verification result result is the authentication failure. Further, the unlinkable authentication data response that has been successfully authenticated is stored in the unlinkable authentication data storage device 30-4 (step 511). However, the unlinkable authentication data for which authentication has failed may also be stored in the unlinkable authentication data storage device 30-4. Since the process of identifying the person to be authenticated from the unlinkable authentication data is the same as that of the first embodiment, the description thereof will be omitted.

The following configuration is possible as a modification of the third embodiment. The authenticated person device 21 receives the encryption key of the group, generates an encryption text, and sends the authentication assist request data to the authentication assist device 61. The authentication assist request unit 21-5 and the authentication assist device 61 assist the authentication. It has at least an unlinkable authentication data generator 21-6 that receives data and generates unlinkable authentication data. The verification device 30 outputs verification auxiliary data to the verification auxiliary device 40 from the verification auxiliary request unit 30-2 that outputs a verification auxiliary request requesting the verification auxiliary action and the verification auxiliary device 40 that responds to the verification auxiliary request. It also has at least a verification unit 30-3 that receives and inputs unlinkable authentication data from the subject device 20 and outputs the verification result. The authenticated person identification device 50 has at least the authenticated person identification unit 50-2 for inputting the unlinkable authentication data and the private key of the group and identifying the authenticated person.

[Specific example 1] This specific example is an example in which the anonymous authentication system according to the first embodiment is realized by using a public key cryptosystem and a digital signature system.

As a public key cryptosystem used in the present invention, for example, Reference: R. Cramer and V. Shoup. "Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack" In Advances in Cryptology-Crypto'98, pp. The public key cryptography described in 13-25, 1998. (Reference 1) (hereinafter referred to as Cramer-Shoup cryptography) can be used. Further, as an electronic signature method used in the present invention, reference: R. Cramer and V. Shoup. "Signature Schemes Based on the Strong RSA Assumption". Use the electronic signature method described in ACM Transactions on Information and System Security (ACM TISSEC), 3 (3), pp. 161-185, 2000. (Reference 2) (hereinafter referred to as the Cramer-Shoup signature method). Can be done. Further, in the present invention, it is possible to mathematically prove the security that not only the Cramer-Shoup encryption method described in Reference 1 but also the RSA-OAEP encryption method, for example, does not leak any information about the message from the cipher statement. As long as it is a public key cryptosystem, it may be another public key cryptosystem. RSA-OAEP cryptography is described in: R. Rivest, A. Shamir and L. Adleman. "A Method for Obtaining Digital Signatures and Public-Key" Cryptosystems. Communications of the ACM, 21 (2), pp. The RSA cryptosystem described in 120-126, 1978. (Reference 3) and Reference: M. Bellare and P. Rogaway. "Optimal Asymmetric Encryption --How to Encrypt with RSA" In Advancesin Cryptology-Eurocrypt '94, pp. It is a public key cryptosystem based on the prime factorization problem that combines Optimal Asymmetric Encryption Padding (OAEP) described in 92-111, Springer-Verlag, 1994. (Reference 4). Similarly, not only the Cramer-Shoup signature method described in Reference 2, but also the signature data accepted by a certain verification key, such as the Fiat-Shamir signature method, is generated without knowing the signature key corresponding to the verification key. Other electronic signature methods may be used as long as the electronic signature method can be mathematically proved to be unsafe. The Fiat-Shamir signature method is described in: Fiat, A., and A. Shamir, "How to prove yourself: Practival solutions to identification and signature problems" "Proceedings of CRYPTO '86, LNCS 263, pp. The signature method described in 186-197, Springer-Verlag, 1987. (Reference 5) assumes the existence of an ideal hash function called a random oracle, and further mathematically assumes the factorization assumption. It is an electronic signature method that can prove the security by setting.

First, the Cramer-Shoup encryption method will be described. The Cramer-Shoup cryptosystem is a public key cryptosystem that can prove its security by making mathematical assumptions called DDH assumptions. Cramer-Shoup cryptography consists of three components: key setup, encryption, and decryption.

Here, Bob sends a message to Alice as an example.

First, let us explain the key setup. Alice generates a cyclic group G of order q and randomly selects two different generators, g_1 and g_2. In addition, Alice randomly selects six values x_1, x_2, y_1, y_2, z_1, z_2 from the remainder group modulo the prime number q (hereinafter referred to as Z_ {q}). Next, Alice c = Calculate g_1 ^ {x_1} g_2 ^ {x_2}, d = g_1 ^ {y_1} g_2 ^ {y_2}, h = g_1 ^ {z_1} g_2 ^ {z_2}. Alice also chooses a hash function H that is hard to collide with. The hash function H is a hash function from three G elements to Z_ {q}. At this time, Alice's encryption key is (G, g_1, g_2, (c, d, h), H). The decryption key of Alice is (x_1, x_2, y_1, y_2, z_1, z_2). Alice reveals the encryption key, and Bob receives Alice's encryption key.

Next, the encryption process will be described. Here, it is assumed that Bob sends a message to Alice by encrypting the original m of the cyclic group G. Bob chooses a random value k from Z_ {q}. Furthermore, u_1 = g_1 ^ {k}, u_2 = g_2 ^ {k}, e = h ^ {k} m, α = H (u_1, u_2, e), v = c ^ {k} d ^ {k Calculate α}. Bob sends (u_1, u_2, e, v) as a ciphertext to Alice.

Next, the decoding process will be described. Alice calculates α = H (u_1, u_2, e) and confirms that v = u_1 ^ {x_1 + α y_1} u_2 ^ {x_2 + α y_2} holds. If the equation does not hold, it is assumed that an undecryptable ciphertext has been sent, and the subsequent processing is stopped. If the equation holds, Alice calculates m = e / (u_1 ^ {z_1} · u_2 ^ {z_2}) and gets the message m.

Next, the Cramer-Shoup signature will be described. The Cramer-Shoup signature method is an electronic signature method that can prove its security by making mathematical assumptions called the Strong RSA Assumption. Cramer-Shoup signatures consist of three components: key setup, signature generation, and signature verification.

First, the key setup will be described. Choose two different security parameters k, k'and randomly choose the k-bit primes p, q. At this time, the prime numbers p and q are selected so as to satisfy p = 2p'+ 1 and q = 2q' + 1 with respect to the prime numbers p'and q'. Next, calculate n = p · q. Hereafter, for law n, the set of a that satisfies x ^ {2} a (mod n) is expressed as QR (n). Next, select two random elements h and x from QR (n). In addition, choose the prime number e'of the (k'+ 1) bits. Also, select the hash function H', which is difficult to collide with. The hash function H'is a hash function from a set of binary series of arbitrary length to a set of binary series of k'+ 1 bit length. At this time, the verification key is ((n, h, x, e'), H') and is open to the public. The signing key corresponding to the verification key is (p, q).

Next, the signature generation process will be described. Here, the message m is signed. The signer first calculates H'(m). Next, a prime number e of k'+ 1 bits different from e'and an element y'of QR (n) are randomly selected, and y'^ {e'} = x' h ^ {H'(m)} Calculate x'that satisfies mod n. Similarly, calculate y that satisfies y ^ {e} = x · h ^ {H'(x')} mod n. Let the signature data be (e, y, y').

Next, the signature verification process will be described. The verifier first verifies that e is a k'+ 1-bit prime number different from e'. Next, calculate x'= (y') ^ {e'} h ^ {-H'(m)}, and x = y ^ {e} h ^ {-H'(x')} Confirm that it holds. If the equal sign is established, the acceptance is output, and if the equal sign is not established, the rejection is output.

Next, the operation of carrying out the present invention will be described with reference to a specific example. This specific example is an example in which the anonymous authentication system according to the first embodiment is implemented by using the Cramer-Shoup encryption method and the Cramer-Shoup signature method. Here, as an example, it is assumed that the Cramer-Shoup encryption key enc_g = (G, g_1, g_2, (c_g, d_g, h_g), H_g) is disclosed as the group encryption key enc_g. Also, set the corresponding decryption key dec_g to dec_g = (x_ {g, 1}, x_ {g, 2}, y_ {g, 1}, y_ {g, 2}, z_ {g, 1}, z_ {g, 2}). In addition, user U trying to join the group has a Cramer-Shoup signature signing key sk_u = (p_u, q_u) and a corresponding validation key vk_u = ((n_u, h_u, x_u, e'_u), H'_u). Explain as having.

First, the pre-processing (membership registration process) at the time of authentication will be described. User U inputs the signature key / verification key pair (sk_u, vk_u) into the authenticated person device 20. Upon receiving the verification key vk_u, the registration request unit 20-1 sends a registration request req_r to the group management device 10. At this time, the registration request req_r contains the verification key vk_u of user U and personal information necessary for registration such as address, name, and age. Upon receiving the registration request req_r, the registration processing unit 10-1 issues a unique ID ID_u to the user U and sends the ID_u to the authenticated person device 20. However, if there are some conditions (gender restriction, age restriction, double registration prohibition, etc.) in the registration, the registration processing department 10-1 will examine according to the registration request req_r, and the registration request from the user U who does not meet the conditions If so, the non-registration may be sent to the authenticated person device 20. If the user cannot be registered, the subsequent communication with the user is stopped. The group management device 10 receives the member list List from the member registration information storage device 10-2, and (ID_u, (req_r) is added to the member list List, and the updated member list List is stored in the member registration information storage device 10-2. The authenticated person device 20 that has received the ID_u stores (ID_u, (sk_u, vk_u)) in the ID / key pair storage device 20-2.

Next, the flow of the authentication process will be described. Here, as an example, it is assumed that the user U having the signature key sk_u and the verification key vk_u has completed registration, and (ID_u, (sk_u, vk_u)) is stored in the ID / key pair storage device 20-2. explain.

First, the authentication request unit 20-3 of the authenticated person device 20 sends an authentication request req_a to the verification device 30. The authentication request req_a may be a fixed phrase defined by the system. Upon receiving the authentication request req_a, the challenge generator 30-1 randomly selects a nonce and sends the nonce to the authenticated person device 20. Upon receiving the challenge nonce, the signature generator 20-4 calculates H'_u (nonce) using the sk_u stored in the ID / key pair storage device 20-2. Next, randomly select a k'+ 1-bit prime number e different from e'_u and the element y'of QR (n_u), and y'^ {e'_u} = x' h_u ^ {H'_u ( nonce)} mod Calculate x'_u that satisfies n_u. Similarly, calculate y that satisfies y_u ^ {e} = x_u · h_u ^ {H'_u (x')} mod n_u. Let the signature data be σ = (e, y, y'). Next, the group encryption key enc_g = (G, g_1, g_2, (c_g, d_g,) Upon receiving h_g) and H_g), the unlinkable authentication data generator 20-5 selects a random value k from Z_ {q}. Furthermore, u_1 = g_1 ^ {k}, u_2 = g_2 ^ {k}, e = h_g ^ {k} (ID_u || σ), α = H_g (u_1, u_2, e), v = c_g ^ {k } d_g ^ {k α} is calculated. Let the ciphertext C = (u_1, u_2, e, v). In addition, the unlinkable authentication data response = (nonce, C) is sent to the verification device 30.

Upon receiving the unlinkable authentication data response, the verification auxiliary request unit 30-2 transmits the verification auxiliary request data req_v = response including the ciphertext C to the verification auxiliary device 40. Verification assistance request data req_v and group decryption key dec_g = (x_ {g, 1}, x_ {g, 2}, y_ {g, 1}, y_ {g, 2}, z_ {g, 1}, z_ { Upon receiving g, 2}), the authentication data decryption unit 40-1 receives α = H_g (u_1, u_2, from the ciphertext C = (u_1, u_2, e, v) included in the verification auxiliary request data req_v. e) is calculated, and v = u_1 ^ {x_ {g, 1} + α y_ {g, 1}} u_2 ^ {x_ {g, 2} + α y_ {g, 2}} is established. Make sure that. If the equation does not hold, it is assumed that an undecryptable ciphertext has been sent, and the subsequent processing is stopped. If the equation holds, calculate m = e / (u_1 ^ {z_ {g, 1}} · u_2 ^ {z_ {g, 2}}) and get the message m. In addition, the resulting message m is parsed as ID || σ. That is, m is decomposed into ID, σ = (e, y, y').

Next, the signature verification unit 40-2, which has received the member list list stored in the member registration information storage device 10-2 of the group management device 10, confirms whether the ID is described in the member list list. If it is not described, the fact that it is not accepted is transmitted to the verification device 30 as verification auxiliary data ans_v. If so, the validation key corresponding to the ID vk = ((n, h, x, e'), Using H'), first check that e is a k'+ 1-bit prime number different from e'. Next, calculate x'= (y') ^ {e'} h ^ {-H'(nonce)}, and x = (y) ^ {e} h ^ {-H'(x') } Confirm that it holds. If the equal sign is established, it is accepted, and if the equal sign is not established, it is rejected. The signature verification result (accepted or rejected) is transmitted to the verification device 30 as verification auxiliary data ans_v. Upon receiving the verification auxiliary data ans_v, the verification unit 30-3 outputs the authentication result result as authentication success if the verification auxiliary data ans_v is accepted. If the verification auxiliary data ans_v is not accepted, the authentication result result is output as an authentication failure. Furthermore, the unlinkable authentication data response for which authentication was successful is stored in the unlinkable authentication data storage device 30-4. However, the unlinkable authentication data for which authentication has failed may also be stored in the unlinkable authentication data storage device 30-4.

Next, the process of identifying the authenticated person from the unlinkable authentication data will be described. Here, as an example, the ID of the authenticated person who generated the unlinkable authentication data response_i stored in the unlinkable authentication data storage device 30-4 provided in the verification device 30 will be specified.

First, the authenticated person identification request unit 30-5 of the verification device 30 that has received the unlinkable authentication data response_i = (nonce_i, C_i) stored in the unlinkable authentication data storage device 30-4 req_t the authenticated person identification request data req_t. Send = response_i to the authenticated person device 50. Authenticated person identification request data req_t and group decryption key dec_g = (x_ {g, 1}, x_ {g, 2}, y_ {g, 1}, y_ {g, 2}, z_ {g, 1}, Upon receiving z_ {g, 2}), the authentication data decryption unit 50-1 uses the ciphertext C_i = (u_ {i, 1}, u_ {i, 2}, e_i, included in the authenticated person identification request data req_t. From v_i), α = H_g (u_ {i, 1}, u_ {i, 2}, Calculate e_i) and v = u_ {i, 1} ^ {x_ {g, 1} + α y_ {g, 1}} u_ {i, 2} ^ {x_ {g, 2} + α Confirm that y_ {g, 2}} holds. If the equation does not hold, it is assumed that an undecryptable ciphertext has been sent, and the subsequent processing is stopped. If the equation holds, calculate m_i = e_i / (u_ {i, 1} ^ {z_ {g, 1}} u_ {i, 2} ^ {z_ {g, 2}}) and message Get m_i. In addition, the resulting message m_i is parsed as ID_i || σ_i. That is, m_i is decomposed into ID_i, σ_i = (e_i, y_i, y'_i). Next, the authenticated person identification unit 50-2 that has received the member list list stored in the member registration information storage device 10-2 provided in the group management device 10 has ID_i listed in the member list list. To confirm. If ID_i is listed in the member list, the validation key corresponding to ID_i vk_i = ((n_i, h_i, x_i, e'_i), Using H'_i), first make sure that e_i is a k'+ 1-bit prime number different from e'_i. Next, calculate x'_i = (y'_i) ^ {e'_i} h_i ^ {-H'_i (nonce_i)} and x_i = (y_i) ^ {e_i} h_i ^ {-H' Confirm that _i (x'_i)} holds. If the equal sign is established, it is accepted, and if the equal sign is not established, it is rejected. If the verification result is accepted, the unlinkable authentication data response_i outputs that it is the authentication data created by the user with ID ID_i. If ID_i is not listed in the member list or the verification result of σ_i is not accepted, the unlinkable authentication data response_i requested to identify the authenticated person is output as unaccepted authentication data.

[Specific example 2] This specific example is a specific example when the anonymous authentication system according to the second embodiment is implemented by using the Cramer-Shoup encryption method and the Cramer-Shoup signature method.

Here, it is assumed that the Cramer-Shoup encryption key enc_g = (G, g_1, g_2, (c_g, d_g, h_g), H_g) is disclosed as the group encryption key enc_g. Also, set the corresponding decryption key dec_g to dec_g = (x_ {g, 1}, x_ {g, 2}, y_ {g, 1}, y_ {g, 2}, z_ {g, 1}, z_ {g, 2}). The group signing key sk_g should have the Cramer-Shoup signing key sk_g = (p_g, q_g) and the corresponding verification key vk_g = ((n_g, h_g, x_g, e'_g), H'_g). .. In addition, user U trying to join the group has a Cramer-Shoup signature signing key sk_u = (p_u, q_u) and a corresponding validation key vk_u = ((n_u, h_u, x_u, e'_u), H'_u). Explain as having.

Since the pre-processing (admission registration process) in this specific example is the same as the pre-processing (admission registration process) in the first specific example, the description thereof will be omitted.

The flow of the authentication process will be described.

First, the authentication request unit 21-3 of the authenticated person device 21 sends an authentication request req_a to the verification device 31. The authentication request req_a may be a fixed phrase defined by the system. Upon receiving the authentication request req_a, the challenge generator 31-1 randomly selects a nonce and sends the nonce to the authenticated person device 21. Upon receiving the challenge nonce, the signature generator 21-4 first calculates H'_u (nonce) using sk_u stored in the ID / key pair storage device 21-2. Next, randomly select a k'+ 1-bit prime number e different from e'_u and the element y'of QR (n_u), and y'^ {e'_u} = x' h_u ^ {H'_u ( nonce)} mod Calculate x'_u that satisfies n_u. Similarly, calculate y that satisfies y_u ^ {e} = x_u · h_u ^ {H'_u (x')} mod n_u. Let the signature data be σ = (e, y, y'). Then the group encryption key enc_g = (G, g_1, g_2, (c_g,) Upon receiving d_g, h_g), H_g), the authentication assistance request unit 21-5 selects a random value k from Z_ {q}. Furthermore, u_1 = g_1 ^ {k}, u_2 = g_2 ^ {k}, e = h_g ^ {k} (ID_u || σ), α = H_g (u_1, u_2, e), v = c_g ^ {k } d_g ^ {k α} is calculated. Let the ciphertext C = (u_1, u_2, e, v). Further, the authentication assistance request data req_h = (nonce, C) is transmitted to the authentication assistance device 61.

Authentication assistance request data req_h and group decryption key dec_g = (x_ {g, 1}, x_ {g, 2}, y_ {g, 1}, y_ {g, 2}, z_ {g, 1}, z_ { Upon receiving g, 2}), the decryption unit 61-1 calculates α = H_g (u_1, u_2, e) from the ciphertext C included in the authentication assistance request data req_h, and v = u_1 ^ {x_ {g , 1} + α y_ {g, 1}} u_2 ^ {x_ {g, 2} + α y_ {g, 2}} is confirmed. If the equation does not hold, it is assumed that an undecryptable ciphertext has been sent, and the subsequent processing is stopped. If the equation holds, calculate m = e / (u_1 ^ {z_ {g, 1}} · u_2 ^ {z_ {g, 2}}) and get the message m. In addition, the resulting message m is parsed as ID || σ. That is, m is decomposed into ID, σ = (e, y, y').

Next, the signature verification unit 61-2, which has received the member list list stored in the member registration information storage device 10-2 of the group management device 10, confirms whether the ID is described in the member list list. If the ID is listed in the member list, use the validation key vk corresponding to the ID to first verify that e is a k'+ 1-bit prime number different from e'. Next, calculate x'= (y') ^ {e'} h ^ {-H'(nonce)}, and x = (y) ^ {e} h ^ {-H'(x') } Confirm that it holds. If the equal sign is established, it is accepted, and if the equal sign is not established, it is rejected. If the ID is not listed in the member list, or if the verification result of σ is not accepted, the subsequent operation is stopped. If the ID is listed in the member list and σ is accepted using the validation key vk corresponding to the ID, then the group signing key sk_g = (p_g,, The signature generator 61-3 of the group that received q_g) first calculates H'_g (nonce || C) using the signature key sk_g = (p_g, q_g) of the group. Next, randomly select a k'+ 1-bit prime number e_g different from e'_g and the element y'_g of QR (n_g), and y'_g ^ {e'_g} = x' h_g ^ {H' _g (nonce || C)} mod Calculate x'_g that satisfies n_g. Similarly, calculate y_g that satisfies y_g ^ {e_g} = x_g · h_g ^ {H'_g (x')} mod n_u. Let the signature data be σ_g = (e_g, y_g, y'_g). Further, the authentication auxiliary data ans_h = (nonce, C, σ_g) is transmitted to the authenticated person device 21. Upon receiving the authentication auxiliary data ans_h, the unlinkable authentication data generation unit 21-6 transmits the unlinkable authentication data response = ans_h to the verification device 31.

Upon receiving the unlinkable authentication data response and the group verification key vk_g, the verification unit 31-2 uses the verification key vk_g = ((n_g, h_g, x_g, e'_g), H'_g), and e_g is first e_g. Make sure it is a k'+1 bit prime different from'_g. Next, calculate x'_g = (y'_g) ^ {e'_g} h_g ^ {-H'_g (nonce || C)} and x_g = (y_g) ^ {e_g} h_g ^ { Confirm that -H'_g (x'_g)} holds. If the equal sign is established, it is accepted, and if the equal sign is not established, it is rejected. If the verification result is not accepted, the authentication result result is output as an authentication failure. However, the unlinkable authentication data for which authentication has failed may also be stored in the unlinkable authentication data storage device 31-3.

Since the process of identifying the person to be authenticated from the unlinkable authentication data is the same as that of the first embodiment, the description thereof will be omitted.

[Third specific example] This specific example is a specific example of the case where the anonymous authentication system according to the third embodiment is realized by using the public key cryptosystem, the electronic signature system, and the message authentication method.

The message authentication method is a guarantee of the identity of the message, and guarantees that the message has not been changed by a vandalism using a computer virus, unauthorized intrusion, or the like. In this specific example, the Cramer-Shoup encryption method is used as the public key cryptography used in the present invention, the Cramer-Shoup signature method is used as the electronic signature method, and the message authentication method is used as the message authentication method. , Hugo Krawczyk, "Keying Hash Functions for Message Authentication", In Advances in Cryptology --Crypto'96, LNCS 1109, The message authentication method (hereinafter referred to as HMAC) described in 1996. (Reference 6) can be used. The hash function H is used for HMAC. As the hash function, any hash function such as MD5, SHA-1, SHA-224, or SHA-256 can be used. Given a private key of K, the HMAC for message m is defined as: HMAC_ {K} (m) = h ((K XOR opad) || h ((K + ipad) || m)). Where XOR represents the bit-by-bit exclusive OR. That is, when A = 1001 and B = 1100, (A XOR B) = 0101. In addition, opad and ipad are constants whose length is the block length size of the hash function, and are defined as opad = 0x5c5c5c ... 5c and ipad = 0x363636 ... 36, respectively. For example, when using a hash function with a block length of 256 bits, opad and ipad are 32 consecutive values of 0x5c and 0x36, respectively. Hereafter, HMAC_ {K} (m) is called the MAC value of m.

Next, an operation for carrying out the present invention will be described with reference to specific examples. This specific example is a specific example in which the anonymous authentication system according to the third embodiment of the present invention is implemented and realized by using the Cramer-Shoup encryption method, the Cramer-Shoup signature method, and HMAC. Here, as an example, it is assumed that the Cramer-Shoup encryption key enc_g = (G, g_1, g_2, (c_g, d_g, h_g), H_g) is disclosed as the group encryption key enc_g. Also, set the corresponding decryption key dec_g to dec_g = (x_ {g, 1}, x_ {g, 2}, y_ {g, 1}, y_ {g, 2}, z_ {g, 1}, z_ {g, 2}). In addition, user U trying to join the group has a Cramer-Shoup signature signing key sk_u = (p_u, q_u) and a corresponding validation key vk_u = ((n_u, h_u, x_u, e'_u), Explain as having H'_u). In addition, the authentication auxiliary device 62 and the verification auxiliary device 42 share the HMAC private key with the authentication shared key ck_g = K.

Since the pre-processing (admission registration process) in this specific example is the same as the pre-processing (admission registration process) in the first specific example, the description thereof will be omitted.

The flow of the authentication process will be described. First, the authentication request unit 21-3 of the authenticated person device 21 sends an authentication request req_a to the verification device 31. The authentication request req_a may be a fixed phrase defined by the system. Upon receiving the authentication request req_a, the challenge generator 30-1 randomly selects a nonce and sends the nonce to the authenticated person device 21. Upon receiving the challenge nonce, the signature generator 21-4 calculates H'_u (nonce) using the sk_u stored in the ID / key pair storage device 21-2. Next, randomly select a k'+ 1-bit prime number e different from e'_u and the element y'of QR (n_u), and y'^ {e'_u} = x' h_u ^ {H'_u ( nonce)} mod Calculate x'_u that satisfies n_u. Similarly, calculate y that satisfies y_u ^ {e} = x_u · h_u ^ {H'_u (x')} mod n_u. Let the signature data be σ = (e, y, y'). Then the group encryption key enc_g = (G, g_1, Upon receiving g_2, (c_g, d_g, h_g), H_g), the unlinkable authentication data generator 21-5 selects a random value k from Z_ {q}. Furthermore, u_1 = g_1 ^ {k}, u_2 = g_2 ^ {k}, e = h_g ^ {k} (ID_u || σ), α = H_g (u_1, u_2, e), v = c_g ^ {k } d_g ^ {k α} is calculated. Let the ciphertext C = (u_1, u_2, e, v). Further, the unlinkable authentication data response = (nonce, C) is transmitted to the authentication assist device 62.

Authentication assistance request data req_h and group decryption key dec_g = (x_ {g, 1}, x_ {g, 2}, y_ {g, 1}, y_ {g, 2}, z_ {g, 1}, z_ { Upon receiving g, 2}), the decryption unit 62-1 calculates α = H_g (u_1, u_2, e) from the ciphertext C included in the authentication assistance request data req_h, and v = u_1 ^ {x_ {g , 1} + α y_ {g, 1}} u_2 ^ {x_ {g, 2} + α y_ {g, 2}} is confirmed. If you have not been satisfied is if equality, restored as No. non-encrypted text has been sent, to stop the subsequent processing. If the equation holds, calculate m = e / (u_1 ^ {z_ {g, 1}} · u_2 ^ {z_ {g, 2}}) and get the message m. In addition, the resulting message m is parsed as ID || σ. That is, m is decomposed into ID, σ = (e, y, y').

Next, the signature verification unit 62-2, which has received the member list list stored in the member registration information storage device 10-2 of the group management device 10, confirms whether the ID is described in the member list list. If the ID is listed in the member list, use the validation key vk corresponding to the ID to first verify that e is a k'+ 1-bit prime number different from e'. Next, calculate x'= (y') ^ {e'} h ^ {-H'(nonce)}, and x = (y) ^ {e} h ^ {-H'(x') } Confirm that it holds. If the equal sign is established, it is accepted, and if the equal sign is not established, it is rejected. If the ID is not listed in the member list, or if the verification result of σ is not accepted, the subsequent operation is stopped. If the ID is listed in the member list and σ is accepted using the verification key vk corresponding to the ID, the message authenticator generator 62-3 that received the shared authentication key ck_g = (K). Is a shared key for authentication Use ck_g = (K) to calculate the MAC value τ = HMAC_ {K} (nonce || C) for nonce || C. In addition, authentication auxiliary data ans_h = (nonce, C, τ) is transmitted to the authenticated person device 21. Upon receiving the authentication auxiliary data ans_h, the unlinkable authentication data generation unit 21-6 transmits the unlinkable authentication data response = ans_h to the verification device 30. Upon receiving the unlinkable authentication data response, the verification auxiliary request unit 30-2 transmits the verification auxiliary request data req_v = response to the verification auxiliary device 42. The message authenticator verification unit 42-1 that received the verification auxiliary request data req_v and the authentication shared key ck_g = (K) uses the authentication shared key ck_g = (K) and uses the authentication shared key ck_g = (K) to set the MAC value of nonce || C to τ' Calculate = HMAC_ {K} (nonce || C). Confirm that τ'= τ. That is, if τ'= τ, the verification auxiliary data ans_v is accepted, and if τ' τ, the verification auxiliary data ans_v is rejected and transmitted to the verification device 30. Upon receiving the verification auxiliary data ans_v, the verification unit 30-3 confirms that the authentication result result is successful if the verification auxiliary data ans_v is accepted, and the verification auxiliary data. If ans_v is not accepted, the authentication result result is output as an authentication failure. Furthermore, the unlinkable authentication data response that has been successfully authenticated is stored in the unlinkable authentication data storage device 30-4. However, the unlinkable authentication data for which authentication has failed may also be stored in the unlinkable authentication data storage device 30-4. Since the process of identifying the person to be authenticated from the unlinkable authentication data is the same as that of the first specific example, the description thereof will be omitted.

[Fourth specific example] In the first embodiment, steps 201 and 202 can be omitted and any message m chosen by the subject device can be used instead of the challenge nonce. In this case, the unlinkable authentication data response is the unlinkable signature data. The unlinkable signature data can only be transmitted to the verification device that does not have the group decryption key dec_g as an input, but it is only the signature of the member belonging to the group, but the ID of the member signed by the authenticated person identification device must be specified. Is possible. In addition, it has the property that it is not possible to distinguish whether they are signed by the same member or by different members from the two unlinkable signature data. Similarly, steps 401 and 402 in the second embodiment and steps 501 and 502 in the third embodiment can be omitted and any message m chosen by the subject device can be used instead of the challenge nonce. Is.

[Fifth specific example] In this embodiment, the business form of the anonymous authentication system of the present invention will be specifically described by taking the first embodiment as an example.

In the anonymous authentication system shown in FIG. 1, for example, the group management device 10 is operated by a business operator that manages the group (hereinafter, referred to as a group management business operator). The group management operator may be, for example, an Internet service provider. Further, the authenticated person device 20 is operated by, for example, a user. The user may be, for example, a member of an Internet service provider. The verification device 30 is operated by, for example, a business operator (hereinafter referred to as a service provider) that confirms the user's registration and provides the service. The service provider may be, for example, an access point in a public wireless LAN service. The verification auxiliary device 40 is operated by, for example, a business operator (hereinafter referred to as a verification auxiliary business operator) that is connected to the verification device 30 via the Internet or the like and responds to a verification assistance request from the verification device 30. The verification assistance provider may be, for example, the online verification department of an Internet service provider. The authenticated person identification device 50 is operated, for example, by a business operator (hereinafter referred to as a certified person specific business operator) that deprives the authenticated person of anonymity as necessary. The person to be authenticated may be, for example, a billing department of an Internet service provider.

In such a business form, the group management company first determines the group encryption key enc_g and the corresponding group decryption key dec_g, and gives the group encryption key enc_g together with information about the group, for example, a newspaper. Publicly known on the website. In addition, the group decryption key dec_g is sent to the verification assistance business operator and the authenticated person specific business operator. Next, the user wants to join a group managed by a group management company. The group management company confirms whether the users who wish to join the group meet the conditions for joining the group (age, etc.), and performs the membership procedure for the users who meet the conditions (for example, issuing a membership card, etc.) Send to user).

Next, the user inputs the group encryption key enc_g into the authenticated person device 20 and causes the verification device 30 to send the unlinkable authentication data (for example, when using the wireless LAN service, as a member of the Internet service provider. We will send you authentication data to prove that you have it). Upon receiving the unlinkable authentication data, the verification device 30 sends a verification assistance request to the verification assistance device 40, obtains the verification assistance data, performs verification, and outputs the authentication result (for example, the access point allows the user to use the Internet). Confirm that you are a member of the service provider and provide wireless LAN service). Further, the verification business operator causes the authenticated person identification device 50 to transmit an authenticated person identification request including unlinkable authentication data of each user. The person to be authenticated receives the unlinkable authentication data transmitted in this way and identifies the person to be authenticated. For example, by identifying a user who has used the wireless LAN service, billing is performed according to the usage status.

The group management business operator, the verification assistance business operator, and the certified person specific business operator may be different business operators or the same business operator.

In the above, a specific example of the business form of the anonymous authentication system according to the first embodiment is shown, but the same business form is possible in other embodiments. In the case of the anonymous authentication system according to the second or third embodiment, for example, the authentication assisting device is operated by a business operator that assists authentication (hereinafter, referred to as an authentication assisting business operator). The group management business operator and the certification assistance business operator may be the same business operator.

The function of each device is such that a program for realizing the function is recorded on a computer-readable recording medium, and the program recorded on the recording medium is read by the computer and executed. Good. The computer-readable recording medium refers to a storage device such as a flexible disk, a magneto-optical disk, a recording medium such as a CD-ROM, or a hard disk device built in a computer system. Furthermore, the computer-readable recording medium is one that dynamically holds the program for a short period of time (transmission medium or transmission wave), as in the case of transmitting a program via the Internet, in the computer that is the server in that case. Includes those that hold the program for a certain period of time, such as the volatile memory of.

Although the preferred embodiments of the present invention have been described above using specific terms, such descriptions are for illustration purposes only, and various modifications and modifications can be made without departing from the scope of the following claims. Should be understood.

This application claims priority on the basis of Japanese Application Japanese Patent Application No. 2007-137852 filed on May 24, 2007 and incorporates all of its disclosures herein. [Industrial applicability] The present invention can be suitably applied to anonymous authentication in which a user's ID is kept secret and authenticated via a communication network.