JP2015185990A - One-to-multiple authentication system, authentication method, and authentication program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To efficiently perform one-to-multiple authentication between input information and encrypted encryption authentication information.SOLUTION: A one-to-multiple authentication system includes: a storage unit for storing, for each of a plurality of users, encryption authentication information obtained by encrypting, by using key information and using a specific rule, authentication information used for user authentication; a comparison unit for comparing, on the basis of the specific rule while keeping a state in which the authentication information is encrypted, input information input as an authentication target with a plurality of pieces of encryption authentication information stored in the storage unit; an identification unit for identifying, on the basis of a result of the comparison by the comparison unit, encryption authentication information satisfying a condition determined on the basis of a characteristic of the key information; and a determination unit for determining the propriety of authentication for the authentication target on the basis of the encryption authentication information identified by the identification unit, the input information, and the key information.

Description

  The present invention relates to a one-to-many authentication technique.

  There is an authentication technique for authenticating a user using a network. In an authentication apparatus that performs authentication, registration information to be verified at the time of authentication, such as password information and biometric information, is registered in advance, and at the time of authentication, the registration information and input information are compared. Then, based on the comparison result, the success or failure of the authentication is determined. Such an authentication technique is used for, for example, an authentication function in a bank system, an authentication function in electronic commerce or electronic payment, and the like.

  In addition to a person, a technique for authenticating a device is also known. For example, there is device authentication using a function called a PUF (Physical Unclonable Function) that outputs a device-specific value using physical characteristics of a device that are difficult to replicate.

  Here, there are roughly two types of authentication technologies. A technique called one-to-one authentication and a technique called one-to-many authentication (also called ID-less authentication or one-to-N authentication). In the one-to-one authentication, for example, by receiving a user ID for identifying a user, one registration information associated with the user ID is specified from registration information registered in advance. Then, the input information and one registered information are collated, and the success or failure of the authentication is determined according to the collation result.

  On the other hand, one-to-many authentication does not accept a user ID or the like. Therefore, at the time of authentication, the input information and a plurality of registered information are collated. In the one-to-many authentication, for example, input information and all registration information are collated, and the success or failure of authentication is determined based on the most similar registration information.

  For example, there is an authentication system that performs one-to-many authentication (for example, Patent Document 1). The authentication system is a system that performs personal authentication using a fingerprint. When registering fingerprint feature data, the authentication system gives classification information to the registered fingerprint feature data based on the similarity between the reference data and the fingerprint feature point data. On the other hand, when collating the input fingerprint feature data, classification information of the input fingerprint feature data is generated, and based on the classification information of the input fingerprint feature data, the fingerprint feature data to be verified is limited or prioritized. Search with collation.

JP 2002-297549 A

  For example, security is improved by encrypting fingerprint feature data at the time of registration. When using such fingerprint feature data encrypted, the authentication system cannot efficiently perform one-to-many authentication.

  In one aspect, an object of the present invention is to efficiently perform a one-to-many authentication process in one-to-many authentication between input information and encrypted encrypted authentication information.

  In one embodiment, the one-to-many authentication system stores, for a plurality of users, encrypted authentication information obtained by encrypting authentication information used for user authentication by using a specific rule using key information. Comparing the storage unit, input information input as an authentication target, and a plurality of encrypted authentication information stored in the storage unit based on the specific rule while maintaining the state where the authentication information is encrypted A comparison unit that identifies the encrypted authentication information that meets a condition determined based on the characteristics of the key information based on the comparison result by the comparison unit, and the encrypted authentication information that is identified by the identification unit. And a determination unit for determining success or failure of authentication for the authentication target based on the input information and the key information.

  In the one-to-many authentication between the input information and the encrypted authentication information, the one-to-many authentication process can be efficiently performed.

FIG. 1 is a diagram for explaining registration processing in the authentication system according to the first embodiment. FIG. 2 is a diagram for explaining an authentication process in the authentication system according to the first embodiment. FIG. 3 is a diagram for explaining processing cost reduction. FIG. 4 is a functional block diagram of the terminal device and the authentication device according to the first embodiment. FIG. 5 is a diagram illustrating a data configuration example of the encrypted authentication information management table. FIG. 6 is a process flowchart of the terminal device in the first embodiment. FIG. 7 is a processing flowchart of the authentication apparatus in the first embodiment. FIG. 8 is a flowchart of the collation process in the first embodiment. FIG. 9 is a diagram for explaining registration processing in the authentication system according to the second embodiment. FIG. 10 is a diagram for explaining an authentication process in the authentication system according to the second embodiment. FIG. 11 is a functional block diagram of the management device and the determination device according to the second embodiment. FIG. 12 is a process flowchart of the determination apparatus according to the second embodiment. FIG. 13 is a flowchart of the collation process according to the second embodiment. FIG. 14 is a processing flowchart of the management apparatus according to the second embodiment. FIG. 15 is a diagram for explaining registration processing in the authentication system according to the third embodiment. FIG. 16 is a diagram for explaining an authentication process in the authentication system according to the third embodiment. FIG. 17 is a functional block diagram of the management device and the determination device according to the third embodiment. FIG. 18 is a process flowchart of the determination apparatus according to the third embodiment. FIG. 19 is a flowchart of the collation process according to the third embodiment. FIG. 20 is a processing flowchart of the management apparatus according to the third embodiment. FIG. 21 is a data configuration example of the mask value management table. FIG. 22 is a hardware configuration example of a terminal device, an authentication device, a management device, and a determination device in each embodiment.

  Detailed examples of the present invention will be described below. Note that the following embodiments can be appropriately combined within a range in which the contents of processing do not contradict each other. Embodiments will be described below with reference to the drawings.

[First embodiment]
1 and 2 are diagrams for explaining an authentication system according to the first embodiment. The authentication system in the first embodiment includes a terminal device 1 and an authentication device 2. The terminal device 1 and the authentication device 2 are connected via a network N. The network N is, for example, the Internet.

  The terminal device 1 is a computer that requests authentication from the authentication device 2. The authentication device 2 is a computer that performs one-to-many authentication in response to a request from the terminal device 1. The authentication device 2 includes a server 200 that executes various processes and a database 201 that stores information necessary for authentication.

  FIG. 1 is a diagram for explaining registration processing in the authentication system according to the first embodiment. The registration process is a process for registering authentication information.

  The terminal device 1 accepts input of the user ID “A” of the user to be registered and the authentication information mA to be registered. The user ID is information given systematically in order to identify the user. The authentication information is information that is collated with the input information at the time of one-to-many authentication, and is information generated by an input from the user, such as password information or biometric information. The biological information is iris information, fingerprint information, and vein information, and is extracted from image data obtained by photographing the biological body by a specific algorithm. The terminal device 1 has a reading device for acquiring various types of authentication information.

  Next, the terminal device 1 transmits the user ID “A” and the authentication information mA to the authentication device 2. In the present embodiment, it is desirable that an encrypted communication technique such as Secure Socket Layer (SSL) is applied to communication via the network N.

The authentication device 2 receives the user ID “A” and the authentication information mA. Then, the authentication device 2 generates encrypted authentication information E _K (mA) by encrypting the authentication information mA using the key information K. The key information K has a bit string longer than the bit length of the authentication information mA. In the following description, the authentication information mA is described as 8 bits, and the key information K is also described as 8 bits.

Then, the database 201 stores the user ID “A” and the encrypted authentication information E _K (mA) in association with each other. Hereinafter, the authentication information is described as “mi” unless it is necessary to distinguish between users.

Here, the encryption authentication information E _K (mi) will be described. The encrypted authentication information E _K (mi) is information obtained by encrypting the authentication information mi received from the terminal device 1 using the key information K included in the authentication device 2 according to a specific rule. Any encryption that satisfies the following conditional expression 1 can be applied to this embodiment.

F is a function that outputs a collation result of two pieces of input information (plain text X and plain text Y). E _K is an encryption function using the key information K. If conditional expression 1 is encrypted so that the collation result between plaintexts is reproduced when collation is performed in a state where the two pieces of input information are encrypted with the same key information, this embodiment It is shown that it can be applied.

Hereinafter, it is assumed that F is a function for calculating an exclusive OR of two pieces of input information. Also, E _K is or functions for computing the exclusive OR of the key information K and the input information, a function of the CTR mode of the AES encryption is applicable. Note that a random number generated from the key information K instead of the key information K itself may be used as key information at the time of encryption. The random number is referred to as a mask value RK.

