WO2014185450A1

WO2014185450A1 - Verification system, node, verification method, and program

Info

Publication number: WO2014185450A1
Application number: PCT/JP2014/062820
Authority: WO
Inventors: 寿幸一色
Original assignee: 日本電気株式会社
Priority date: 2013-05-15
Filing date: 2014-05-14
Publication date: 2014-11-20
Also published as: JPWO2014185450A1

Abstract

A second node generates a public key/secret key pair, and transmits the public key to a first node. The first node uses the public key to encrypt authentication data, and transmits the encrypted authentication data to the third node. The third node stores the encrypted authentication data therein. When data to be authenticated that is to be verified against the authentication data is received, the first node acquires the encrypted authentication data from the third node, and calculates the distance between the data to be authenticated and the authentication data in a state of being encrypted by the public key. The third node generates a polynomial expression including, as a parameter thereof, a threshold value for the distance between the data to be authenticated and the authentication data, and transmits the polynomial expression to the first node. The first node assigns the distance to the polynomial expression to generate, as verification data, a value encrypted by the public key, and transmits said value to the second node. The second node verifies, against the authentication data, on the basis of the secret key and the verification data, the data to be authenticated. As a result, data to be authenticated and authentication data are concealed in a server on the basis of simple processing.

Description

Verification system, node, verification method and program

[Description of related applications]
The present invention is based on a Japanese patent application: Japanese Patent Application No. 2013-102955 (filed on May 15, 2013), and the entire contents of this application are incorporated in the present specification by reference.
The present invention relates to a collation system, a node, a collation method, and a program, and more particularly, to a collation system, a node, a collation method, and a program that allow ambiguity of data to be collated.

In recent years, with the spread of the cloud, users' data is accumulated in computer resources connected to the network, and services provided using the accumulated data are rapidly spreading. In such services, opportunities for handling sensitive data of users are increasing. Therefore, it has become important to ensure that user 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 passwords and magnetic cards have frequently occurred, and biometric technology with higher safety based on biometric features such as fingerprints and veins has attracted attention. Yes.

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, and if information is leaked, it causes enormous damage, so high confidentiality is required.

For this reason, template protection type biometric authentication technology that performs authentication while keeping template information secret is becoming important so that “spoofing” cannot be performed even if a template leaks.

For example, Patent Document 1 describes a method in which fingerprint data is expressed as a point on a polynomial, and a biometric authentication is performed using data in which fingerprint data is concealed by adding a random point to the point as a template.

Further, Non-Patent Document 1 describes a method for protecting the biometric information of a client seeking authentication by using public key cryptography having homogeneity.

Further, in Patent Document 2, a certification device encrypts a feature vector for registration using a public key and a random number, registers the encrypted feature vector for registration in an authentication device, and at the time of authentication, the certification device authenticates for authentication. The feature vector is encrypted using a public key and a random number, and the authentication device derives the similarity between the two feature vectors by decryption processing using the secret key while the two encrypted feature vectors remain encrypted. A system is described in which possible encryption similarity information is generated, a decryption device decrypts the encryption similarity information to derive plain text similarity, and if the similarity is greater than or equal to a threshold value, the system determines that the person is the person Yes.

JP 2006-158581 A International Publication No. 2011/052056

The entire disclosure of the above-mentioned patent documents and non-patent documents is incorporated by reference in this document. The following analysis was made by the present inventors.

It is known that the method of Patent Document 1 may not protect biometric information with sufficient strength when biometric authentication is repeated many times.

On the other hand, Non-Patent Document 1 proposes a method for protecting biometric information of a client seeking authentication by using public key cryptography having homogeneity.

In a biometric authentication method that does not protect biometric information, feature points called minutiae are extracted from biometric information (for example, fingerprints) and the minutiae is registered in the server as an authentication template. Generally, a minutiae is composed of three components: type, coordinates (x, y), and angle. The type represents the type of feature point, for example, an end point or a branch point. The coordinate represents the coordinate of the feature point, and the angle represents the slope of the tangent line at the feature point.

At the time of authentication, the server confirms that the minutia extracted from the biometric information of the client matches the minutia registered as the authentication template. When the following three conditions are satisfied: (1) the feature point types match, (2) the distance between the feature points is within the threshold, and (3) the tangential slope difference at the feature point is within the threshold. , Maneusha is considered a match.

Specifically, when the minutiae extracted at the time of authentication is (type1, (x1, y1), θ1) and the registered minutiae is (type2, (x2, y2), θ2),
(1) type1 = type2
(2) 0 ≦ ((x1-x2) ^ 2 + (y1-y2) ^ 2) ≦ δd
(3) 0 ≦ (θ1-θ2) ^ 2 ≦ δt
When the three conditions are satisfied, it is considered that the two minutiae coincide.

Here, δd and δt are parameters determined by the system. The distance evaluated in (2) is called a two-dimensional Euclidean distance or L2 norm. Similarly, the distance evaluated in (3) is called a one-dimensional Euclidean distance. Hereinafter, these are collectively called the Euclidean distance, and the Euclidean distance between D and D ′ is represented as d (D, D ′).

Non-Patent Document 1 describes a biometric authentication method capable of concealing biometric information of a client who has requested authentication. Specifically, by using an encryption protocol called Aided Computation and Set Intersection, the minutiae (type1, (x1, y1), θ1) extracted at the time of authentication is not disclosed to the server, and the minutiae registered on the server It can be confirmed whether (type2, (x2, y2), θ2) and minutiae (type1, (x1, y1), θ1) match.

In the following, data registered in advance from the client to the server is referred to as “authentication data”. Data extracted at the time of authentication and verified with authentication data is referred to as “authenticated data”. In the above example, minutiae (type2, (x2, y2), θ2) corresponds to authentication data, and minutiae (type1, (x1, y1), θ1) corresponds to data to be authenticated.

As a preparation for explaining these cryptographic protocols, public key cryptography will be explained. Public key cryptography consists of three algorithms: key generation, encryption, and decryption. Key generation is a probabilistic algorithm that receives a security parameter as input and outputs a public key pk and a secret key sk. Encryption is a probabilistic algorithm that receives a public key pk and a message M as input and outputs ciphertext C. Decryption is a definitive algorithm that receives a secret key sk and ciphertext C as input and outputs a decryption result M.

Hereinafter, the key generation, encryption, and decryption algorithms are described as follows.
Key generation: KeyGen (1 ^ k) → (pk, sk)
Encryption: Enc (pk, M) → C
Decryption: Dec (sk, C) → M

The public key cryptosystem has homomorphism means that the following expression holds for certain operations (*) and (+).
Enc (pk, M1 (+) M2) = Enc (pk, M1) (*) Enc (pk, M2)

For example, it is known that the Paillier cipher is a public key cipher having homomorphism in which (*) is multiplied and (+) is added. Next, the Paillier encryption will be described.

Key generation: Receives security parameter 1 ^ k.
K-bit prime numbers p and q are selected at random, and n = pq.
Next, g = 1 + n mod n ^ 2.
The public key pk = (n, g) and the secret key sk = (p, q) are output.

Encryption: pk = (n, g), message m is received as input.
Choose r at random from Z * _ {n ^ 2}.
C = (1 + mn) · r ^ n mod n ^ 2 is calculated.
Output ciphertext C.

Decryption: sk = (p, q), ciphertext C is received as input.
Calculate λ = (p−1) (q−1).
m = (c ^ {λ} mod n ^ 2 −1) / (g ^ {λ} mod n ^ 2 −1) mod n is calculated.
Output plaintext m.

