JP2018042045A - Collation system and method and program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a collation system and a method and a program for reducing the objects of collation processing, by circumventing information leakage related to registration data.SOLUTION: A collation method includes a first step S1 of generating encryption registration data by encrypting plaintext data of a registration object, and generating partial registration data corresponding the plaintext data part of the registration object, a second step S2 of registering them in a storage device, and generating encrypted collation data by encrypting the plaintext data of collation object, and a third step S3 of generating partial collation data corresponding to the plaintext data of collation object, and performing collation with the encrypted collation data for the encrypted registration data corresponding to the partial registration data where the distance to the partial collation data is equal to or less than a predetermined value.SELECTED DRAWING: Figure 14

Description

  The present invention relates to a verification system, method, and program.

  In recent years, with the spread of the cloud, user data is placed on computing resources connected to a network, and services based on the data are rapidly spreading. In such services, the opportunity for users to handle sensitive data is increasing, so it has become important for users to ensure that their data is managed safely. Under such circumstances, research and development of techniques for managing data while encrypting it in an open network environment and performing search, statistical processing, etc. without decrypting the data are being actively conducted.

  In recent years, crimes with vulnerability to personal authentication using conventional passwords and magnetic cards have frequently occurred, and biometric authentication technology based on biometric features such as fingerprints and veins, which are more secure, has attracted attention. Collecting.

  In biometric authentication, it is necessary to store a template related to biometric information in a database in order to verify authentication information. Biometric information such as fingerprints and veins is basically data that does not change throughout the lifetime. When information leaks, it is the information that requires the most confidentiality. For this reason, in order to prevent “spoofing” from being performed even if a template leaks, a template protection type biometric authentication technique that performs authentication while keeping template information secret has become important.

  In Patent Document 1, a first node (corresponding to a client) encrypts authentication data with a public key received from a second node (corresponding to an authentication node) that generates a public key and a secret key. 3 is transmitted to the third node (corresponding to the server), and when the data to be authenticated is received, the authentication data is obtained from the third node, and the distance between the data to be authenticated and the authentication data is calculated while encrypted with the public key. A method is disclosed in which a value obtained by substituting the distance into a polynomial obtained from a node and encrypted in a public key is generated as verification data and transmitted to a second node. The polynomial includes a threshold value of the distance between the authentication data and the data to be authenticated as a parameter. In Patent Literature 1, authentication data and data to be authenticated can be concealed from the server by introducing a reliable third party into the system. However, this related technique has a large load on a third party in verification.

  In Patent Document 2, the first node generates an evaluation formula for evaluating the distance from the authentication data, and encrypts the coefficient of the evaluation formula with the public key received from the second node that generates the public key and the secret key. When the data to be authenticated is received and the data to be authenticated is received, the encrypted coefficient is obtained from the third node, and the data to be authenticated is obtained based on the data to be authenticated and the encrypted coefficient. A method of generating an evaluation value for collation with authentication data and transmitting the evaluation value to a second node is disclosed.

  In Patent Literature 3, an encrypted random similarity calculation unit (similarity intermediate ciphertext calculation unit) includes an encrypted feature vector (comparison ciphertext) encrypted using a public key of a decryption device, and a decryption device. Two encrypted feature vectors C, based on an encrypted feature vector (target ciphertext) encrypted using a public key and a random number (temporary key) generated by a random number generator (temporary key generator), With C ′ still encrypted, the first step of calculating the similarity is calculated to calculate the second challenge C ^. The decryption device decrypts the second challenge C ^ with the private key of the decryption device, and performs the second step of the similarity calculation in a state where the decrypted result is still encrypted with the temporary key. Response Z is calculated. A configuration is disclosed in which the plaintext similarity extraction unit (similarity calculation unit) calculates the similarity by decrypting the second response Z with a temporary key.

  Patent Document 4 discloses a registration client that functions as a data registration transmission / reception device that transmits encrypted deposit data to a database server, and a search client that transmits a concealed search query to a database server and receives a search result. A configuration is disclosed that includes a search client that functions as a transmission / reception device, a database server that functions as a secret search device that registers encrypted deposit data and the like in a database and searches for data in the database. In Patent Document 4, data stored in a database server is read from a storage device, a concealment index is generated from the contents of the consignment data using a searchable encryption specific algorithm, and the generated concealment index is notified to a registration unit, or a memory Alternatively, the data is temporarily output to a storage device. In the secret search processing, the database server first selects a representative (pivot) of the concealment index in each cluster, and collates this pivot with the trap door that conceals the search keyword included in the search query by the search client. By doing so, the priority order of the clusters at the time of registration data collation is determined. The database server collates all registered data for each cluster based on the priority order, and outputs the search result to the search client.

  In Patent Document 5, when registering reference information used for biometric authentication, a registration sensor extracts a feature amount of a part of a normal user's living body to vectorize the feature amount, and the vectorized feature amount is homomorphic. In addition, the registration sensor transmits the homomorphic encrypted feature quantity to the calculation server, and registers it as encryption registration data in the calculation server database. In order to authenticate whether the user is a regular user, the matching sensor extracts and vectorizes a part of the features of the user's biological body, homomorphically encrypts the vectorized features, and is homomorphically encrypted. The feature value is transmitted to the calculation server. The calculation server calculates the concealment distance between the received homomorphic encrypted feature and the registered encryption registration data, obtains the concealment distance calculation result, and sends it to the certificate authority with the homomorphic encryption secret key To do. The certificate authority decrypts the transmitted secret distance calculation result, compares the decryption result with a threshold value, and authenticates the user when the decryption result is smaller than the threshold value. The Hamming distance is used as the secret distance. The disclosure of Patent Document 5 is an invention related to exact match search.

  In addition to the above, the following non-patent documents are also referred to.

International Publication No. 2014/185450 International Publication No. 2014/185447 International Publication No. 2012/114454 International Publication No. 2013/080365 JP 2014-126865 A

“Confidential fingerprint authentication method with small template size”, Higo, Isshiki, Mori, Ohana, Cryptography and Information Security Symposium (SCIS2015), 2015.