In the present embodiment, encryption is a Vernam cipher is employed, E _K is described as a function for calculating an exclusive OR of the key information K and the input information. That is, the encrypted authentication information E _K (mA) is obtained by an exclusive OR of the authentication information mA and the key information K. When encryption using exclusive OR is employed, the amount of processing calculations in each device can be reduced in the registration process and the authentication process described later. In addition, an increase in the amount of data due to encryption can be prevented.

  FIG. 2 is a diagram for explaining an authentication process in the authentication system according to the first embodiment. The terminal device 1 makes an authentication request to the authentication device 2. Then, the terminal device 1 generates input information m ′ to be input as an authentication target to the authentication device 2 and transmits the input information m ′ to the authentication device 2. The input information m ′ is information generated by input from the user, and is password information or biometric information, for example. The input information m ′ is generated by the same algorithm as the authentication information.

  In the authentication process, the user does not need to input a user ID to the terminal device 1. Therefore, the user ID is not transmitted when the input information m ′ is transmitted from the terminal device to the authentication device 2. As described above, in the authentication process for one-to-one authentication, a user ID is used to specify one piece of information to be verified, but in the authentication process for one-to-N authentication, a user ID is used. Therefore, it is not necessary to input a user ID or the like.

Upon receiving the input information m ′, the authentication device 2 sequentially reads out a plurality of encrypted authentication information E _K (mi) stored in the database 201. Then, the authentication device 2 compares the encrypted authentication information E _K (mi) with the input information m ′. For example, the authentication device 2 performs exclusive OR of the encrypted authentication information E _K (mi) and the input information m ′, and obtains the comparison result E _K (HVi). HVi is an exclusive OR operation result between the authentication information mi and the input information m ′, and indicates a collation result between the authentication information mi and the input information m ′.

It should be noted that the operation result of the exclusive OR of the encrypted authentication information E _K (mi) that is the operation result of the exclusive OR of the key information K and the authentication information mi and the input information m ′ is the authentication information mi and The exclusive OR operation result HVi with the input information m ′ is the same as the exclusive OR operation result with the key information K. Therefore, the comparison result is indicated as E _K (HVi).

For example, the authentication device 2 reads “E _K (mA)” and calculates the comparison result E _K (HVA) by exclusive OR of the input information m ′ and the encrypted authentication information E _K (mA). Here, since the comparison result E _K (HVA) is the information obtained by encrypting the verification information HVA between the authentication information mA and the input information m ′ with the key information K, the comparison result E _K (HVA) is used as the key information. By decrypting using K, the authentication device 2 can acquire a verification result HVA between the authentication information mA and the input information m ′.

  When the authentication device 2 acquires the collation result HVA by decryption, the authentication device 2 determines whether or not the authentication has succeeded, for example, based on whether or not the number of bits indicating 1 is equal to or less than a threshold value d. When the authentication information mA and the input information m ′ indicate different values in the bit-by-bit comparison between the authentication information mA and the input information m ′, the authentication device 2 sets “1” in the verification result HVA. Therefore, the fact that the number of bits indicating “1” in the collation result HVA is equal to or less than the threshold value d means that the similarity between the authentication information mA and the input information m ′ is high. In this case, it can be estimated that the input information m ′ is highly likely to be derived from the user of the authentication information mA. Therefore, the authentication device 2 determines the authentication success, assuming that the user for the input information m ′ is registered in advance.

However, according to the above-described method, the comparison result E _K (HVi) is calculated for the encrypted authentication information E _K (mi) of each registered user, and all the comparison results E _K (HVi) are used as the key information K. Need to be decrypted. Therefore, the processing cost related to decoding is generated by the number of registered users. Therefore, in this embodiment, only the comparison result E _K (HVi) that matches a predetermined condition is decrypted using the key information K.

FIG. 3 is a diagram for explaining processing cost reduction. FIG. 3 shows an outline of processing in the authentication device 2. First, the authentication device 2 performs an exclusive OR of the encrypted authentication information E _K (mi) and the input information m ′, and calculates a comparison result E _K (HVi) for each registered user. Then, the authentication device 2 performs the decryption process using the key information K only for the comparison result E _K (HVi) that satisfies the following conditional expression 2. Conditional expression 2 is determined based on the characteristics of the key information K. Further, when the threshold value d used for determining the success / failure of the authentication is other than 0, the conditional expression 2 is further determined based on the threshold value d used for determining the success / failure of the authentication.

HW (K) is information indicating the characteristics of the key information K, and is the number of bits indicating “1” in the bit string of the key information. For example, when the key information K is 11000011, HW (K) is 4. The threshold d is a value used as a determination threshold in the process of determining authentication success / failure. For example, the threshold value d is set to 5% of the bit length of the authentication information, but is set to “2” in this embodiment. At this time, according to conditional expression 2, when HW (E _K (HVi)) is larger than 2 and smaller than 6, HW (E _K (HVi)) is decrypted with the key information K. HW (E _K (HVi)) is the number of bits indicating “1” in the bit string of the comparison result E _K (HVi).

Here, the derivation of the conditional expression 2 will be described. First, a condition when authentication is determined to be successful is expressed by the following conditional expression 3.

  HDi indicates a hamming distance HDi between the input information m ′ and the authentication information mi. That is, HDi is the number of bits indicating 1 in the matching result HVi between the input information m ′ and the authentication information mi. Conditional expression 3 indicates that the authentication is determined to be successful if the Hamming distance HDi is equal to or less than the threshold value d.

Next, HDi is the number of bits HW (E _K (HVi)) indicating “1” in the bit string of the comparison result E _K (HVi) and the bit indicating “1” in the bit string of the key information K. Since the absolute value of the difference with the number HW (K) is always larger, the following conditional expression 4 is satisfied.

When conditional expression 3 and conditional expression 4 are put together, the following conditional expression 5 is satisfied. Therefore, by expanding the leftmost side and the rightmost side of conditional expression 5, conditional expression 2 is obtained.

For example, when the encrypted authentication information E _K (mA) is 11000010 and the input information m ′ is 00000101, the comparison result E _K (HVA) is 11000111. At this time, HW (E _K (HVA)) is “5”. Therefore, the comparison result E _K (HVA) is decoded. On the other hand, for example, when the encrypted authentication information E _K (mB) is 10111011 and the input information m ′ is similarly 00000101, the comparison result E _K (HVB) is 10111110. At this time, HW (E _K (HVB)) is “6”. Therefore, the comparison result E _K (HVB) is not decoded.

In this way, the authentication device 2 acquires the verification result HVi by decrypting only the one that satisfies the conditional expression 2 among the plurality of comparison results E _K (HVi) using the key information K. For example, the authentication device 2 obtains the collation result HVA “00000100” by decrypting the comparison result E _K (HVA) “11000111” with the key information K “11000011”. In the collation result HVA, the number of bits indicating 1 is “1”, which is equal to or less than the threshold d “2”. Therefore, since the authentication information mA having a certain degree of similarity or more is registered as the input information m ′, the authentication success is determined.