If C1 = Enc (pk, m1) = (1 + m1 n) ・ r1 ^ n mod n ^ 2, C2 = Enc (pk, m2) = (1 + m2 n) ・ r2 ^ n mod n ^ 2 C1 × C2 = (1+ (m1 + m2) n + m1 ・ m2 ・ n ^ 2) ・ (r1r2) ^ n mod n ^ 2 = (1+ (m1 + m2) n) ・ (r1r2) ^ n mod n ^ 2 = Enc (pk, m1 + m2), and the Paillier cipher has homomorphism. Thus, public key cryptography that can add plaintext while encrypted is called additive homomorphic public key cryptography.

“Set Intersection” is a cryptographic protocol performed between two entities, Alice and Bob. Assume that Alice has some data a and Bob has a set B of data. At this time, Set Intersection is a protocol for confirming whether data a is included in set B while keeping data A held by Alice confidential to Bob.

For simplicity, Set Intersection will be described as a set B = {b1, b2, b3}. Bob releases the public key pk of the additive homomorphic public key encryption and holds the corresponding secret key sk.

1. Bob generates a polynomial F (x) having a value of 0 when x = b1, b2, b3, and a value other than 0 otherwise. For example, F (x) = (x−b1) (x−b2) (x−b3) may be set. Such a polynomial can be easily generated using Lagrange interpolation. Here, the coefficients of F (x) are α [0], α [1],..., Α [n]. That is, F (x) = α [n] x ^ n + α [n-1] x ^ {n-1} + ... + α [1] x + α [0].
2. Bob encrypts α [0], α [1],..., Α [n] using the public key pk. Bob also sends ciphertexts C [0], C [1],..., C [n] to Alice.
3. Alice calculates a ^ {n}, a ^ {n-1}, ..., a ^ {0}. In addition, Alice replaces C [n] ^ {a ^ {n}}, C [n-1] ^ {a ^ {n-1}}, ..., C [0] ^ {a ^ {0}} calculate.
4). Alice uses C = C [n] ^ {a ^ {n}} ・ C [n-1] ^ {a ^ {n-1}} ...… C [0] ^ {a ^ {0}} calculate. Due to the isomorphism, C = Enc (pk, F (a)). Alice selects r at random and sets C ′ = C ^ {r}. In addition, Alice sends C 'to Bob.
5. Bob decrypts the received C ′. Bob determines that Alice has data included in set B if the decoding result is 0, and determines that Alice does not have data included in set B if the decoding result is other than 0.

For simplicity, the protocol of SetsectionIntersection by Alice with input a and Bob with set B and secret key sk is denoted as Set Intersection [Alice (a), Bob (B, sk)] (pk). Here, pk represents a public key pk that is a common input to Alice and Bob.

Next, Aided Computation will be explained. Aided Computation is also a cryptographic protocol performed between two entities, Alice and Bob. Assume that Alice has a ciphertext Enc (pk, a) of some data a, and Bob has a secret key sk corresponding to the data set B and the public key pk. Bob's cipher is an additive homomorphic public key cipher. At this time, Aided Computation is a protocol for checking whether data a is included in the set B while keeping Alice's data a confidential to Bob. In Aided Computation, unlike Set Intersection, Alice does not know the plaintext of data a.

For simplicity, Aided Computation is described as B = {b1, b2, b3}. Further, it is assumed that a polynomial F (x) that is 0 when x = b1, b2, b3, and other than 0 otherwise is disclosed. That is, F (x) = α [n] x ^ n + α [n-1] x ^ {n-1} +… + α [1] x + α [0], and α [0] to α [n] is publicly available.

1. Alice chooses r at random, calculates Enc (pk, ra) = {Enc (pk, a)} ^ {r} and sends it to Bob.
2. Bob decrypts Enc (pk, ra) and gets ra.
3. Bob computes (ra) ^ {α [1]}, (ra) ^ {α [2]}, ..., (ra) ^ {α [n]} and encrypts each using the public key pk. . That is, C [i] = Enc (pk, (ra) ^ {α [i]}) is performed for i = 1 to n, and C [1] to C [n] are sent to Alice.
4). Alice calculates C ′ [i] = (C [i]) ^ {1 / (r ^ {i})} for i = 1 to n.
5. Alice calculates C = C '[1], C' [2], ..., C '[n], Enc (pk, α [0]), and sends it to Bob. From the isomorphism, C = Enc (pk, F (a)).
6). Bob decrypts C. Bob determines that Alice has the ciphertext of the data included in set B if the decryption result is 0, and if Alice has no ciphertext of the data included in set B if the decryption result is other than 0 to decide.

For simplicity, the protocol of AidedutComputation for Alice with input Enc (pk, a) and the function F (x) by Bob with set B and secret key sk is Aided Computation [Alice (Enc (pk, a)), Bob (B, sk)] (pk, F (x)). Here, pk represents a public key pk that is a common input to Alice and Bob.

In Non-Patent Document 1, client minutiae (type1, (x1, y1), θ1) (authenticated data) and authentication template (type2, (x2, y2), θ2) (authentication data) stored in the server ) Use Set 一致 Intersection and Aided Computation to confirm that they match. Specifically, the following processing is performed.

(1) Type match: Set Intersection [client (type 1), server (type 2, sk)] (pk) is performed.

(2) Distance match: First, the Euclidean distance between (x1, y1) and (x2, y2) is calculated with encryption.
(A) The server generates F (x) as B = {0, 1,..., Δd}.
(A) The server calculates Enc (pk, x2 ^ 2), Enc (pk, x2), Enc (pk, y2 ^ 2), and Enc (pk, y2), and sends them to the client.
(C) The client calculates Enc (pk, x1 ^ 2), Enc (pk, y1 ^ 2).
(D) Clients are Enc (pk, x1 ^ 2), {Enc (pk, x2)} ^ {-2x1}, Enc (pk, x2 ^ 2), Enc (pk, y1 ^ 2), {Enc ( pk, y2)} ^ {-2y1} · Enc (pk, y2 ^ 2) = Enc (pk, (x1-x2) ^ 2 + (y1-y2) ^ 2) is calculated.
(E) Aided Computation [Client (Enc (pk, (x1-x2) ^ 2 + (y1-y2) ^ 2)), Server ({0,1,…, δd}, sk)] (pk, F ( x)) is executed.

(3) Angle match: Similar to the distance match, Enc (pk, (θ1-θ2) ^ 2) is calculated and for G (x) corresponding to B '= {0,1, ..., δt} Execute AidedutComputation [client (Enc (pk, (θ1-θ2) ^ 2)), server (B ', sk)] (pk, G (x)).

According to the technique described in Non-Patent Document 1, data to be authenticated that is authenticated based on authentication data registered in the server from the client can be kept secret from the server. However, according to the technique described in Non-Patent Document 1, since authentication data registered on the server is plain text, there is a risk that authentication data, which is client sensitive data, may be leaked from the server. Another problem is that the authentication data is not concealed.

In order to solve this problem, it is conceivable to employ the technique described in Patent Document 2. However, according to the technique described in Patent Document 2, when encrypting a feature vector for registration (authentication data) and a feature vector for authentication (authenticated data), a special trap called double-homomorphic encryption is used. It is necessary to use the same cipher. In general, the double homomorphic encryption has a calculation cost and has a problem that it is difficult to process in a realistic time because the size of the secret key and the public key becomes very large.