“Privacy-Preserving Fingerprint Authentication Resistant to Hill-Climbing Attacks”, Haruna Higo, Toshiyuki Isshiki, Kengo Mori, Satoshi Obana, SAC2015, 2015. “Confidential biometric authentication method with little information disclosure at the time of authentication”, Higo, Isshiki, Mori, Ohana, Cryptography and Information Security Symposium (SCIS2016), 2016.

  Patent Document 2, Non-Patent Document 1, and Patent Document 3 disclose a technique in which a load of a third party in the verification is reduced in a system in which a reliable third party is introduced. However, since these methods have a high calculation cost, they correspond only to 1: 1 authentication and are not suitable for 1: N authentication. The 1: 1 authentication is authentication in which the person to be authenticated claims who he is (the person to be authenticated), and the verifier verifies that the person to be authenticated is the person claimed by the person to be authenticated. is there. In 1: N authentication, the person to be authenticated claims that he (the person to be authenticated) belongs to a certain set (organization), and the verifier belongs to the group claimed by the person to be authenticated. It is authentication that verifies that.

  It is generally known that 1: N authentication can be configured by performing 1: 1 authentication with each person registered in the set N times.

  However, since the methods described in Patent Document 2, Non-Patent Document 1, and Patent Document 3 require a large calculation cost for one-time 1: 1 authentication, when N of 1: N authentication is large, Be unrealistic.

  Therefore, in 1: N authentication, a method with a low calculation cost per 1: 1 authentication and a method for reducing N to be verified are desired.

  In general, in biometric authentication that does not conceal biometric information, when 1: N authentication is performed, grouping using a rough classification (for example, classification based on a fingerprint emblem) based on a feature amount obtained from a biometric or a part of biometric information The efficiency is improved by pruning the verification candidates by performing simple verification using.

  However, when collation is performed while keeping the biometric information secret, the biometric information sent from the person to be authenticated is kept secret by encryption or the like. For this reason, it is not possible to perform rough classification based on feature amounts or simple verification using a part of biological information.

In a ciphertext verification system that allows ambiguity of encrypted data,
While keeping your data secret
There is a problem that the reduction of the number of ciphertexts to be verified cannot be satisfied at the same time.

  The present invention has been made to solve the above-described problems, and an object of the present invention is to provide a system, method, and program capable of avoiding information leakage related to registered data and reducing the number of targets to be collated. There is.

According to one aspect of the present invention, encrypted registration data obtained by encrypting plaintext data to be registered is generated, partial registration data corresponding to the plaintext data portion to be registered is generated, and registered in a storage device. A first means;
Second means for generating encrypted collation data obtained by encrypting the plaintext data to be collated and generating partial collation data corresponding to the portion of the plaintext data to be collated;
A third means for collating the encrypted registration data corresponding to the partial registration data whose distance to the partial verification data is equal to or less than a predetermined value; Is provided.

According to one aspect of the present invention, encrypted registration data obtained by encrypting plaintext data to be registered is generated, partial registration data corresponding to the portion of the plaintext data to be registered is generated, and these are stored in a storage device. A first step of registration;
A second step of generating encrypted collation data obtained by encrypting the plaintext data to be collated, and generating partial collation data corresponding to a portion of the plaintext data to be collated;
And a third step of collating the encrypted registration data corresponding to the partial registration data corresponding to the partial registration data whose distance to the partial verification data is equal to or less than a predetermined value. A verification method is provided.