As described above, the inventor can use the key information K even if the verification result HVi between the authentication information mi and the input information m ′ is encrypted (comparison result E _K (HVi)). It has been found that by considering K and the threshold value d, it is possible to determine whether or not the authentication in the state where the comparison result E _K (HVi) is decrypted may be successful. Therefore, by performing the determination under the conditional expression 2, only the comparison result E _K (HVi) that may be successfully authenticated is set as the decryption target, and all the comparison results E _K (HV) are decrypted. Compared with the case where it does, the authentication apparatus 2 can reduce the processing cost required for the decoding process of the comparison result E _K (HVi).

  Next, functional configurations of the terminal device and the authentication device according to the first embodiment will be described. FIG. 4 is a functional block diagram of the terminal device and the authentication device according to the first embodiment.

  The terminal device 1 includes a reception unit 11, a transmission unit 12, a control unit 13, a storage unit 15, and a display unit 16. The receiving unit 11 is a processing unit that receives information from the authentication device 2. For example, in the authentication process, the receiving unit 11 receives an authentication result from the authentication device 2.

  The transmission unit 12 is a processing unit that transmits information to the authentication device 2. For example, the transmission unit 12 transmits a registration request to the authentication device 2 in the registration process. The registration request is information including the user ID “i” and the authentication information mi, and is information for requesting the authentication apparatus 2 to register the authentication information mi. In addition, the transmission unit 12 transmits an authentication request to the authentication device 2 in the authentication process. The authentication request is information including the input information m ′ and is information for requesting the authentication device 2 to perform authentication.

  The control unit 13 is a processing unit that controls the operation of the terminal device 1. For example, the control unit 13 controls registration processing and authentication processing. The control unit 13 includes, for example, a generation unit 14. The generation unit 14 is a processing unit that generates authentication information mi and input information m ′ to be authenticated.

  The generation unit 14 is a processing unit that generates authentication information mi and input information m ′ to be authenticated. For example, the generation unit 14 acquires an image or password input from an imaging device that captures an image or an input device that accepts input of a password or the like. When the authentication information mi and the input information m ′ are biometric information, the generation unit 14 obtains an image obtained by capturing a part of the user from the imaging device and extracts information about the feature points from the image. , Authentication information mi and input information m ′ are generated.

  The storage unit 15 stores information necessary for registration processing and authentication processing. The display unit 16 displays various information. For example, after receiving the authentication result, the display unit 16 displays the authentication result.

  Next, the authentication device 2 includes a reception unit 21, a transmission unit 22, a control unit 23, and a storage unit 29. The receiving unit 21 is a processing unit that receives information from the terminal device 1. For example, the receiving unit 21 receives a registration request or an authentication request from the terminal device 1. The transmission unit 22 is a processing unit that transmits information to the terminal device. For example, the transmission unit 22 transmits the authentication result to the terminal device 1.

  The control unit 23 is a processing unit that controls the operation of the authentication device 2. For example, the control unit 23 performs registration processing and authentication processing. The control unit 23 includes an encryption unit 24, a comparison unit 25, a specification unit 26, a decryption unit 27, and a determination unit 28.

The encryption unit 24 is a processing unit that executes encryption processing. For example, the encryption unit 24 encrypts the authentication information mi with the key information K in the registration process to generate the encrypted authentication information E _K (mi). Then, the encryption unit 24 stores the encrypted authentication information E _K (mi) and the user ID “i” in the storage unit 29 in association with each other.

The comparison unit 25 is a processing unit that compares the input information m ′ and a plurality of encrypted authentication information E _K (mi) based on a specific rule while maintaining the state where the authentication information mi is encrypted. . For example, the comparison unit 25 calculates the comparison result E _K (HVi) between the encrypted authentication information E _K (mi) and the input information m ′ by exclusive OR.

Based on the comparison result E _K (HVi) calculated by the comparison unit, the specifying unit 26 specifies the encrypted authentication information E _K (mi) that meets the condition determined based on the feature HW (K) of the key information K. Is a processing unit. For example, the identifying unit 26 identifies the comparison result that satisfies the conditional expression 2 determined based on the feature HW (K) of the key information K among the plurality of comparison results E _K (HVi), thereby authenticating the authentication result. The encryption authentication information E _K (mi) that may be determined to be successful in the success / failure determination is identified. Then, the specifying unit 26 inputs the comparison result E _K (HVi) satisfying the condition to the decoding unit 27 as a decoding target. Note that the comparison result E _K (HVi) that does not satisfy the condition is not input to the decoding unit 27.

Next, the decryption unit 27 decrypts the verification result (comparison result E _K (HVi)) between the encrypted authentication information E _K (mi) specified by the specification unit 26 and the input information m ′ with the key information K. It is a processing unit. For example, the decryption unit 27 calculates an exclusive OR of the comparison result E _K (HVi) and the key information K, and obtains a verification result HVi of the authentication information mi and the input information m ′.

The determination unit 28 determines the success or failure of authentication based on the encrypted authentication information E _K (mi) specified by the specifying unit 26, the input information m ′, and the key information K. For example, the bit indicating “1” in the comparison result HVi obtained by decrypting the comparison result E _K (HVi) of the encrypted authentication information E _K (mi) specified by the specifying unit 26 is compared with the threshold value d. . The number of bits indicating “1” in the collation result HVi is the hamming distance HDi between the input information m ′ and the authentication information mi, and indicates the difference between the input information m ′ and the authentication information mi.

  The determination unit 28 determines that the authentication is successful when the hamming distance HDi is smaller than the threshold value d. Then, the determination unit 28 generates an authentication result. For example, when there is a collation result in which the hamming distance HDi is smaller than the threshold value d, an authentication result indicating authentication success is generated. On the other hand, the determination unit 28 generates an authentication result indicating an authentication failure when there is no collation result in which the hamming distance HDi is smaller than the threshold value d.

  Note that the determination unit 28 may end the authentication success / failure determination process when a matching result HVi whose hamming distance HDi is smaller than the threshold value d is found. Further, the determination unit 28 may identify the collation result with the hamming distance HDi being smaller than the threshold d and the hamming distance HDi being the smallest by comparing all the collation results with the threshold d.

The storage unit 29 stores information necessary for registration processing and authentication processing. For example, the storage unit 29 stores the encrypted authentication information E _K (mA) in association with the user ID “A”. Furthermore, the storage unit 29 stores information such as key information K, a feature HW (K) of the key information, and a threshold value d.

  FIG. 5 is a diagram illustrating a data configuration example of the encrypted authentication information management table. The encrypted authentication information management table is stored in the storage unit 29. The encrypted authentication information management table stores record numbers (i), user IDs, and encrypted authentication information in association with each other. The record number (i) is information for identifying a record in the table.

  Next, processing of the terminal device 1 in the first embodiment will be described. FIG. 6 is a process flowchart of the terminal device in the first embodiment. The control unit 13 determines whether or not to execute the registration process (Op. 1). For example, an affirmative determination is made when there is an input from the user to start the registration process.

  When executing the registration process (Op. 1 Yes), the control unit 13 generates a user ID (Op. 2). Here, although the user ID is generated on the terminal device 1 side, the control unit 13 may request the authentication device 2 to generate the user ID.

  Furthermore, the generation unit 14 generates authentication information using a predetermined algorithm based on the information acquired from the reading device (Op. 3). Then, the control unit 13 generates a registration request including authentication information and a user ID. And the control part 13 controls the transmission part 12, and transmits a registration request to the authentication apparatus 2 (Op.4).

  On the other hand, when the registration process is not executed (Op. 1 No), the generation unit 14 generates input information to be input as an authentication target to the authentication device 2 based on the information acquired from the reading device (Op. 5). . Then, the control unit 13 generates an authentication request and controls the transmission unit 12 to transmit the authentication request to the authentication device 2 (Op.6). In the present embodiment, since one-to-many authentication is executed, the user does not need to input a user ID in the authentication process. Therefore, the user ID is not included in the authentication request.

  Next, the control unit 13 determines whether an authentication result for the authentication request has been received (Op. 7). Wait until the authentication result is received (Op. 7 No), and when the receiving unit 11 receives the authentication result (Op. 7 Yes), the display unit 16 displays the authentication result under the control of the control unit 13 ( Op.8). For example, the display unit 16 displays a screen that notifies the user of success or failure of the authentication result.

  Next, the process of the authentication device 2 in the first embodiment will be described. FIG. 7 is a processing flowchart of the authentication apparatus in the first embodiment. The control unit 23 determines whether or not the reception unit 21 has received a registration request (Op. 11).

When the registration request is received (Op. 11 Yes), the control unit 23 executes a registration process. First, the encryption unit 24 generates encrypted authentication information E _K (mi) by encrypting the authentication information mi using a predetermined rule using the key information K (Op. 12). The authentication information mi is included in the registration request. For example, the encryption unit 24 generates the encrypted authentication information E _K (mi) by calculating the exclusive OR of the key information K and the authentication information mi.