Therefore, it is desired to conceal the data to be authenticated and the authentication data from the server based on simple processing. An object of the present invention is to provide a collation system, a collation method, and a program that contribute to such a demand.

The collation system according to the first aspect of the present invention is:
Comprising a first node, a second node and a third node;
The first node encrypts authentication data with a public key and transmits the encrypted data to the third node;
When the data to be authenticated that is collated with the authentication data is received, the encrypted authentication data is obtained from the third node, and the distance between the data to be authenticated and the authentication data is encrypted with the public key A distance calculation unit to calculate as is,
A verification data generation unit that generates a value encrypted by the public key by substituting the distance into the polynomial acquired from the third node as verification data and transmits the verification data to the second node. And
The second node generates a pair of the public key and the secret key, and transmits the public key to the first node;
A collation unit that collates the data to be authenticated with the authentication data based on the secret key and the collation data;
The third node includes a storage unit that stores the encrypted authentication data;
A collation information generating unit that generates a polynomial that includes a threshold value of a distance between the authentication data and the data to be authenticated as a parameter.

The node according to the second aspect of the present invention is:
An encryption unit that encrypts authentication data with the public key received from the second node that generates a public key and private key pair, and transmits the encrypted authentication data to the third node;
When the data to be authenticated that is collated with the authentication data is received, the encrypted authentication data is obtained from the third node, and the distance between the data to be authenticated and the authentication data is encrypted with the public key A distance calculation unit to calculate as is,
A verification data generation unit that generates a value encrypted with the public key by substituting the distance into the polynomial acquired from the third node, and generates the verification data and transmits the verification data to the second node; ,
The polynomial includes a threshold value of a distance between the authentication data and the data to be authenticated as a parameter.

The collation method according to the third aspect of the present invention is:
A first node encrypting authentication data with the public key received from the second node that generates a public key and private key pair and transmitting the encrypted data to the third node;
When the data to be authenticated that is collated with the authentication data is received, the encrypted authentication data is obtained from the third node, and the distance between the data to be authenticated and the authentication data is encrypted with the public key The process of calculating as it is,
Including substituting the distance into the polynomial obtained from the third node and encrypting the encrypted value using the public key as verification data and transmitting the verification data to the second node.
The polynomial includes a threshold value of a distance between the authentication data and the data to be authenticated as a parameter.

The program according to the fourth aspect of the present invention is:
A process of encrypting authentication data with the public key received from the second node that generates a public key and private key pair and transmitting the encrypted authentication data to the third node;
When the data to be authenticated that is collated with the authentication data is received, the encrypted authentication data is obtained from the third node, and the distance between the data to be authenticated and the authentication data is encrypted with the public key Processing while calculating
A process of substituting the distance into the polynomial obtained from the third node and generating a value encrypted with the public key as verification data and transmitting it to the second node. Run it on the computer provided,
The polynomial includes a threshold value of a distance between the authentication data and the data to be authenticated as a parameter.
The program can be provided as a program product recorded on a non-transitory computer-readable storage medium.

According to the collation system, node, collation method, and program according to the present invention, it becomes possible to conceal the data to be authenticated and the authentication data from the server based on simple processing.

It is a block diagram which shows the structure of the collation system which concerns on one Embodiment as an example. It is a block diagram which shows the structure of the collation system which concerns on 1st Embodiment as an example. It is a sequence diagram which shows the data registration operation | movement of the collation system which concerns on 1st Embodiment as an example. It is a sequence diagram which shows the ciphertext collation operation | movement of the collation system which concerns on 1st Embodiment as an example.

First, an outline of one embodiment will be described. Note that the reference numerals of the drawings attached to this summary are merely examples for facilitating understanding, and are not intended to limit the present invention to the illustrated embodiment.

FIG. 1 is a block diagram illustrating an example of a configuration of a verification system according to an embodiment. Referring to FIG. 1, the verification system includes a first node 100 corresponding to a client, a second node 200 corresponding to an authentication node, and a third node 300 corresponding to a server. The first node 100 includes an encryption unit 11, a distance calculation unit 22, and a collation data generation unit 23. On the other hand, the second node includes a key generation unit 51 and a verification unit 54. The third node 300 includes a storage unit 31 and a collation information generation unit 41.

The key generation unit 51 of the second node 200 generates a public key / private key pair and transmits the public key to the first node 100. The encryption unit 11 of the first node 100 encrypts the authentication data with the public key and transmits it to the third node 300. The storage unit 31 of the third node 300 holds encrypted authentication data.

When the distance calculation unit 22 of the first node receives the authentication target data to be verified with the authentication data, the distance calculation unit 22 acquires the encrypted authentication data from the third node 300, and the distance between the authentication target data and the authentication data. Is calculated with the public key encrypted. The verification information generation unit 41 of the third node 300 generates a polynomial including a threshold value of the distance between the authentication data and the data to be authenticated as a parameter. The verification data generation unit 23 of the first node 100 generates a value obtained by substituting the calculated distance into the polynomial acquired from the third node 300 and encrypted with the public key as verification data. Transmit to node 200. The collation unit 54 of the second node 200 collates the data to be authenticated with the authentication data based on the secret key and the collation data.

Here, the encryption unit 11 preferably performs encryption based on an encryption method having additive homomorphism. As an example, the encryption unit 11 may perform encryption based on Paillier encryption.

The collation information generating unit 41 may generate a polynomial that becomes zero when the distance between the independent variable and the authentication data is within the above threshold as the above polynomial.

In addition, the encryption unit 11 further encrypts the square of the authentication data with the public key and transmits it to the third node 300, and the storage unit 31 further holds the square of the encrypted authentication data. You may do it. At this time, the distance calculation unit 22 obtains the encrypted authentication data and the square of the encrypted authentication data from the third node 300, and encrypts the distance between the data to be authenticated and the authentication data using the public key. It is preferable that the calculation is carried out with the change.

Furthermore, the authentication data and the data to be authenticated may include an n-dimensional element. At this time, it is preferable that the distance calculation unit 22 calculates the n-dimensional Euclidean distance between the data to be authenticated and the authentication data while being encrypted with the public key.

Further, the authentication data and the data to be authenticated may include a plurality of elements. At this time, the distance calculation unit 22 calculates the above-mentioned distance encrypted for each element, the collation information generation unit 41 generates a polynomial for each element, and the collation data generation unit 23 It is preferable that the verification data is generated, and the verification unit 54 uses the secret key and the verification data generated for a plurality of elements to verify the authentication data with the authentication data.

According to the technology described in Non-Patent Document 1, the data registered in the server remains in plain text, so there is a possibility of data leaking from the server. Another problem is that data cannot be kept confidential to the server administrator.

According to the collation system according to the above embodiment, not only the data to be authenticated sent from the client (first node) to the server (third node) at the time of authentication but also the database of the server (third node), etc. The stored authentication data is also encrypted using an encryption method with high confidentiality. Therefore, according to such a collation system, the above-mentioned problem in the technique described in Non-Patent Document 1 is solved. Also, by giving the encryption method a special property of homomorphism, it is possible to calculate the Euclidean distance of the data while it is encrypted, and it is guaranteed that the encrypted data can be verified without being decrypted. The Furthermore, by adding a square ciphertext of authentication data as data generated at the time of registration, it becomes possible to calculate the distance between encrypted data, which was impossible in Non-Patent Document 1.