According to one aspect of the present invention, encrypted registration data obtained by encrypting plaintext data to be registered is generated, partial registration data corresponding to the plaintext data portion to be registered is generated, and registered in a storage device. A first process;
A second process of generating encrypted collation data obtained by encrypting the plaintext data to be collated, and generating partial collation data corresponding to a portion of the plaintext data to be collated;
A third process for collating the encrypted registration data corresponding to the partial registration data corresponding to the partial registration data whose distance from the partial verification data is equal to or less than a predetermined value; A program to be executed by a computer is provided. According to the present invention, a computer-readable recording medium (for example, RAM (Random Access Memory), ROM (Read Only Memory), or EEPROM (Electrically Erasable and Programmable ROM)), HDD ( Non-transitory computer readable recording media (Hard Disk Drive), CD (Compact Disc), DVD (Digital Versatile Disc), etc. are provided.

  According to the present invention, it is possible to avoid information leakage related to registered data and to reduce the number of targets for collation processing.

It is a figure which illustrates the structure of the whole system of one Embodiment of this invention. (A) And (B) is a figure which illustrates the structure of the registration data production | generation apparatus and registration apparatus of one Embodiment of this invention. (A) And (B) is a figure which illustrates the structure of the memory | storage device and key generation apparatus of one Embodiment of this invention. (A) And (B) is a figure which illustrates the structure of the collation request | requirement apparatus and collation apparatus of one Embodiment of this invention. It is a figure which illustrates the composition of the collation auxiliary device of one embodiment of the present invention. It is a figure explaining operation | movement of one Embodiment of this invention. It is a figure explaining operation | movement of one Embodiment of this invention. It is a figure explaining operation | movement of one Embodiment of this invention. It is a figure explaining operation | movement of one Embodiment of this invention. It is a figure explaining operation | movement of one Embodiment of this invention. It is a figure explaining operation | movement of one Embodiment of this invention. (A) And (B) is a figure which illustrates the structure of the registration data production | generation apparatus and collation request | requirement apparatus of the modification of one Embodiment of this invention. (A) And (B) is a figure which illustrates the structure of the collation apparatus and collation auxiliary | assistance apparatus of the modification of one Embodiment of this invention. It is a figure which illustrates one form of this invention. It is a figure which illustrates another form of this invention.

An embodiment of the present invention will be described. FIG. 14 is a diagram illustrating an embodiment of the present invention. FIG. 14 illustrates an operation principle of one embodiment of the present invention. Referring to FIG. 14, a first step of generating encrypted registration data obtained by encrypting plaintext data to be registered, generating partial registration data corresponding to the plaintext data portion to be registered, and registering it in a storage device. (S1),
A second step (S2) of generating encrypted collation data obtained by encrypting the plaintext data to be collated, and generating partial collation data corresponding to the portion of the plaintext data to be collated;
A third step (S3) in which the encrypted registration data corresponding to the partial registration data whose distance to the partial verification data is equal to or less than a predetermined value is compared with the encrypted verification data; Have.

According to an aspect of the present invention, in the first step (S1),
The plaintext data to be registered and the partial registration data in plaintext may be encrypted with a public key of homomorphic encryption, and the encrypted registration data and the encrypted partial registration data may be generated and registered in the storage device.

  In the second step (S2), the plaintext data to be collated and the plaintext partial collation data may be encrypted with the public key of the homomorphic encryption to generate the encrypted collation data and the encrypted partial collation data. .

In the third step (S3), the following steps may be included.
The encrypted partial collation data and the encrypted partial registration data are encrypted and the distance between the partial collation data and the partial registration data is calculated and a collation (collation assistance) process is requested.
In the collation (collation assistance) process, the distance is decrypted with the secret key of the homomorphic encryption.
When the distance between the partial verification data and the partial registration data is equal to or smaller than a predetermined first value (t ′) as a result of the verification (verification assistance) process (when simple verification is accepted), the encryption A distance is calculated while the verification data and the encrypted registration data are encrypted, and a verification (verification assistance) process is requested.
In the verification (auxiliary) processing, the distance is decrypted with the secret key of the homomorphic encryption, and verification data and verification data are verified.

According to an aspect of the present invention, the third step (S3) may include the following steps.
In the verification (verification assistance) process, the distance between the encrypted partial verification data and the encrypted partial registration data is received, and the distance is decrypted using a secret key of the homomorphic encryption.
It is determined whether or not the distance between the decrypted partial collation data and the partial registration data is equal to or less than the first value (t ′) determined in advance.
If the distance between the partial verification data and the partial registration data is equal to or less than the first value determined in advance, the encrypted verification data and the encrypted registration data are encrypted and the distance is calculated and verified ( Request processing for verification.
In the verification (verification assistance) process, the distance between the encrypted verification data and the encrypted registration data is decrypted using the secret key of the homomorphic encryption.
The collation process is performed by determining whether the distance between the decrypted collation data and the registered data is equal to or less than a predetermined second value (t).

According to another aspect of the present invention, in the first step (S1), the plaintext data to be registered may be encrypted with a homomorphic public key to generate the encrypted registration data.
In the second step (S2), the plaintext data to be verified may be encrypted with a public key of homomorphic encryption, and the encrypted verification data may be generated.
In the third step (S3), calculating a distance between the plaintext partial matching data and the plaintext partial registration data;
When the distance between the partial verification data and the partial registration data is equal to or less than a predetermined first value (t ′), the distance is calculated while the encrypted verification data and the encrypted registration data are encrypted. Steps,
Decrypting the distance between the encrypted verification data and the encrypted registration data using the secret key of the homomorphic encryption;
You may make it include the step which performs a collation process by determining whether the distance between the said collation data and the said registration data is below a predetermined 2nd value (t).

  According to another aspect of the present invention, partial data (partial registration data or partial collation data) may be encrypted in either the first step or the second step.

  FIG. 15 is a diagram exemplifying a form in which the method according to the embodiment described with reference to FIG. 14 is realized by a computer. Referring to FIG. 15, the computer device 1 includes, for example, a CPU (Central Processing Unit) 2, a storage device (memory) 3, an input / output (I / O) interface 4, and a communication interface 5. The storage device 3 includes a hard disk drive (HDD), a semiconductor memory (for example, a solid state drive (SSD), a dynamic random access memory (DRAM), a static random access memory (SRAM), a read only read only memory (ROM), an electric The read-only memory (Electrically Erasable and Programmable Read-Only Memory), a compact disc (CD), and a digital versatile disc (DVD)) that can be erased and programmed can be configured, or a plurality of combinations. The storage device 3 stores a program executed by the CPU 2. The CPU 2 executes the program stored in the storage device 3 to execute the processing of the steps in FIG. The computer apparatus 1 may be connected to, for example, a network (local area network or wide area network) via the communication interface 5 and communicate with another computer apparatus (not shown).

  Note that steps S1 to S3 (or its substeps) in FIG. 14 may be implemented in cooperation with a plurality of computer apparatuses 1 that are connected for communication via a network. The computer apparatus 1 is connected to a sensor 6 (option) such as a fingerprint sensor or a vein sensor via the I / O interface 4 to register biometric information (digital data) such as a fingerprint to be registered or a fingerprint to be collated. You may make it acquire. When the computer device 1 of FIG. 15 constitutes a registration device, the storage device 3 may store encrypted registration data or partial registration data.

  According to the present invention, at the time of registration, a ciphertext of data and a partial ciphertext of data are registered as a pair, and at the time of collation, a ciphertext of a part of data to be collated with a part of data is used for collation. An efficient 1: N ciphertext matching system is realized by matching a part of the target data with registered data close to a part. It is suitable to be applied to a collation system that allows ambiguity of encrypted data, and in particular, in a situation where both data to be collated and data to be collated are encrypted, an index of ambiguity, Applicable to collation system in case of plain text distance.

  According to the present invention, at the time of data registration, the ciphertext of the data is registered, and at the time of verification, the distance between the plaintext data registered as encrypted and the plaintext data to be verified is allowed. It is possible to verify that it is within range. Further, the number of verification target data can be reduced by verifying a part of the registration data and the verification target data. The registered data (encrypted registration data, encrypted partial registration data) is always encrypted, and leakage of information about the data is avoided. For this reason, it becomes possible to use a system safely and safely. This makes it possible to use an efficient 1: N ciphertext matching system. In the following, some exemplary embodiments will be described.

<Exemplary Embodiment 1>
An exemplary embodiment of the present invention will be described in detail with reference to the drawings. Referring to FIG. 1, a system according to an embodiment includes a registration data generation device 100 that generates registration data obtained by encrypting data, a registration device 200 that receives registration data and registers it in a storage device 300, and a key generation. The apparatus 400, the collation request | requirement apparatus 500, the collation apparatus 600, and the collation assistance apparatus 700 are provided. These devices may include a processor (CPU), a storage device (memory), a communication interface (IF), and the like, and may be configured as a plurality of node devices that are communicatively connected via a network (private network or wide area network). Each device will be described with reference to FIGS.

  Referring to FIG. 2A, the registration data generation device 100 includes a registration data generation unit 101, a partial registration data generation unit 102, a partial registration data encryption unit 103, a registration data encryption unit 104, and registration data. A sending unit 105 and a communication interface (IF) 106 are provided. The registration data generation unit 101 generates registration target data (also referred to as “plaintext registration data”). The partial registration data generation unit 102 receives the plaintext registration data from the registration data generation unit 101 and generates partial registration data. The partial registration data encryption unit 103 receives the partial registration data from the partial registration data generation unit 102, receives the public key generated by the key generation device 400, encrypts the partial registration data using the public key, and encrypts it. Generate partial registration data. The registration data encryption unit 104 receives plain text registration data from the registration data generation unit 101, receives the public key from the key generation device 400 as input, and generates encrypted registration data using the public key. The registration data sending unit 105 receives the encrypted partial registration data from the partial registration data generation unit 102 and the encrypted registration data from the registration data encryption unit 104 as input, generates registration data, and via the communication IF 106, It is sent to the registration device 200.

  Referring to FIG. 2B, the registration device 200 includes a registration processing unit 201, a registration data receiving unit 202, and a communication IF 203. The registration processing unit 201 receives registration data received from the registration data generating apparatus 100 via the communication IF 203 and the registration data receiving unit 202, and performs registration processing of registration data.

  Referring to FIG. 3A, the storage device 300 includes an encrypted partial data storage unit 301, an encrypted data storage unit 302, and a communication IF 303. The storage device 300 includes a hard disk drive (HDD), a solid state drive (SSD), a dynamic random access memory (DRAM), or a static random access memory (SRAM), and an electrically programmable erasable read only memory (Electrically Erasable). and Programmable Read Only Memory (EEPROM) or the like.

  Referring to FIG. 3B, the key generation device 400 includes a key generation unit 401 and a communication IF 402. The key generation unit 401 receives a security parameter and generates a public key and a secret key.

  Referring to FIG. 4A, collation request apparatus 500 includes collation data generation unit 501, partial collation data generation unit 502, partial collation data encryption unit 503, collation data encryption unit 504, and collation query transmission. Unit 505 and a communication IF 506. The collation data generation unit 501 generates plaintext data to be collated (referred to as “plaintext collation data”). The partial collation data generation unit 502 receives the plain text collation data and generates partial collation data. The partial verification data encryption unit 503 receives the partial verification data and the public key generated by the key generation device 400 as input, and generates encrypted partial verification data. The verification data encryption unit 504 receives the plaintext verification data and the public key generated by the key generation device 400, and generates encrypted plaintext verification data. The verification query sending unit 505 receives the encrypted verification data and the encrypted partial verification data, generates a verification query, and sends it to the verification device 600 via the communication IF 506.

  Referring to FIG. 4B, the verification device 600 includes an encrypted partial distance generation unit 601, a partial data verification auxiliary request unit 602, an encrypted verification data distance generation unit 603, a verification auxiliary request unit 604, a verification A processing unit 605, a collation query receiving unit 606, and a communication IF 607 are provided. The encrypted partial distance generation unit 601 receives the encrypted partial registration data stored in the encrypted partial data storage unit 301 of the storage device 300 and the encrypted partial collation data included in the collation query as inputs. Is generated. The partial data verification assistance request unit 602 receives the encrypted partial distance and generates a partial data verification assistance request. The encrypted verification data distance generation unit 603 corresponds to the partial data verification auxiliary result generated by the verification auxiliary device 700 according to the partial data verification auxiliary request, and the encrypted registration data stored in the storage device 300 corresponding to the partial data verification auxiliary result. Is input, and an encrypted distance that is a ciphertext of the distance between the verification data and the registered data is generated. The verification assistance request unit 604 generates a verification assistance request with the encrypted distance as an input. In accordance with the verification assistance request, the verification processing unit 605 generates the verification result using the verification assistance result generated by the verification assistance device 700 as an input via the communication IF 607.

  Referring to FIG. 5, the verification assisting device 700 includes a key storage unit 701, a partial data verification assisting unit 702, a verification assisting unit 703, and a communication IF 704.

  The key storage unit 701 receives and stores the secret key generated by the key generation device 400 via the communication IF 704. The partial data verification assistance unit 702 receives the secret key stored in the key storage unit 701 and the partial data verification assistance request sent from the verification device 600, and generates a partial data verification assistance result. The partial data collation assisting unit 702 receives the secret key stored in the key storage unit 701 and the collation assist request received from the collation device 600 and received via the communication IF 704, and generates a collation assist result.

  Next, the operation of this embodiment will be described. The operation of the ciphertext verification system of this embodiment is roughly divided into four phases: a registration setup phase, a data registration phase, a verification setup phase, and a ciphertext verification phase.

  The registration setup phase is a phase in which security parameters are input to the key generation device 400, a public key and a secret key of homomorphic encryption are generated, and necessary keys are sent to each device.

  The collation setup phase is a phase in which the key generation device 400 sends the public key and secret key generated in the registration setup phase to each device.

  The data registration phase encrypts plaintext registration data generated by the registration data generation device 100 and plaintext partial registration data (also referred to as “partial plaintext registration data”) that is a part of the plaintext registration data, and stores the storage device 300. This is the phase to register with.

  The ciphertext verification phase is a method in which the input data is close to the plaintext of the encrypted data stored in the storage device 300 (a certain distance is small) while concealing the plaintext verification data generated by the verification requesting device 500. This is a phase for judging whether or not there is. Hereinafter, the operation in each phase will be described in detail.

<Registration setup phase>
FIG. 6 is a diagram illustrating a registration setup phase. The key generation unit 401 of the key generation apparatus 400 receives the security parameter k and generates a public key and a secret key of homomorphic encryption (step S101), and registers the public key with the registration data generation apparatus 100 via the communication IF 402. It is sent to the apparatus 200 (steps S102 and S103).

Encryption function ENC of homomorphic encryption method for addition or multiplication for plaintext m1 and m2
With respect to
ENC (pk, m1) (+) ENC (pk, m2) = ENC (pk, m1 + m2) (additive homomorphism) or
ENC (pk, m1) (*) ENC (pk, m2) = ENC (pk, m1 * m2) (multiplicative homomorphism)
Holds. Here, (+) and (*) are binary operators determined by the encryption method. As homomorphic encryption methods, RSA (Rivest Shamir Adleman) encryption used for multiplication, additive Elgamal encryption used for addition, and the like are known.

<Data registration phase>
FIG. 7 is a diagram illustrating a data registration phase.

  The registration data generation unit 101 of the registration data generation device 100 generates plaintext registration data (step S201).

  Next, the partial registration data generation unit 102 generates partial plaintext registration data from the plaintext registration data (step S202).

  Next, the partial registration data encryption unit 103 receives the partial plaintext registration data and the public key generated by the key generation device 400, and generates encrypted partial registration data (step S203).

  Next, the registration data encryption unit 104 receives the plain text registration data and the public key, and generates encrypted registration data (step S204).

  Next, the registration data sending unit 105 receives the encrypted partial registration data and the encrypted registration data, and generates the encrypted partial registration data and registration data including the encrypted registration data (step S205).

  The registration data sending unit 105 sends the registration data to the registration device 200 via the communication IF 106 (step S206).

  The registration processing unit 201 of the registration device 200 stores the encrypted partial registration data included in the received registration data in the encrypted partial data storage unit 301 of the storage device 300 via the communication IF 203 (step S207). The registered data is stored in the encrypted data storage unit 302 of the storage device 300 via the communication IF 203 (step S209).

<Verification setup phase>
FIG. 8 is a diagram illustrating the collation setup phase. The key generation device 400 transmits the homomorphic public key generated in the registration setup phase to the verification request device 500, the verification device 600, and the verification auxiliary device 700 via the communication IF 402 (steps S301 to S303). Also, the key generation device 400 sends the homomorphic encryption secret key generated in the registration setup phase to the verification assistant device 700 via the communication IF 402 (step S304).

  The verification auxiliary device 700 stores the secret key received via the communication IF 704 in the key storage unit 701 (step S305).

<Ciphertext verification phase>
FIG. 9 is a diagram illustrating the ciphertext verification phase. The collation data generation unit 501 of the collation request apparatus 500 generates plain text collation data (step S401).

  Next, the partial collation data generation unit 502 receives the plaintext collation data generated by the collation data generation unit 501 and generates partial collation data (step S402).

  Next, the partial collation data encryption unit 503 generates encrypted partial collation data using the partial collation data generated by the partial collation data generation unit 502 and the public key generated by the key generation device 400 as inputs (step S403). ).

  Next, the collation data encryption unit 504 receives the plaintext collation data generated by the collation data generation unit 501 and the public key, and generates encrypted collation data (step S404).

  Next, the verification query sending unit 505 receives the encrypted partial verification data generated by the partial verification data encryption unit 503 and the encrypted verification data generated by the verification data encryption unit 504 as input. Then, a verification query including the encrypted verification data is generated (step S405).

  The verification query sending unit 505 sends the verification query to the verification device 600 via the communication IF 506 (step S406).

  Next, the encrypted partial distance generation unit 601 of the verification device 600 that has received the verification query transmits the encrypted partial verification data included in the verification query and the encrypted partial data storage unit 301 of the storage device 300. Using the partial registration data and the public key as input, an encrypted partial distance is generated (step S407). Here, when a plurality of pieces of data are stored in the encrypted partial data storage unit 301, step S407 may be performed a plurality of times. In this case, the input to the next partial data verification assistance request unit 602 is a plurality of encrypted partial distances.

  Next, the partial data verification assistance request unit 602 of the verification device 600 generates a partial data verification assistance request using the encrypted partial distance as an input (step S408).

  The partial data verification assistance request unit 602 sends a partial data verification assistance request to the verification assistance device 700 (step S409).

  Upon receiving the partial data verification assistance request, the partial data verification assistance unit 702 of the verification assistance device 700 receives the partial data verification assistance request and the secret key stored in the key storage unit 701 and generates a partial data verification assistance result. (Step S410), and sent to the verification device 600 via the communication IF 704 (Step S411).

  The encrypted verification data distance generation unit 603 of the verification device 600 that has received the partial data verification auxiliary result receives the encrypted registration data defined by the partial data verification auxiliary result from the encrypted data storage unit 302 of the storage device 300. Then, the encrypted collation data Z included in the collation query, the encrypted registration data Z ′, and the public key pk are input, and the encryption distance ENC (pk, d (Z, Z ′)) is generated (step S412). .

  Next, the verification assistance request unit 604 of the verification device 600 receives the encrypted distance, generates a verification assistance request (step S413), and sends it to the verification assistance device 700 (step S414).

  The collation assisting unit 703 of the collation assisting device 700 that has received the collation assisting request receives the secret key stored in the key storage unit 701 and the collation assisting request as input, generates a collation assist result (step S415), and the collation device 600. (Step S416).

  The collation processing unit 605 of the collation apparatus 600 that has received the collation auxiliary result generates a collation result (step S417) and outputs it (step S418).

<Example 1>
Next, the exemplary embodiment described above will be described with reference to more detailed examples. In this embodiment, the square n-dimensional Euclidean distance is used as the distance. That is,
Two n-dimensional vectors
X = (x [1], x [2],…, x [n])
Y = (y [1], y [2],…, y [n]
)
The distance d (X, Y) between X and Y is
d (X, Y) = [(x [1] -y [1]) ^ {2} + (x [2] -y [2]) ^ {2} +… + (x [n] -y [ n]) ^ {2}]
It is defined as This square n-dimensional Euclidean distance is a conditional expression that defines the distance (1. (Nonnegative): d (X, Y)> = 0, X = Y ⇒ d (X, Y) = 0, 2. (Symmetry) ): D (X, Y) = d (Y, X), 3. (triangular inequality): d (X, Y) + d (Y, Z)> = d (X, Y)) Although not satisfied, it is known that it can be used for match determination as used in the present embodiment.

  When d (X, Y) is equal to or smaller than the threshold t, X and Y are determined to be close, and when larger than the threshold t, X and Y are determined to be far. In the present embodiment, when X and Y are close, it is determined that they match (match acceptance), and when they are far away, it is determined that they do not match (check non-acceptance).

  Although not particularly limited, in this embodiment, Somewhat homomorphic encryption is used. Somewhat homomorphic cipher is a cipher that can calculate an arbitrary number of plaintext additions and a constant number of multiplications while encrypted. Somewhat homomorphic encryption consists of five algorithms: key generation KeyGen, encryption Enc, decryption Dec, homomorphic addition HomAdd, and homomorphic multiplication HomMul. Each will be described below.

