Collation system, node, collation method, and computer readable medium
09910478 ยท 2018-03-06
Assignee
Inventors
Cpc classification
H05K1/142
ELECTRICITY
H01L2924/0002
ELECTRICITY
G06F3/00
PHYSICS
H05K1/029
ELECTRICITY
H04L63/0442
ELECTRICITY
H01L2924/00
ELECTRICITY
G06F1/3212
PHYSICS
H01L23/5382
ELECTRICITY
H01L2924/0002
ELECTRICITY
H04L9/3093
ELECTRICITY
Y02D10/00
GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
H01L2924/00
ELECTRICITY
International classification
G06F3/00
PHYSICS
H04L9/30
ELECTRICITY
Abstract
A collation system includes a first node, a second node and a third node. The first node includes: an encryption unit; a distance calculation unit t; and a collation data generation unit. The second node includes: a key generation unit; and a collation unit. The third node includes: a storage unit; and a collation information generation unit.
Claims
1. A collation system comprising: a first node; a second node; and a third node, the first node including: an encryption unit that encrypts authentication data by a public key and transmits the encrypted authentication data to the third node; a distance calculation unit that acquires the encrypted authentication data from the third node when authentication target data to be collated with the authentication data is received, and calculates a distance between the authentication target data and the authentication data by the public key in an encrypted state to generate encrypted distance data; and a collation data generation unit that generates a value, which is obtained by putting the distance into a polynomial acquired from the third node and encrypting the polynomial by the public key, as data for collation, and transmits the data for collation to the second node, the second node including: a key generation unit that generates a pair of the public key and a secret key and transmits the public key to the first node; and a collation unit that collates the authentication target data with the authentication data based on the secret key and the data for collation, and the third node including: a storage unit that holds the encrypted authentication data; and a collation information generation unit that generates, as the polynomial, a polynomial including a threshold value of the distance between the authentication data and the authentication target data as a parameter, wherein the encryption unit performs encryption based on Paillier encryption.
2. The collation system according to claim 1, wherein the collation information generation unit generates, as the polynomial, a polynomial having a value of 0 when a distance between an independent variable and the authentication data is within the threshold value.
3. The collation system according to claim 1, wherein the encryption unit further encrypts a square of the authentication data by the public key and transmits the encrypted square of the authentication data to the third node, the storage unit further holds the encrypted square of the authentication data, and the distance calculation unit acquires the encrypted authentication data and the encrypted square of the authentication data from the third node, and calculates the distance between the authentication target data and the authentication data by the public key in an encrypted state.
4. The collation system according to claim 3, wherein the authentication data and the authentication target data include an n-dimensional element, and the distance calculation unit calculates an n-dimensional Euclid distance between the authentication target data and the authentication data by the public key in an encrypted state.
5. The collation system according to claim 1, wherein the authentication data and the authentication target data include a plurality of elements, the distance calculation unit calculates the distance with respect to each element in an encrypted state, the collation information generation unit generates the polynomial with respect to each element, the collation data generation unit generates the data for collation with respect to each element, and the collation unit collates the authentication target data with the authentication data by using the secret key and the data for collation generated with respect to the plurality of elements.
6. A node comprising: an encryption unit that encrypts authentication data by a public key received from a second node that generates a pair of the public key and a secret key, and transmits the encrypted authentication data to a third node; a distance calculation unit that acquires the encrypted authentication data from the third node when authentication target data to be collated with the authentication data is received, and calculates a distance between the authentication target data and the authentication data by the public key in an encrypted state to generate encrypted distance data; and a collation data generation unit that generates a value, which is obtained by putting the distance into a polynomial acquired from the third node and encrypting the polynomial by the public key, as data for collation, and transmits the data for collation to the second node, wherein the polynomial includes a threshold value of the distance between the authentication data and the authentication target data as a parameter, wherein the encryption unit performs encryption based on Paillier encryption.
7. A collation method comprising: encrypting, based on Paillier encryption, authentication data, in a first node, by a public key received from a second node that generates a pair of the public key and a secret key, and transmitting the encrypted authentication data to a third node; acquiring the encrypted authentication data in the first node from the third node when authentication target data to be collated with the authentication data is received, and calculating a distance between the authentication target data and the authentication data by the public key in an encrypted state to generate encrypted distance data; and generating a value, which is obtained, using the first node, by putting the distance into a polynomial acquired from the third node and encrypting the polynomial by the public key, as data for collation, and transmitting the data for collation to the second node, wherein the polynomial includes a threshold value of the distance between the authentication data and the authentication target data as a parameter.
8. A non-transitory computer readable medium storing a program causing a computer in a first node to execute: encrypting, based on Paillier encryption, authentication data by a public key received from a second node that generates a pair of the public key and a secret key, and transmitting the encrypted authentication data to a third node; acquiring the encrypted authentication data from the third node when authentication target data to be collated with the authentication data is received, and calculating a distance between the authentication target data and the authentication data by the public key in an encrypted state to generate encrypted distance data; and generating a value, which is obtained by putting the distance into a polynomial acquired from the third node and encrypting the polynomial by the public key, as data for collation, and transmitting the data for collation to the second node, wherein the polynomial includes a threshold value of the distance between the authentication data and the authentication target data as a parameter.
Description
BRIEF DESCRIPTION OF DRAWINGS
(1)
(2)
(3)
(4)
DESCRIPTION OF EMBODIMENTS
(5) Firstly, the overview of an exemplary embodiment will be described. In addition, reference numerals supplemented to the overview are examples for only understanding, and are not intended to limit the present invention to the illustrated exemplary embodiment.
(6)
(7) The key generation unit 51 of the second node 200 generates a pair of a public key and a secret key and transmits the public key to the first node 100. The encryption unit 11 of the first node 100 encrypts authentication data by the public key and transmits the encrypted authentication data to the third node 300. The storage unit 31 of the third node 300 holds the encrypted authentication data.
(8) When authentication target data to be collated with authentication data is received, the distance calculation unit 22 of the first node 100 acquires the encrypted authentication data from the third node 300 and calculates a distance between the authentication target data and the authentication data by the public key in an encrypted state. The collation 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 authentication target data as a parameter. The collation data generation unit 23 of the first node 100 generates a value, which is obtained by putting the calculated distance into the polynomial acquired from the third node 300 and encrypting the polynomial by the public key, as data for collation, and transmits the data for collation to the second node 200. The collation unit 54 of the second node 200 collates the authentication target data with the authentication data based on the secret key and the data for collation.
(9) Herein, preferably, the encryption unit 11 performs encryption based on an encryption scheme having additive homomorphism. As an example, the encryption unit 11 may also perform the encryption based on Paillier encryption.
(10) The collation information generation unit 41 may also, as the aforementioned polynomial, a polynomial having a value of 0 when a distance between an independent variable and the authentication data is within the aforementioned threshold value.
(11) Furthermore, the encryption unit 11 may further encrypt a square of the authentication data by the public key and transmit the encrypted square of authentication data to the third node 300, and the storage unit 31 may further hold the encrypted square of authentication data. At this time, preferably, the distance calculation unit 22 acquires the encrypted authentication data and the encrypted square of authentication data from the third node 300, and calculates the distance between the authentication target data and the authentication data by the public key in an encrypted state.
(12) Moreover, the authentication data and the authentication target data may also include an n-dimensional element. At this time, preferably, the distance calculation unit 22 calculates an n-dimensional Euclid distance between the authentication target data and the authentication data by the public key in an encrypted state.
(13) Furthermore, the authentication data and the authentication target data may also include a plurality of elements. At this time, the distance calculation unit 22 calculates the aforementioned distance with respect to each element in an encrypted state. The collation information generation unit 41 generates a polynomial with respect to each element. The collation data generation unit 23 generates data for collation with respect to each element. Preferably, the collation unit 54 collates the authentication target data with the authentication data by using the secret key and the data for collation generated with respect to the plurality of elements.
(14) According to the technology disclosed in Non-Patent Literature 1, since the data registered in the server is a plaintext as is, it is probable that the data is leaked from the server. Furthermore, there is also a problem that the secrecy of data to the server manager may not be kept.
(15) In accordance with the collation system according to the aforementioned exemplary embodiment, as well as the authentication target data sent from the client (the first node) to the server (the third node) during authentication, authentication data stored in a database and the like of the server (the third node) is also encrypted using an encryption scheme with a high degree of secrecy. Consequently, according to the collation system, the aforementioned problem in the technology disclosed in Non-Patent Literature 1 is solved. Furthermore, since the special property of homomorphism is added to the encryption scheme, it is possible to calculate a Euclid distance of data in an encrypted state, so that it is guarantee to be able to collate encrypted data without decrypting the encrypted data. Moreover, a ciphertext of a square of authentication data is added as data generated during registration, so that it is possible to calculate a distance between encrypted data, which is not possible in Non-Patent Literature 1.
(16) As described above, in accordance with the collation system according to the aforementioned exemplary embodiment, it is possible to prevent leakage of authentication data held in the third node (the server), and to prevent leakage of a plaintext of the authentication data even though a server manager is malicious. The reason for this is because the authentication data is encrypted by an encryption key not decrypted by the server manager, during data registration.
Exemplary Embodiment 1
(17) Next, a collation system according to a first exemplary embodiment will be described with reference to the drawings.
(18)
(19) In addition,
(20) The registration data generation device 10 has an encryption unit 11. The encryption unit 11 employs authentication data to be concealed and an encryption key opened by the collation assist device 50 as input, performs a concealment process on the authentication data by using the encryption key, and outputs encrypted data.
(21) Herein, the encryption key opened by the collation assist device 50 is a public key of additive homomorphism public key encryption.
(22) The storage device 30 has a storage unit 31 and an identifier management unit 32. The storage unit 31 stores the encrypted data sent from the registration data generation device 10 and a unique identifier assigned by the identifier management unit 32.
(23) The collation request device 20 has a collation request unit 21, a distance calculation unit 22, and a collation data generation unit 23. The collation request unit 21 sends a collation request to the data collation device 40 when authentication target data to be collated with authentication data is received as input. The distance calculation unit 22 employs the authentication target data to be collated and information for collation received from the data collation device 40 as input, and generates encrypted distance data. The collation data generation unit 23 employs the encrypted distance data as input and generates data for collation while communicating with the collation assist device 50.
(24) The data collation device 40 has a collation information generation unit 41, a collation information sending unit 42, a collation assist request unit 43, and a determination unit 44. The collation information generation unit 41 employs the encrypted data stored in the storage device 30 as input, and generates information for collation. The collation information sending unit 42 receives the collation request sent from the collation request device 20 as input, and sends the information for collation. The collation assist request unit 43 receives the data for collation sent from the collation request device 20 as input, generates a collation assist request, and sends the collation assist request to the collation assist device 50. The determination unit 44 receives a comprehensive result received from the collation assist device 50 as input, and generates and outputs a collation result.
(25) The collation assist device 50 has a key generation unit 51, a collation assist unit 52, and a comprehensive result assist unit 53. The key generation unit 51 generates a public key and a secret key of additive homomorphism encryption, opens the public key, and holds the secret key. The collation assist unit 52 communicates with the collation data generation unit 23 of the collation request device 20, and assists the generation of the data for collation. The comprehensive result assist unit 53 receives the collation assist request sent from the data collation device 40 and the secret key of the additive homomorphism encryption as input, and generates the comprehensive result.
(26) Next, an operation of the collation system (
(27) The operation of the collation system is classified into two phases of a data registration phase and a ciphertext collation phase. In the data registration phase, authentication data is input to the registration data generation device 10, is encrypted, and is registered in the storage device 30. On the other hand, in the ciphertext collation phase, the authentication target data input to the collation request device 20 is being kept secret and it is determined whether the authentication target data is approximate to (the Euclid distance is short) the plaintext of the encrypted data stored in the storage device 30. Hereinafter, an operation in each phase will be described in detail.
(28) [Data Registration Phase]
(29)
(30) Referring to
(31) Next, the registration data generation device 10 receives authentication data to be concealed and the public key (step A2).
(32) Next, the encryption unit 11 of the registration data generation device 10 generates encrypted data from the input authentication data and public key, and sends the encrypted data to the storage device 30 (step A3).
(33) When the encrypted data is received, the identifier management unit 32 of the storage device 30 assigns a unique identifier to the encrypted data (step A4). Furthermore, the identifier management unit 32 stores a set of the encrypted data and the identifier in the storage unit 31 (step A5).
(34) [Ciphertext Collation Phase]
(35)
(36) Referring to
(37) Next, the collation request unit 21 of the collation request device 20 receives authentication target data and a public key (step B3).
(38) Next, when the authentication target data and the public key are received, the collation request unit 21 of the collation request device 20 generates a collation request and outputs the collation request to the data collation device 40 (step B4).
(39) When the collation request is received, the collation information sending unit 42 of the data collation device 40 outputs information for collation to the collation request device 20 (step B5).
(40) When the information for collation is received, the distance calculation unit 22 of the collation request device 20 calculates a Euclid distance of the authentication target data and the plaintext of the encrypted data in an encrypted state, and generates encrypted distance data (step B6).
(41) The collation data generation unit 23 employs the encrypted distance data and the information for collation as input, generates data for collation while communicating with the collation assist unit 52 of the collation assist device 50, and outputs the data for collation to the data collation device 40 (step B7).
(42) When the data for collation is received, the collation assist request unit 43 of the data collation device 40 generates a collation assist request and outputs the collation assist request to the collation assist device 50 (step B8).
(43) When the collation assist request is received, the comprehensive result assist unit 53 of the collation assist device 50 employs the secret key as input, generates a comprehensive result, and outputs the comprehensive result to the data collation device 40 (step B9).
(44) When the comprehensive result is received, the determination unit 44 of the data collation device 40 performs determination and outputs a determination result (step B10).
(45) In accordance with the collation system according to the present exemplary embodiment, as well as authentication target data sent from the registration data generation device 10 to the storage device 30 during authentication, authentication data stored in the storage device 30 is also encrypted using an encryption scheme with a high degree of secrecy. Consequently, for example, when a server is configured by the storage device 30 and the data collation device 40, it is possible to prevent authentication data from being leaked from the server in accordance with the collation system according to the present exemplary embodiment.
Exemplary Embodiment 2
(46) Next, a collation system according to a second exemplary embodiment will be described with reference to the drawings.
(47) In the present exemplary embodiment, in the collation system according to the first exemplary embodiment, a one-dimensional Euclid distance is used as a distance. That is, when d (D,D)=(DD).sup.{2} is equal to or less than a threshold value d, it is determined that matching has been made, and when d (D,D)=(DD).sup.{2} is larger than d, it is determined that matching has not been made. Furthermore, in the present exemplary embodiment, additive homomorphism encryption (for example, Paillier encryption and the like) is used. Hereinafter, an operation in each phase will be described in detail with reference to
(48) [Data Registration Phase]
(49) Referring to
(50) Next, the registration data generation device 10 receives authentication data D to be concealed and the public key pk generated by the key generation unit 51 (step A2).
(51) Next, the encryption unit 11 of the registration data generation device 10 generates encrypted data (Enc(pk,D), Enc(pk,D.sup.2)) from the input authentication data D and public key pk, and sends the encrypted data to the storage device 30 (step A3). Herein, Enc(pk,D) indicates a result obtained by encrypting the authentication data D by using the public key pk. Similarly, Enc(pk,D.sup.2) indicates a result obtained by encrypting a square of the authentication data D by using the public key pk.
(52) The identifier management unit 32 of the storage device 30 assigns a unique identifier ID to the encrypted data when the encrypted data is received (step A4). Furthermore, the identifier management unit 32 stores a set ((Enc(pk,D), Enc(pk,D.sup.2)), ID) of the encrypted data and the identifier in the storage unit 31 (step A5).
(53) [Ciphertext Collation Phase]
(54) Referring to
(55) 1. The collation information generation unit 41 randomly generates a polynomial F(x) which is equal to 0 when x=0, 1, . . . , d and is not equal to 0 in other cases. For example, F(x)=x(x1)(x2) . . . (xd) is a polynomial of the (d+1).sup.th degree, which satisfies the aforementioned property. In general, a polynomial of the (d+1).sup.th degree or more, which satisfies such conditions, can be easily configured. For the purpose of simplification, it is assumed that coefficients of F(x) are [0] to [N]. That is, F(x)=[N]x.sup.N+[N1]x.sup.{N-1}+ . . . +[0]. When F(x)=x(x1)(x2) . . . (xd), N=d.
(56) 2. The collation information generation unit 41 employs ((Enc(pk,D),Enc(pk,D.sup.2)), [0] to [N]) as information for collation.
(57) Next, the collation request unit 21 of the collation request device 20 receives authentication target data D and the public key pk (step B3).
(58) Next, when the authentication target data D and the public key pk are received, the collation request unit 21 of the collation request device 20 generates a collation request req and outputs the collation request req to the data collation device 40 (step B4). The collation request req is a message requesting collation.
(59) When the collation request is received, the collation information sending unit 42 of the data collation device 40 outputs the information for collation to the collation request device 20 (step B5).
(60) When the information for collation is received, the distance calculation unit 22 of the collation request device 20 calculates a Euclid distance of the authentication target data D and the plaintext of the encrypted data in an encrypted state, and generates encrypted distance data as follows (step B6).
(61) 1. The distance calculation unit 22 calculates Enc(pk,D.sup.2).
(62) 2. The distance calculation unit 22 calculates Enc(pk,d(D,D))=Enc(pk,D.sup.2).Math.Enc(pk,D).sup.{2D}.Math.Enc(pk,D.sup.2).
(63) The collation data generation unit 23 employs the encrypted distance data and the information for collation as input, and generates data for collation while communicating with the collation assist unit 52 of the collation assist device 50 and outputs the data for collation to the data collation device 40 as follows (step B7).
(64) 1. The collation data generation unit 23 randomly selects r, calculates Enc(pk,r.Math.d(D,D))=Enc(pk,d(D,D)).sup.{r}, and sends it to the collation assist device 50.
(65) 2. The collation assist unit 52 of the collation assist device 50 decrypts Enc(pk,r.Math.d(D,D)) by using the secret key sk, and calculates r.Math.d(D,D).
(66) 3. The collation assist unit 52 calculates (r.Math.d(D,D)).sup.{2}, . . . , (r.Math.d(D,D)).sup.{N}, respectively encrypts them by using the public key pk, calculates Enc(pk,((.Math.d(D,D)).sup.{2})), . . . , Enc(pk,((.Math.d(D,D)).sup.{N})), and outputs it to the collation request device 20.
(67) 4. The collation data generation unit 23 calculates Enc(pk,((.Math.d(D,D)).sup.{2})).sup.{1/r^2}, . . . , Enc(pk,((.Math.d(D,D)).sup.{N})).sup.{1/(r^{N})} by using r selected in step 1, and obtains Enc(pk,(((D,D)).sup.{2})), . . . , Enc(pk,(((D,D)).sup.{N})).
(68) 5. The collation data generation unit 23 calculates Enc(pk,F(d(D,D)))=(Enc(pk,(((D,D)).sup.{N})).sup.{[N]}.Math.(Enc(pk,(((D,D)).sup.{N-1})).sup.{[N-1]} . . . (Enc(pk,d(D,D))).sup.{ [1]}.Math.Enc(pk,[0]).
(69) 6. The collation data generation unit 23 randomly selects R, calculates Enc(pk,F(d(D,D))).sup.{R}, and outputs it to the data collation device 40.
(70) Herein, step 6 is performed in order to allow output when d(D,D)<d to be randomly performed. When it is not necessary to allow the output to be randomly performed, step 6 may also be omitted. Furthermore, step 1 is performed in order to keep the value of d(D,D) secret to the collation assist device 50. When it is not necessary to keep the value of d(D,D) secret, step 1 may also be omitted.
(71) When the data for collation is received, the collation assist request unit 43 of the data collation device 40 generates a collation assist request and outputs the collation assist request to the collation assist device 50 as follows (step B8).
(72) 1. The collation assist request unit 43 randomly selects s, calculates C=Enc(pk,F(d(D,D))).sup.{R}.Math.Enc(pk,s), and outputs it to the collation assist device 50.
(73) Herein, step 1 is performed in order to prevent a collation result from being known to the collation assist device 50 by allowing a plaintext of C to be random. When the collation result is allowed to be known to the collation assist device 50, step 1 may also be omitted.
(74) When the collation assist request is received, the comprehensive result assist unit 53 of the collation assist device 50 employs the secret key sk as input, generates a comprehensive result P as follows, and outputs the comprehensive result P to the data collation device 40 (step B9). That is, the comprehensive result assist unit 53 decrypts a ciphertext C by using the secret key sk, and outputs a decryption result to the data collation device 40 as the comprehensive result P.
(75) When the comprehensive result P is received, the determination unit 44 of the data collation device 40 performs determination as follows and outputs a determination result (step B10). That is, when P=s, the determination unit 44 determines that 0d(D,D)d, and in other cases, the determination unit 44 determines that d(D,D)>d.
(76) In the present exemplary embodiment, data registered in the storage device 30 is encrypted data. Furthermore, all data sent from the collation request device 20 in the collation phase is a ciphertext. Consequently, information regarding the registered authentication data D and the authentication target data D is not absolutely leaked to the storage device 30 and the data collation device 40.
(77) Moreover, the collation request device 20 and the data collation device 40 use random numbers, so that the information regarding the registered authentication data D and the authentication target data D is not also absolutely leaked to the collation assist device 50.
Exemplary Embodiment 3
(78) Next, a collation system according to a third exemplary embodiment will be described.
(79) In the present exemplary embodiment, in the collation system according to the first exemplary embodiment, a two-dimensional Euclid distance is used as a distance. That is, when a distance d(D,D)=(DxDx).sup.{2}+(DyDy).sup.{2} of two pieces of two-dimensional data D=(Dx,Dy) and D=(Dx,Dy) is equal to or less than a threshold value d, it is determined that matching has been made, and when the distance is larger than d, it is determined that matching has not been made. Furthermore, in the present exemplary embodiment, additive homomorphism encryption (for example, Paillier encryption and the like) is used. Hereinafter, an operation in each phase will be described in detail.
(80) [Data Registration Phase]
(81) In step A3 of the data registration phase of the collation system according to the second exemplary embodiment using the one-dimensional Euclid distance as a distance, encrypted data (Enc(pk,D), Enc(pk,D.sup.2)) is replaced with encrypted data (Enc(pk,Dx),Enc(pk,Dx.sup.2),Enc(pk,Dy),Enc(pk,Dy.sup.2)).
(82) [Ciphertext Collation Phase]
(83) In the ciphertext collation phase of the collation system according to the second exemplary embodiment using the one-dimensional Euclid distance as a distance, step B6 is changed as follows.
(84) 1. Calculate Enc(pk,Dx.sup.2),Enc(pk,Dy.sup.2).
(85) 2. Calculate Enc(pk,d(D,D))=Enc(pk,Dx.sup.2).Math.Enc(pk,Dx).sup.{2Dx}.Math.Enc(pk,Dx.sup.2).Math.Enc(pk,Dy.sup.2).Math.Enc(pk,Dy).sup.{2Dy}.Math.Enc(pk,Dy.sup.2).
(86) In the present exemplary embodiment, similarly to the second exemplary embodiment, data registered in the storage device 30 is encrypted data. Furthermore, all data sent from the collation request device 20 in the collation phase is a ciphertext. Consequently, information regarding the registered authentication data D and the authentication target data D is not absolutely leaked to the storage device 30 and the data collation device 40.
(87) Moreover, the collation request device 20 and the data collation device 40 use random numbers, so that the information regarding the registered authentication data D and the authentication target data D is not also absolutely leaked to the collation assist device 50.
Exemplary Embodiment 4
(88) Next, a collation system according to a fourth exemplary embodiment will be described with reference to the drawings.
(89) In the present exemplary embodiment, in the collation system according to the first exemplary embodiment, collation of data having two or more plural elements is performed. Herein, as an example, a description will be provided for the case in which each data has two elements, one element employs a one-dimensional Euclid distance as an index, and the other element employs a two-dimensional Euclid distance as an index, so that collation is performed. That is, when two pieces of data is D=(t,(x,y)),D=(e,(x,y)), if d(t,t)d_{t} and d((x,y),(x,y))d_{e}, it is determined that matching has been made, and in other cases, it is determined that matching has not been made. Furthermore, in the present exemplary embodiment, additive homomorphism encryption (for example, Paillier encryption and the like) is used. Hereinafter, an operation in each phase will be described in detail.
(90) [Data Registration Phase]
(91) Referring to
(92) Next, the registration data generation device 10 receives authentication data D to be concealed and the public key pk generated by the key generation unit 51 (step A2).
(93) Next, the encryption unit 11 of the registration data generation device 10 generates encrypted data (Enc(pk,t),Enc(pk,t.sup.2)),(Enc(pk,x),Enc(pk,x.sup.2)),(Enc(pk,y),Enc(pk,y.sup.2)) from the input authentication data D and public key pk, and sends the encrypted data to the storage device 30 (step A3).
(94) Herein, Enc(pk,a) indicates a result obtained by encrypting data a by using the public key pk. Similarly, Enc(pk,a.sup.2) indicates a result obtained by encrypting a square of the data a by using the public key pk.
(95) The identifier management unit 32 of the storage device 30 assigns a unique identifier ID to the encrypted data when the encrypted data is received (step A4). Furthermore, the identifier management unit 32 stores a set ((Enc(pk,t),Enc(pk,t.sup.2)),(Enc(pk,x),Enc(pk,x.sup.2)),(Enc(pk,y),Enc(pk,y.sup.2)),ID) of the encrypted data and the identifier in the storage unit 31 (step A5).
(96) [Ciphertext Collation Phase]
(97) Referring to
(98) 1. The collation information generation unit 41 randomly generates a polynomial F(x) which is equal to 0 when x=0, 1, . . . , d_t and is not equal to 0 in other cases. For example, F(x)=x(x1)(x2) . . . (xd_t) is a polynomial of the (d_t+1).sup.th degree, which satisfies the aforementioned property. In general, a polynomial of the (d_t+1).sup.th degree or more, which satisfies such conditions, can be easily configured. For the purpose of simplification, it is assumed that coefficients of F(x) are [0] to [N]. That is, F(x)=[n]x.sup.n+[n1]x.sup.{n-1}+ . . . +[0]. For example, when F(x)=x(x1)(x2) . . . (xd_t), N=d_t.
(99) 2. Similarly to 1, the collation information generation unit 41 randomly generates a polynomial G(x) which is equal to 0 when x=0, 1, . . . , d_e and is not equal to 0 in other cases. For the purpose of simplification, it is assumed that coefficients of G(x) are [0] to [N]. That is, G(x)=[N]x.sup.n+[N1]x.sup.{n-1}+ . . . [0]. For example, when G(x)=x(x1)(x2) . . . (xd_e), N=d_e.
(100) 3. The collation information generation unit 41 employs ((Enc(pk,t),Enc(pk,t.sup.2)),(Enc(pk,x),Enc(pk,x.sup.2)),(Enc(pk,y),Enc(pk,y.sup.2)),[0] to [N], [0] to [N]) as information for collation.
(101) Next, the collation request unit 21 of the collation request device 20 receives input data D and the public key pk (step B3).
(102) Next, when the authentication target data D and the public key pk are received, the collation request unit 21 of the collation request device 20 generates a collation request req and outputs the collation request req to the data collation device 40 (step B4). The collation request req is a message requesting collation.
(103) When the collation request is received, the collation information sending unit 42 of the data collation device 40 outputs the information for collation to the collation request device 20 (step B5).
(104) When the information for collation is received, the distance calculation unit 22 of the collation request device 20 calculates a Euclid distance of the authentication target data and the plaintext of the encrypted data in an encrypted state, and generates encrypted distance data as follows (step B6).
(105) 1. The distance calculation unit 22 calculates Enc(pk,t.sup.2),Enc(pk,x.sup.2),Enc(pk,y.sup.2).
(106) 2. The distance calculation unit 22 calculates Enc(pk,d(t,t))=Enc(pk,t.sup.2).Math.Enc(pk,t).sup.{2t}.Math.Enc(pk,t.sup.2).
(107) 3. The distance calculation unit 22 calculates Enc(pk,d((x,y),(x,y)))=Enc(pk,x.sup.2) Enc (pk,x).sup.{2z}.Math.Enc (pk,x.sup.2).Math.Enc(pk,y.sup.2).Math.Enc(pk,y).sup.{2y}.Math.Enc (pk,y.sup.2).
(108) The collation data generation unit 23 employs the encrypted distance data and the information for collation as input, and generates data for collation while communicating with the collation assist unit 52 of the collation assist device 50 and outputs the data for collation to the data collation device 40 as follows (step B7).
(109) 1. The collation data generation unit 23 randomly selects r_t, and calculates Enc(pk,r_t.Math.d(t,t))=Enc(pk,d(t,t)).sup.{r.sup._.sup.t}.
(110) 2. The collation data generation unit 23 randomly selects r_e, calculates Enc(pk,r_e.Math.d((x,y),(x,y)))=Enc(pk,d((x,y),(x,y))).sup.{r.sup._.sup.e}, and sends it to the collation assist device 50 together with Enc(pk,r_t.Math.d(t,t)) calculated in 1.
(111) 3. The collation assist unit 52 of the collation assist device 50 decrypts Enc(pk,r_t.Math.d(t,t)) and Enc(pk,r_e.Math.d((x,y),(x,y))) by using the secret key sk, and calculates r_t.Math.d(t,t),r_e.Math.d((x,y),(x,y)).
(112) 4. The collation assist unit 52 calculates (r_t.Math.d(t,t)).sup.{2}, . . . , (r_t.Math.d(t,t)).sup.{N}, (r_e.Math.d((x,y),(x,y))).sup.{2}, . . . , (r_e.Math.d((x,y),(x,y))).sup.{N}, respectively encrypts them by using the public key pk, calculates Enc(pk,(r_t.Math.d(t,t)).sup.{2}), . . . , Enc(pk,(r_t.Math.d(t,t)).sup.{N}),Enc(pk,(r_e.Math.d((x,y),(x,y))).sup.{2}), . . . , Enc(pk,(r_e.Math.d((x,y),(x,y))).sup.{N}), and outputs it to the collation request device 20.
(113) 5. The collation data generation unit 23 calculates)) Enc(pk,((.Math.Enc(pk,(r_t.Math.d(t,t)).sup.{2}).sup.{1/r.sup._.sup.t^2}, . . . , Enc(pk,(r_t.Math.d(t,t)).sup.{N}).sup.{1/(r.sup._.sup.t)^N}, Enc(pk,(r_e.Math.d((x,y),(x,y))).sup.{2}).sup.{1/r.sup._.sup.t^2}, . . . ,Enc(pk,(r_e.Math.d((x,y),(x,y))).sup.{N}).sup.{1/(r.sup._.sup.e)^{N}} by using r_t and r_e selected in steps 1 and 2, and obtains Enc(pk,((.Math.Enc(pk,(r_t.Math.d(t,t)).sup.{2}), . . . , Enc(pk,(r_t.Math.d(t,t)).sup.{N}),Enc(pk,(r_e.Math.d((x,y),(x,y))).sup.{2}), . . . , Enc(pk,(r_e.Math.d((x,y),(x,y))).sup.{N}).
(114) 6. The collation data generation unit 23 calculates Enc(pk,F(d(t,t)))=(Enc(pk,(((t,t)).sup.{N})).sup.{[N]}.Math.(Enc(pk,(((t,t).sup.{N-1})).sup.{[N-1]} . . . (Enc(pk,d(t,t))).sup.{[1]}.Math.Enc(pk,[0]),Enc(pk,G(d((x,y),(x,y))))=(Enc(pk,((((x,y),(x,y))).sup.{N})).sup.{[N]}.Math.(Enc(pk,((((x,y),(x,y))).sup.{N-1})).sup.{[N-1]} . . . (Enc(pk,d((x,y),(x,y)))).sup.{[1]}.Math.Enc(pk,[0]).
(115) 7. The collation data generation unit 23 calculates Enc(pk,d(D,D))=Enc(pk,F(d(t,t))).Math.Enc(pk,G(d((x,y),(x,y)))).
(116) 8. The collation data generation unit 23 randomly selects R, calculates Enc(pk,F(d(D,D))).sup.{R}, and outputs it to the data collation device 40.
(117) Herein, step 8 is performed in order to allow output when d(D,D)<d to be randomly performed. When it is not necessary to allow the output to be randomly performed, step 8 may also be omitted. Furthermore, steps 1 and 2 are performed in order to keep the value of d(D,D) secret to the collation assist device 50. When it is not necessary to keep the value of d(D,D) secret, steps 1 and 2 may also be omitted.
(118) When the data for collation is received, the collation assist request unit 43 of the data collation device 40 generates a collation assist request and outputs the collation assist request to the collation assist device 50 as follows (step B8).
(119) 1. The collation assist request unit 43 randomly selects s, calculates C=Enc(pk,F(d(D,D))).sup.{R}.Math.Enc(pk,s), and outputs it to the collation assist device 50.
(120) Herein, step 1 is performed in order to prevent a collation result from being known to the collation assist device 50 by allowing a plaintext of C to be random. When the collation result is allowed to be known to the collation assist device 50, step 1 may also be omitted.
(121) When the collation assist request is received, the comprehensive result assist unit 53 of the collation assist device 50 employs the secret key sk as input, generates a comprehensive result P as follows, and outputs the comprehensive result P to the data collation device 40 (step B9). That is, the comprehensive result assist unit 53 decrypts a ciphertext C by using the secret key sk, and outputs a decryption result to the data collation device 40 as the comprehensive result P.
(122) When the comprehensive result P is received, the determination unit 44 of the data collation device 40 performs determination as follows and outputs a determination result (step B10). That is, when P=s, the determination unit 44 determines that the authentication data D and the authentication target data D have matched with each other, and in other cases, the determination unit 44 determines that the authentication data D and the authentication target data D do not match with each other.
(123) In the present exemplary embodiment, data registered in the storage device 30 is encrypted data. Furthermore, all data sent from the collation request device 20 in the collation phase is a ciphertext. Consequently, information regarding the registered authentication data D and the authentication target data D is not absolutely leaked to the storage device 30 and the data collation device 40.
(124) Moreover, the collation request device 20 and the data collation device 40 use random numbers, so that the information regarding the registered authentication data D and the authentication target data D is not also absolutely leaked to the collation assist device 50.
(125) In the present exemplary embodiment, the case, in which data includes two elements, and the elements respectively employ a one-dimensional Euclid distance and a two-dimensional Euclid distance as indexes, so that collation is performed, has been described. However, even when data includes three elements or more, the present invention can be easily applied. Furthermore, even when the Euclid distance employed as an index is a three-dimension or more, the present invention can be easily applied.
(126) The collation system according to the aforementioned exemplary embodiment, as an example, can be applied to biometric authentication using a minutia including a type, a two-dimensional coordinate, and an angle as elements. In detail, input data in the data registration phase and input data in the ciphertext collation phase are used as biometric information (a minutia) acquired from a fingerprint, a vein and the like. In this way, while the biometric information is being kept secret, it is possible to determine whether encrypted biometric data stored in a storage device and encrypted biometric data created from a collation request device have been obtained from the same person. The determination is processed by whether Euclid distances of two pieces of input data are equal to or less than a constant number. Particularly, the biometric information has been known that the same data is not able to be always stably acquired. On the other hand, it can be assumed that data acquired from the same person is similar (it is possible to acquire data in which Euclid distances of each element are short). Consequently, the collation system according to the aforementioned exemplary embodiment can be preferably applied to biometric authentication.
(127) In addition, the entire disclosure contents of the aforementioned Patent Literature and Non-Patent Literature are incorporated herein by reference. In a frame of the entire disclosure (including the appended claims) of the present invention, modification and adjustment of the exemplary embodiment are further possible based on the basic technical scope thereof. Furthermore, in the frame of the entire disclosure of the present invention, various combinations and selections of various disclosure elements (including each element of each claim, each element of each exemplary embodiment, each element of each drawing, and the like) are possible. That is, it is of course that the present invention includes various modifications and corrections which can be obtained by those skilled in the art according to the entire disclosure including the appended claims and the technical scope. Particularly, for a numerical value range disclosed herein, it should be noted that an arbitrary numerical value or a small range included in the range has been disclosed in detail even though there is no particular mention.
(128) In addition, in the present invention, the following exemplary embodiments are possible.
Exemplary Embodiment 1
(129) It is a collation system according to the aforementioned first aspect.
Exemplary Embodiment 2
(130) The collation system according to the exemplary embodiment 1, the encryption unit performs encryption based on an encryption scheme having additive homomorphism.
Exemplary Embodiment 3
(131) The collation system according to the exemplary embodiment 2, the encryption unit performs encryption based on Paillier encryption.
Exemplary Embodiment 4
(132) The collation system according to any one of exemplary embodiments 1 to 3, the collation information generation unit generates, as the polynomial, a polynomial having a value of 0 when a distance between an independent variable and the authentication data is within the threshold value.
Exemplary Embodiment 5
(133) The collation system according to any one of the exemplary embodiments 2 to 4, the encryption unit further encrypts a square of the authentication data by the public key and transmits the encrypted square of the authentication data to the third node, the storage unit further holds the encrypted square of the authentication data, and the distance calculation unit acquires the encrypted authentication data and the encrypted square of the authentication data from the third node, and calculates the distance between the authentication target data and the authentication data by the public key in an encrypted state.
Exemplary Embodiment 6
(134) The collation system according to the exemplary embodiment 5, the authentication data and the authentication target data include an n-dimensional element, and the distance calculation unit calculates an n-dimensional Euclid distance between the authentication target data and the authentication data by the public key in an encrypted state.
Exemplary Embodiment 7
(135) The collation system according to any one of the exemplary embodiments 1 to 6, the authentication data and the authentication target data include a plurality of elements, the distance calculation unit calculates the distance with respect to each element in an encrypted state, the collation information generation unit generates the polynomial with respect to each element, the collation data generation unit generates the data for collation with respect to each element, and the collation unit collates the authentication target data with the authentication data by using the secret key and the data for collation generated with respect to the plurality of elements.
Exemplary Embodiment 8
(136) It is the collation system according to the aforementioned second aspect.
Exemplary Embodiment 9
(137) The node according to the exemplary embodiment 8, the encryption unit performs encryption based on an encryption scheme having additive homomorphism.
Exemplary Embodiment 10
(138) The node according to the exemplary embodiment 9, the encryption unit performs encryption based on Paillier encryption.
Exemplary Embodiment 11
(139) The node according to any one of the exemplary embodiments 8 to 10, the polynomial is a polynomial having a value of 0 when a distance between an independent variable and the authentication data is within the threshold value.
Exemplary Embodiment 12
(140) The node according to any one of the exemplary embodiments 9 to 11, wherein the encryption unit further encrypts a square of the authentication data by the public key and transmits the encrypted authentication data to the second node, and the distance calculation unit acquires the encrypted authentication data and the encrypted square of authentication data from the third node, and calculates the distance between the authentication target data and the authentication data by the public key in an encrypted state.
Exemplary Embodiment 13
(141) The node according to the exemplary embodiment 12, the authentication data and the authentication target data include an n-dimensional element, and the distance calculation unit calculates an n-dimensional Euclid distance between the authentication target data and the authentication data by the public key in an encrypted state.
Exemplary Embodiment 14
(142) The node according to any one of the exemplary embodiments 8 to 13, the authentication data and the authentication target data include a plurality of elements, the distance calculation unit calculates the distance with respect to each element in an encrypted state, and the collation data generation unit generates the data for collation with respect to each element by using the polynomial generated with respect to each element, and transmits the data for collation to the second node.
Exemplary Embodiment 15
(143) A collation method in a collation system includes a first node, a second node, and a third node. The collation method includes:
(144) a step in which the second node which generate a pair of a public key and a secret key and transmits the public key to the first node;
(145) a step in which the first node which encrypt authentication data by the public key and transmits the encrypted authentication data to the third node;
(146) a step in which the third node which hold the encrypted authentication data;
(147) when authentication target data to be collated with the authentication data is received, the first node which acquire the encrypted authentication data from the third node, and calculate a distance between the authentication target data and the authentication data by the public key in an encrypted state;
(148) a step in which the third node which generate a polynomial including a threshold value of the distance between the authentication target data and the authentication data as a parameter, and transmit the polynomial to the first node;
(149) a step in which the first node which generate a value, which is obtained by putting the distance into the polynomial and encrypting the polynomial by the public key, as data for collation, and transmit the data for collation to the second node; and
(150) a step in which the second node which collate the authentication target data with the authentication data based on the secret key and the data for collation.
Exemplary Embodiment 16
(151) It is the collation method according to the aforementioned third aspect.
Exemplary Embodiment 17
(152) The collation method according to the exemplary embodiment 16, the first node performs encryption based on an encryption scheme having additive homomorphism.
Exemplary Embodiment 18
(153) The collation method according to the exemplary embodiment 17, the first node performs encryption based on Paillier encryption.
Exemplary Embodiment 19
(154) The collation method according to any one of the exemplary embodiments 16 to 18, the polynomial is a polynomial having a value of 0 when a distance between an independent variable and the authentication data is within the threshold value.
Exemplary Embodiment 20
(155) The collation method according to any one of the exemplary embodiments 17 to 19, further includes:
(156) a step in which the first node which encrypt a square of the authentication data by the public key and transmit the encrypted square of authentication data to the third node,
(157) wherein the first node acquires the encrypted authentication data and the encrypted square of authentication data from the third node, and calculates the distance between the authentication target data and the authentication data by the public key in an encrypted state.
Exemplary Embodiment 21
(158) The collation method according to the exemplary embodiment 20, wherein the authentication data and the authentication target data include an n-dimensional element, and
(159) the first node calculates an n-dimensional Euclid distance between the authentication target data and the authentication data by the public key in an encrypted state.
Exemplary Embodiment 22
(160) The collation method according to any one of the exemplary embodiments 16 to 21, the authentication data and the authentication target data include a plurality of elements, the first node calculates the distance with respect to each element in an encrypted state, the collation information generation unit generates the polynomial with respect to each element, the collation data generation unit generates the data for collation with respect to each element, and the collation unit collates the authentication target data with the authentication data by using the secret key and the data for collation generated with respect to the plurality of elements, and transmits the data for collation to the second node.
Exemplary Embodiment 23
(161) It is the program according to the aforementioned fourth aspect.
Exemplary Embodiment 24
(162) The program according to the exemplary embodiment 23, wherein the program causes the computer to execute a process of performing encryption based on an encryption scheme having additive homomorphism.
Exemplary Embodiment 25
(163) The program according to the exemplary embodiment 24, the first node performs encryption based on Paillier encryption.
Exemplary Embodiment 26
(164) The program according to any one of the exemplary embodiments 23 to 25, the polynomial is a polynomial having a value of 0 when a distance between an independent variable and the authentication data is within the threshold value.
Exemplary Embodiment 27
(165) The program according to any one of the exemplary embodiments 24 to 26, the program causes the computer to execute:
(166) a process of encrypting a square of the authentication data by the public key and transmitting the encrypted square of the authentication data to the third; and
(167) a process of acquiring the encrypted authentication data and the encrypted square of the authentication data from the third node, and calculating the distance between the authentication target data and the authentication data by the public key in an encrypted state.
Exemplary Embodiment 28
(168) The program according to the exemplary embodiment 27, the program causes the computer to execute: the authentication data and the authentication target data include an n-dimensional element, and
(169) a process of calculating an n-dimensional Euclid distance between the authentication target data and the authentication data by the public key in an encrypted state.
Exemplary Embodiment 29
(170) The program according to any one of the exemplary embodiments 23 to 28, the program causes the computer to execute:
(171) the authentication data and the authentication target data include a plurality of elements,
(172) a process of calculating the distance with respect to each element in an encrypted state, and the collation data generation unit generates the data for collation with respect to each element by using the polynomial generated with respect to each element, and transmits the data for collation to the second node.
REFERENCE SIGNS LIST
(173) 10 registration data generation device 11 encryption unit 20 collation request device 21 collation request unit 22 distance calculation unit 23 collation data generation unit 30 storage device 31 storage unit 32 identifier management unit 40 data collation device 41 collation information generation unit 42 collation information sending unit 43 collation assist request unit 44 determination unit 50 collation assist device 51 key generation unit 52 collation assist unit 53 comprehensive result assist unit 54 collation unit 100,200,300 node