Then, the encryption unit 24 stores the user ID and the encrypted authentication information E _K (mi) in the encrypted authentication information management table of the storage unit 29 (Op. 13). And the control part 23 complete | finishes a series of registration processes.

  On the other hand, when the registration request has not been received (No in Op. 11), the control unit 23 determines whether or not the receiving unit 21 has received the authentication request (Op. 14). When the authentication request is not received (Op. 14 No), the control unit 23 ends the series of processes. On the other hand, when the authentication request has been received (Op. 14 Yes), the control unit 23 executes a matching process (Op. 15).

  FIG. 8 is a flowchart of the collation process in the first embodiment. First, the control unit 23 performs initial setting (Op. 21). The control unit 23 sets the minimum hamming distance variable HDmin to the number of bits of authentication information (for example, 8). The minimum hamming distance variable is a variable indicating the minimum hamming distance among the hamming distances HDi between the input information m ′ and the authentication information mi, and is updated by executing the subsequent matching process.

  In addition, the control unit 23 sets the counter variable j to “1” in the initial setting. The counter variable corresponds to the record number in the encrypted authentication information management table. Furthermore, the control unit 23 sets the number of records in the encrypted authentication information management table as the maximum counter value Nj. Then, the minimum ID variable IDmin for managing the user ID of the user who succeeds in authentication is set to a value (for example, −1) in which the corresponding user ID does not exist. The minimum ID variable IDmin is updated by executing the subsequent verification process.

After completing the initial setting, the control unit 23 determines whether the counter variable j matches the maximum counter value Nj (Op.22). If they do not match (Op. 22 No), the comparison unit 25 refers to the record corresponding to the counter variable j, acquires the encrypted authentication information E _K (mi) stored in the record, and inputs the input information. A comparison result E _K (HVi) with m ′ is calculated (Op. 23). For example, the comparison unit 25 calculates the comparison result E _K (HVi) by performing an exclusive OR of the encrypted authentication information E _K (mi) and the input information m ′.

Then, the specifying unit 26 determines whether or not the comparison result E _K (HVi) output from the comparison unit 25 satisfies the condition defined by the conditional expression 2 (Op. 24). When the conditional expression 2 is satisfied (Op. 24 Yes), the decryption unit 27 decrypts the comparison result E _K (HVi) with the key information K (Op. 25). Then, the determination unit 28 calculates a hamming distance HDi between the authentication information mi and the input information m ′ based on the collation result HVi obtained by decoding. Then, the determination unit 28 determines whether the hamming distance HDi is smaller than the minimum hamming distance variable HDmin (Op.26).

  When the hamming distance HDi is smaller than the minimum hamming distance variable HDmin (Op. 26 Yes), the determination unit 28 updates the minimum hamming distance variable HDmin to the hamming distance HDi and sets the minimum ID variable IDmin to the counter variable j. Update (Op.27).

  Op. 27 or when Conditional Expression 2 is not satisfied (Op. 24 No), or when the Hamming distance HDi is greater than or equal to the minimum Hamming distance variable HDmin (Op. 26 No), the control unit 23 increments the counter variable j. (Op.28). And Op. Return to 22 and repeat the process. That is, when a smaller hamming distance HDi is found, the minimum hamming distance HDmin is updated to the hamming distance HDi. Further, the minimum ID variable IDmin is also updated.

If the counter variable j matches the maximum counter value Nj (Op. 22 Yes), the processing for all the encrypted authentication information E _K (mi) is completed. The verification process ends.

  Next, returning to FIG. 7, after the collation process (Op.15) is completed, the determination unit 28 determines whether or not the minimum hamming distance HDmin is smaller than the threshold value d (Op.16). When the minimum hamming distance HDmin is smaller than the threshold value d (Op.16 Yes), the determination unit 28 generates an authentication result indicating that the authentication is successful. Further, the determination unit 28 acquires the user ID “i” stored in the record “j” indicated by the minimum ID variable IDmin from the encrypted authentication information management table. Then, the transmission unit 22 transmits an authentication result indicating that the authentication was successful and a user ID to the terminal device 1 (Op. 17).

  When the authentication device 2 manages the user ID and the user name in association with each other, the user name corresponding to the user ID may also be transmitted to the terminal device 1. In this case, Op. 8, the display unit 16 of the terminal device 1 displays a message asking whether the authenticated user is correct, along with the fact that the authentication is successful. For example, a message “Authentication has succeeded, Mr. A?” Is displayed. In the one-to-many authentication, it is not necessary to input a user ID. Therefore, the success or failure of the authentication is determined based on the collation result between the user input information m ′ and the plurality of authentication information mi. As a result, it may be determined that the input information m ′ of the user and the authentication information mi other than the user are similar, and authentication may be successful. Therefore, by allowing the user to confirm the user name, the user can confirm whether or not the user has been correctly authenticated.

  On the other hand, when the minimum hamming distance HDmin is equal to or greater than the threshold value d (Op.16 No), the determination unit 28 generates an authentication result indicating that the authentication has failed. And the transmission part 22 transmits the authentication result which shows that authentication was unsuccessful to the terminal device 1 (Op.18).

As described above, the authentication device 2 omits the decryption process for the comparison result E _K (HVi) of the encrypted authentication information E _K (mi) that does not satisfy the condition of the conditional expression 2. On the other hand, the comparison result E _K (HVi) of the encrypted authentication information E _K (mi) that satisfies the condition of the conditional expression 2 and is likely to be authenticated is decrypted. Therefore, the authentication device 2 prevents the encrypted authentication information E _K (mi) that can be successfully authenticated from being excluded from the narrowing targets.

[Second Example]
9 and 10 are diagrams for explaining an authentication system according to the second embodiment. The authentication system in the second embodiment includes a terminal device 3, a management device 4, and a determination device 5. The terminal device 3, the management device 4, and the determination device 5 are connected via the network N. Moreover, the management apparatus 4 and the determination apparatus 5 may be connected by a dedicated network. In addition, the structure which the some determination apparatus 5 connects with respect to the one management apparatus 4 may be sufficient.

The terminal device 3 is a computer that requests the management device 4 for authentication processing. The management device 4 is a computer that manages encrypted authentication information. The management device 4 includes a server 400 that executes processing and a database 401 that stores encrypted authentication information. The determination device 5 is a computer that determines the success or failure of authentication using the comparison result E _K (HVi) received from the management device 4.

FIG. 9 is a diagram for explaining registration processing in the authentication system according to the second embodiment. In the registration process, first, the terminal device 3 transmits the user ID “A” and the authentication information mA to the determination device 5. The determination device 5 receives the user ID “A” and the authentication information mA. Then, the determination device 5 generates the encrypted authentication information E _K (mA) by encrypting the authentication information mA using the key information K. In the present embodiment, the determination device 5 generates encrypted authentication information E _K (mA) by exclusive OR of the key information K and the authentication information mA.

Then, the user ID “A” and the encrypted authentication information E _K (mA) are transmitted to the management apparatus 4. The management device 4 stores the user ID “A” received from the determination device 5 in the database 401 in association with the encrypted authentication information E _K (mA).

FIG. 10 is a diagram for explaining an authentication process in the authentication system according to the second embodiment. The terminal device 3 generates input information m ′ and transmits it to the management device 4. When receiving the input information m ′, the management device 4 calculates a comparison result E _K (HVi) with the input information m ′ for each of the encrypted authentication information E _K (mi) registered in the database 401. In the present embodiment, the comparison result E _K (HVi) is obtained, for example, by exclusive OR of the input information m ′ and the encrypted authentication information E _K (mi). Note that HVi indicates a collation result between the authentication information mi and the input information m ′. The comparison result E _K (HVi) corresponds to information obtained by encrypting the collation result between the authentication information mi and the input information m ′ with the key information K.

Next, the management apparatus 4, like the first embodiment, to identify the comparison result _E K are true condition 2 (HVi), the comparison result _E K is true conditional expression 2 (HVi), the corresponding user It transmits to the determination apparatus 5 with ID. Then, the determination device 5 decrypts the received comparison result E _K (HVi) using the key information K, and obtains a matching result HVi between the authentication information mi and the input information m ′. Then, the determination device 5 determines the success or failure of the authentication by comparing the number of bits indicating “1” in the verification result HVi with the threshold value d. The number of bits indicating “1” in the verification result HVi is the Hamming distance HDi between the authentication information mi and the input information m ′. Then, the determination device 5 transmits the authentication result to the terminal device 3.

Here, the management device 4 does not need to manage the key information K itself. The management device 4 holds only the characteristics of the key information K necessary for the determination using the conditional expression 2. For example, the determination device 5 generates a feature HW (K) of the key information K managed by the determination device 5 and transmits it to the management device 4 prior to the authentication process. Furthermore, the determination device 5 also transmits to the management device 4 a threshold value d for determining success or failure of authentication. Then, the management device 4 uses the feature HW (K) of the key information and the threshold value d for determining whether or not the comparison result E _K (HV) is to be decrypted.