Key generation KeyGen: The security parameter 1 ^ k is input and the public key pk and secret key sk are output.
(pk, sk) ← KeyGen (1 ^ k)
.

Encryption Enc: Public key pk and message M are input and ciphertext C is output.
C ← Enc (pk, M).

Decryption Dec: Secret key sk and ciphertext C are input, and message M is output.
M ← Dec (sk, C)
.

Homomorphic addition HomAdd:
Using public key pk, ciphertext C_1 ← Enc (pk, M_1) and C_2 ← Enc (pk, M_2) as inputs,
Ciphertext C_3 ← Enc (pk, M_1 + M_2) is output. this,
C_3 ← HomAdd (pk, C_1, C_2)
.

Homomorphic multiplication HomMul: Using public key pk and ciphertext C_1 ← Enc (pk, M_1) and C_2 ← Enc (pk, M_2) as inputs
Ciphertext C_3 ← Enc (pk, M_1 ・ M_2)
Is output. this,
C_3 ← HomMul (pk, C_1, C_2)
.

When using somewhat homomorphic encryption, two n-dimensional vectors
X = (x [1], x [2],…, x [n]) and
Y = (y [1], y [2],…, y [n])
Ciphertext:
Enc (pk, X) = (Enc (pk, x [1]), Enc (pk, x [2]),…, Enc (pk, x [n])) and
Enc (pk, Y) = (Enc (pk, y [1]), Enc (pk, y [2]), ..., Enc (pk, y [n]))
Against
The ciphertext Enc (pk, d (X, Y)) of the distance between X and Y can be calculated with X and Y encrypted.

  The operation of each phase in the present embodiment will be described below with reference to the drawings.

  The key generation unit 401 of the key generation device 400 having the security parameter 1 ^ k as an input executes the key generation algorithm KeyGen (1 ^ k) of the Somewhat homomorphic encryption to generate the public key pk and the secret key sk, and makes them public The key pk is sent to the registration data generation device 100 and the registration device 200 (steps S101 to S102 in FIG. 6).