As described above, according to the collation system according to the embodiment, it is possible to prevent leakage of authentication data stored in the third node (server), and even if the server administrator is malicious, Plain text leakage can be prevented. The reason is that at the time of data registration, the authentication data is encrypted by the first node (client) with an encryption key that is not decrypted by the server administrator.

<Embodiment 1>
Next, the collation system according to the first embodiment will be described in detail with reference to the drawings.

FIG. 2 is a block diagram showing an example of the configuration of the collation system according to this embodiment. Referring to FIG. 2, the collation system includes a registered data generation device 10, a collation request device 20, a storage device 30, a data collation device 40, and a collation auxiliary device 50.

Note that FIG. 2 illustrates a case where the verification system is configured by five nodes, but the verification system of the present invention is not limited to the illustrated mode. As an example, the registered data generation device 10 and the verification requesting device 20 are collectively set as a first node (client), the verification auxiliary device 50 is set as a second node (authentication node), and the storage device 30 and the data verification device 40 are combined. The third node (server) may be used.

The registered data generation device 10 has an encryption unit 11. The encryption unit 11 receives the authentication data to be concealed and the encryption key disclosed by the verification assisting device 50, conceals the authentication data using the encryption key, and outputs the encrypted data.

Here, the encryption key disclosed by the verification assistant device 50 is a public key of additive homomorphic public key encryption.

The storage device 30 includes a storage unit 31 and an identifier management unit 32. The storage unit 31 stores the unique identifier assigned by the identifier management unit 32 together with the encrypted data sent from the registered data generation device 10.

The verification request device 20 includes a verification request unit 21, a distance calculation unit 22, and a verification data generation unit 23. When the verification request unit 21 receives authentication target data to be verified as input, the verification request unit 21 sends a verification request to the data verification device 40. The distance calculation unit 22 receives the authentication target data to be verified and the verification information received from the data verification device 40, and generates encrypted distance data. The verification data generation unit 23 receives the encrypted distance data as input and generates verification data while interacting with the verification auxiliary device 50.

The data collating device 40 includes a collation information generating unit 41, a collation information sending unit 42, a collation auxiliary request unit 43, and a determination unit 44. The verification information generation unit 41 receives the encrypted data stored in the storage device 30 and generates verification information. The collation information sending unit 42 receives the collation request sent from the collation requesting device 20 as an input, and sends the collation information. The verification auxiliary request unit 43 receives the verification data sent from the verification requesting device 20 as an input, generates a verification auxiliary request, and sends it to the verification auxiliary device 50. The determination unit 44 receives the overall result received from the verification assisting device 50 as an input, and generates and outputs the verification result.

The collation assisting device 50 includes a key generation unit 51, a collation assisting unit 52, and an overall result assisting unit 53. The key generation unit 51 generates a public key and a secret key of additive homomorphic encryption, discloses the public key, and holds the secret key. The collation assisting unit 52 interacts with the collation data generating unit 23 of the collation requesting device 20 to assist the generation of collation data. The total result auxiliary unit 53 receives the verification auxiliary request sent from the data verification device 40 and the secret key of the additive homomorphic encryption as inputs, and generates a total result.

Next, the operation of the verification system (FIG. 2) according to this embodiment will be described in detail with reference to the drawings.

The operation of the verification system is roughly divided into two phases: the data registration phase and the ciphertext verification phase. In the data registration phase, the authentication data is input to the registration data generation device 10, the authentication data is encrypted and registered in the storage device 30. On the other hand, in the ciphertext verification phase, the data to be authenticated is close to the plaintext of the encrypted data stored in the storage device 30 (the Euclidean distance is small) while concealing the data to be authenticated input to the verification requesting device 20 It is determined whether or not. Hereinafter, the operation in each phase will be described in detail.

[Data registration phase]
FIG. 3 is a sequence diagram illustrating an operation in the data registration phase of the verification system as an example.

Referring to FIG. 3, the key generation unit 51 of the verification assisting device 50 generates a public key and a secret key of additive homomorphic encryption, and publishes the public key (step A1).

Next, the registration data generation device 10 receives authentication data to be concealed and a public key (step A2).

Next, the encryption unit 11 of the registration data generation device 10 generates encryption data from the input authentication data and the public key, and sends it to the storage device 30 (step A3).

When the identifier management unit 32 of the storage device 30 receives the encrypted data, it assigns a unique identifier to the encrypted data (step A4). Further, the identifier management unit 32 stores the set of the encrypted data and the identifier in the storage unit 31 (Step A5).

[Ciphertext verification phase]
FIG. 4 is a sequence diagram illustrating an operation in the ciphertext verification phase of the verification system as an example.

Referring to FIG. 4, the verification information generation unit 41 of the data verification device 40 receives the encrypted data stored in the storage unit 31 and the identifier and parameter corresponding to the encrypted data (step B1), and generates verification information. (Step B2).

Next, the verification requesting unit 21 of the verification requesting device 20 receives the data to be authenticated and the public key (step B3).

Next, when the verification request unit 21 of the verification requesting device 20 receives the data to be authenticated and the public key, it generates a verification request and outputs it to the data verification device 40 (step B4).

When the verification information sending unit 42 of the data verification device 40 receives the verification request, it outputs the verification information to the verification request device 20 (step B5).

Upon receiving the verification information, the distance calculation unit 22 of the verification requesting device 20 calculates the plaintext Euclidean distance between the data to be authenticated and the encrypted data while encrypting it, and generates encrypted distance data (step B6).

The verification data generation unit 23 receives the encrypted distance data and the verification information as input, generates verification data while interacting with the verification auxiliary unit 52 of the verification auxiliary device 50, and outputs the verification data to the data verification device 40 (step). B7).

The collation assistance request unit 43 of the data collation device 40 receives the collation data, generates a collation assistance request, and outputs it to the collation assistance device 50 (step B8).

When receiving the verification assistance request, the overall result auxiliary unit 53 of the verification auxiliary device 50 receives the secret key, generates an overall result, and outputs it to the data verification device 40 (step B9).

When the determination unit 44 of the data collating device 40 receives the comprehensive result, the determination unit 44 performs the determination and outputs the determination result (step B10).

According to the collation system according to the present embodiment, not only the data to be authenticated sent from the registered data generation device 10 to the storage device 30 during authentication but also the authentication data stored in the storage device 30 uses an encryption method with high confidentiality. Encrypted. Therefore, for example, when the server is configured by the storage device 30 and the data collation device 40, according to the collation system according to the present embodiment, it is possible to prevent leakage of authentication data from the server.

<Embodiment 2>
Next, a verification system according to the second embodiment will be described with reference to the drawings.

In this embodiment, a one-dimensional Euclidean distance is used as a distance in the collation system according to the first embodiment. That is, when d (D, D ′) = (D−D ′) ^ {2} is equal to or less than the threshold value d, it is determined that the match is satisfied, and when it is greater than d, it is determined that the match is not satisfied. In this embodiment, additive homomorphic encryption (for example, Paillier encryption) is used. Hereinafter, the operation in each phase will be described in detail with reference to FIG. 3 and FIG.

[Data registration phase]
Referring to FIG. 3, the key generation unit 51 of the verification assisting device 50 generates the public key pk and the secret key sk of the additive homomorphic encryption, and publishes the public key pk (Step A1).

Next, the registration data generation device 10 receives the authentication data D to be concealed and the public key pk generated by the key generation unit 51 (step A2).