Thus, in the second embodiment, the entity that manages the key information K and performs encryption and decryption (determination device 5), and the entity that manages the encrypted authentication information E _K (mi) (management device) 4) is divided. Therefore, the administrator of the management device 4 cannot decrypt the encrypted authentication information E _K (mi). That is, the administrator cannot obtain the authentication information mi. The determination device 5, because it does not manage the key information K and the encrypted authentication information E _{K (mi)} with the key information K and the encrypted authentication information E _{K (mi)} is both stolen, authentication information mi is It can be prevented from being obtained by a malicious third party.

  Next, functional configurations of the management device and the determination device according to the second embodiment will be described. FIG. 11 is a functional block diagram of the management device and the determination device according to the second embodiment. The terminal device 3 has the same functional configuration as the terminal device 1 shown in FIG. However, the transmission unit 12 is controlled by the control unit 13 so that the registration request in the registration process is transmitted to the determination device 5. In addition, the transmission unit 12 is controlled by the control unit 13 so that an authentication request in the authentication process is transmitted to the management device 4.

The management device 4 includes a reception unit 41, a transmission unit 42, a control unit 43, and a storage unit 46. The receiving unit 41 receives information from the terminal device 3 or the determination device 5. For example, the receiving unit 41 receives the encrypted authentication information E _K (mi) and the user ID from the determination device 5. The encrypted authentication information E _K (mi) is generated by the determination device 5. The receiving unit 41 receives an authentication request including the input information m ′ to be authenticated from the terminal device 3.

The transmission unit 42 transmits information to the determination device 5. For example, the transmission unit 42 transmits the comparison result E _K (HVi) between the input information m ′ and the encrypted authentication information E _K (mi) to the determination device 5 under the control of the control unit 43. Further, information on the user ID corresponding to the comparison result E _K (HVi) may also be transmitted.

  The control unit 43 is a processing unit that controls the operation of the management device 4. For example, the control unit 43 executes a registration process and an authentication process. The control unit 43 includes a comparison unit 44 and a specifying unit 45.

The comparison unit 44 is a processing unit that calculates a comparison result E _K (HVi) between the encrypted authentication information E _K (mi) and the input information m ′ when an authentication request is received. For example, the comparison unit 44 sequentially acquires the encrypted authentication information E _K (mi) from the storage unit 46, and performs exclusive OR of the input information m ′ included in the authentication request and the encrypted authentication information E _K (mi). Is obtained as a comparison result E _K (HVi). All the comparison results E _K (HVi) are output to the specifying unit 45.

The identification unit 45 identifies encrypted authentication information that may be successfully authenticated in the authentication success / failure determination performed by the determination device 5. For example, the specifying unit 45 compares the condition of conditional expression 2 in the first embodiment with the comparison result E _K (HVi). Then, the specifying unit 45 specifies that the comparison result E _K (HVi) that matches the condition is a comparison result related to the encrypted authentication information E _K (mi) that may be successfully authenticated. The identification unit 45 outputs the identified comparison result E _K (HVi) to the transmission unit 42.

The storage unit 46 stores information necessary for registration processing and authentication processing. For example, the storage unit 46 stores the encrypted authentication information E _K (mA) in association with the user ID “A”. For example, the storage unit 46 holds an encrypted authentication information management table shown in FIG. Further, the storage unit 46 stores the feature HW (K) of the key information K and the threshold value d used for the authentication success / failure determination.

Next, the determination device 5 includes a reception unit 51, a transmission unit 52, a control unit 53, and a storage unit 57. The receiving unit 51 receives information from the terminal device 3 or the management device 4. For example, the receiving unit 51 receives a registration request including the authentication information mi and the user ID from the terminal device 3 in the registration process. Further, the receiving unit 51 receives the comparison result E _K (HVi) between the encrypted authentication information E _K (mi) and the input information m ′ from the management device 4 in the authentication process.

The transmission unit 52 transmits information to the terminal device 3 or the management device 4. For example, the transmission unit 52 transmits the user ID and the encrypted authentication information E _K (mi) to the management device 4 in the registration process. Moreover, the transmission part 52 transmits an authentication result to the terminal device 3 in an authentication process.

  The control unit 53 is a processing unit that controls the operation of the determination device 5. For example, the control unit 53 performs a registration process and an authentication process. The control unit 53 includes an encryption unit 54, a decryption unit 55, and a determination unit 56.

The encryption unit 54 is a processing unit that executes encryption processing. For example, in the registration process, the encryption unit 54 encrypts the authentication information mi using a specific rule using the key information K, and generates the encrypted authentication information E _K (mi). As in the first embodiment, encryption satisfying conditional expression 1 is used.

The decrypting unit 55 is a processing unit that decrypts the comparison result E _K (HVi) received from the management device 4 with the key information K. For example, the determination unit 56 obtains a verification result HVi between the authentication information mi and the input information m ′ by decrypting the comparison result E _K (HVi) with the key information K.

  The determination unit 56 uses the collation result HVi obtained by decryption by the decryption unit 55 to determine whether or not the authentication is successful. For example, the number of bits indicating “1” (Hamming distance HDi) in the comparison result HVi is compared with the threshold value d. Then, the determination unit 56 determines the success or failure of the authentication according to the comparison result between the hamming distance HDi and the threshold value d, and generates an authentication result.

  The storage unit 57 stores information necessary for registration processing and authentication processing. For example, the storage unit 57 stores key information K and a threshold value d.

  Next, the flow of processing by various devices in the second embodiment will be described. The flow of processing by the terminal device 3 is the same as in the first embodiment. However, the terminal device 3 is not limited to Op. 6 is sent to the management apparatus 4, and Op. 3 is transmitted to the determination device 5.

  FIG. 12 is a process flowchart of the determination apparatus according to the second embodiment. The control unit 53 determines whether a registration request is received from the terminal device 3 (Op.30). For example, the determination is performed based on whether or not flag information indicating a registration request is added to the information received by the receiving unit 51.

When the registration request is received (Op. 30 Yes), the encryption unit 54 generates the encrypted authentication information E _K (mi) using the authentication information mi and the key information K included in the registration request (Op. 31). ). The transmission unit 52 transmits the encrypted authentication information E _K (mi) together with the user ID to the management device 4 (Op.32). And the determination apparatus 5 complete | finishes a registration process.

On the other hand, when the registration request is not received (Op. 30 No), the control unit 53 transmits the comparison result E _K (HVi) between the input information m ′ and the encrypted authentication information E _K (mi) from the management device 4. It is determined whether or not a start notification to start is received (Op.33). For example, the determination is performed based on whether or not flag information indicating a start notification is added to the information received by the reception unit 51. In the present embodiment, it is determined that the start notification is received when the comparison result E _K (HVi) and the corresponding user ID are received for the first time. If the start notification has not been received (No in Op. 33), the process ends. On the other hand, when the start notification is received (Op. 33 Yes), the control unit 53 executes a matching process (Op. 34).

  FIG. 13 is a flowchart of the collation process according to the second embodiment. The control unit 53 performs initial setting (Op.40). The control unit 53 sets the minimum hamming distance variable HDmin to the number of bits (for example, 8) of the authentication information.

The control unit 53 determines whether or not an end notification indicating that transmission of the comparison result E _K (HVi) is to be ended is received from the management device 4 (Op. 41). When the end notification is not received (Op. 41 No), the decryption unit 55 acquires the comparison result E _K (HVi) and the user ID (Op. 42). The comparison result E _K (HVi) is independent of the verification process and is received every time the management apparatus 4 transmits the comparison result E _K (HVi). Therefore, the decoding unit 55 receives the comparison result E _K received. (HVi) is sequentially processed.

Next, the decryption unit 55 decrypts the comparison result E _K (HVi) with the key information K (Op. 43). Then, the determination unit 56 calculates the hamming distance HDi between the authentication information mi and the input information m ′ based on the collation result HVi obtained by decoding. Then, the determination unit 56 determines whether the hamming distance HDi is smaller than the minimum hamming distance variable HDmin (Op.44).

  When the hamming distance HDi is smaller than the minimum hamming distance variable HDmin (Op. 44 Yes), the determination unit 56 updates the minimum hamming distance variable HDmin to the hamming distance HDi, and the minimum ID variable IDmin from the management device 4. The received user ID is updated (Op. 45).