<Data registration phase>
The registration data generation unit 101 of the registration data generation device 100 generates plaintext registration data X = (x [1],..., X [n]) (step S201 in FIG. 7).

  Next, the partial registration data generation unit 102 generates partial plaintext registration data X ′ = (x ′ [1],..., X ′ [from plaintext registration data X = (x [1],..., X [n]). m]) is generated (step S202 in FIG. 7).

  At this time, if n> m, partial plaintext registration data may be generated by any method, but if X and Y are close to a certain integer (threshold value) t ′ <= t (distance d (X, Y) <t), and the distance d (X ′, Y ′) between the respective partial data X ′ and Y ′ is set to be equal to or less than t ′. For example, if t ′ = t and {x ′ [1],..., X ′ [m]} is a subset of {x [1],. However, you may produce | generate by the method different from the above.

  Next, the partial registration data encryption unit 103 receives the partial plaintext registration data X ′ and the public key pk generated by the key generation device 400, and generates the encrypted partial registration data ENC (X ′) according to the following procedure. (Step S203 in FIG. 7).

<Registration setup phase>
1. For i = 1, ..., m,
enc_x '[i] = Enc (pk, x' [i])
Calculate

2. ENC (X ') = (enc_x' [1],…, enc_x '[m])
And

  Next, the registration data encryption unit 104 receives the plaintext registration data X and the public key pk generated by the key generation device 400, and generates encrypted registration data ENC (X) according to the following procedure (FIG. 7). Step S204).