Next, the encryption unit 11 of the registration data generation device 10 generates encryption data (Enc (pk, D), Enc (pk, D ^ 2)) from the input authentication data D and public key pk, The data is sent to the storage device 30 (step A3). Here, Enc (pk, D) represents the result of encrypting the authentication data D using the public key pk. Similarly, Enc (pk, D ^ 2) represents the result of encrypting the square of the authentication data D using the public key pk.

When the identifier management unit 32 of the storage device 30 receives the encrypted data, it assigns a unique identifier ID to the encrypted data (step A4). Further, the identifier management unit 32 records the set of encrypted data and the identifier ((Enc (pk, D), Enc (pk, D ^ 2)), ID) in the storage unit 31 (step A5).

[Ciphertext verification phase]
Referring to FIG. 4, the collation information generating unit 41 of the data collating device 40 includes a set of encrypted data stored in the storage unit 31 and an identifier corresponding to the encrypted data ((Enc (pk, D), Enc (pk , D ^ 2)), ID) is received (step B1), and verification information is generated according to the following procedure (step B2).

1. When x = 0, 1,..., d, a polynomial F (x) is randomly generated such that F (x) = 0, otherwise F (x) ≠ 0. For example, F (x) = x (x-1) (x-2)... (X-d) is a d + 1 order polynomial satisfying the above properties. In general, a polynomial of d + 1 order or higher satisfying such a condition can be easily constructed. For simplicity, the coefficient of F (x) is α [0] to α [N]. That is, F (x) = α [N] x ^ N + α [N-1] x ^ {N-1} + ... + α [0]. When F (x) = x (x-1) (x-2)... (X-d), N = d.

2. ((Enc (pk, D), Enc (pk, D ^ 2)), α [0] to α [N]) is used as collation information.

Next, the collation request unit 21 of the collation requesting device 20 receives the authenticated data D 'and the public key pk (step B3).

Next, when the verification request unit 21 of the verification requesting device 20 receives the authenticated data D 'and the public key pk, it generates a verification request req and outputs it to the data verification device 40 (step B4). The verification request req is a message for requesting verification.

When the distance calculation unit 22 of the verification requesting device 20 receives the verification information, it calculates the encrypted Euclidean distance between the authenticated data D ′ and the encrypted data as encrypted as follows, and generates encrypted distance data: (Step B6).