And Op. Returning to 41, the processing is repeated until an end notification is received. On the other hand, when an end notification is received (Op. 41 Yes), the control unit 53 ends a series of collation processes. When an unprocessed comparison result E _K (HVi) is present at the time when the end notification is received, the control unit 53 processes the comparison results E _K (HVi) and then performs the matching process. finish.

  Returning to FIG. 12, after the collation process (Op. 34) is completed, the determination unit 56 determines whether or not the minimum hamming distance HDmin is smaller than the threshold value d (Op. 35). When the minimum hamming distance HDmin is smaller than the threshold value d (Op. 35 Yes), the determination unit 56 generates an authentication result indicating that the authentication is successful. And the transmission part 52 transmits the authentication result which shows that authentication was successful to the terminal device 3 with the user ID set to the minimum ID variable IDmin (Op.36).

  On the other hand, when the minimum hamming distance HDmin is equal to or greater than the threshold value d (Op. 35 No), the determination unit 56 generates an authentication result indicating that the authentication has failed. Then, the transmission unit 52 transmits an authentication result indicating that the authentication has failed to the terminal device 3 (Op. 37).

Next, FIG. 14 is a processing flowchart of the management apparatus according to the second embodiment. The control unit 43 determines whether or not the user ID and the encrypted authentication information E _K (mi) are received from the determination device 5 (Op. 50). For example, the determination is performed based on whether or not flag information indicating encryption authentication information is added to the information received by the reception unit 41.

When the encrypted authentication information is received (Op. 50 Yes), the control unit 43 associates the encrypted authentication information E _K (mi) with the user ID and stores them in the storage unit 46 (Op. 51). Then, the management device 4 ends the authentication process.

  On the other hand, when encryption authentication information is not received (Op.50 No), the control part 43 determines whether the authentication request | requirement was received from the terminal device 3 (Op.52). For example, the determination is performed based on whether or not flag information indicating an authentication request is added to the information received by the reception unit 41.

  When the authentication request has not been received (Op. 52 No), the control unit 43 ends the process. On the other hand, when the authentication request is received (Op. 52 Yes), the control unit 43 performs initial setting (Op. 53). The controller 43 sets the counter variable j to “1” in the initial setting. Furthermore, the control unit 43 sets the number of records in the encrypted authentication information management table as the maximum counter value Nj.

Next, the control unit 43 determines whether the counter variable j matches the maximum counter value Nj (Op. 54). If they do not match (Op. 54 No), the comparison unit 44 refers to the record corresponding to the counter variable j, acquires the encrypted authentication information E _K (mi) stored in the record, and inputs the input information. A comparison result E _K (HVi) with m ′ is calculated (Op. 55). For example, the comparison unit 44 calculates the comparison result E _K (HVi) by performing an exclusive OR of the encrypted authentication information E _K (mi) and the input information m ′.

Then, the specifying unit 45 determines whether or not the comparison result E _K (HVi) output from the comparison unit 44 satisfies the condition defined by the conditional expression 2 (Op. 56). When the conditional expression 2 is satisfied (Op. 56 Yes), under the control of the control unit 43, the transmission unit 42 determines the comparison result E _K (HVi) and the user ID of the record corresponding to the counter variable j as the determination device 5. (Op. 57).

And Op. After the end of 57 or when the comparison result E _K (HVi) does not satisfy the condition defined by the conditional expression 2 (Op. 56 No), the control unit 43 increments the counter variable j (Op. 58). . And Op. Returning to 54, the process is repeated.

  On the other hand, if the counter variable j matches the maximum counter value Nj (Op. 54 Yes), the processing has been completed for all the records. Therefore, under the control of the control unit 43, the transmission unit 42 terminates. A notification is transmitted to the determination device 5 (Op. 59). And the management apparatus 4 complete | finishes a series of processes.

As described above, according to the second embodiment, security can be improved by separately managing the key information K and the encrypted authentication information E _K (mi). Further, the decryption process by the determination device 5 is executed only for the comparison result E _K (HVi) related to the encrypted authentication information E _K (mi) determined to be necessary for the decryption by the management device 4. Therefore, the processing cost of the determination device 5 can be reduced, and the amount of communication between devices is reduced as compared with the case where all the comparison results E _K (HVi) are transmitted from the management device 4 to the determination device 5. be able to.

[Third embodiment]
In the third embodiment, the condition for narrowing down the comparison result E _K (HVi) that is the object of the decoding process is updated. That is, in the third embodiment, the lower limit value and the upper limit value set by the conditional expression 2 are updated.

  When it is detected that there is authentication information mi having a hamming distance HDi that is equal to or less than the threshold value d, it is searched whether or not there is authentication information mi ′ having a hamming distance HDi ′ that is smaller than the hamming distance HDi. Good. Therefore, the lower limit value and the upper limit value set by the conditional expression 2 are updated to stricter conditions according to the Hamming distance HDi.

  By updating the condition defined by the lower limit value and the upper limit value to a stricter condition, the comparison result that is the target of the decoding process is further limited. The third embodiment further reduces the processing cost for decoding as compared to the first and second embodiments by further limiting the objects of the decoding process.

  15 and 16 are diagrams for explaining an authentication system according to the third embodiment. In the example shown in FIGS. 15 and 16, the authentication system according to the third embodiment includes a terminal device 3, a management device 6, and a determination device 7. However, the third embodiment is also applicable to a system including a terminal device and an authentication device, as in the first embodiment.

  The terminal device 3, the management device 6, and the determination device 7 are connected via a network N. Moreover, the management apparatus 6 and the determination apparatus 7 may be connected by a dedicated network. Since the terminal device 3 performs the same process as the terminal device according to the second embodiment, a description thereof is omitted. The management device 6 performs the same processing as the management device 4 according to the second embodiment, and updates the lower limit value and the upper limit value according to the conditional expression 2 according to the output from the determination device 7. The determination device 7 performs the same processing as the determination device 5 according to the second embodiment, and instructs the management device 6 to update the lower limit value and the upper limit value according to the conditional expression 2.

  FIG. 15 is a diagram for explaining registration processing in the authentication system according to the third embodiment. In the registration process of the third embodiment, the management apparatus 6 performs the same process as the management apparatus 4 according to the second embodiment. The determination device 7 performs the same process as the determination device 5 according to the second embodiment.

Next, FIG. 16 is a diagram for explaining an authentication process in the authentication system according to the third embodiment. As in the second embodiment, the terminal device 3 generates input information m ′ and transmits it to the management device 6. As in the second embodiment, the management device 6 sequentially calculates the comparison result E _K (HVi) between the input information m ′ and the encrypted authentication information E _K (mi). When the comparison result E _K (HVi) satisfies the conditional expression 2, the management device 6 sequentially transmits the comparison result E _K (HVi) together with the corresponding user ID to the determination device 7.

On the other hand, the determination device 7 sequentially decrypts the received comparison results E _K (HVi) using the key information K, as in the second embodiment. And the determination apparatus 7 determines authentication success or failure using the collation result HVi of authentication information mi and input information m '. That is, the determination device 7 determines whether the hamming distance HDi between the authentication information mi and the input information m ′ is equal to or less than the threshold value d.