1. For i = 1, ..., n,
enc_x [i] = Enc (pk, x [i])
Calculate

2. ENC (X) = (enc_x [1],…, enc_x [n])
And

3. Next, the registration data sending unit 105 receives the encrypted partial registration data ENC (X ′) and the encrypted registration data ENC (X) as input, and includes the encrypted partial registration data and the encrypted registration data. Data (ENC (X), ENC (X) ′) is generated (step S205 in FIG. 7) and transmitted to the registration device 200 (step S206 in FIG. 7). The registration device 200 includes the encrypted partial registration data, The encrypted registration data is sent to the storage device 300 (steps S207 and S208 in FIG. 7).

  The storage device 300 stores the encrypted partial registration data included in the received registration data in the encrypted partial data storage unit 301 and the encrypted registration data in the encrypted data storage unit 302 (step S209 in FIG. 7). .

<Verification setup phase>
The homomorphic encryption public key pk generated by the key generation device 400 during the registration setup phase is sent to the verification requesting device 500, the verification device 600, and the verification auxiliary device 700 (steps S301 to S303 in FIG. 8), and the secret key sk is sent. The data is sent to the verification assisting device 700 (step S304 in FIG. 8).

  The verification auxiliary device 700 stores the received secret key sk in the key storage unit 701 (step S305 in FIG. 8).

<Ciphertext verification phase>
The collation data generation unit 501 of the collation request device 500 receives the plaintext collation data.
Y = (y [1],…, y [n])
Is generated (step S401 in FIG. 9).

  Next, the partial collation data generation unit 502 receives the plain text collation data Y as input and generates partial collation data Y ′ = (y ′ [1],..., Y ′ [m]) (step S402 in FIG. 9). . Here, Y ′ is generated by the same method as in step S202 (FIG. 7) of the data registration phase.

  Next, the partial verification data encryption unit 503 receives the partial verification data Y ′ and the public key pk generated by the key generation device 400, and generates encrypted partial verification data ENC (Y ′) in the following procedure. (Step S403 in FIG. 9).

1. For i = 1, ..., m,
enc_y '[i] = Enc (pk, y' [i])
And

2. ENC (Y ′) = (enc_y ′ [1],..., Enc_y ′ [m]).

  Next, the verification data encryption unit 504 receives the plaintext verification data Y and the public key pk as input, and generates encrypted verification data ENC (Y) in the following procedure (step S404 in FIG. 9).

3. For i = 1, ..., n,
enc_y [i] = Enc (pk, y [i])
And

4. ENC (Y) = (enc_y [1],…, enc_y [n])
And

  Next, the verification query sending unit 505 receives the encrypted partial verification data ENC (Y ′) and the encrypted verification data ENC (Y), receives the encrypted partial verification data ENC (Y ′), and the encrypted verification data. A verification query (ENC (Y), ENC (Y ′)) including ENC (Y) is generated (step S405 in FIG. 9) and sent to the verification device 600 (step S406 in FIG. 9).

  Next, the encrypted partial distance generation unit 601 of the verification device 600 that has received the verification query (ENC (Y), ENC (Y ′)) includes the encrypted partial verification data ENC (Y ′) included in the verification query, The encrypted partial registration data ENC (X ′) stored in the encrypted partial data storage unit 301 of the storage device 300 and the public key pk are input, and the encrypted partial distance ENC (d ′) is generated by the following procedure. (Step S407 in FIG. 10).

1. For i = 1, ..., m
(a) Using homomorphic addition HomAdd,
From Enc (pk, x '[i]) and Enc (pk, y' [i])
Enc (pk, x '[i] -y' [i])
Calculate
(b) Using homomorphic multiplication HomMul,
From Enc (pk, x '[i] -y' [i])
Enc (pk, (x '[i] -y' [i]) ^ 2)
Calculate