1. Calculate Enc (pk, D '^ 2).
2. Enc (pk, d (D, D ')) = Enc (pk, D ^ 2) .Enc (pk, D) ^ {-2D'}. Enc (pk, D '^ 2) is calculated.

The collation data generation unit 23 receives the encrypted distance data and the collation information as input, and generates collation data while interacting with the collation auxiliary unit 52 of the collation auxiliary device 50 as follows. (Step B7).

1. R is selected at random, and Enc (pk, r · d (D, D ′)) = Enc (pk, d (D, D ′)) ^ {r} is calculated and sent to the verification assisting device 50.
2. The verification assistant unit 52 of the verification assistant device 50 decrypts Enc (pk, r · d (D, D ′)) using the secret key sk and calculates r · d (D, D ′).
3. The verification assistant 52 calculates (r · d (D, D ')) ^ {2}, ..., (r · d (D, D')) ^ {N}, and uses the public key pk, respectively. Enc (pk, ((r ・ d (D, D ')) ^ {2})), ..., Enc (pk, ((r ・ d (D, D')) ^ {N})) Is output to the verification requesting device 20.
4). The matching data generation unit 23 uses the r selected in step 1 to enc (pk, ((r · d (D, D ')) ^ {2})) ^ {1 / r ^ 2},. , Enc (pk, ((r ・ d (D, D ')) ^ {N})) ^ {1 / (r ^ {N})} and calculate Enc (pk, ((d (D, D ')) ^ {2})), ..., Enc (pk, ((d (D, D')) ^ {N})).
5. Enc (pk, F (d (D, D '))) = (Enc (pk, ((d (D, D')) ^ {N})) ^ {α [N]} ・ (Enc (pk, ((d (D, D ')) ^ {N-1})) ^ {α [N-1]} ...… (Enc (pk, d (D, D'))) ^ {α [1] } ・ Enc (pk, α [0]) is calculated.
6). R is selected at random, and Enc (pk, F (d (D, D ′))) ^ {R} is calculated and output to the data verification device 40.

Here, step 6 is performed in order to make the output random when d (D, D ′) <d. If the output need not be random, step 6 may be omitted. Step 1 is performed in order to keep the value of d (D, D ′) secret from the verification assisting device 50. If it is not necessary to keep secret, step 1 may be omitted.

The collation assistance request unit 43 of the data collation apparatus 40 receives the collation data, generates a collation assistance request as follows, and outputs it to the collation assistance apparatus 50 (step B8).

1. S is selected at random, and C = Enc (pk, F (d (D, D ′))) ^ {R} · Enc (pk, s) is calculated and output to the verification auxiliary device 50.

Here, Step 1 is performed so as not to notify the verification result to the verification assistant device 50 by randomizing the plaintext of C. When the verification result may be notified to the verification auxiliary device 50, step 1 may be omitted.

When receiving the verification assistance request, the overall result auxiliary unit 53 of the verification auxiliary device 50 receives the secret key sk, generates the overall result P as follows, and outputs it to the data verification device 40 (step B9). That is, the overall result auxiliary unit 53 decrypts the ciphertext C using the secret key sk, and outputs the decrypted result to the data verification device 40 as the overall result P.

When receiving the comprehensive result P, the determination unit 44 of the data collating device 40 performs the determination as follows and outputs the determination result (step B10). That is, the determination unit 44 determines that 0 ≦ d (D, D ′) ≦ d when P = s, and determines that d (D, D ′)> d otherwise.

In this embodiment, the data registered in the storage device 30 is encrypted data. All data sent from the verification requesting device 20 in the verification phase is a ciphertext. Therefore, the information regarding the registered authentication data D and the authenticated data D ′ is not leaked to the storage device 30 and the data verification device 40.

Furthermore, the verification requesting device 20 and the data verification device 40 also use the random numbers for the verification assisting device 50 so that no information regarding the registered authentication data D and authenticated data D ′ is leaked.

<Embodiment 3>
Next, a verification system according to the third embodiment will be described.

In the present embodiment, the two-dimensional Euclidean distance is used as the distance in the matching system according to the first embodiment. That is, the distance d (D, D ') = (Dx-D'x) ^ {2} + (2) between the two two-dimensional data D = (Dx, Dy) and D' = (D'x, D'y) Dy-D'y) ^ If {2} is less than or equal to the threshold d, it is determined that there is a match, and if it is greater than d, it is determined that there is no match. In this embodiment, additive homomorphic encryption (for example, Paillier encryption) is used. Hereinafter, the operation in each phase will be described in detail.

[Data registration phase]
In step A3 of the data registration phase of the collation system according to the second embodiment using the one-dimensional Euclidean distance as the distance, the encrypted data (Enc (pk, D), Enc (pk, D ^ 2)) is converted into the encrypted data (Enc Replace with (pk, Dx), Enc (pk, Dx ^ 2), Enc (pk, Dy), Enc (pk, Dy ^ 2)).

[Ciphertext verification phase]
In the ciphertext verification phase of the verification system according to the second embodiment using the one-dimensional Euclidean distance as the distance, step B6 is changed as follows.

1. Calculate Enc (pk, D'x ^ 2), Enc (pk, D'y ^ 2).
2. Enc (pk, d (D, D ')) = Enc (pk, Dx ^ 2), Enc (pk, Dx) ^ {-2D'x}, Enc (pk, D'x ^ 2), Enc (pk , Dy ^ 2) · Enc (pk, Dy) ^ {-2D'y} · Enc (pk, D'y ^ 2).

In this embodiment, as in the second embodiment, the authentication data registered in the storage device 30 is encrypted data. All data sent from the verification requesting device 20 in the verification phase is a ciphertext. Therefore, the information regarding the registered authentication data D and the authenticated data D ′ is not leaked to the storage device 30 and the data verification device 40.

<Embodiment 4>
Next, a verification system according to a fourth embodiment will be described with reference to the drawings.

In this embodiment, data having two or more elements is collated in the collation system according to the first embodiment. Here, as an example, a case will be described in which each data has two elements and one is collated using one-dimensional Euclidean distance as an index and the other as a two-dimensional Euclidean distance as an index. That is, when two data D = (t, (x, y)), D ′ = (t ′, (x ′, y ′)), d (t, t ′) ≦ d_ {t}, and , D ((x, y), (x ′, y ′)) ≦ d_ {e}, it is determined that there is a match, otherwise it is determined that there is no match. In this embodiment, additive homomorphic encryption (for example, Paillier encryption) is used. Hereinafter, the operation in each phase will be described in detail.

Next, the encryption unit 11 of the registration data generation device 10 uses the input authentication data D and public key pk to generate encrypted data.
(Enc (pk, t), Enc (pk, t ^ 2)), (Enc (pk, x), Enc (pk, x ^ 2)), (Enc (pk, y), Enc (pk, y ^ 2))
Is sent to the storage device 30 (step A3).

Here, Enc (pk, a) represents the result of encrypting data a using the public key pk. Similarly, Enc (pk, a ^ 2) represents the result of encrypting the square of data a using the public key pk.

When receiving the encrypted data, the identifier management unit 32 of the storage device 30 gives a unique identifier ID to the encrypted data (step A4). In addition, the identifier management unit 32 is a combination of encrypted data and an identifier.
((Enc (pk, t), Enc (pk, t ^ 2)), (Enc (pk, x), Enc (pk, x ^ 2)), (Enc (pk, y), Enc (pk, y ^ 2)), ID)
Is stored in the storage unit 31 (step A5).

[Ciphertext verification phase]
Referring to FIG. 4, the verification information generation unit 41 of the data verification device 40 includes a set of encrypted data stored in the storage unit 31 and an identifier corresponding to the encrypted data.
((Enc (pk, t), Enc (pk, t ^ 2)), (Enc (pk, x), Enc (pk, x ^ 2)), (Enc (pk, y), Enc (pk, y ^ 2)), ID)
Is input (step B1), and verification information is generated by the following procedure (step B2).

1. When x = 0, 1,..., d_t, a polynomial F (x) is generated randomly such that F (x) = 0, otherwise F (x) ≠ 0. For example, F (x) = x (x-1) (x-2)... (X-d_t) is a d_t + 1 order polynomial satisfying the above property. In general, a polynomial of d_t + 1 order or higher that satisfies such a condition can be easily constructed. For simplicity, the coefficient of F (x) is α [0] to α [N]. That is, F (x) = α [N] x ^ N + α [N-1] x ^ {N-1} + ... + α [0]. For example, when F (x) = x (x-1) (x-2)... (X-d_t), N = d_t.
2.1. Similarly, a polynomial G (x) that satisfies G (x) = 0 in the case of x = 0, 1,..., D_e, and G (x) ≠ 0 in other cases is randomly generated. For simplicity, the coefficient of G (x) is β [0] to β [N ′]. That is, G (x) = β [N '] x ^ n + β [N'-1] x ^ {n-1} + ... + β [0]. For example, when G (x) = x (x-1) (x-2)... (X-d_e), N ′ = d_e.
3. ((Enc (pk, t), Enc (pk, t ^ 2)), (Enc (pk, x), Enc (pk, x ^ 2)), (Enc (pk, y), Enc (pk, y ^ 2)), α [0] to α [N], β [0] to β [N ']) are used as collation information.

Next, the collation request unit 21 of the collation requesting device 20 receives the input data D 'and the public key pk (step B3).

When the distance calculation unit 22 of the verification requesting device 20 receives the verification information, it calculates the encrypted Euclidean distance between the data to be authenticated and the encrypted data while encrypting them, and generates encrypted distance data ( Step B6).

1. Calculate Enc (pk, t '^ 2), Enc (pk, x' ^ 2), Enc (pk, y '^ 2).
2. Enc (pk, d (t, t ′)) = Enc (pk, t ^ 2) · Enc (pk, t) ^ {− 2t ′} · Enc (pk, t ′ ^ 2) is calculated.
3. Enc (pk, d ((x, y), (x ', y'))) = Enc (pk, x ^ 2) ・ Enc (pk, x) ^ {-2x '} ・ Enc (pk, x' ^ 2) ・ Enc (pk, y ^ 2) ・ Enc (pk, y) ^ {-2y '} ・ Enc (pk, y' ^ 2) is calculated.

1. R_t is selected at random, and Enc (pk, r_t · d (t, t ′)) = Enc (pk, d (t, t ′)) ^ {r_t} is calculated.
2. Choose r_e at random,
Enc (pk, r_e ・ d ((x, y), (x ', y'))) = Enc (pk, d ((x, y), (x ', y'))) ^ {r_e}
And is sent to the verification assistant device 50 together with Enc (pk, r_t · d (t, t ′)) calculated in 1.
3. The verification assistant unit 52 of the verification assistant device 50 uses the secret key sk to specify Enc (pk, r_t · d (t, t ′)) and Enc (pk, r_e · d ((x, y), (x ′, y ′))) is decoded and r_t · d (t, t ′) and r_e · d ((x, y), (x ′, y ′)) are calculated.
4). The collation assisting unit 52 has (r_t · d (t, t ')) ^ {2}, ..., (r_t · d (t, t')) ^ {N}, (r_e · d ((x, y) , (x ', y'))) ^ {2}, ..., (r_e · d ((x, y), (x ', y'))) ^ {N '} Enc (pk, (r_t · d (t, t ')) ^ {2}), ..., Enc (pk, (r_t · d (t, t')) ^ {N}), Enc (pk, (r_e ・ d ((x, y), (x ', y'))) ^ {2}), ..., Enc (pk, (r_e ・ d ((x, y), (x ' , y ′))) ^ {N ′}) is calculated and output to the verification requesting device 20.
5. The verification data generation unit 23 uses En_ (pk, ((r · Enc (pk, (r_t · d (t, t ')) ^ {2}) using r_t and r_e selected in steps 1 and 2. ^ {1 / r_t ^ 2}, ..., Enc (pk, (r_t ・ d (t, t ')) ^ {N}) ^ {1 / (r_t) ^ N}, Enc (pk, (r_e ・ d ((x, y), (x ', y'))) ^ {2}) ^ {1 / r_e ^ 2}, ..., Enc (pk, (r_e ・ d ((x, y), (x ' , y '))) ^ {N'}) ^ {1 / (r_e) ^ {N}} and calculate Enc (pk, ((r ・ Enc (pk, (r_t ・ d (t, t ') ) ^ {2}), ..., Enc (pk, (r_t ・ d (t, t ')) ^ {N}), Enc (pk, (r_e ・ d ((x, y), (x', y '))) ^ {2}), ... Enc (pk, (r_e · d ((x, y), (x', y '))) ^ {N'}).
6). Enc (pk, F (d (t, t '))) = (Enc (pk, ((d (t, t')) ^ {N})) ^ {α [N]} ・ (Enc (pk, ((d (t, t ')) ^ {N-1})) ^ {α [N-1]} ...… (Enc (pk, d (t, t'))) ^ {α [1] } ・ Enc (pk, α [0]), Enc (pk, G (d ((x, y), (x ', y'))))) = (Enc (pk, ((d ((x, y ), (x ', y'))) ^ {N '})) ^ {β [N']} ・ (Enc (pk, ((d ((x, y), (x ', y'))) ) ^ {N'-1})) ^ {β [N'-1]} ...… (Enc (pk, d ((x, y), (x ', y')))) ^ {β [ 1]} ・ Enc (pk, β [0]) is calculated.
7). Enc (pk, d (D, D ')) = Enc (pk, F (d (t, t'))) ・ Enc (pk, G (d ((x, y), (x ', y')) ))) Is calculated.
8). R is selected at random, and Enc (pk, F (d (D, D ′))) ^ {R} is calculated and output to the data verification device 40.

Here, step 8 is performed in order to randomize the output when d (D, D ′) <d. If the output need not be random, step 8 may be omitted. Steps 1 and 2 are performed to conceal the value of d (D, D ′) from the verification assisting device 50. If it is not necessary to keep secret, steps 1 and 2 may be omitted.

When receiving the verification data, the verification auxiliary request unit 43 of the data verification device 40 generates a verification auxiliary request as follows and outputs it to the verification auxiliary device 50 (step B8).
1. S is selected at random, C = Enc (pk, F (d (D, D ′))) ^ {R} · Enc (pk, s) is calculated and output to the verification assisting device 50.

When receiving the verification assistance request, the overall result auxiliary unit 53 of the verification auxiliary device 50 receives the secret key sk, generates the overall result P as follows, and outputs it to the data verification device 40 (step B9). That is, the overall result auxiliary unit 53 decrypts the ciphertext C using the secret key sk, and outputs the decrypted result to the data collating device 40 as the overall result P.

When receiving the comprehensive result P, the determination unit 44 of the data verification device 40 determines as follows and outputs the determination result (step B10). That is, the determination unit 44 determines that the authentication data D and the authenticated data D ′ match when P = s, and determines that the authentication data D and the authenticated data D ′ do not match otherwise.

In the present embodiment, the case has been described in which data is composed of two elements, and collation is performed using each of the one-dimensional Euclidean distance and the two-dimensional Euclidean distance as an index. However, the present invention can be easily applied to a case where data is composed of three or more elements. Is possible. Further, the present invention can be easily applied when the Euclidean distance as an index is three-dimensional or more.

As an example, the authentication system according to the above embodiment can be applied to biometric authentication using a minutiae whose elements are a type, a two-dimensional coordinate, and an angle. Specifically, the input data in the data registration phase and the input data in the ciphertext collation phase are biometric information (maneuver) acquired from a fingerprint or a vein. Whether or not the encrypted biometric data stored in the storage device and the encrypted biometric data created from the verification requesting device are collected from the same person while keeping the biometric information secret Can be determined based on whether the Euclidean distance between the two input data is equal to or less than a certain number. In particular, it is known that biometric information cannot always stably acquire the same data. On the other hand, it can be assumed that data acquired from the same person is similar (data with a small Euclidean distance of each element can be acquired). Therefore, the verification system according to the present invention can be suitably applied to biometric authentication.

It should be noted that the entire disclosure contents of the above patent documents and non-patent documents are incorporated herein by reference. Within the scope of the entire disclosure (including claims) of the present invention, the embodiment can be changed and adjusted based on the basic technical concept. Further, various combinations or selections of various disclosed elements (including each element of each claim, each element of each embodiment, each element of each drawing, etc.) are possible within the scope of the entire disclosure of the present invention. is there. 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. In particular, with respect to the numerical ranges described in this document, any numerical value or small range included in the range should be construed as being specifically described even if there is no specific description.

In the present invention, the following modes are possible.
[Form 1]
It is as the collation system which concerns on the said 1st viewpoint.
[Form 2]
The collation system according to aspect 1, wherein the encryption unit performs encryption based on an encryption method having additive homomorphism.
[Form 3]
The collation system according to mode 2, wherein the encryption unit performs encryption based on Paillier encryption.
[Form 4]
The collation system according to any one of aspects 1 to 3, wherein the collation information generation unit generates a polynomial that becomes zero when the distance between the independent variable and the authentication data is within the threshold as the polynomial.
[Form 5]
The encryption unit further encrypts the square of the authentication data with the public key and transmits it to the third node,
The storage unit further holds the square of the encrypted authentication data,
The distance calculation unit acquires the encrypted authentication data and the square of the encrypted authentication data from the third node, and calculates the distance between the authentication target data and the authentication data as the public key. 5. The collation system according to any one of forms 2 to 4, wherein calculation is performed with encryption performed by the method.
[Form 6]
The authentication data and the data to be authenticated include an n-dimensional element,
The collation system according to mode 5, wherein the distance calculation unit calculates an n-dimensional Euclidean distance between the data to be authenticated and the authentication data while being encrypted with the public key.
[Form 7]
The authentication data and the data to be authenticated include a plurality of elements,
The distance calculation unit calculates the distance while encrypting each element,
The verification information generation unit generates the polynomial for each element,
The verification data generation unit generates the verification data for each element,
The verification system according to any one of modes 1 to 6, wherein the verification unit uses the secret key and verification data generated for the plurality of elements to verify the data to be authenticated with the authentication data. .
[Form 8]
As in the node according to the second viewpoint.
[Form 9]
The node according to mode 8, wherein the encryption unit performs encryption based on an encryption method having additive homomorphism.
[Mode 10]
The node according to mode 9, wherein the encryption unit performs encryption based on Paillier encryption.
[Form 11]
The node according to any one of forms 8 to 10, wherein the polynomial is a polynomial that becomes zero when the distance between the independent variable and the authentication data is within the threshold.
[Form 12]
The encryption unit further encrypts the square of the authentication data with the public key and transmits it to the second node,
The distance calculation unit acquires the encrypted authentication data and the square of the encrypted authentication data from the third node, and calculates the distance between the authentication target data and the authentication data as the public key. The node according to any one of forms 9 to 11, wherein the node is calculated while encrypted according to the above.
[Form 13]
The authentication data and the data to be authenticated include an n-dimensional element,
The node according to mode 12, wherein the distance calculation unit calculates an n-dimensional Euclidean distance between the data to be authenticated and the authentication data while being encrypted with the public key.
[Form 14]
The authentication data and the data to be authenticated include a plurality of elements,
The distance calculation unit calculates the distance while encrypting each element,
The collation data generation unit generates the collation data for each element using the polynomial generated for each element, and transmits the collation data to the second node. Nodes.
[Form 15]
A verification method in a verification system comprising a first node, a second node, and a third node, comprising:
The second node generates a public / private key pair and transmits the public key to the first node;
The first node encrypts authentication data with the public key and transmits it to the third node;
The third node holding the encrypted authentication data;
When the first node receives data to be authenticated that is collated with the authentication data, the encrypted authentication data is acquired from the third node, and the distance between the data to be authenticated and the authentication data Calculating with encryption using the public key;
The third node generates a polynomial including a threshold value of a distance between the data to be authenticated and the authentication data as a parameter and transmits the generated polynomial to the first node;
A step in which the first node substitutes the distance into the polynomial and encrypts a value encrypted with the public key as verification data and transmits the data to the second node;
The second node includes a step of comparing the authentication target data with the authentication data based on the secret key and the verification data.
[Form 16]
It is as the collation method which concerns on the said 3rd viewpoint.
[Form 17]
The collation method according to mode 16, wherein the first node performs encryption based on an encryption method having additive homomorphism.
[Form 18]
The collation method according to mode 17, wherein the first node performs encryption based on Paillier encryption.
[Form 19]
The collation method according to any one of modes 16 to 18, wherein the polynomial is a polynomial that becomes zero when the distance between the independent variable and the authentication data is within the threshold.
[Form 20]
The first node further includes encrypting the square of the authentication data with the public key and transmitting to the third node;
The first node acquires the encrypted authentication data and the square of the encrypted authentication data from the third node, and discloses the distance between the authentication target data and the authentication data. 20. The collation method according to any one of forms 17 to 19, wherein the calculation is performed while encrypted with a key.
[Form 21]
The authentication data and the data to be authenticated include an n-dimensional element,
The collation method according to mode 20, wherein the first node calculates an n-dimensional Euclidean distance between the data to be authenticated and the authentication data while being encrypted with the public key.
[Form 22]
The authentication data and the data to be authenticated include a plurality of elements,
The first node calculates the distance while encrypting each element,
The collation data generation unit generates the collation data for each element using the polynomial generated for each element, and transmits the collation data to the second node. Collation method.
[Form 23]
The program is related to the fourth viewpoint.
[Form 24]
The program according to mode 23, which causes the computer to execute processing for encryption based on an encryption method having additive homomorphism.
[Form 25]
The program according to mode 24, which causes the computer to execute processing for encryption based on Paillier encryption.
[Form 26]
The program according to any one of forms 23 to 25, wherein the polynomial is a polynomial that becomes zero when the distance between the independent variable and the authentication data is within the threshold.
[Form 27]
A process of encrypting the square of the authentication data with the public key and transmitting it to the third node;
Obtaining the encrypted authentication data and the square of the encrypted authentication data from the third node, and calculating the distance between the data to be authenticated and the authentication data encrypted with the public key The program according to any one of forms 24 to 26, which causes the computer to execute a process to perform.
[Form 28]
The authentication data and the data to be authenticated include an n-dimensional element,
The program according to aspect 27, causing the computer to execute a process of calculating an n-dimensional Euclidean distance between the authentication data and the authentication data while being encrypted with the public key.
[Form 29]
The authentication data and the data to be authenticated include a plurality of elements,
A process of calculating the distance for each element with encryption;
The collation data generation unit generates the collation data for each element using the polynomial generated for each element, and causes the second node to perform transmission processing on the computer. Thirty-eighth program.

DESCRIPTION OF SYMBOLS 10 Registration data generation apparatus 11 Encryption part 20 Verification request apparatus 21 Verification request part 22 Distance calculation part 23 Verification data generation part 30 Storage device 31 Storage part 32 Identifier management part 40 Data verification apparatus 41 Verification information generation part 42 Verification Information sending unit 43 Collation assistance request unit 44 Judgment unit 50 Collation assistance device 51 Key generation unit 52 Collation assistance unit 53 Overall result assistance unit 54

Collation units

100, 200, 300 Nodes

Claims

Comprising a first node, a second node and a third node;
The first node encrypts authentication data with a public key and transmits the encrypted data to the third node;
When the data to be authenticated that is collated with the authentication data is received, the encrypted authentication data is obtained from the third node, and the distance between the data to be authenticated and the authentication data is encrypted with the public key A distance calculation unit to calculate as is,
A verification data generation unit that generates a value encrypted by the public key by substituting the distance into the polynomial acquired from the third node as verification data and transmits the verification data to the second node. And
The second node generates a pair of the public key and the secret key, and transmits the public key to the first node;
A collation unit that collates the data to be authenticated with the authentication data based on the secret key and the collation data;
The third node includes a storage unit that stores the encrypted authentication data;
A collation system comprising: a collation information generating unit that generates a polynomial that includes a threshold value of a distance between the authentication data and the data to be authenticated as a parameter as the polynomial.
The verification system according to claim 1, wherein the encryption unit performs encryption based on an encryption method having additive homomorphism.
The verification system according to claim 2, wherein the encryption unit performs encryption based on Paillier encryption.
The collation according to any one of claims 1 to 3, wherein the collation information generation unit generates a polynomial that becomes zero when the distance between the independent variable and the authentication data is within the threshold as the polynomial. system.
The encryption unit further encrypts the square of the authentication data with the public key and transmits it to the third node,
The storage unit further holds the square of the encrypted authentication data,
The distance calculation unit acquires the encrypted authentication data and the square of the encrypted authentication data from the third node, and calculates the distance between the authentication target data and the authentication data as the public key. The collation system according to any one of claims 2 to 4, wherein the collation system calculates the data while encrypting it.
The authentication data and the data to be authenticated include an n-dimensional element,
The collation system according to claim 5, wherein the distance calculation unit calculates an n-dimensional Euclidean distance between the data to be authenticated and the authentication data while being encrypted with the public key.
The authentication data and the data to be authenticated include a plurality of elements,
The distance calculation unit calculates the distance while encrypting each element,
The verification information generation unit generates the polynomial for each element,
The verification data generation unit generates the verification data for each element,
The said collation part collates the said to-be-authenticated data with the said authentication data using the said secret key and the data for collation produced | generated about the said some element, The any one of Claim 1 thru | or 6 Matching system.
An encryption unit that encrypts authentication data with the public key received from the second node that generates a public key and private key pair, and transmits the encrypted authentication data to the third node;
When the data to be authenticated that is collated with the authentication data is received, the encrypted authentication data is obtained from the third node, and the distance between the data to be authenticated and the authentication data is encrypted with the public key A distance calculation unit that calculates as is,
A verification data generation unit that generates a value encrypted with the public key by substituting the distance into the polynomial acquired from the third node, and generates the verification data and transmits the verification data to the second node; ,
The polynomial is a node including a threshold value of a distance between the authentication data and the authentication data as a parameter.
A first node encrypting authentication data with the public key received from the second node that generates a public key and private key pair and transmitting the encrypted data to the third node;
When the data to be authenticated that is collated with the authentication data is received, the encrypted authentication data is obtained from the third node, and the distance between the data to be authenticated and the authentication data is encrypted with the public key The process of calculating as it is,
Including substituting the distance into the polynomial obtained from the third node and encrypting the encrypted value using the public key as verification data and transmitting the verification data to the second node.
The matching method, wherein the polynomial includes a threshold value of a distance between the authentication data and the data to be authenticated as a parameter.
A process of encrypting authentication data with the public key received from the second node that generates a public key and private key pair and transmitting the encrypted authentication data to the third node;
When the data to be authenticated that is collated with the authentication data is received, the encrypted authentication data is obtained from the third node, and the distance between the data to be authenticated and the authentication data is encrypted with the public key Processing while calculating
A process of substituting the distance into the polynomial obtained from the third node and generating a value encrypted with the public key as verification data and transmitting it to the second node. Run it on the computer provided,
The polynomial program includes a threshold value of a distance between the authentication data and the authentication target data as a parameter.