When the hamming distance HDi between the authentication information mi and the input information m ′ is equal to or less than the threshold value d, the determination device 7 transmits an update instruction for the upper limit value and the lower limit value according to the conditional expression 2 to the management device 6. . In the update instruction, the determination device 7 notifies the hamming distance HDi to the management device 6 as a new threshold value d ′. The management device 6 that has received the notification uses the upper limit value and the lower limit value corresponding to the new threshold value d ′ to determine whether or not the comparison result E _K (HVi) is to be decrypted.

  As described above, the threshold value d 'is smaller than the threshold value d. Therefore, the lower limit value “HW (K) −d” is a larger value “HW (K) −d ′”, and the upper limit value “HW (K) + d” is a smaller value “HW (K) + d ′”. Changed to That is, the condition defined by the conditional expression 2 is updated to a stricter condition by the update instruction.

  Next, functional configurations of the management device and the determination device according to the third embodiment will be described. FIG. 17 is a functional block diagram of the management device and the determination device according to the third embodiment.

  The management device 6 includes a reception unit 61, a transmission unit 62, a control unit 63, and a storage unit 66. The receiving unit 61 performs the same process as the receiving unit 41. The transmission unit 62 performs the same processing as the transmission unit 42. The storage unit 66 stores the same information as the storage unit 46.

  The control unit 63 is a processing unit that controls the operation of the management device 6. For example, the control unit 63 performs a registration process and an authentication process. The control unit 63 includes a comparison unit 64 and a specifying unit 65.

  The comparison unit 64 performs the same process as the comparison unit 44. The specifying unit 65 performs the same processing as that of the specifying unit 45, and updates the condition according to the conditional expression 2 when an update instruction is received from the determination device 7. That is, the specifying unit 65 updates the upper limit value and the lower limit value using the new threshold value d ′.

  Next, the determination device 7 includes a reception unit 71, a transmission unit 72, a control unit 73, and a storage unit 77. The receiving unit 71 performs the same processing as the receiving unit 51. The transmission unit 72 performs the same process as the transmission unit 52. The storage unit 77 stores the same information as the storage unit 57.

  The control unit 73 is a processing unit that controls the operation of the determination device 7. For example, the control unit 73 performs registration processing and authentication processing. The control unit 73 includes an encryption unit 74, a decryption unit 75, and a determination unit 76.

  The encryption unit 74 performs the same processing as the encryption unit 54. The decoding unit 75 performs the same process as the decoding unit 55. The determination unit 76 performs the same processing as the determination unit 56, and generates an update instruction including a new threshold value d 'when the collation result HVi having a hamming distance HDi smaller than the threshold value d is detected. Then, the determination unit 76 controls the transmission unit 72 to transmit an update instruction to the management device 6. The new threshold value d ′ is the Hamming distance HDi determined to be smaller than the threshold value d.

  Next, the flow of processing by various devices in the third embodiment will be described. The flow of processing by the terminal device 3 is the same as in the second embodiment.

  FIG. 18 is a process flowchart of the determination apparatus according to the third embodiment. Op. 60, Op. 61, Op. 62, Op. 63, Op. 66, Op. 67, according to the second embodiment, Op. 30, Op. 31, Op. 32, Op. 33, Op. 36, Op. 37. Hereinafter, Op. 64 (FIG. 19) and Op. 65 will be described.

  FIG. 19 is a flowchart of the collation process according to the third embodiment. The control unit 73 performs initial setting (Op. 70). The control unit 73 sets the minimum hamming distance variable HDmin to the number of bits (for example, 8) of the authentication information. Then, the minimum ID variable IDmin is set to a value (for example, −1) where the corresponding user ID does not exist.

The control unit 73 determines whether or not an end notification indicating that transmission of the comparison result is ended is received from the management device 6 (Op. 71). When the end notification is not received (Op. 71 No), the decrypting unit 75 acquires the comparison result E _K (HVi) and the user ID (Op. 72).

Next, the decryption unit 75 decrypts the comparison result E _K (HVi) with the key information K (Op. 73). Then, the determination unit 76 calculates the hamming distance HDi between the authentication information mi and the input information m ′ based on the collation result HVi obtained by decoding. Then, the determination unit 76 determines whether the hamming distance HDi is smaller than the threshold value d (Op. 74).

  When the hamming distance HDi is smaller than the threshold value d (Op.74 Yes), the determination unit 76 determines whether the hamming distance HDi is smaller than the minimum hamming distance variable HDmin (Op.75). On the other hand, when the hamming distance HDi is larger than the threshold value d (Op. 74 No), the control unit 73 sets the Op. Return to 71.

  When the hamming distance HDi is smaller than the minimum hamming distance variable HDmin (Op.75 Yes), the determination unit 76 updates the minimum hamming distance variable HDmin to the hamming distance HDi and sets the minimum ID variable IDmin to the corresponding user ID. (Op.76). Then, the determination unit 75 updates the threshold d to the minimum Hamming distance variable HDmin and generates an update instruction including the new threshold d ′ (HDmin). The transmission unit 72 transmits an update instruction to the management device 6 (Op. 77).

  When the hamming distance HDi is larger than the minimum hamming distance variable HDmin (Op. 75 No), the control unit 73 determines that the Op. Returning to 71, the processing is repeated until an end notification is received. On the other hand, when an end notification is received (Op. 71 Yes), the control unit 73 ends a series of collation processes.

  Returning to FIG. 18, after the collation process (Op. 64) is completed, the determination unit 76 determines whether the minimum ID variable IDmin has been updated from the initial setting value (Op. 65). For example, the determination unit 76 determines whether the minimum ID variable IDmin is -1. When the minimum ID variable IDmin is updated from the initial setting value (Op.65 Yes), the determination unit 76 generates an authentication result indicating that the authentication is successful. On the other hand, when the minimum ID variable IDmin has not been updated from the initial setting value (Op. 65 No), the determination unit 76 generates an authentication result indicating that the authentication has failed.

  Next, FIG. 20 is a processing flowchart of the management apparatus according to the third embodiment. Op. 80, Op. 81, Op. 82, Op. 83, Op. 84, Op. 85, Op. 86, Op. 87, Op. 90, Op. 91, Op. 50, Op. 51, Op. 52, Op. 53, Op. 54, Op. 55, Op. 56, Op. 57, Op. 58, Op. 59. In the third embodiment, Op. 86 or Op. After 87, the management device 6 makes an Op. 88 and Op. 89 is executed.

  The identifying unit 65 determines whether an update instruction is received from the determination device 7 (Op.88). When the update instruction has not been received (Op. 88 No), the control unit 63 determines that the Op. 90 is executed. On the other hand, if an update instruction has been received (Op. 88 Yes), the specifying unit 65 updates the threshold d with the new threshold d '(Op. 89). That is, Op. 86 is updated, the lower limit value and the upper limit value of conditional expression 2 are set to Op. Changed after 89.

  As described above, the management device 6 and the determination device 7 cooperate with each other in real time, so that the management device 6 can update a condition for determining whether or not to be a decoding target. Therefore, since the decoding target can be further limited, the processing cost of the decoding process in the determination device 7 is further reduced.

[Modification example]
Here, modifications of the first embodiment, the second embodiment, and the third embodiment will be described. In the first embodiment, the second embodiment, and the third embodiment, it has been described that all users are encrypted with the uniform key information K (or mask value RK). In the modified example, different key information Ki (or mask value RKi) is used for each user. In the modified example, the authentication information mi is encrypted with the key information Ki (or the mask value RKi) to generate the encrypted authentication information E _K i (mi). In the modified example, key information Ki (or mask value RKi) for each user is used in decryption. Hereinafter, two examples in the modified example will be described.

[First variant]
First, a case where different key information (or mask value) having the same characteristics is used will be described. That is, key information is used in which the number of bits indicating “1” in the bit string of the key information Ki (or mask value RKi) is the same. In the first variation, key information Ki (or mask value RKi) applied to authentication information mi is managed for each user ID. At this time, since the characteristics of the key information Ki are the same, one-to-many authentication is executed by the same processing as in the first to third embodiments using the conditions defined in the conditional expression 2. .

[Second variation]
In the second modification, a case will be described in which the characteristics of the key information (or mask value) applied for each user differ between the key information. In the following description, a plurality of mask values RKi are generated from one key information K, and authentication information mi of each user is encrypted. However, the same applies to the case where the key information Ki itself is different for each user.

In conditional expression 2 used in the first to third embodiments, the key information K (or mask value RK) used for encryption of each authentication information is the same, and the key information feature HW (K) is a conditional expression derived by utilizing the uniqueness. Therefore, in the second modification, the following conditional expression 6 is used.

  HW (RK) min is the smallest value among the number of bits indicating “1” in the bit string of each mask value. HW (RK) max is the maximum value among the number of bits indicating “1” in the bit string of each mask value. Conditional expression 6 employs “HW (RKi) min−d” that gives the smallest value when conditional expression 2 is applied for each mask value RKi as the lower limit value and “HW (RKi) that gives the largest value. ) Max + d "as an upper limit value.

  FIG. 21 is a data configuration example of the mask value management table. Note that when the present modification is applied to the first embodiment, the authentication device 2 stores a mask value management table. When the present modification is applied to the second embodiment, the determination device 5 stores a mask value management table. When this modification is applied to the third embodiment, the determination device 7 stores a mask value management table. Below, the case where it applies to a 2nd Example is demonstrated.