2. Using homomorphic addition HomAdd,
From Enc (pk, (x '[1] -y' [1]) ^ 2), ..., Enc (pk, (x '[m] -y' [m]) ^ 2)
ENC (d ') = Enc (pk, d (X', Y '))
Calculate

  Here, when a plurality of data are stored in the encrypted partial data storage unit 301, step S407 may be performed a plurality of times. In that case, the input to the next partial data verification auxiliary request unit 602 is a plurality of encrypted partial distances {ENC (d ')}. For simplicity, one ENC (d ′) will be described below. It can be easily applied to the case of a plurality of encrypted partial distances.

  Next, the partial data verification assistance request unit 602 receives the encrypted partial distance ENC (d ′) as an input and generates a partial data verification assistance request (ENC (d ′)) (step S408 in FIG. 10). The data is sent to the apparatus 700 (step S409 in FIG. 10).

  Next, the partial data verification auxiliary unit 702 of the verification auxiliary device 700 that has received the partial data verification auxiliary request (ENC (d ′)) receives the partial data verification auxiliary request (ENC (d ′)) and the key storage unit 701. Using the stored secret key sk as input, the decryption Dec (sk, ENC (d ′)) of the homomorphic encryption is calculated (step S410 in FIG. 10).

The partial data verification auxiliary unit 702 of the verification auxiliary device 700
If the decryption result is less than or equal to the threshold t ′, the partial matching acceptance is
If not, reject partial verification
The partial data collation auxiliary result Result_y ′ is sent to the collation apparatus 600 (step S411 in FIG. 10).

  Next, the encrypted collation data distance generation unit 603 of the collation apparatus 600 that has received the partial data collation auxiliary result Result_y ′ outputs a rejection if the partial data verification auxiliary result Result_y ′ is unacceptable, and performs the subsequent operations. Stop.

  If the partial data verification auxiliary result Result_y ′ is accepted, the corresponding encrypted registration data ENC (X) is received from the encrypted data storage unit 302 of the storage device 300, and the encrypted verification data included in the verification query ENC (Y), the encrypted registration data ENC (X), and the public key pk are input, and an encrypted distance ENC (d) is generated as follows (step S412 in FIG. 10).

  Here, when the partial data verification assistance request is a plurality of ciphertexts, the partial data verification assistance result includes information (for example, data ID and index) that indicates which encrypted partial distance is the partial verification acceptance. can do.

  In this case, the data ID and the like are included in the partial data verification assistance request.

1. For i = 1, ..., n
(a) Using homomorphic addition HomAdd,
From Enc (pk, x [i]) and Enc (pk, y [i])
Enc (pk, x [i] -y [i])
Calculate
(b) Using homomorphic multiplication HomMul,
From Enc (pk, x [i] -y [i])
Enc (pk, (x [i] -y [i]) ^ 2)
Calculate

2. Using homomorphic addition HomAdd,
From Enc (pk, (x [1] -y [1]) ^ 2), ..., Enc (pk, (x [n] -y [n]) ^ 2)
ENC (d) = Enc (pk, d (X, Y))
Calculate

  Next, the verification assistance request unit 604 of the verification device 600 receives the encrypted distance ENC (d) as an input, generates a verification assistance request (ENC (d)) (step S413 in FIG. 10), and sends it to the verification assistance device 700. This is sent (step S414 in FIG. 10).

Upon receiving the verification assistance request (ENC (d)), the verification assistance unit 703 of the verification assistance device 700 receives the secret key sk stored in the key storage unit 701 and the verification assistance request (ENC (d)) as inputs, Decryption of homomorphic encryption
Execute Dec (sk, ENC (d)).

If the decryption result d is less than or equal to the threshold t, accept
If the decryption result d exceeds the threshold t, the rejection is set as a verification auxiliary result Result_y (step S415 in FIG. 11).
The verification auxiliary result Result_y is sent to the verification device 600 (step S416 in FIG. 11).

The collation processing unit 605 of the collation device 600 that has received the collation auxiliary result Result_y,
If Result_y is accepted, accept verification
If Result_y is not accepted, a verification rejection is generated as a verification result Result (step S417 in FIG. 11).
The collation result is output to collation requesting device 500 (step S418 in FIG. 11).

  In this embodiment, an example of the square Euclidean distance has been described, but the present invention can be easily applied to other distances (such as a Hamming distance and a Mahalanobis distance).

  In this embodiment, the example in which the partial data is also encrypted has been described. However, the partial data may not be encrypted.

  In this case, the collation device can calculate the distance between the plaintext partial data and the plaintext collation data at the time of collation, and determine whether the partial data is accepted or not.

  In the embodiment, the partial data is encrypted. However, as a modification, a case where the partial data is not encrypted will be described below.

<Modification 1 of Embodiment>
12 and 13 are diagrams for explaining the configuration of this modification. As illustrated in FIG. 12, the registration data generation device 100A does not include the partial registration data encryption unit 103, and the registration data transmission unit 105 transmits the encrypted registration data and the plaintext partial registration data to the registration device 200. . Further, the collation requesting device 500A does not include the partial collation data encryption unit 503, and the collation query sending unit 505 generates a query by inputting the encrypted collation data and the plaintext partial collation data, and transmits the query to the collation device 600. . Referring to FIG. 13, the collation apparatus 600 does not include the encrypted partial distance generation unit 601 and the partial data collation auxiliary request unit 602, and the distance between the plaintext partial registration data and the plaintext partial collation data is predetermined. A plaintext partial data collation processing unit 608 that determines whether or not the threshold value (t ′) is equal to or less and outputs partial collation acceptance / rejection is provided. Note that the encrypted partial data storage unit 301 of the storage device 300 in FIG. 3A is replaced with a storage unit that stores plaintext partial registration data.

  In the modification, the process of step S203 of FIG. 7 is deleted, and in step S205, the registration data includes encrypted registration data and plaintext partial registration data. In step S207, the plaintext partial registration data is transferred to the storage device 300. In step S209, the encrypted registration data and the plaintext partial registration data (partial plaintext registration data) are stored. The processing in steps S402 and 403 in FIG. 9 is deleted. In step S405 in FIG. 9, the collation query includes encrypted collation data and plaintext partial collation data (partial plaintext collation data). Further, steps S407 to S411 in FIG. 10 are omitted. Instead of steps S407 to S411 in FIG. 10, in the collation apparatus 600A, the plaintext partial data collation processing unit 608 determines the distance between the plaintext registration partial data (partial plaintext registration data) and the plaintext collation partial data (partial plaintext collation data). Is equal to or smaller than a threshold value t ′, and if the distance is equal to or smaller than the threshold value (t ′), partial verification is accepted, and if the distance exceeds the threshold value (t ′), partial verification is not accepted. In the case of partial collation acceptance, the encrypted collation data distance generation unit 603 executes the process of step S412 in FIG. 10 and the processes of step 413 in FIG. 10 to step 418 in FIG.

<Modification 2 of Embodiment>
Similarly, partial plaintext data may be encrypted only during registration or during verification. In this case, in the collation apparatus 600 (FIG. 4B), for example, the encrypted partial distance generation unit 601 is deleted, and the partial data collation auxiliary request unit 602 performs one plaintext of the partial registration data and the partial collation data. The verification assisting device 700 is requested to request partial data verification assistance for the partial data and the other encrypted partial data of the partial registration data and partial verification data. The partial data verification auxiliary unit 702 (FIG. 5) of the verification auxiliary device 700 decrypts the other part of the partial registration data and the partial verification data using the secret key, and then compares the partial registration data and the partial verification data. The distance between the one plaintext partial data of the data is obtained. The partial data collation assisting unit 702 (FIG. 5) accepts partial collation when the distance is equal to or smaller than the threshold (t ′), and rejects partial collation when the distance exceeds the threshold (t ′). May be transmitted to the verification device 600. The subsequent processing of the verification device 600 and the verification processing of the encrypted verification data and the encrypted registration data by the verification auxiliary device 700 are the same as those in the above-described embodiment, and thus the description thereof is omitted.

  Further, Non-Patent Document 2 and Non-Patent Document 3 describe a method of performing collation while keeping the distance between registered data and collation data secret, and the present invention can be combined with these methods.

The above embodiment can be applied to biometric authentication using a multi-value vector as a feature quantity.
Can be mentioned.

  For example, the feature quantity (features) extracted from the biometric information acquired by the fingerprint sensor or the vein sensor between the data input by the registration data generation apparatus 100 in the data registration phase and the data input by the verification request apparatus 500 in the ciphertext verification phase. Vector), the encrypted biometric data stored in the storage device and the encrypted biometric data sent from the verification requesting device are collected from the same person while keeping the biometric information secret. It is possible to determine whether the distance between the two input data is a certain number or less. In particular, it is known that biometric information cannot always stably acquire the same data, and the data acquired from the same person is similar (data with a small distance between each element can be acquired). Therefore, it is suitable for application to biometric authentication.

  The disclosures of Patent Documents 1-5 and Non-Patent Documents 1-3 are incorporated herein by reference. Within the scope of the entire disclosure (including claims) of the present invention, the embodiments and examples can be changed and adjusted based on the basic technical concept. Various disclosed elements (including elements in each supplementary note, elements in each embodiment, elements in each drawing, and the like) can be combined and selected within the scope of the claims of the present invention. That is, the present invention of course includes various variations and modifications that could be made by those skilled in the art according to the entire disclosure including the claims and the technical idea.

1 Computer device 2 CPU
3 Storage device 4 I / O interface 5 Communication interface 6 Sensor 100, 100A Registration data generation device 101 Registration data generation unit 102 Partial registration data generation unit 103 Partial registration data encryption unit 104 Registration data encryption unit 105 Registration data transmission unit 106 Communication interface (IF)
200 Registration Device 201 Registration Processing Unit 202 Registration Data Receiving Unit 203 Communication Interface (IF)
300 Storage Device 301 Encrypted Partial Data Storage Unit 302 Encrypted Data Storage Unit 303 Communication Interface (IF)
400 Key generation device 401 Key generation unit 402 Communication interface (IF)
500, 500A Collation request device 501 Collation data generation unit 502 Partial collation data generation unit 503 Partial collation data encryption unit 504 Collation data encryption unit 505 Collation query sending unit 506 Communication interface (IF)
600, 600A Verification device 601 Encrypted partial distance generation unit 602 Partial data verification auxiliary request unit 603 Encrypted verification data distance generation unit 604 Verification auxiliary request unit 605 Verification processing unit 606 Verification query reception unit 607 Communication interface (IF)
608 Plain text partial data collation processing unit 700, 700A Collation assist device 701 Key storage unit 702 Partial data collation assist unit 703 Collation assist unit 704 Communication interface (IF)

Claims (10)

Generating encrypted registration data obtained by encrypting plaintext data to be registered, generating partial registration data corresponding to a portion of the plaintext data to be registered, and registering in a storage device;
Second means for generating encrypted collation data obtained by encrypting the plaintext data to be collated and generating partial collation data corresponding to the portion of the plaintext data to be collated;
A third means for collating the encrypted registration data corresponding to the partial registration data corresponding to the partial registration data having a distance between the partial verification data and a predetermined value or less;
A collation system characterized by including. The first means includes
A registration data generation device that encrypts the plaintext data to be registered and the partial registration data of plaintext with a public key of a homomorphic encryption generated by a key generation device, and generates the encrypted registration data and the encrypted partial registration data When,
A registration device for registering the encrypted registration data and the encrypted partial registration data in the storage device;
With
The second means includes
The verification request device generates the encrypted verification data and the encrypted partial verification data by encrypting the plaintext data to be verified and the partial verification data of the plaintext respectively with the public key of the homomorphic encryption,
The third means includes
A verification device that calculates a distance while encrypting the encrypted partial verification data and the encrypted partial registration data;
Receiving the encrypted distance from the verification device, decrypting the distance using a secret key of the homomorphic encryption generated by the key generation device, and whether the distance is equal to or less than a predetermined value A verification auxiliary device for determining whether or not
With
The verification device is
When the distance between the partial verification data and the partial registration data is equal to or less than a predetermined first value, the distance is calculated while the encrypted verification data and the encrypted registration data are encrypted,
The verification assisting device receives the encrypted distance from the verification device, decrypts the distance using a secret key of the homomorphic encryption, and the distance is equal to or less than a predetermined second value. The collation system according to claim 1, wherein it is determined whether or not there is any. The first means includes
A registration data generation device that encrypts the plaintext data to be registered with a public key of a homomorphic encryption generated by a key generation device, and generates the encrypted registration data and plaintext partial registration data;
A registration device for registering the encrypted registration data and the plaintext partial registration data in the storage device;
With
The second means includes
A verification request device that encrypts the plaintext data to be verified with the public key of the homomorphic encryption and generates the encrypted verification data;
The third means includes
A plaintext partial data matching processing unit for calculating a distance between the plaintext partial matching data and the plaintext partial registration data;
When the distance between the plaintext partial verification data and the plaintext partial registration data is equal to or less than a predetermined first value, the distance is calculated while the encrypted verification data and the encrypted registration data are encrypted. A matching device to
The encrypted distance is received from the verification device, and the distance is decrypted using the secret key of the homomorphic encryption generated by the key generation device, and the distance is equal to or less than a predetermined second value. The collation system according to claim 1, further comprising a collation assisting device that determines whether or not.   The collation system according to claim 1, wherein either one of the first means and the second means encrypts the plaintext partial registration data or the plaintext partial collation data. Generating encrypted registration data obtained by encrypting plaintext data to be registered, generating partial registration data corresponding to a portion of the plaintext data to be registered, and registering them in a storage device;
A second step of generating encrypted collation data obtained by encrypting the plaintext data to be collated, and generating partial collation data corresponding to a portion of the plaintext data to be collated;
A third step of collating the encrypted registration data corresponding to the partial registration data corresponding to the partial registration data with a distance between the partial verification data and a predetermined value or less;
The collation method characterized by including. In the first step,
The plaintext data to be registered and the partial registration data in plaintext are each encrypted with a public key of homomorphic encryption, and the encrypted registration data and the encrypted partial registration data are generated and registered in the storage device,
In the second step,
Encrypting the plaintext data to be collated and the plaintext partial collation data with the public key of the homomorphic encryption to generate the encrypted collation data and the encrypted partial collation data,
In the third step,
Calculate the distance while encrypting the encrypted partial verification data and the encrypted partial registration data, and request verification.
When the distance between the partial verification data and the partial registration data is equal to or less than a predetermined first value,
Calculate the distance while encrypting the encrypted verification data and the encrypted registration data, and request verification.
6. The verification method according to claim 5, wherein the encrypted verification data and the encrypted registration data are verified. In the third step,
In response to the verification request, the distance between the encrypted partial verification data and the encrypted partial registration data is decrypted using a secret key of the homomorphic encryption, and the partial verification data and the partial registration data Whether or not the distance between the first and second values is less than or equal to the predetermined first value;
When the distance between the partial verification data and the partial registration data is equal to or less than the first value,
Calculate the distance while encrypting the encrypted verification data and the encrypted registration data, and request verification.
In response to the verification request, the distance between the encrypted verification data and the encrypted registration data is decrypted using the secret key of the homomorphic encryption,
The collation method according to claim 6, wherein collation is performed by determining whether or not a distance between the decrypted collation data and registered data is equal to or less than a predetermined second value. . In the first step,
Encrypting the plaintext data to be registered with a public key of homomorphic encryption to generate the encrypted registration data, registering the encrypted registration data and the plaintext partial registration data in the storage device;
In the second step,
Encrypting the plaintext data to be verified with a public key of homomorphic encryption to generate the encrypted verification data;
In the third step,
When the distance between the plaintext partial matching data and the plaintext partial registration data is equal to or less than a predetermined first value,
Calculate the distance while encrypting the encrypted verification data and the encrypted registration data, and request verification.
A distance between the encrypted verification data and the encrypted registration data is decrypted using the secret key of the homomorphic encryption, and a distance between the verification data and the registration data is predetermined. 6. The collation method according to claim 5, wherein collation processing is performed by determining whether or not the value is equal to or less than a value.   6. The collation method according to claim 5, wherein either one of the first step and the second step encrypts the plaintext partial registration data or the plaintext partial collation data. Generating encrypted registration data obtained by encrypting plaintext data to be registered, generating partial registration data corresponding to a portion of the plaintext data to be registered, and registering in a storage device;
A second process of generating encrypted collation data obtained by encrypting the plaintext data to be collated, and generating partial collation data corresponding to a portion of the plaintext data to be collated;
A third process for collating the encrypted registration data corresponding to the partial registration data whose distance to the partial verification data is equal to or less than a predetermined value;
A program that causes a computer to execute.

Images