The mask value management table stores record numbers, user IDs, mask values, and features of mask values in association with each other. For example, when a registration request is received from the terminal device 3, the determination device 5 generates a mask value from the key information K. Then, the determination apparatus 5 generates encrypted authentication information E _K 1 (mA) by encrypting the authentication information (for example, mA) included in the registration request with a mask value (for example, RK1 “11001100”). To do. At this time, the determination apparatus 5 registers the mask value RK1 “11001100” in the mask value management table in association with the user ID “A” included in the registration request.

  The determination device 5 also registers the mask value feature HW (RKi) in the mask value management table. The feature HW (RKi) of the mask value is the number of bits indicating “1” in the bit string of the mask value RKi. The determination device 5 transmits the maximum value HW (RKi) max and the minimum value HW (RKi) min of the mask value feature HW (RKi) to the management device 4, so that the management device 4 satisfies the conditional expression 6 Judgment can be made.

  Next, various processing flows when the modified example is applied will be described. When applied to the first embodiment, Op. 24, determination using Conditional Expression 6 is performed, and Op. At 25, the comparison result is decoded with the mask value corresponding to the user ID.

  In the case where the modified example is applied to the second embodiment, the determination device 5 is an Op. In 43, the comparison result is decrypted with the mask value corresponding to the user ID. Further, the management device 4 is an Op. At 56, the determination using Conditional Expression 6 is performed.

  In the case where the modified example is applied to the third embodiment, the determination device 7 is the Op. In 73, the comparison result is decrypted with the mask value corresponding to the user ID. Further, the management device 6 is an Op. In 86, the determination using Conditional Expression 6 is performed.

As described above, according to the second modification, different key information Ki (or mask value RKi) can be used for each user. Therefore, the security of the encrypted authentication information E _K (mi) can be further improved. Then, by using conditional expression 6, even if different key information Ki is used for each user, only the comparison result E _K (HVi) that can be successfully authenticated in the authentication success / failure determination is obtained. By making it a decoding target, the processing cost can be reduced.

[Hardware configuration example]
The terminal device, the authentication device, the management device, and the determination device relating to each of the first embodiment, the second embodiment, and the third embodiment are each realized by a computer. FIG. 22 is a hardware configuration example of a terminal device, an authentication device, a management device, and a determination device in each embodiment. Note that the computer 1000 having the configuration shown in FIG. 22 functions as a terminal device, an authentication device, a management device, and a determination device.

  The computer 1000 executes registration processing and authentication processing according to each embodiment, and functions as a terminal device, an authentication device, a management device, and a determination device according to each embodiment. A computer 1000 includes a central processing unit (CPU) 1001, a read only memory (ROM) 1002, a random access memory (RAM) 1003, a communication device 1004, a hard disk drive (HDD) 1005, an input device 1006, a display device 1007, and a medium reading device 1007. 1008, and each unit is connected to each other via a bus 1009. Data can be transmitted and received with each other under the control of the CPU 1001.

  The authentication program describing the registration process or the authentication process shown in the flowchart of each embodiment is recorded on a recording medium readable by the computer 1000. Examples of the recording medium readable by the computer 1000 include a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory. Examples of the magnetic recording device include an HDD, a flexible disk (FD), and a magnetic tape (MT).

  Optical discs include Digital Versatile Disc (DVD), DVD-RAM, Compact Disc-Read Only Memory (CD-ROM), and Compact Disc-Recordable / Rewritable (CD-R / RW). Magneto-optical discs (MO) are examples of magneto-optical recording media. When distributing the authentication program, for example, a portable recording medium such as a DVD or a CD-ROM in which the authentication program is recorded may be sold.

  Then, the medium reading device 1008 of the computer 1000 that executes the authentication program describing the registration process and the authentication process according to each embodiment reads the program from the recording medium on which the authentication program is recorded. The CPU 1001 stores the read authentication program in the HDD 1005, the ROM 1002, or the RAM 1003.

  A CPU 1001 is a central processing unit that controls operation of the entire apparatus according to each embodiment. Then, the CPU 1001 reads out an authentication program related to each embodiment from the HDD 1005 and executes it. The CPU 1001 functions as a control unit in each device. As described above, the program may be stored in the ROM 1002 or the RAM 1003 accessible to the CPU 1001.

  Next, the communication device 1004 functions as a reception unit or a transmission unit in each device under the control of the CPU 1001.

  The HDD 1005 functions as a storage unit in each device under the management of the CPU 1001. That is, the HDD 1005 stores information necessary for registration processing and authentication processing. Similar to the program, information necessary for registration processing and authentication processing may be stored in the ROM 1002 or the RAM 1003 accessible to the CPU 1001. Further, various information generated in the course of processing is stored in the RAM 1003, for example. That is, the RAM 1003 may function as a storage unit.

  The input device 1006 accepts various inputs. The input device 1006 is, for example, a keyboard or a mouse. The display device 1007 displays various information. The display device 1007 is a display, for example.

1, 3 Terminal device 2 Authentication device 4, 6 Management device 5, 7 Determination device 1000 Computer 1001 CPU
1002 ROM
1003 RAM
1004 Communication device 1005 HDD
1006 Input device 1007 Display device 1008 Medium reader 1009 Bus

Claims (10)

A storage unit that stores, for a plurality of users, encrypted authentication information obtained by encrypting authentication information used for user authentication with a specific rule using key information;
A comparison unit that compares input information input as an authentication target and a plurality of encrypted authentication information stored in the storage unit based on the specific rule while maintaining a state where the authentication information is encrypted; ,
Based on the comparison result by the comparison unit, a specifying unit that specifies encrypted authentication information that satisfies a condition determined based on the characteristics of the key information;
A one-to-many authentication system, comprising: a determination unit that determines whether authentication is successful or not based on the encrypted authentication information specified by the specifying unit, the input information, and the key information.   The specific rule collates the first encrypted information in which the first plaintext is encrypted with the key information and the second encrypted information in which the second plaintext is encrypted with the key information. The one-to-many authentication system according to claim 1, wherein the result is a rule in which the first plaintext and the collation result of the second plaintext are the same.   3. The one-to-many authentication system according to claim 2, wherein the encrypted authentication information is generated by subjecting the authentication information to Vernam encryption using the key information.   4. The decrypting unit according to claim 1, further comprising: a decrypting unit configured to decrypt a verification result between the encrypted authentication information identified by the identifying unit and the input information using the key information. 1 to many authentication system.   The determination unit compares a difference between the authentication information and the input information indicated by a verification result of the authentication information and the input information obtained by the decryption by the decryption unit, and compares the difference from the threshold. 5. The one-to-many authentication system according to claim 4, wherein the authentication of the user is determined to be successful if the user authentication is smaller than 5.   The one-to-many authentication system according to claim 5, wherein the condition is set based on the feature and the threshold value.   The pair of conditions according to claim 6, wherein the condition is defined by a numerical range from a value obtained by subtracting the threshold value from a value indicating the feature to a value obtained by adding the value indicating the feature and the threshold value. Multi-authentication system.   The one-to-many authentication system according to any one of claims 1 to 7, wherein the feature is the number of bits indicating 1 in the bit string of the key information. Computer
Input information entered as an authentication target by referring to a storage unit that stores encrypted authentication information obtained by encrypting authentication information used for user authentication with specific rules using key information for a plurality of users And a plurality of encrypted authentication information stored in the storage unit based on the specific rule while maintaining a state where the authentication information is encrypted,
Based on the comparison result, identify the encryption authentication information that meets the conditions determined based on the characteristics of the key information,
An authentication method comprising: performing a process of determining success or failure of authentication for the authentication target based on the specified encrypted authentication information, the input information, and the key information. On the computer,
Input information entered as an authentication target by referring to a storage unit that stores encrypted authentication information obtained by encrypting authentication information used for user authentication with specific rules using key information for a plurality of users And a plurality of encrypted authentication information stored in the storage unit based on the specific rule while maintaining a state where the authentication information is encrypted,
Based on the comparison result, identify the encryption authentication information that meets the conditions determined based on the characteristics of the key information,
An authentication program for executing a process of determining success or failure of authentication for the authentication target based on the specified encrypted authentication information, the input information, and the key information.