WO2017170780A1 - Cryptogram collation system, node device, cryptogram collation method, and program - Google Patents

Abstract

The present invention makes it possible to speed up an arithmetic operation and enables a safer collation process. According to the present invention, a registration request device encrypts a polynomial generated from registration information that is a numerical vector by using an encryption key, a collation auxiliary device generates a challenge derived by encrypting a polynomial in which the coefficient of one term is a random number and the coefficients of other terms are 0, and an authentication request device generates, as a response, a cryptogram of the product of the challenge and a polynomial generated from authentication information. The collation auxiliary device generates a cryptogram of the distance between the registration information and the authentication information on the basis of a cryptogram of the polynomial generated from the registration information and a cryptogram of the product of a challenge auxiliary comprising the one coefficient and an order and a polynomial generated from the authentication information, and transmits the cryptogram of the distance between the registration information and the authentication information to a verification device. The verification device decrypts the cryptogram of the distance between the registration information and the authentication information using a decryption key, and calculates the distance.

Description

Ciphertext verification system, node device, ciphertext verification method, and program

(Description of related applications)
The present invention is based on the priority claim of Japanese Patent Application No. 2016-072770 (filed on Mar. 31, 2016), the entire contents of which are incorporated herein by reference. Shall.
The present invention relates to encryption technology, and in particular, to a ciphertext verification system, a node device, a ciphertext verification method, and a program.

As cloud computing (cloud) becomes widespread, cloud services that manage client data using cloud-side computer resources that are connected to a communication network by clients are becoming widespread. For example, since the service manages highly confidential data of the client, it is necessary to ensure that the data handled in the service is secure on the cloud side.

Research on technology that manages data in an encrypted state in a network environment where users can freely connect to a communication network (open), and performs searches, statistical processing, etc. without decrypting the data Development is underway.

Recently, crimes using vulnerabilities in personal authentication using passwords or magnetic cards have frequently occurred. As a result, biometric authentication technology that realizes authentication with higher safety using information (biometric information) based on characteristics of a biometric feature such as fingerprints or veins has attracted attention.

In one typical example of well-known biometric authentication technology, a client creates a template based on biometric information extracted from a biometric subject to registration, and the created template is transmitted to the server and stored in the server. . In the biometric authentication technology, the server performs matching processing using biometric information extracted by the client from the biometric subject to authentication and a template stored in the server (a template created by the client and transmitted to the server).

A plurality of pieces of biological information extracted from the same living body do not always match completely. However, when a distance is measured using a certain distance function, the distance between the plurality of pieces of biological information extracted from the same living body is different. It is known that the distance is shorter than the distance between a plurality of pieces of biometric information extracted from each.

The biometric authentication technology uses the above-described properties to collate a template generated based on a registration target with biometric information created based on the authentication target. That is, in biometric authentication technology,
The authentication target is accepted when the biological information extracted from the biometric target that is the registration target and the biometric information extracted from the biometric target that is the authentication target are similar (or coincident).
The authentication target is not accepted when the biometric information extracted from the biometric target to be registered and the biometric information extracted from the biometric target to be authenticated are not similar (or matched).

Generally, the similarity of biometric information is determined by distance as described above. That is,
-It will be accepted if the distance between the biological information extracted from the living body to be registered and the biological information extracted from the living body to be authenticated is equal to or less than a predetermined threshold.
-If the distance between the biometric information extracted from the biometric target to be registered and the biometric information extracted from the biometric target to be authenticated is larger than a predetermined threshold value, it is not accepted.

For example, the characteristics of living bodies such as fingerprints and veins are data that does not change throughout life. Since the damage caused when the biometric information is leaked outside the verification system is enormous, the biometric information is one of information that requires confidentiality. Therefore, even if the template leaks to the outside from a collation system that collates a template generated based on biometric information extracted from a biometric subject to registration and biometric information created based on an authentication target, It is desirable to satisfy the property that biological information does not leak outside.

Also, in the biometric authentication technology, as with other authentication technologies, it is necessary to prevent a biometric body different from the biometric registered biometric information from impersonating the biometric subject of registration (ie, “spoofing”). For example, it can be said that an authentication technique that succeeds in authentication by transmitting a specific value to the verification system is not sufficiently resistant to impersonation.

Furthermore, in the authentication technology, there is a risk that the communication content at the time of authentication is wiretapped (intercepted) as well as the risk of the template leaking. In the authentication technology, it is necessary to prevent the above-mentioned impersonation even if the communication content is wiretapped. For example, when an authentication target is accepted, a method in which data transmitted to the verification system is re-accepted by resending the data is not sufficiently resistant to impersonation.

For example, Non-Patent Document 2 discloses a biometric authentication method that enables authentication while keeping biometric information extracted from a biometric subject to be registered and biometric information extracted from a biometric subject being authenticated. It is disclosed. Non-Patent Document 1 discloses a homomorphic encryption method having homomorphism regarding addition and multiplication.

Outline of homomorphic encryption method. The homomorphic cryptosystem is a public key cryptosystem having a special property called homomorphism or homomorphism.

Public key cryptography is
An algorithm (key generation algorithm) for generating a public key (referred to as “encryption key”) and a secret key (referred to as “decryption key”);
-An algorithm that encrypts the message using the generated encryption key (encryption algorithm), and
-An algorithm for decrypting ciphertext using the generated decryption key (decryption algorithm)
including.

The key generation algorithm (denoted as “Gen”) is an algorithm for calculating the encryption key pk and the decryption key sk based on the security parameter λ.
Gen (λ) → (pk, sk) (Formula 1)
It is expressed. The security parameter λ is a measure representing the security of encryption, and is a parameter that determines the length of the encryption key and the decryption key.

The encryption algorithm (denoted as “Enc”) is an algorithm for calculating a ciphertext c in which the message x is encrypted using the encryption key pk based on the encryption key pk and the message x.
Enc (pk, M) → c (Formula 2)
It is expressed.

The decryption algorithm (denoted as “Dec”) is an algorithm for calculating a decryption result X obtained by decrypting the ciphertext c using the decryption key sk based on the decryption key sk and the ciphertext c.
Dec (sk, c) → X (Expression 3)
It is expressed.

However,
A (B) → C (Formula 4)
Means that if B is input to algorithm A, C is output.

The public key cryptosystem has homomorphism when the condition shown in the following formula 5 is satisfied.

Enc (pk, x1 # x2) = Enc (pk, x1) @Enc (pk, x2) (Formula 5)

However, # and @ each represent a binary operator. X1 and x2 each represent a message.

Especially, when # is addition, a public key cryptosystem that satisfies the condition shown in Equation 5 is said to have homomorphism for addition. The calculation of Enc (pk, x1) @Enc (pk, x2) in this case is called “addition of ciphertext”.

Also, when # is multiplication, a public key cryptosystem that satisfies the condition shown in Expression 5 is said to have homomorphism for multiplication. The calculation of Enc (pk, x1) @Enc (pk, x2) in this case is called “ciphertext multiplication”.

Furthermore, by applying ciphertext addition and ciphertext multiplication, there are homomorphic ciphers that satisfy the condition shown in Equation 6 below.

Enc (pk, n # x) = Enc (pk, x) @n (Expression 6)

However, # and @ each represent a binary operator. X and n each represent a message.

Especially, when # is addition, a public key cryptosystem that satisfies the condition shown in Equation 6 is said to have homomorphism with respect to scalar multiplication. The calculation of Enc (pk, x) @n in this case is called “scalar multiplication of ciphertext”.

A homomorphic encryption method having homomorphism for addition and multiplication described in Non-Patent Document 1 will be described. This scheme is a cipher based on the difficulty of the ring-LWE problem that treats polynomials as messages. A feature of cryptography based on the difficulty of the ring-LWE problem is that the computation can be performed at high speed.

The key generation algorithm mainly receives four parameters N, q, t, and σ as inputs.

N is an integer of 2 冪 and defines a polynomial ring R = Z [x] / <x ^N +1> that is a remainder ring by the polynomial x ^N +1.

q is a prime number congruent with 1 (q≡1 mod 2N) modulo 2N, and defines a polynomial ring R _q = R / qR = Z _q [x] / <x ^N +1> representing the ciphertext space (Rq Is an (N-1) th order polynomial) where each coefficient is an element of the group Zq.

t is a positive integer smaller than q (not necessarily a prime number), and defines a polynomial ring R _t = R / tR = (Z / tZ) [x] / <x ^N +1> representing a plaintext space in the cryptosystem. (The element of R _t is an (N−1) th order polynomial in which each coefficient is an element of the remainder group Z / tZ).

σ is the standard deviation of the N-dimensional discrete Gaussian distribution χ = D (Z ^N , σ). An N-dimensional integer vector sampled by an N-dimensional discrete Gaussian distribution is a vector having, as components, integer values obtained by rounding real values according to a Gaussian distribution (also called normal distribution) having a standard deviation of σ.
The probability density function of an N-dimensional discrete Gaussian distribution with a standard deviation of σ is

A polynomial ε (x) εR is sampled from an N-dimensional discrete Gaussian distribution χ = D (Z ^N , σ) with a standard deviation σ. Polynomial addition and multiplication are defined by modulo (x ^N + 1, q).

Next, one element (N−1 order polynomial) s∈R sampled from the N-dimensional discrete Gaussian distribution χ with standard deviation σ is fixed.

Next, it is assumed that ring elements (N-1th order polynomials where each coefficient is smaller than q) p ₁ ∈R _q sampled uniformly and randomly from R _q . An element eεR obtained from an N-dimensional discrete Gaussian distribution χ with a standard deviation of σ is taken.

next,
p ₀ = − (p ₁ × s + t × e) (Equation 8)
Calculate

pk = (p ₀ , p ₁ ) (Equation 9)
Is the public key (encryption key)
sk = s (Equation 10)
Is a secret key (decryption key).

However, in the case of calculating the product of the polynomial as in the case of calculating the polynomial p ₀ , when the degree of the polynomial is N or more, the following replacement is performed.

x ^N = (x ^N +1) -1 = −1 mod (x ^N +1) (Formula 11-1)
^{x N + 1 = x (x} N +1) -x = -x mod (x N +1) ··· ( Equation 11-2)

Furthermore, when calculating the sum or product of polynomials, if each coefficient is equal to or greater than q, the coefficient is calculated by replacing it with the remainder divided by q (mod q). As a result, the calculated polynomial is always an N-1 or lower order polynomial in which each coefficient is smaller than q. The same applies to the following calculations.

The encryption algorithm includes, as inputs, a set of four parameters (N, q, t, σ) input to the above key generation algorithm, and an encryption key pk = (p ₀ , p generated by the above key generation algorithm) ₁ ) and message x are received.

However, the message x (xεR _t ) is an N−1 order polynomial in which each coefficient is smaller than t.

Next, three N−1 order polynomials u, g, and f are generated according to an N-dimensional discrete Gaussian distribution χ having a standard deviation of σ.

Next, from the N−1th order polynomials u, g and f and the encryption key (public key) pk, t,
c ₀ = p ₀ × u + t × g + x (Formula 12-1)
c ₁ = p ₁ × u + t × f (Formula 12-2)
Calculate

And
c = (c ₀ , c ₁ ) ∈ (R _q ) ² (Equation 13)
Are output as ciphertext.

The decryption algorithm receives as input the four parameter pairs (N, q, t, σ) input to the key generation algorithm, the decryption key sk, and the ciphertext c = (c ₀ , c ₁ ) ∈ (R _q ) ² or (c ₀ , c ₁ , c ₂ ) ε (R _q ) ³
Receive. Hereinafter, in the former case, it is considered that c ₂ = 0.

next,
C = c ₀ + c ₁ × sk + c ₂ × sk ² (Expression 14)
Calculate

If the number of polynomials included in the ciphertext is l + 1,
For c = (c ₀ ,..., c _l ) ∈ (R _q ) ^{l + 1} ,
C = Σ _{i = 0 to l} c _i sk ⁱ ∈ R _q (Equation 15)
Calculate

Suppose D is the remainder of dividing C by q. If D is greater than or equal to q / 2, D is changed to Dq. This is a remainder operation to [−q / 2, q / 2) modulo D of q.

Next, the remainder (D mod t) obtained by dividing D by t is output as a decryption result X.

This public key cryptosystem has homomorphism in addition and information.

For the two messages x and y, the ciphertexts are respectively Enc (pk, x) → (c ₀ , c ₁ ) (Equation 16-1)
Enc (pk, y) → (d ₀ , d ₁ ) (Equation 16-2)
And

At this time, the addition of the ciphertext is
Enc (pk, x) + Enc (pk, y) = (c ₀ + d ₀ , c ₁ + d ₁ ) (Expression 17)
Can be calculated by

Applying the case of x = y in the addition of ciphertext, a scalar multiple of the ciphertext can be calculated for any integer n smaller than t. That is, the scalar multiple of the ciphertext is
n × Enc (pk, x) = (n × c ₀ , n × c ₁ ) (Equation 18)
Can be calculated by

Ciphertext multiplication is
Enc (pk, x) @Enc (pk, y) = (c ₀ × d ₀ , c ₀ × d ₁ + c ₁ × d ₀ , c ₁ × d ₁ ) (Equation 19)
Can be calculated by

This public key cryptosystem handles polynomials as messages. A vector can be regarded as a polynomial by regarding each component as a coefficient of the polynomial. Therefore, the vector can be encrypted using this public key cryptosystem.

Described below is a method of calculating a ciphertext of an inner product while encrypting two vectors by devising a method of converting vectors into polynomials and further using additive homomorphism and multiplicative homomorphism.

Two L (L <N) order vectors, each component being smaller than t,
A = (a ₀ ,..., A _L−1 ),
B = (b ₀ ,..., B _L−1 )
And

Using the components of the vector A as the coefficients in the ascending order and the components of the vector B as the coefficients in the descending order, the polynomials f _A and f _B are obtained according to the equations 20 and 21, respectively.

f _A (x) = Σ _{i = 0 to L−1} a _i × x ⁱ (Equation 20)

f _B (x) = − Σ _{i = 0 to L−1} b _i × x ^N−i (Expression 21)

The calculation methods of Equation 20 and Equation 21 for converting a vector into a polynomial are called “ascending polynomialization” and “descending polynomialization”, respectively. The product of the two polynomials f _A and f _B is calculated as follows:

f _A (x) × f _B (x) = − Σ _{i = NL + 1 to N−1} (Σ _{j = 0 to i} (a _j × b _{N−i + j} )) x ⁱ + Σ _{i = 0 to L−1} Σ _{j = i to L−1} (a _j × b _j−i ) x ⁱ (Equation 22)

The constant term of the polynomial in Equation 22 is Σ _j (a _j × b _j ), that is, the inner product of vectors A and B <A, B> = Σ _{i = 0 to n−1} a _i × b _i. 23)
Is equal to

Two vectors A = (a ₀ ,..., A _L−1 ), each component being 0 or 1;
B = (b ₀ ,..., B _L−1 )
, The number of different components among the corresponding components is referred to as a Hamming distance d _H (A, B).

That is, for each i (i = 0,..., L−1), the number of _i satisfying a _i ≠ b _i is the Hamming distance. The Hamming distance of two vectors can be calculated using the inner product.

Suppose that the N-dimensional vector C is a vector in which all components are 1, that is, C = (1,..., 1). At this time, the following equation 24 holds for the Hamming distance.

d _H (A, B) = <A, C> + <C, B> −2 <A, B> (Equation 24)

Two vectors A = (a ₀ ,..., A _L−1 ),
B = (b ₀ ,..., B _L−1 )
For Euclidean distance between A and B,
d _E (A, B) = Σ _{i = 0 to n−1} (a _i −b _i ) ² (Equation 25)
Defined by

The Euclidean distance between the two vectors can be calculated using the inner product as shown in Equation 26 below.

d _E (A, B) = (Σ _{i = 0 to n−1} a _i ² ) + (Σ _{i = 0 to n−1} b _i ² ) −2 <A, B> (Equation 26)

The biometric authentication method described in Non-Patent Document 2 is configured using homomorphic encryption methods (Gen, Enc, Dec) having homomorphism for addition and multiplication described in Non-Patent Document 1 above. The

In this method, it is assumed that vectors less than Nth order can be extracted from a living body, the hamming distance of vectors extracted from the same living body is short, and the hamming distance of vectors extracted from different living bodies is long. The above formula 24 is used for calculation of the Hamming distance.

The biometric authentication method described in Non-Patent Document 1 is executed as follows. Biometric information A = (a ₀ ,..., A _L−1 ) represented in the form of a vector in which each component is 0 or 1
, The client converts the vector A into an ascending polynomial according to the above equation 20 to be f _A, and the ciphertext Enc (pk, f _A ) encrypted using the encryption key pk as a template Remember me.

Biological information B = (b ₀ ,..., B _L−1 ) represented in the form of a vector in which each component is 0 or 1
For, when performing the authentication, the client, the vector B, and f _B and descending polynomial in accordance with Equation 21 above, the ciphertext Enc (pk, f _B) encrypted using the encryption key pk to the server Send.

The server uses a polynomial f _C = Σ _{i = 0 to n−1} x ⁱ (equation 27) in which all coefficients are 1.
Is calculated using the encryption key pk, and Enc (pk, f _C ) is calculated.
_{Enc (pk, f A) @Enc} (pk, f C) + Enc (pk, f C) @Enc (pk, f B) -2Enc (pk, f A) @Enc (pk, f B) ··· ( Equation 28)
Calculate

This is sent to an entity having a decryption key different from that of the server and the client, so that the entity decrypts the ciphertext.

A constant term of a polynomial, which is a message obtained by decoding with the entity, is a Hamming distance d _H (A, B) between two vectors A and B.

The authentication result can be determined depending on whether the obtained Hamming distance is longer or shorter than a predetermined threshold.

Further, it is pointed out that non-patent document 3 can also perform authentication based on the length of the Euclidean distance by using the method of non-patent document 2 and the above equation 26 (distance between two vectors).

Also, the method of Non-Patent Document 2 does not have resistance to spoofing attacks. For example, when the communication content is wiretapped and accepted, it is accepted again by retransmitting the data transmitted to the verification system.

Specifically, when the client authenticates the biometric information B = (b ₀ ,..., B _L−1 ), the client converts the vector B into a descending order polynomial according to the above equation 21 to f _B. , The ciphertext Enc (pk, f _B ) is sent to the server and accepted.

The Enc (pk, _{f B)} eavesdropping the attacker Enc (pk, _{f B)} and the the resending it, so that the attacker is accepted.

In the methods of Non-Patent Document 2 and Non-Patent Document 3, an entity having a decryption key calculates a distance between biological information. In Non-Patent Document 4, it is pointed out that restoration of registered biometric information by the entity cannot be prevented in a situation where an entity that can obtain the distance between the biometric information can perform an active attack. . Furthermore, Non-Patent Document 4 describes a method of calculating an authentication result for all entities including the entity having a decryption key while keeping the distance between biometric information secret.

Brakerski, Z .; Vaikuntanathan, V., "Fully homomorphic encryption from ring-LWE and security for key dependent messages", CRYPTO 2011 Yasuda, M .; Shimoyama, T .; Kogure, J .; Yokoyama, K .; Koshiba, T., "Secure Pattern Matching Using Somewhat Homomorphic Encryption", CCSW 2013. Yasuda, M .; Shimoyama, T .; Kogure, J .; Yokoyama, K .; Koshiba, T., "Practical Packing Method in Somewhat Homomorphic Encryption", DPM2013. Haruna Higo; Toshiyuki Isshiki; Kengo Kashimori; Kengo Kashio, “Secret biometric authentication method to conceal the distance between biometric information”, 2016 Cryptography and Information Security Symposium (SCIS2016).

Related technology analysis is given below.

Since the biometric authentication method described in Non-Patent Document 2 is configured using encryption based on the difficulty of the ring-LWE problem, the computation at the time of authentication is light.

However, as described above, the biometric authentication method described in Non-Patent Document 2 is not sufficiently resistant to impersonation.

Therefore, there is a demand for a biometric authentication method capable of performing calculations at high speed and preventing leakage of biometric information and spoofing attacks.

The object of the present invention was devised in view of the above-mentioned problems, and one of the objects is to perform ciphertext verification that makes it possible to increase the speed of computation and to prevent leakage of biometric information and spoofing attacks. A system, a node, a method, and a program therefor are provided.

The ciphertext matching system according to one aspect of the present invention includes a registration requesting device, a verification assisting device, an authentication requesting device, and a verification device. The verification device calculates a pair of encryption keys and decryption keys of a homomorphic encryption method capable of performing a polynomial operation, and discloses the encryption key. The registration requesting apparatus polynomializes registration information that is a numerical vector, and encrypts the registration information that has been polynomialized using the encryption key. When receiving the authentication request from the authentication requesting device, the verification assisting device randomly selects one coefficient and its order, generates a polynomial in which coefficients other than the order coefficient are 0, and the polynomial is A challenge consisting of a ciphertext encrypted using an encryption key is sent to the authentication requesting device. The authentication requesting device polynomializes authentication information that is a numerical vector, and based on the authentication information that is polynomialized and the challenge from the verification auxiliary device, the authentication that is polynomialized using the encryption key A ciphertext of a product of information and the polynomial used to generate the challenge is calculated, and the ciphertext of the product of the authentication information polynomialized and the polynomial used to generate the challenge is the response As shown in FIG. The verification assisting device, upon receiving a response from the authentication requesting device, based on the response, a challenge assist consisting of the one coefficient and its order, and the registration information encrypted by the registration requesting device, A ciphertext of the distance between the registration information and the authentication information is calculated using an encryption key, and the ciphertext of the distance between the registration information and the authentication information is sent to the verification device. The verification device decrypts the encrypted text of the distance between the registration information and the authentication information received from the verification assisting device using the decryption key to calculate the distance, and the calculated distance or the distance And a comparison result with a predetermined threshold value are output as a comparison result.

An apparatus according to an aspect of the present invention is a verification assisting apparatus that acquires the encryption key published by a verification apparatus that calculates a pair of encryption key and decryption key of a homomorphic encryption method capable of polynomial operation, When an authentication request is received from the authentication requesting device, one coefficient and its order are selected at random, a polynomial with coefficients other than the order coefficient set to 0 is generated, and the polynomial is encrypted using the encryption key. A challenge generator configured to send a challenge composed of encrypted ciphertext to the authentication requesting device, and polynomialize authentication information that is a numerical vector, and based on the challenge, using the encryption key, the authentication information that is polynomialized and A ciphertext of a product of the polynomial used to generate the challenge is calculated, and the ciphertext of the product of the polynomialized authentication information and the polynomial used to generate the challenge is Registration information that is received as a response from the authentication requesting device, received as a response, challenge assistance consisting of the one coefficient and its order, and stored in a storage device encrypted by the registration requesting device A ciphertext of the distance between the registration information and the authentication information is calculated using the encryption key, and the ciphertext of the distance between the registration information and the authentication information is sent to a verification device. And comprising. In the verification device, the distance between the registration information and the authentication information is decrypted using the decryption key to calculate the distance, and the calculated distance or the distance and a predetermined threshold value are calculated. The comparison result is output as a matching result.

An apparatus according to an aspect of the present invention is an authentication request for obtaining a pair of encryption keys and decryption keys of a homomorphic encryption method capable of polynomial operations and obtaining the encryption key from a verification device that discloses the encryption key An authentication information extraction unit that polynomializes authentication information that is a numerical vector, and an authentication request generation unit that generates an authentication request to be transmitted to the verification auxiliary device. Further, upon receiving the authentication request, one coefficient and its order are selected at random, a polynomial in which coefficients other than the order coefficient are set to 0 is generated, and the polynomial is encrypted using the encryption key. The challenge received from the verification assistant device that sends a challenge composed of ciphertext to the authentication request device, and based on the authentication information polynomialized by the authentication request generator and the challenge, using the encryption key To calculate a ciphertext of the product of the authentication information polynomialized and the polynomial used to generate the challenge, and the product of the polynomialized authentication information and the polynomial used to generate the challenge The apparatus further includes a response generation unit that sends the ciphertext as a response to the verification assisting device. The verification assisting device uses the encryption key based on the response, challenge assistance consisting of the one coefficient and its order, and polynomialized registration information encrypted by the registration requesting device. The ciphertext of the distance between the registration information and the authentication information is calculated, and the ciphertext of the distance between the registration information and the authentication information is sent to the verification device.

When receiving an authentication request from an authentication requesting device, an apparatus according to an aspect of the present invention randomly selects one coefficient and its order, generates a polynomial in which coefficients other than the order coefficient are 0, and the polynomial Is sent to the authentication requesting device and a response is received from the authentication requesting device. And a ciphertext of the distance between the registration information and the authentication information using the encryption key based on the registration information encrypted by the registration request device and stored in the storage device. A verification device connected to an auxiliary device, wherein the key generation unit calculates a pair of the encryption key and the decryption key of a homomorphic encryption method capable of performing a polynomial operation, and discloses the encryption key; When the ciphertext of the distance between the registration information and the authentication information is received from a device, the ciphertext of the distance between the registration information and the authentication information is decrypted using the decryption key to calculate the distance And a collation result generation unit that outputs the calculated distance or a comparison result between the distance and a predetermined threshold value as a collation result.

The method according to one aspect of the present invention is a ciphertext processing method by at least one computer,
(A) calculating a pair of encryption key and decryption key of a homomorphic encryption method capable of polynomial operation, and publishing the encryption key;
(B) When registering registration information,
Registration information that is a numeric vector is polynomialized,
The registration information that has been polynomialized is encrypted using the encryption key,
(C) In the verification assistance process,
When receiving an authentication request, one coefficient and its order are selected at random,
Generating a polynomial in which the coefficients other than the coefficient of the order are 0;
Sending a challenge consisting of ciphertext encrypted using the encryption key to the request source of the authentication request, the polynomial,
(D) In the authentication request source,
The authentication information, which is a numeric vector, is polynomialized,
Based on the authentication information that has been polynomialized and the challenge from the verification auxiliary process, the encryption of the product of the authentication information that has been polynomialized and the polynomial that was used to generate the challenge, using the encryption key Calculate the sentence,
The ciphertext of the product of the polynomial authentication information and the polynomial used to generate the challenge is sent as the response to the verification assisting process,
(E) In the verification assistance process,
When receiving a response from the authentication request source, based on the response, challenge assistance consisting of the one coefficient and its order, and the encrypted registration information, the registration information is Calculate ciphertext of authentication information distance,
Send the ciphertext of the distance between the registration information and the authentication information to the verification destination,
(F) In the verification destination,
The encrypted text of the distance between the registration information and the authentication information received from the verification assisting process is decrypted using the decryption key to calculate the distance,
The calculated distance or a comparison result between the distance and a predetermined threshold is output as a matching result.

A program according to an aspect of the present invention is connected to a verification device that calculates a pair of encryption keys and decryption keys of a homomorphic encryption method capable of polynomial operations and discloses the encryption key, and is connected to an authentication request device. In the computer that constitutes the verification assisting device,
Upon receiving an authentication request from the authentication requesting device, one coefficient and its order are randomly selected,
Generating a polynomial in which the coefficients other than the coefficient of the order are 0;
A process of sending a challenge consisting of a ciphertext obtained by encrypting the polynomial using the encryption key to the authentication requesting device;
The authentication information, which is a numerical vector, is polynomialized, and based on the challenge, a ciphertext of a product of the authentication information polynomialized and the polynomial used to generate the challenge is calculated using the encryption key, and the polynomial Processing to receive a response from the authentication requesting device that outputs the ciphertext of the product of the authentication information and the polynomial used to generate the challenge as a response;
Upon receiving a response from the authentication requesting device, the response, challenge assistance consisting of the one coefficient and its order, and polynomial registration information encrypted by the registration requesting device and stored in the storage device, Based on the encryption key, a ciphertext of the distance between the registration information and the authentication information is calculated, and the ciphertext of the distance between the registration information and the authentication information is sent to the verification device. It consists of a program to let you.

The program according to one aspect of the present invention obtains an encryption key published by a verification device that calculates a pair of an encryption key and a decryption key of a homomorphic encryption method capable of a polynomial operation,
Upon receipt of the authentication request, one coefficient and its order are selected at random, a polynomial in which a coefficient other than the coefficient of the order is 0 is generated, and the polynomial is encrypted using the encryption key. To the authentication requesting device, the response received from the authentication requesting device, challenge assistance consisting of the one coefficient and its order, and the polynomialized registration information encrypted by the registration requesting device. Based on the encryption key, the ciphertext of the distance between the registration information and the authentication information is calculated, and the ciphertext of the distance between the registration information and the authentication information is connected to a verification auxiliary device that sends the ciphertext to the verification device A computer constituting the authentication requesting device,
Processing to generate the authentication request and send it to the verification assistant device;
Receiving a challenge from the verification assisting device;
The authentication information that is a numerical vector is polynomialized, and the authentication information that is polynomialized using the encryption key based on the authentication information that is polynomialized and the challenge received from the verification auxiliary device, and generation of the challenge Calculate the ciphertext of the product with the polynomial used in
A program for executing the process of sending the ciphertext of the product of the authentication information polynomialized and the polynomial used for generating the challenge as the response to the verification assisting device.

When receiving the authentication request from the authentication requesting device, the program according to an aspect of the present invention randomly selects one coefficient and its order, generates a polynomial in which coefficients other than the order coefficient are 0, and the polynomial Is sent to the authentication requesting device, and when a response is received from the authentication requesting device, the challenge is made up of the response, the one coefficient, and its order. And a ciphertext of the distance between the registration information and the authentication information using the encryption key based on the registration information encrypted by the registration request device and stored in the storage device. In the computer constituting the verification device connected to the auxiliary device,
A key generation process for calculating a pair of the encryption key and the decryption key of the homomorphic encryption method capable of performing a polynomial operation and publishing the encryption key;
When the ciphertext of the distance between the registration information and the authentication information is received from the verification assisting device, the ciphertext of the distance between the registration information and the authentication information is decrypted using the decryption key, and query verification is performed to calculate the distance Processing,
It comprises a program for executing the calculated distance or a comparison result generating process for outputting a comparison result between the distance and a predetermined threshold value as a comparison result. According to one aspect of the present invention, there is provided a computer-readable storage medium (semiconductor memory, magnetic disk medium / optical disk medium, etc .: non-transitory computer-readable recording medium) in which the program is recorded.

According to the present invention, it is possible to perform collation processing at high speed and prevent leakage of plain text data and spoofing attacks.

It is a figure which illustrates the structure of the 1st, 3rd exemplary embodiment of this invention. It is a figure explaining an example of the process of the preparation phase of the 1st, 3rd exemplary embodiment of this invention. It is a figure explaining an example of the process of the registration phase of the 1st, 3rd exemplary embodiment of this invention. It is a figure explaining an example of the process of the authentication phase of the 1st, 3rd exemplary embodiment of this invention. It is a figure which illustrates the structure of the 2nd, 4th exemplary embodiment of this invention. It is a figure explaining an example of the process of the preparation phase of the 2nd, 4th exemplary embodiment of this invention. It is a figure explaining an example of the process of the registration phase of the 2nd, 4th exemplary embodiment of this invention. It is a figure explaining an example of the process of the authentication phase of the 2nd, 4th exemplary embodiment of this invention.

First, the basic concept of the present invention will be described. In the system (ciphertext collation system) according to one aspect of the present invention, the verification device (means) calculates a pair of an encryption key pk and a decryption key sk of a homomorphic encryption method capable of a polynomial operation, and the encryption Publish the key pk.

The registration requesting device (means) (for example, 110 in FIG. 1) polynomializes the registration information (A = (a ₀ ,..., A _L−1 )) that is a numerical vector (for example, f _A ), and performs the above polynomial registration The information is encrypted using the encryption key (pk) (for example, Enc (pk, f _A )), and the square sum Enc (pk, Σ _{i = 0 to 0} ) of each coefficient of the polynomial (each component of the numerical vector) _n-1 a _i ² ))).

When the verification assisting device (means) (for example, 140 in FIG. 1) receives an authentication request from the authentication requesting device (means) (for example, 130 in FIG. 1), it randomly selects one coefficient (r) and its degree (h). And generating a polynomial (r × x ^h ) in which a coefficient other than the coefficient of the order (h) is 0, and encrypting the polynomial (r × x ^h ) using the encryption key pk A challenge consisting of a sentence (Enc (pk, r × x ^h )) is sent to the authentication requesting device (means).

When the verification assisting device (means) receives a response (Enc (pk, (r × x ^h ) × (f _B )) from the authentication requesting device (means), the response and the one coefficient (r) And the challenge assistance (r, h) consisting of the order (h) and the registration information (Enc (pk, f _A )) encrypted by the registration requesting device (means) (eg, 110 in FIG. 1). Then, by using the encryption key (pk), an encrypted inner product (Enc (pk, f _A × f _B )) of the registration information Enc (pk, f _A ) and authentication information is generated. Means) includes an encryption key (pk), an inner product (Enc (pk, f _A × f _B )), and encrypted registration information (Enc (pk, Σ _{i = 0 to n−1} a _i ^2). )) And Enc (pk, Σ _{i = 0 to n−1} b _i included in the response) Based on ^2), the distance ciphertext _{(d E (A, B)} ) (Enc (pk, d E (A, B))) is calculated.

The verification assisting device (means) sends the encrypted text at a distance between the encrypted registration information and the authentication information to a verification device (for example, 150 in FIG. 1).

The authentication requesting device (means) polynomializes authentication information (b ₀ ,..., B _L-1 ) that is a numerical vector, and the authentication information that is polynomialized and the authentication information transmitted from the verification assisting device (means) Based on the challenge (Enc (pk, r × x ^h )), the authentication information (f _B ) polynomialized using the encryption key (pk) and the polynomial (r × used for generating the challenge) x ^h ) product ciphertext (Enc (pk, (r × x ^h ) × (f _B ))) and polynomial sum of squares (each component of a numerical vector) ciphertext (Enc (Pk, Σ _{i = 0 to n−1} b _i ² )) is calculated.

The authentication requesting device (means) is configured to use the ciphertext (Enc (pk, r) of the product of the authentication information (f _B ) converted into a polynomial and the polynomial (r × x ^h ) used for generating the challenge. × x ^h ) × (f _B )) and the ciphertext of the sum of squares of each coefficient (each component of the numerical vector) of the polynomial (Enc (pk, Σ _{i = 0 to n−1} b _i ² )) The response is sent to the verification assisting device (means).

The verification device (means) receives the ciphertext (Enc (pk, d _E (A, B))) between the registration information and the authentication information received from the verification assisting device (means) as the decryption key. Decoding using (sk), calculating the distance between the registration information and the authentication information, and outputting the calculated distance or a comparison result between the distance and a predetermined threshold as a comparison result.

According to one aspect of the invention, a storage device (eg, 120 in FIG. 1) is further provided. The storage device
A registered data storage unit (for example, 123 in FIG. 1);
An identifier giving unit (means) (for example, 121 in FIG. 1) for giving an identifier to the encrypted registration information received from the registration requesting device (means);
A registration data generation unit (means) (for example, 122 in FIG. 1) that generates registration data including a pair of the encrypted registration information and the identifier and stores the registration data in the registration data storage unit;
Upon receiving a registration data request from the verification assisting device (means), the encrypted data that is paired with an identifier included in the registration data request from the registration data stored in the registration data storage unit The registration information search unit (means) (for example, 124 in FIG. 1) for sending the registered information to the verification assisting device (means) may be provided.

In this case, the verification assisting device (means) sends a registration data request included in the authentication request received from the authentication requesting device (means) and including an authentication identifier corresponding to the authentication information to the storage device (means). It is good also as composition to do. The verification assisting device (means) receives the encrypted registration information corresponding to the authentication identifier from the storage device (means), receives the response received from the authentication requesting device (means), and the challenge assisting And a ciphertext of the distance between the registration information and the authentication information may be calculated based on the encrypted registration information received from the storage device (means).

According to an embodiment of the present invention, the apparatus further includes a storage device (for example, 220 in FIG. 5). The storage device
A registered data storage unit (for example, 223 in FIG. 5);
An identifier giving unit (means) (for example, 221 in FIG. 5) for giving an identifier to the encrypted registration information received from the registration requesting device (means);
A registration data generation unit (means) (for example, 222 in FIG. 5) that generates registration data including a pair of the encrypted registration information and the identifier and stores the registration data in the registration data storage unit;
It is good also as a structure provided with.

In this case, a registration data request is received from the verification assisting device (means) (for example, 240 in FIG. 5), and one or a plurality of registration data stored in the registration data storage unit (223 in FIG. 5). A part or all of the registration data may be transmitted to the verification assisting device (means) (240 in FIG. 5). The verification assisting device (means) (240 in FIG. 5) receives one or a plurality of registration data from the storage device (means), and the authentication request for each registration data received from the storage device (means). The registration information and the authentication information encrypted based on the response received from the device (means) (for example, 230 in FIG. 5), the challenge assistance, and the encrypted registration information included in the registration data. A distance between the registration information and the authentication information distance, and a pair of identifiers included in the registration data as verification data, A plurality of verification data may be sent to the verification device (means) (for example, 250 in FIG. 5).

The verification device (means) (250 in FIG. 5) receives one or a plurality of the verification data from the verification auxiliary device (means) (240 in FIG. 5), and each verification data is included in the verification data. The encrypted distance is decrypted using the decryption key, the distance is calculated, the comparison result between the calculated distance and a predetermined threshold, or the calculated distance and the identifier included in the verification data It is good also as a structure which makes a set and a collation result and outputs this collation result.

As described above, according to one aspect of the present invention, a polynomial generated based on registration information that is a numerical vector is encrypted using an encryption key, and the coefficient of one term is a random number and the coefficient of the other term is Generating a ciphertext of a product of a challenge that is a polynomial that is 0 and a polynomial that is generated based on authentication information that is a numerical vector, a ciphertext of a polynomial that is generated based on registration information, and the challenge, A ciphertext of the distance between the registration information and the authentication information is generated from the ciphertext of the product of the challenge and the polynomial generated based on the authentication information. Then, the ciphertext (ciphertext of the distance between the registration information and the authentication information) is decrypted using a decryption key to calculate the distance.

In the above aspect, the registration requesting device uses an i-th component of registration information (registration vector) (where i is a non-negative integer equal to or less than L−1 and L is a positive integer equal to or greater than 2) as a coefficient of an i-th term. A first-order polynomial (fA) is generated, and the authentication requesting device calculates the inverse element of the i-th component (where i is a non-negative integer equal to or less than L-1) of the authentication information (authentication vector), the N-th order (N is N-th order polynomial is generated as a coefficient of a term of a positive integer greater than L), but the registration request device reverses the i-th component of registration information (registration vector) (where i is a non-negative integer less than or equal to L-1). An N-th order polynomial is generated with the element as a coefficient of a term of N-th order (N is a positive integer greater than L), and the authentication requesting device generates the i-th component of authentication information (authentication vector) (where i is L- A non-negative integer of 1 or less, L is a positive integer of 2 or more) is used to generate an L−1th order polynomial fA having an i-th order coefficient. There.

DETAILED DESCRIPTION Exemplary embodiments of the present invention will be described in detail with reference to the drawings.

In each of the following exemplary embodiments, the case where the present invention is used as biometric authentication will be described. The ciphertext matching system of each embodiment is not limited to the use of biometric authentication.

(First embodiment)
FIG. 1 is a diagram illustrating a configuration of a ciphertext matching system 100 according to the first exemplary embodiment. The ciphertext verification system 100 is configured by an information processing system such as a computer system. The ciphertext matching system 100 according to the first exemplary embodiment roughly includes a registration requesting device 110, a storage device 120, an authentication requesting device 130, a verification assisting device 140, and a verification device 150.

The registration request device 110 includes a registration information extraction unit 111, a first template generation unit 112, a second template generation unit 113, and a template generation unit 114.

The storage device 120 includes an identifier assigning unit 121, a registration data generation unit 122, a registration data storage unit 123, and a registration data search unit 124.

The authentication request device 130 includes an authentication request generation unit 131, an authentication information extraction unit 132, a first response generation unit 133, a second response generation unit 134, and a response generation unit 135.

The collation assisting device 140 includes a challenge assist generating unit 141, a challenge generating unit 142, a registration data request generating unit 143, an encrypted inner product calculating unit 144, and a query generating unit 145.

The verification device 150 includes a key generation unit 151, a decryption key storage unit 152, a query verification unit 153, and a matching result generation unit 154.

The registration request device 110 and the storage device 120, the storage device 120 and the verification auxiliary device 140, the authentication request device 130 and the verification request device 140, and the verification auxiliary device 140 and the verification device 150 communicate with each other via, for example, a communication network. It shall be possible. Alternatively, the registration request device 110, the storage device 120, the verification auxiliary device 140, the authentication request device 130, and the verification device 150 are connected via a network such as a LAN (Local Area Network) or a WAN (Wide Area Network). It is good. Of course, a plurality of devices among the registration request device 110, the storage device 120, the verification auxiliary device 140, the authentication request device 130, and the verification device 150 may be mounted in one unit. The registration requesting device 110, the storage device 120, the verification assisting device 140, and the authentication requesting device 130 are the public key released by the verification device 150 (the encryption key of the homomorphic encryption method created by the verification device 150 and capable of polynomial operation). The encryption key of the decryption key pair) can be acquired. In at least one or all of the registration requesting device 110, the storage device 120, the verification assisting device 140, the authentication requesting device 130, and the verification device 150, at least a part or all of the processing of each unit is performed by a computer (CPU (Central (Processing Unit) or a program executed by a processor). In this case, by reading the program from the computer-readable semiconductor memory, HDD (Hard Disk Drive), CD (Compact Disk), DVD (Digital Versatile Disk), etc. in which the program is recorded, the program is read into the main memory of the computer and executed Processing of each part is realized.

In the ciphertext verification system 100, the registration requesting device 110 and the authentication requesting device 130 may be collectively represented as “first node”. In the ciphertext verification system 100, the storage device 120 and the verification auxiliary device 140 may be collectively represented as a “second node”. Further, in the ciphertext matching system 100, the verification device 150 may be represented as a “third node”. That is, the ciphertext matching system 100 is not limited to the mode illustrated in FIG.

[Description of operation]
Next, the operation of the ciphertext matching system 100 according to the present embodiment will be described with reference to the drawings. Processing in the ciphertext matching system 100 according to the first exemplary embodiment of the present invention will be described.

The processing in the ciphertext verification system 100 is roughly classified as follows:
・ Preparation phase,
・ Registration phase, and
-Includes a verification phase.

First, an overview of processing in each phase will be described. In the ciphertext matching system 100 according to the first exemplary embodiment of the present invention, a homomorphic encryption method having homomorphism is used for addition and multiplication. For convenience of explanation, it is assumed that the encryption method used handles, as a message, an N−1 degree polynomial in which each coefficient is a non-negative integer smaller than _t (coefficient ∈ Z _t = {0, 1, 2,..., t-1}).

In the preparation phase, an encryption key and a decryption key are mainly generated using the received security parameters.

In the registration phase, a template in which the extracted registration vector is encrypted is created and stored mainly using the encryption key generated in the preparation phase.

In the verification phase, the distance between the newly extracted authentication vector and one registered vector is mainly calculated using the decryption key generated in the preparation phase.

Next, the process executed by the ciphertext verification system 100 in each phase described above will be described in detail.

FIG. 2 is a flowchart showing an example of processing executed by the ciphertext matching system 100 according to the first exemplary embodiment in the preparation phase. A process executed by the ciphertext matching system 100 according to the present embodiment in the preparation phase will be described with reference to FIG.

The key generation unit 151 in the verification device 150 receives the security parameter, and uses the received security parameter, for example, according to the key generation algorithm (Non-Patent Document 1) described above, the encryption key (public key) pk, and A decryption key (secret key) sk is generated (step A1). The generated encryption key and decryption key conform to a public key cryptosystem having homomorphism with respect to addition and multiplication.

The key generation unit 151 discloses the generated encryption key pk in the ciphertext verification system 100 (step A2).

The key generation unit 151 stores the generated decryption key sk in the decryption key storage unit 152 (step A3).

Note that the processing executed by the ciphertext matching system 100 according to the present embodiment in the preparation phase is not limited to the mode illustrated in FIG.

FIG. 3 is a flowchart illustrating an example of processing executed by the ciphertext matching system 100 according to the first exemplary embodiment in the registration phase. With reference to FIG. 3, processing executed by the matching system 100 according to the present embodiment in the registration phase will be described.

The registration information extraction unit 111 in the registration requesting device 110 receives biometric information (referred to as “registration vector”) from a biometric subject to registration.
A = (a ₀ ,..., A _L−1 ) (Expression 29)
Is extracted (step B1).

Next, the first template generation unit 112 in the registration request device 110 uses the encryption key pk to generate each i-th (i = 0,..., L−1) of the registration vector A generated according to the following equation 30. ) Component a _i as the coefficient of the i-th term, L-1 order polynomial f _A (x) = Σ _{i = 0 to L−1} a _i × x ⁱ (Equation 30)
Ciphertext Enc (pk, f _A )
Is calculated (step B2).

The ciphertext Enc (pk, f _A ) calculated in step B2 will be referred to as a “first template”.

Next, the second template generation unit 113 in the registration requesting apparatus 110 uses the encryption key pk to calculate the sum of squares Σ _{i = 0 to L−1} a _i ^{2 of the} components of the registration vector A (Equation 31). )
Ciphertext Enc (pk, Σ _{i = 0 to L−1} a _i ² )
Is calculated (step B3).

The square sum cipher text Enc (pk, Σ _{i = 0 to L−1} a _i ² ) of each component of the registration vector A calculated in step B3 will be referred to as a “second template”.

Next, the template generation unit 114 in the registration requesting device 110 collects the first template and the second template, and the templates (Enc (pk, f _A ), Enc (pk, Σ _{i = 0 to n−1} a _i ² )). (Equation 32)
(Step B4).

The registration requesting device 110 sends the template (Enc (pk, f _A ), Enc (pk, Σ _{i = 0 to n−1} a _i ² )) to the storage device 120 (step B5).

Next, the storage device 120 receives a template (Enc (pk, f _A ), Enc (pk, Σ _{i = 0 to n−1} a _i ² )) from the registration requesting device 110 (step B6).

The identifier assigning unit 121 in the storage device 120 is an identifier unique to the template (Enc (pk, f _A ), Enc (pk, Σ _{i = 0 to n−1} a _i ² )) received from the registration requesting device 110. The registration identifier id is determined (step B7).

The storage device 120 sends the registration identifier id to the registration request device 110 (step B8).

Next, the registration request device 110 receives the registration identifier id from the storage device 120 (step B9).

The registration request device 110 displays the received registration identifier id on a user interface (UI) such as a display (step B10). Alternatively, the registration request device 110 may store the received registration identifier id in an IC (integrated_circuit) card such as an employee ID card or an identifier card.

Next, the registration data generation unit 122 in the storage device 120 collects the template and the registration identifier id, and registers the registration data ((Enc (pk, f _A ), Enc (pk, Σ _{i = 0 to n−1} a _i ² )). ), Id) (Expression 33)
(Step B11).

The registration data (formula 33) is stored in the registration data storage unit 123 in the storage device 120 (step B12).

Note that the process executed by the ciphertext matching system 100 according to the present embodiment in the registration phase is not limited to the mode illustrated in FIG. For example, step B11 and step B12 may be executed prior to step B8.

FIG. 4 is a flowchart showing an example of processing executed by the ciphertext matching system 100 according to the first exemplary embodiment in the authentication phase. With reference to FIG. 4, processing executed by the verification system 100 according to the present embodiment in the authentication phase will be described.

The authentication requesting device 130 receives an identifier (referred to as “authentication identifier”) possessed by the authentication target (step C1).

Next, the authentication request generator 131 in the authentication request device 130 generates an authentication request including the received authentication identifier (step C2).

The authentication requesting device 130 sends an authentication request to the verification assisting device 140 (step C3).

The collation assisting device 140 receives an authentication request from the authentication requesting device 130 (step C4).

Next, the challenge auxiliary generation unit 141 in the verification auxiliary device 140 randomly selects an integer r smaller than the integer t and an integer h smaller than N-1. The challenge auxiliary generation unit 141 collects the selected values r and h and sets them as challenge auxiliary (r, h) (step C5).

Next, the challenge generation unit 142 in the verification assisting device 140 uses the encryption key pk to calculate the polynomial r × x ^h (equation 34) calculated from the challenge assist (r, h).
Cipher text Enc (pk, r × x ^h ) is calculated (step C6). The ciphertext Enc (pk, r × x ^h ) calculated in step C6 is called a “challenge”.

The verification assisting device 140 sends the challenge Enc (pk, r × x ^h ) to the authentication requesting device 130 (step C7).

Next, the registration data request generation unit 143 in the verification auxiliary device 140 generates a registration data request including the authentication identifier included in the authentication request received from the authentication requesting device 130 (step C8).

The collation assisting device 140 sends a registration data request to the storage device 120 (step C9).

Next, the storage device 120 receives a registration data request from the verification auxiliary device 140 (step C10).

The registration data search unit 124 in the storage device 120 specifies registration data including the authentication identifier included in the registration data request from one or a plurality of registration data stored in the registration data storage unit 123 (step C11). ). A template included in the specified registered data is referred to as a “matching target template”.

Storage device 120 sends the verification target template to verification auxiliary device 140 (step C12).

The collation auxiliary device 140 receives the collation target template from the storage device 120 (step C13).

The authentication requesting device 130 receives the challenge transmitted by the verification assisting device 140 in step C7 (step C14).

Next, the authentication information extraction unit 132 in the authentication requesting device 130 obtains biometric information (referred to as “authentication vector”) from the biometric subject to authentication.
B = (b ₀ ,..., B _L−1 ) (Expression 35)
Is extracted (step C15).

Next, the first response generation unit 133 in the authentication requesting device 130 performs the inverse element −b related to the addition of each i-th (i = 0,..., L−1) component b _i of the authentication vector B according to the above equation 21. _i a, n-i Next n order polynomial _f B having the coefficient of the term _{(x) = - Σ i =} 0 ~ n-1 b i × x n-i ··· ( formula 36)
Is calculated. further,
An encryption key pk;
The generated polynomial f _B and
A challenge Enc (pk, r × x ^h ) received from the verification auxiliary device 140;
Based on
For example, the first response Enc (pk, (r × x ^h ) × (f _B )) (Equation 37) is used by utilizing the property (Equation 6) of the encryption method that can calculate the scalar multiplication of the ciphertext.
Is generated (step C16).

Next, the second response generation unit 134 in the authentication requesting apparatus 130 uses the encryption key pk to calculate the sum of squares Σ _{i = 0 to L−1} b _i ^{2 of the} components of the authentication vector B (Expression 38). )
Ciphertext Enc (pk, Σ _{i = 0 to L−1} b _i ² )
Is calculated (step C17). The ciphertext of the sum of squares of each component of the authentication vector B calculated in step C17 is referred to as “second response”.

Next, the response generation unit 135 in the authentication requesting apparatus 130
First response Enc (pk, (r × x ^h ) × (f _B )),
The second response Enc (pk, Σ _{i = 0 to L−1} b _i ² ) is collected, and the response (Enc (pk, (r × x ^h ) × (f _B )), Enc (pk, Σ _{i = 0 to L-1} b _i ² )) (Equation 39)
(Step C18).

The authentication requesting device 130 sends the response (formula 39) generated in step C18 to the verification assisting device 140 (step C19).

Next, the verification assistant device 140 receives the response (formula 39) from the authentication requesting device 130 (step C20).

Next, the encryption inner product calculation unit 144 in the verification auxiliary device 140
An encryption key pk;
· Generated challenge auxiliary in step C5 (r, h) a polynomial ^{-r -1} × ^{x N-h} generated from,
The first response Enc (included in the response (Enc (pk, (r × x ^h ) × (f _B )), Enc (pk, Σ _{i = 0 to L−1} b _i ² )) received in step C20) pk, (r × x ^h ) × (f _B )),
Based on
For example, using the property (formula 5) that can calculate the scalar multiplication of the ciphertext of the encryption method,
Enc (pk, f _B ) = (− r ⁻¹ × x ^N−h ) × Enc (pk, (r × x ^h ) × (f _B )) (Equation 40)
Calculate

Furthermore, the encryption inner product calculation unit 144
An encryption key pk;
_A first template Enc (pk, f _A ) included in the verification target template received in step C13;
The calculated ciphertext Enc (pk, f _B ),
Based on
Encrypted inner product Enc (pk, f _A × f _B ) using the multiplicative homomorphism of the encryption method
Is generated (step C21).

Incidentally, as described above (Equation 22, Equation 23), the constant term of _{f A} × _{f B} is the inner product of the registration vectors A and authentication vector B <A, B> = Σ i = 0 ~ n-1 a i × b _i
Is equal to

Next, the query generation unit 145 in the verification assisting device 140
An encryption key pk;
Encrypted inner product Enc (pk, f _A × f _B ) generated in step C21
When,
A second template Enc (pk, Σ _{i = 0 to n−1} a _i ² ) included in the collation target template received in step C13;
A second response Enc (pk, Σ _{i = 0 to L−1} b _i ² ) included in the response received in step C20;
From the query Enc (pk, f) using the additive homomorphism of the encryption method.
Is generated (step C22).

However, in the query Enc (pk, f), the constant term of f is the Euclidean distance d _E (A, B) = (Σ _{i = 0 to n−1} ) between the registration vector A and the authentication vector B according to the above equation 26. a _i ² ) + (Σ _{i = 0 to n−1} b _i ² ) −2 <A, B>
And

The collation assisting device 140 sends the query Enc (pk, f) to the verification device 150 (step C23).

Next, the verification device 150 receives the query Enc (pk, f) from the verification auxiliary device 140 (step C24).

Next, the query verification unit 153 in the verification device 150 decrypts the query Enc (pk, f) using the decryption key sk.

The constant term of the polynomial obtained as the decoding result Dec (sk, Enc (pk, f)) is set as the verification result (step C25).

As described above, the verification result is the Euclidean distance d _E (A, B) between the registration vector A and the authentication vector B.

Next, the verification result generation unit 154 in the verification device 150 uses the verification result as the verification result. Or the collation result production | generation part 154 is good also considering the result of having compared the magnitude of a verification result and a predetermined threshold value as a collation result (step C26).

The verification device 150 outputs the calculated collation result (step C27).

The process executed by the ciphertext matching system 100 according to the present embodiment in the authentication phase is not limited to the mode illustrated in FIG. For example, steps C9 to C13 may be executed prior to step C5.

In the above description of the ciphertext matching system 100 according to the present embodiment,
The polynomial f _A generated by the first template generation unit 112 in the registration request apparatus 110 in step B2 of FIG. 3 is a polynomial generated from the registration vector A according to Equation 19,
The polynomial f _B generated by the first response generation unit 133 in the authentication requesting apparatus 130 in step C16 in FIG. 4 is a polynomial generated from the authentication vector according to the equation 21. However, it is obvious that the method of generating two polynomials in this embodiment is not limited to the above method. For example,
The polynomial f _A generated by the first template generation unit 112 in the registration request apparatus 110 in step B2 is a polynomial generated according to the expression 21 based on the registration vector A,
- an authentication request apparatus polynomial f _B to generate first response generator 133 in step C16 in 130, based on the authentication vector may be a polynomial generated according to Equation 20.

[Description of effects]
Next, effects related to the ciphertext matching system 100 according to the first exemplary embodiment will be described.

According to the collation system 100 according to the first exemplary embodiment, it is possible to safely realize 1: 1 authentication in which a user requesting authentication performs authentication by presenting his / her own living body and an identifier. It is. That is, it has the following two effects.

According to the ciphertext matching system 100 according to the first exemplary embodiment, the registration vector extracted by the registration requesting device 110 is encrypted on the registration requesting device 110 and sent to the storage device 120. The authentication vector extracted by the authentication requesting device 130 is encrypted on the authentication requesting device 130 and sent to the verification assisting device 140.

The ciphertext can be decrypted by the verification device 150 having a decryption key, but the data received by the verification device 150 is a ciphertext of the Euclidean distance between the registration vector and the authentication vector. The value of is not disclosed. Therefore, according to the ciphertext matching system 100 according to the first exemplary embodiment, a value other than the distance between the registered vector and the authentication vector is not leaked to a device other than the device that extracts each vector, and verification is performed. In the device, it is possible to calculate the distance between the registration vector and the authentication vector.

Further, according to the ciphertext matching system 100 according to the first exemplary embodiment, even when performing authentication with the same registration vector, the process using the random number selected in step C5 in FIG. 4 is performed. Done. Therefore, even if the communication content of the verification process is leaked,
-Resend leaked content,
-Even if you send the data created using the leaked content,
It is impossible to calculate a distance equal to the leaked distance at the time of collation or to calculate a small value. In particular, when the ciphertext matching system 100 according to the first exemplary embodiment is used for authentication for accepting when the distance between the registration vector and the authentication vector is smaller than the threshold, the registration vector is not known. It has the property that an attacker is not "accepted", that is, it is resistant to spoofing attacks.

Furthermore, in the ciphertext matching system 100 according to the first exemplary embodiment, the verification device 150 having the decryption key can be modified so as not to disclose the Euclidean distance between the registration vector and the authentication vector. For example, by applying the same method as the method described in Non-Patent Document 4, the verification device 150 having a decryption key can be transformed into a method that cannot calculate the Euclidean distance between the registration vector and the authentication vector. A method that does not disclose the Euclidean distance between the registration vector and the authentication vector for the verification device 150 having the decryption key means that the verification device 150 having the decryption key calculates the value of the registration vector even under special circumstances. Since it can be prevented, higher safety can be achieved.

[Second Embodiment]
[Description of configuration]
FIG. 5 is a diagram schematically illustrating a configuration of a ciphertext matching system (also referred to as an “information processing system”) 200 according to the second exemplary embodiment. The ciphertext matching system 200 according to the second exemplary embodiment roughly includes a registration requesting device 210, a storage device 220, an authentication requesting device 230, a verification assisting device 240, and a verification device 250.

The registration requesting apparatus 210 includes a registration information extraction unit 211, a first template generation unit 212, a second template generation unit 213, and a template generation unit 214.

The storage device 220 includes an identifier assigning unit 221, a registration data generation unit 222, and a registration data storage unit 223.

The authentication request device 230 includes an authentication request generation unit 231, an authentication information extraction unit 232, a first response generation unit 233, a second response generation unit 234, and a response generation unit 235.

The verification auxiliary device 240 includes a challenge auxiliary generation unit 241, a challenge generation unit 242, a registration data request generation unit 243, an encrypted inner product calculation unit 244, a query generation unit 245, and a verification data generation unit 246. .

The verification device 250 includes a key generation unit 251, a decryption key storage unit 252, a query verification unit 253, and a matching result generation unit 254.

The registration request device 210 and the storage device 220, the storage device 220 and the verification auxiliary device 240, the authentication request device 230 and the verification request device 240, and the verification auxiliary device 240 and the verification device 250 communicate with each other via a communication network, for example. Suppose that it is possible.

In the ciphertext matching system 200, the registration requesting device 210 and the authentication requesting device 230 may be collectively represented as “first node”. In the ciphertext verification system 200, the storage device 220 and the verification auxiliary device 240 may be collectively represented as a “second node”. Further, in the ciphertext matching system 200, the verification device 250 may be represented as a “third node”. That is, the ciphertext matching system 200 is not limited to the mode illustrated in FIG.

[Description of operation]
Next, the operation of the ciphertext matching system 200 according to the second exemplary embodiment will be described.

The operation in the ciphertext matching system 200 according to the second exemplary embodiment of the present invention will be described. The processing in the ciphertext verification system 200 is roughly divided into a preparation phase, a registration phase, and a verification phase. First, an overview of processing in each phase will be described.

In the ciphertext matching system according to the second exemplary embodiment of the present invention, a homomorphic cryptosystem having homomorphism is used for addition and multiplication. For convenience of explanation, it is assumed that the encryption method used is an N−1 degree polynomial whose coefficients are non-negative integers smaller than t as messages.

In the preparation phase, an encryption key and a decryption key are mainly generated using the received security parameters.

In the registration phase, a template in which the extracted registration vector is encrypted is created and stored mainly using the encryption key generated in the preparation phase.

In the verification phase, the distance between the newly extracted authentication vector and one or more registered vectors is mainly calculated using the decryption key generated in the preparation phase.

Next, the process executed by the ciphertext matching system 200 in each phase described above will be described in detail.

FIG. 6 is a flowchart showing an example of processing executed by the ciphertext matching system 200 according to the second exemplary embodiment in the preparation phase. A process executed by the ciphertext matching system 200 according to the second exemplary embodiment in the preparation phase will be described with reference to FIG.

The key generation unit 251 in the verification device 250 receives the security parameter, and generates the encryption key pk and the decryption key sk using the received security parameter, for example, according to the above-described key generation algorithm (step D1). . The generated encryption key and decryption key conform to a public key cryptosystem having homomorphism with respect to addition and multiplication.

The key generation unit 251 discloses the encryption key pk in the ciphertext verification system 200 (step D2).

The key generation unit 251 stores the decryption key sk in the decryption key storage unit 252 (step D3).

Note that the processing executed by the ciphertext matching system 200 according to the present embodiment in the preparation phase is not limited to the mode illustrated in FIG.

FIG. 7 is a flowchart illustrating an example of processing executed by the ciphertext matching system 200 according to the second exemplary embodiment in the registration phase. With reference to FIG. 7, a description will be given of processing executed by the verification system 200 according to the present embodiment in the registration phase.

The registration information extraction unit 211 in the registration request apparatus 210 receives biometric information (referred to as a “registration vector”) from a biometric subject to registration.
A = (a ₀ ,..., A _L−1 ) (Formula 41)
Is extracted (step E1).

Next, the first template generation unit 212 in the registration request apparatus 210 uses the encryption key pk to generate each i-th (i = 0,..., L−1) of the registration vector A generated according to the following equation 42. ) Component a _i as the coefficient of the i-th term, L−1 order polynomial f _A (x) = Σ _{i = 0 to L−1} a _i × x ⁱ (Equation 42)

The ciphertext Enc (pk, f _A ) is calculated (step E2).

The ciphertext Enc (pk, f _A ) calculated in step E2 is referred to as “first template”.

Next, the second template generation unit 213 in the registration request apparatus 210 uses the encryption key pk to calculate the sum of squares Σ _{i = 0 to L−1} a _i ^{2 of the} components of the registration vector A (Formula 43) )
Ciphertext Enc (pk, Σ _{i = 0 to L−1} a _i ² ) is calculated (step E3). The square sum ciphertext Enc (pk, Σ _{i = 0 to L−1} a _i ² ) of each component of the registration vector A calculated in step E3 is referred to as a “second template”.

Next, the template generation unit 214 in the registration requesting apparatus 210 combines the first template and the second template, and the templates (Enc (pk, f _A ), Enc (pk, Σ _{i = 0 to n−1} a _i ² )). (Equation 44)
(Step E4).

The registration requesting device 210 sends the template (Enc (pk, f _A ), Enc (pk, Σ _{i = 0 to n−1} a _i ² )) to the storage device 220 (step E5).

Next, the storage device 220 receives the template (Enc (pk, f _A ), Enc (pk, Σ _{i = 0 to n−1} a _i ² )) from the registration requesting device 210 (step E6).

The identifier assigning unit 221 in the storage device 220 determines a registered identifier id that is an identifier unique to the received template (step E7).

Storage device 220 sends registration identifier id to registration request device 210 (step E8).

Next, the registration request device 210 receives a registration identifier id from the storage device 220 (step E9). For example, the registration requesting device 210 may display the received registration identifier id on a user interface (UI) such as a display (step E10). Alternatively, the registration request apparatus 210 may store the received registration identifier in an IC (integrated_circuit) card such as an employee ID card or an identifier card.

Next, the registration data generation unit 222 in the storage device 220 summarizes the template and the registration identifier, and registers the registration data ((Enc (pk, f _A ), Enc (pk, Σ _{i = 0 to n−1} a _i ² )). , Id) (Formula 45)
(Step E11).

The registration data generation unit 222 in the storage device 220 stores the registration data in the registration data storage unit 223 (step E12).

Note that the processing executed by the ciphertext matching system 200 according to the second exemplary embodiment in the registration phase is not limited to the mode illustrated in FIG. For example, step E11 and step E12 may be executed prior to step E8.

FIG. 8 is a flowchart showing an example of processing executed by the ciphertext matching system 200 according to the second exemplary embodiment in the authentication phase. With reference to FIG. 8, processing executed by the verification system 200 according to the present embodiment in the authentication phase will be described.

The authentication request generation unit 231 in the authentication request device 230 generates an authentication request (step F1).

The authentication requesting device 230 sends an authentication request to the verification assisting device 240 (step F2).

The verification auxiliary device 240 receives the authentication request from the authentication requesting device 230 (step F3).

Next, the challenge auxiliary generation unit 241 in the verification auxiliary device 240 randomly selects an integer smaller than t and an integer h smaller than N−1. The selected values are collected and used as challenge assistance (r, h) (step F4).

Next, the challenge generation unit 242 in the verification assisting device 240 uses the encryption key pk to calculate the polynomial r × x ^h (equation 46) calculated from the challenge assist (r, h).
The ciphertext Enc (pk, r × x ^h ) is calculated (step F5).

The ciphertext Enc (pk, r × x ^h ) calculated in step F5 is called a “challenge”.

The collation assisting device 240 sends the challenge to the authentication requesting device 230 (step F6).

Next, the registration data request generation unit 243 in the verification auxiliary device 240 generates a registration data request (step F7).

The collation assisting device 240 sends a registration data request to the storage device 220 (step F8).

Next, the storage device 220 receives a registration data request from the verification auxiliary device 240 (step F9).

The storage device 220 sends a part or all (M) of registration data of one or a plurality of registration data stored in the registration data storage unit 223 to the verification assisting device 240 (step F10). ). However, each registration data is a set of a template and a registration identifier.

The collation assisting device 240 receives M pieces of registered data from the storage device 220 (step F11).

In the following, it is assumed that a template included in each j-th (j = 1,..., M) registration data is generated from the registration vector A _j .

The first template included in each j-th (j = 1,..., M) registration data is a ciphertext Enc (pk, f _{A, j} ) of the polynomial f _{A, j} generated from the registration vector A _j. Suppose that

Each j-th (j = 1, ..., M ) second templates included in the registration data of the registration vector _A square sum of the components of _{j Σ i = 0 ~ n-} 1 a j, i 2 ·· (Formula 47)
Ciphertext Enc (pk, Σ _{i = 0 to n−1} a _{j, i} ² )
Suppose that

The authentication requesting device 230 receives the challenge Enc (pk, r × x ^h ) from the verification assisting device 240 (step F12).

Next, the authentication information extraction unit 232 in the authentication requesting device 230 obtains biometric information (referred to as “authentication vector”) from the biometric subject to authentication.
B = (b ₀ ,..., B _L−1 ) (Formula 48)
Is extracted (step F13).

Next, the first response generation unit 233 in the authentication requesting device 230 performs the inverse element −b related to the addition of each i-th (i = 0,..., L−1) component b _i of the authentication vector B according to the above equation 21. _i a, n-i Next n order polynomial _f B having the coefficient of the term _{(x) = - Σ i =} 0 ~ n-1 b i × x n-i ··· ( formula 49)
Is calculated. further,
An encryption key pk;
The generated polynomial f _B and
・ The received challenge Enc (pk, r × x ^h ),
From
For example, using the property (equation 6) that can calculate the scalar multiplication of the ciphertext of the encryption method,
First response Enc (pk, (r × x ^h ) × (f _B )) (Formula 50)
Is generated (step F14).

Next, the second response generation unit 234 in the authentication requesting device 230 uses the encryption key pk to calculate the sum of squares Σ _{i = 0 to L−1} b _i ^{2 of the} components of the authentication vector B (Formula 51). )
Cipher text Enc (pk, Σ _{i = 0 to L−1} b _i ² ) is calculated (step F15). The ciphertext Enc (pk, Σ _{i = 0 to L−1} b _i ² ) of the sum of squares of each component of the authentication vector B calculated in step F15 is referred to as “second response”.

Next, the response generation unit 235 in the authentication requesting device 230 collects the first response and the second response, and the response (Enc (pk, (r × x ^h ) × (f _B )), Enc (pk, Σ _{i = 0 to L-1} b _i ² )) (Formula 52)
(Step F16).

The authentication requesting device 230 sends the response, which is a summary of the first response and the second response, to the verification assisting device 240 (step F17).

Next, the verification auxiliary device 240 receives the response from the authentication requesting device 230 (step F18).

Next, the encrypted inner product calculation unit 244 in the verification auxiliary device 240
An encryption key pk;
A term formula ^{-r -1} × ^{x N-h} generated from-generated challenge auxiliary in step F4 (r, h),
A first response Enc (pk, (r × x ^h ) × (f _B )) included in the response received in step F18;
Based on
For example, using the property (equation 6) that can calculate the scalar multiplication of the ciphertext of the encryption method,
Enc (pk, f _B ) = (− r ⁻¹ × x ^N−h ) × Enc (pk, (r × x ^h ) × (f _B )) (Formula 53)
Calculate
Further, the encrypted inner product calculation unit 244 in the verification assisting device 240 performs the following for each j (j = 1,..., M).
An encryption key pk;
_A first template Enc (pk, f _{A, j} ) included in the j-th registration data among the M registration data received in step F11;
The calculated ciphertext Enc (pk, f _B ),
Based on the above, by using the multiplicative homomorphism of the encryption method, the encrypted inner product Enc (pk, f _{A, j} × f _B ) (Formula 54)
Is generated (step F19).

Incidentally, as described above, each of j (j = 1, ..., M) _{for, f A,} the constant term of the _j × _{f B} is the inner product of the registration vector _{A j} and an authentication vector B _<A j ,B> = Σ _{i = 0 to n−1} a _{j, i} × b _i
Is equal to

Next, the query generation unit 245 in the verification assisting device 240 for each j (j = 1,..., M)
An encryption key pk;
Encrypted inner product Enc (pk, f _{A, j} × f _B ) generated in step F19
When,
A second template Enc (pk, Σ _{i = 0 to n−1} a _{j, i} ² ) included in the j-th registration data among the M pieces of registration data received in step F11;
A second response Enc (pk, Σ _{i = 0 to L−1} b _i ² ) included in the response received in step F18;
Based on the additive homomorphism of cryptography,
Query Enc (pk, f _j )
Is generated (step F20).

However, each of j (j = 1, ..., M) for the constant term of _{f j} is according to the equation 26, the Euclidean distance _d E of the registered vectors _{A j} and an authentication vector _{B (A j, B) =} (Σ _{i = 0 to n−1} a _{j, i} ² ) + (Σ _{i = 0 to n−1} b _i ² ) −2 <A _j ,B>
And

Next, in step F20, the verification data generation unit 246 in the verification assisting apparatus 240 starts from the second template included in the jth registered data among the M registered data for each j (j = 1,..., M). The generated query and the registration identifier included in the jth registration data among the M pieces of registration data are set as the jth verification data (step F21).

Next, the verification assisting device 240 sends M pieces of verification data to the verification device 250 (step F22).

Next, the verification device 250 receives M pieces of verification data from the verification auxiliary device 240 (step F23).

The query verification unit 253 in the verification device 250 uses the decryption key pk for each j (j = 1,..., M) to decrypt the query included in the jth verification data among the M verification data. The constant term of the polynomial obtained as the decoding result is set as the verification result (step F24).

As described above, for each j (j = 1,..., M), the constant term of the polynomial obtained as a decoding result generated from the j-th verification data among the M verification data is the registered vector A _j and the authentication The Euclidean distance d _E (A _j , B) with the vector B.

Next, the verification result generation unit 254 in the verification device 250 generates each j (j = 1,..., M) from the query included in the jth verification data among the M verification data in step F24. The verification result and the registration identifier included in the jth verification data are collected and used as the jth verification result.

Alternatively, for each j (j = 1,..., M), the verification result generation unit 254 in the verification device 250 generates j generated in step F24 from the query included in the jth verification data among the M verification data. The result of comparing the size of the th-th verification result with a predetermined threshold value and the registration identifier included in the j-th verification data may be collected and used as the j-th collation result (step F25).

The verification device 250 outputs the calculated M verification results (step F26).

Note that the processing executed by the ciphertext matching system 200 according to the second exemplary embodiment in the authentication phase is not limited to the mode illustrated in FIG. For example, steps F12 to F17 may be executed prior to step F7.

In the above description of the ciphertext matching system 200 according to the second exemplary embodiment, the polynomial f _A generated by the first template generating unit 212 in the registration requesting device 210 in step E2 of FIG. Based on the above equation 20, the polynomial is generated. Further, the polynomial f _B generated by the first response generation unit 233 in the authentication requesting device 230 in step F16 of FIG. 8 is a polynomial generated according to the above equation 21 based on the authentication vector.

The method of generating the two polynomials in the second exemplary embodiment is not limited to the above method. For example, the polynomial f _A generated by the first template generation unit 212 in the registration request device 210 in step E2 is a polynomial generated based on the registration vector A according to the above equation 21, and the first response generation unit 233 in the authentication request device 230 is used. There polynomial f _B to generate at step F16 in FIG. 8, may be a polynomial generated according to the formula 20 based on the authentication vector.

[Description of effects]
Next, effects related to the ciphertext matching system 200 according to the second exemplary embodiment will be described. According to the collation system 200 according to the second embodiment, the user who requests the authentication collates all the registered information and the information used for the authentication without presenting its own identifier. 1: N Authentication can be realized safely. That is, it has the following two effects.

According to the ciphertext matching system 200 according to the second exemplary embodiment, the registration vector extracted by the registration requesting device 210 is encrypted on the registration requesting device 210 and sent to the storage device 220.

Also, the authentication vector extracted by the authentication requesting device 230 is encrypted on the authentication requesting device 230 and sent to the verification assisting device 240. The ciphertext can be decrypted by the verification device 250 having a decryption key, but the data received by the verification device 250 is a ciphertext of the Euclidean distance between the registration vector and the authentication vector. The value is not disclosed.

Therefore, according to the ciphertext matching system 200 according to the second exemplary embodiment, a value other than the distance between the registration vector and the authentication vector is not leaked to a device other than the device that extracts each vector, It is possible to calculate the distance between the authentication vectors.

Further, according to the ciphertext matching system 200 according to the second exemplary embodiment, even when performing authentication with the same registration vector, the process using the random number selected in step F5 in FIG. 8 is performed. Done.

Therefore, even if the communication content of the verification process is leaked, the distance equal to the distance at the time of the leaked verification is calculated by resending the leaked content or sending data created using the leaked content Or a small value cannot be calculated.

In particular, when the ciphertext matching system 200 according to the second exemplary embodiment is used for authentication that accepts when the distance is smaller than the threshold, an attacker who does not know the registered vector is not accepted. The property, ie, resistance to spoofing attacks.

Further, in the ciphertext matching system 200 according to the second exemplary embodiment, the verification device 250 having the decryption key can be modified so as not to disclose the Euclidean distance between the registration vector and the authentication vector. It is. For example, by applying the same method as the method described in Non-Patent Document 4, the verification device 250 having a decryption key can be transformed into a method that cannot calculate the Euclidean distance between the registration vector and the authentication vector. The method that does not disclose the Euclidean distance between the registration vector and the authentication vector for the verification device 250 having the decryption key allows the verification device 250 having the decryption key to calculate the value of the registration vector even under special circumstances. Can be prevented. For this reason, higher safety can be achieved.

[Third Embodiment]
Next, a third exemplary embodiment will be described. The third exemplary embodiment is a case where the encryption scheme shown in Non-Patent Document 1 is used in the ciphertext matching system 100 shown in FIG. 1 referred to in the description of the first exemplary embodiment. . In the following, characteristic portions according to the third exemplary embodiment will be mainly described, and description of the same portions as those of the first exemplary embodiment will be omitted as appropriate.

The third exemplary embodiment is configured by using an encryption method having homomorphism regarding addition and information described in Non-Patent Document 1 described above. The configuration of this embodiment uses the following characteristics of the encryption method of Non-Patent Document 1.

The parameters received by the encryption method key generation algorithm of Non-Patent Document 1 include an integer N and a prime number t. The encryption algorithm of the encryption method of Non-Patent Document 1 receives, as a message, an N−1 order polynomial whose coefficients are smaller than t.

For an N−1th order polynomial f with each coefficient smaller than t, there is not necessarily f ⁻¹ satisfying f × f ⁻¹ = 1. That is, an inverse element related to multiplication is not necessarily present in a message encrypted by the encryption method of Non-Patent Document 1.

On the other hand, since t is a prime number, there exists an integer r ⁻¹ of 1 or more and less than t that satisfies r × r ⁻¹ = 1 by modulo t for any integer r of 1 or more and less than t.

Further, h is an integer of 0 to N-1.
x ^h × (−x ^N−h ) = − x ^N = 1 (Expression 55)
Holds.

For r and h
(R × x ^h ) × (r ⁻¹ × (−x ^N−h )) = 1 (Formula 56)
Holds.

Therefore, for any integer r greater than or equal to 1 and less than t and integer h greater than or equal to 0 and less than or equal to N−1, r × x ^h is a message that can be encrypted using the encryption scheme of Non-Patent Document 1, and the inverse element −r ⁻¹ × x ^N−h .

[Description of configuration]
The configuration of the third exemplary embodiment is the same as the configuration of the ciphertext matching system 100 according to the first embodiment shown in FIG.

[Description of operation]
Next, the operation of the ciphertext matching system 100 according to the third exemplary embodiment will be described. Similar to the first exemplary embodiment, the operation of the verification system 100 according to the present embodiment is roughly divided into a preparation phase, a registration phase, and a verification phase. First, an overview of processing in each phase will be described.

In the preparation phase, an encryption key and a decryption key are mainly generated using the received security parameters.

In the registration phase, a template in which the extracted registration vector is encrypted is created and stored mainly using the encryption key generated in the preparation phase.

In the verification phase, mainly the distance between the newly extracted authentication vector and one registered vector is calculated using the decryption key generated in the preparation phase.

Next, the process executed by the ciphertext verification system 100 in each phase described above will be described in detail.

The preparation phase of the third exemplary embodiment follows the flowchart of FIG. 2 of the first exemplary embodiment. Processing executed by the ciphertext matching system 100 according to the third embodiment in the preparation phase will be described with reference to FIG.

The key generation unit 151 in the verification device 150 includes a set of four parameters λ = (N, q, t, σ) (Expression 57)
Receive. However, as described above, N is an integer of 2 冪, q is a prime number congruent with 1 modulo 2N, t is a positive prime number smaller than q, and σ is a standard deviation of an N-dimensional discrete Gaussian distribution.

Next, two N−1 order polynomials s and e are generated according to an N-dimensional discrete Gaussian distribution with a standard deviation of σ. That is, a polynomial having N values generated according to the discrete Gaussian distribution as coefficients is generated. s is a secret key.

Next, an N−1 order polynomial p _{1 in} which each coefficient is smaller than t is randomly generated.

next,
p ₀ = − (p ₁ × s + t × e) (Formula 58)
Is calculated (step A1).
(Λ, p ₀ , p ₁ ) as an encryption key pk,
Let (λ, p ₀ , p ₁ , s) be the decryption key sk.

The key generation unit 151 discloses the encryption key pk in the ciphertext verification system 100 (step A2). The key generation unit 151 stores the decryption key sk in the decryption key storage unit 152 (step A3).

The process executed by the ciphertext matching system 100 according to the third embodiment in the preparation phase is not limited to the mode illustrated in FIG.

The registration phase of the third exemplary embodiment follows the flowchart of FIG. 3 of the first exemplary embodiment. A process executed by the ciphertext matching system 100 according to the third embodiment in the registration phase will be described with reference to FIG.

The registration information extraction unit 111 in the registration requesting device 110 receives biometric information (referred to as “registration vector”) from a biometric subject to registration.
A = (a ₀ ,..., A _L−1 ) (Formula 59)
Is extracted (step B1).

Next, the first template generation unit 112 in the registration request apparatus 110 generates a registration vector A generated from the registration vector A = (a ₀ ,..., A _L−1 ) according to the following expression 60 (the above expression 20). L−1 order polynomial f _A = Σ _{i = 0 to L−1} a _i × x ⁱ having each i th (i = 0,..., L−1) component a _i as a coefficient of the i th order term. ... (Formula 60)
Is generated.

Next, the parameter σ included in the encryption key pk = (λ, p ₀ , p ₁ ) disclosed by the verification apparatus 150 in step A2 of the preparation phase is used, and 3 according to an N-dimensional discrete Gaussian distribution with a standard deviation of σ. Two N-1th order polynomials u ₁ , g ₁ and f ₁ are generated.

Next, based on these, t, p ₀ , p ₁ included in the encryption key pk, and the generated polynomial f _A , the following two polynomials:
c _1,0 = p ₀ × u ₁ + t × g ₁ + f _A (Formula 61-1)
c _1,1 = p ₁ × u ₁ + t × f ₁ (Formula 61-2)
Calculate _Let (c _1,0 , c _1,1 ) be the ciphertext C ₁ (step B2).

That is, C ₁ is a ciphertext of f _{A with} the encryption key pk. The ciphertext C ₁ = (c _1,0 , c _1,1 ) calculated in step B2 is referred to as a “first template”.

Next, the second template generation unit 113 in the registration request device 110 calculates the sum of squares Σ _{i = 0 to L−1} a _i ^{2 of the} components of the registration vector A (Expression 62).
Calculate

Next, the parameter σ included in the encryption key pk = (λ, p ₀ , p ₁ ) disclosed by the verification apparatus 150 in step A2 of the preparation phase is used, and 3 according to an N-dimensional discrete Gaussian distribution with a standard deviation of σ. Generate two N−1 degree polynomials u ₂ , g ₂ and f ₂ .

Next, based on these, t, p ₀ , p ₁ included in the encryption key, and the generated values Σ _{i = 0 to L−1} a _i ² , the following two polynomials:
c _2,0 = p ₀ × u ₂ + t × g ₂ + (Σ _{i = 0 to L−1} a _i ² ) (Formula 63-1)
c _2,1 = p ₁ × u ₂ + t × f ₂ (Formula 63-2)
Calculate _Let (c _2,0 , c _2,1 ) be the ciphertext C ₂ (step B3). That is, C ₂ is a ciphertext of Σ _{i = 0 to L−1} a _i ^{2 with} the encryption key pk. The ciphertext C ₂ = (c _2,0 , c _2,1 ) calculated in step B3 is referred to as a “second template”.

Next, the template generation unit 114 in the registration requesting apparatus 110 sets the first template C ₁ = (c _1,0 , c _1,1 ) and the second template C ₂ = (c _2,0 , c _2,1 ). In summary, the template (C ₁ , C ₂ ) is used (step B4).

The registration requesting device 110 sends the template (C ₁ , C ₂ ) to the storage device 120 (step B5).

Next, the storage device 120 receives the template (C ₁ , C ₂ ) from the registration request device 110 (step B6).

The identifier assigning unit 121 in the storage device 120 determines a registration identifier id that is an identifier unique to the received template (C ₁ , C ₂ ) (step B7).

The storage device 120 sends the registration identifier id to the registration request device 110 (step B8).

Next, the registration request device 110 receives the registration identifier id from the storage device (step B9).

The registration request device 110 displays the received registration identifier id on a user interface (UI) such as a display (step B10), for example. Alternatively, the registration data device 102 may store the received registration identifier id in an IC (integrated_circuit) card such as an employee ID card or an identifier card. *

Next, the registration data generation unit 122 in the storage device 120 collects the template (C ₁ , C ₂ ) and the registration identifier id to register the registration data ((C ₁ , C ₂ ), id).
(Step B11).

The registration data generation unit 122 in the storage device 120 stores the registration data ((C ₁ , C ₂ ), id) in the registration data storage unit 123 (step B12).

Note that the processing executed by the ciphertext matching system 100 according to the third embodiment in the registration phase is not limited to the mode illustrated in FIG. For example, step B11 and step B12 may be executed prior to step B8.

The authentication phase of the third exemplary embodiment follows the flowchart of FIG. 4 of the first exemplary embodiment. A process executed by the ciphertext matching system 100 according to the third embodiment in the authentication phase will be described with reference to FIG.

The authentication request device 130 receives an identifier id (referred to as “authentication identifier”) possessed by the authentication target (step C1).

Next, the authentication request generator 131 in the authentication request device 130 generates an authentication request including the received authentication identifier id (step C2).

The authentication requesting device 130 sends an authentication request to the verification assisting device 140 (step C3).

The collation assisting device 140 receives an authentication request from the authentication requesting device 130 (step C4).

Next, the challenge auxiliary generation unit 141 in the verification auxiliary device 140 randomly selects an integer r smaller than t and an integer h smaller than N-1. The selected values are collected and used as challenge assistance (r, h) (step C5).

Next, the challenge generation unit 142 in the verification assisting device 140 calculates the polynomial r × x ^h (Expression 64) from the challenge assist (r, h).
Is calculated.

Next, the parameter σ included in the encryption key pk = (λ, p ₀ , p ₁ ) disclosed by the verification apparatus 150 in step A2 of the preparation phase is used, and 3 according to an N-dimensional discrete Gaussian distribution with a standard deviation of σ. Two N−1 degree polynomials u ₃ , g ₃ and f ₃ are generated.

Next, based on the N−1 order polynomials u ₃ , g _3, and f ₃ , t, p ₀ , p ₁ including the encryption key, and the polynomial r × x ^h , the following two polynomials:
c _3,0 = p ₀ × u ₃ + t × g ₃ + (r × x ^h ) (Formula 65-1)
c _3,1 = p ₁ × u ₃ + t × f ₃ (Formula 65-2)
Calculate _Let (c _3,0 , c _3,1 ) be the ciphertext C ₃ (step C6). That is, C ₃ is an r × x ^h ciphertext with the encryption key pk. The ciphertext C ₃ = (c _3,0 , c _3,1 ) calculated in step C 6 is called a “challenge”.

Verification auxiliary apparatus 140, sends the challenge _{C 3} to the authentication request unit 130 (step C7).

Next, the registration data request generation unit 143 in the verification assistant device 140 generates a registration data request including the authentication identifier id included in the authentication request received from the authentication request device 130 (step C8).

The collation assisting device 140 sends a registration data request to the storage device 120 (step C9).

Next, the storage device 120 receives a registration data request from the verification auxiliary device 140 (step C10).

The registration data search unit 124 in the storage device 120 includes registration data ((C ₁ , C ₂₎ including an authentication identifier id included in the registration data request among one or a plurality of registration data stored in the registration data storage unit. ), Id) is specified (step C11).

The templates (C ₁ , C ₂ ) included in the specified registered data are referred to as “collation target templates”.

The storage device 120 sends the verification target template (C ₁ , C ₂ ) to the verification auxiliary device 140 (step C12).

The verification auxiliary device 140 receives the verification target template (C ₁ , C ₂ ) from the storage device 120 (step C13).

The authentication requesting device 130 receives the challenge C ₃ = (c _3,0 , c _{3,1 −} ) from the verification assisting device 140 (step C14).

Next, the authentication information extraction unit 132 in the authentication requesting device 130 receives biometric information (referred to as an authentication vector) from the biometric subject to authentication.
B = (b ₀ ,..., B _L−1 ) (Expression 66)
Is extracted (step C15).

Next, the first response generation unit 133 in the authentication requesting device 130 relates to the addition of each i-th (i = 0,..., L−1) component b _i of the authentication vector B generated according to the following expression 67. A polynomial f _B = −Σ _{i = 0 to n−1} b _i × x ^{N i} (equation 67) having the inverse element −b _i as the coefficient of the Ni order term

Is generated.

However, when the degree of the polynomial is N or more, as described above,
x ^N = -1,
x ^{N + 1} = -x, ...
To make the polynomial less than or equal to the (N−1) th order. The same applies to the following calculations.

Next, the challenge C ₃ = (c _3,0 , c _3,1 ) received in step C14,
Based on the generated polynomial f _B,
c _4,0 = f _B × c _3,0 (Formula 68-1)
c _4,1 = f _B × c _3,1 (Formula 68-2)
Calculate _Let (c _4,0 , c _4,1 ) be the ciphertext C ₄ (step C16). That is, C ₄ is an encrypted text of r × x ^h × f _{B with} the encryption key pk. C ₄ = (c _4,0 , c _4,1 ) is called a “first response”.

Next, the second response generation unit 134 in the authentication requesting apparatus 130 calculates the sum of squares Σ _{i = 0 to L−1} b _i ^{2 of the} components of the authentication vector B (Equation 69).
Calculate

Next, the parameter σ included in the encryption key pk = (λ, p ₀ , p ₁ ) disclosed by the verification apparatus 150 in step A2 of the preparation phase is used, and 3 according to an N-dimensional discrete Gaussian distribution with a standard deviation of σ. Two N−1 degree polynomials u ₅ , g ₅ and f ₅ are generated.

Next, three N−1 degree polynomials u ₅ , g ₅ and f ₅ , t, p ₀ , p ₁ including the encryption key, and generated values Σ _{i = 0 to L−1} b _i ² , Based on the following two polynomials,
c _5,0 = p ₀ × u ₅ + t × g ₅ + (Σ _{i = 0 to L−1} b _i ² ) (Equation 70-1)
c _5,1 = p ₁ × u ₅ + t × f ₅ (Equation 70-2)
Calculate _Let (c _5,0 , c _5,1 ) be the ciphertext C ₅ (step C17).

That is, C ₅ is a ciphertext of Σ _{i = 0 to L−1} b _i ^{2 with} the encryption key pk. The ciphertext C ₅ = (c _5,0 , c _5,1 ) calculated in step C 17 is referred to as a “second response”.

Next, the response generation unit 135 in the authentication requesting device 130 obtains the first response C ₄ = (c _4,0 , c _4,1 ) and the second response C ₅ = (c _5,0 , c _5,1 ). In summary, responses (C ₄ , C ₅ ) are set (step C 18).

The authentication requesting device 130 sends the response (C ₄ , C ₅ ) to the verification assisting device 140 (step C19).

Next, the verification assisting device 140 receives the response (C ₄ , C ₅ ) from the authentication requesting device 130 (step C20).

Next, the encrypted inner product calculation unit 144 in the verification assisting device 140 uses the challenge assist (r, h) generated in Step C5,
^{-R -1 × x N-h ···} ( Formula 71)
Calculate However, r ⁻¹ is an integer of 1 or more and less than t that satisfies r × r ⁻¹ = 1 by modulo t.

Next, the encryption inner product calculation unit 144 in the verification auxiliary device 140
The first response C ₄ = (c _4,0 , c _4,1 ) included in the response (C ₄ , C ₅ ) received in step 19;
And ^{-r -1} × ^{x N-h} of generated-, based on,
c _6,0 = (− r ⁻¹ × x ^N−h ) × c _4,0 (Formula 72-1)
c _6,1 = (− r ⁻¹ × x ^N−h ) × c _4,1 (Formula 72-2)
Calculate
(C _6,0 , c _6,1 ) (Expression 73)
It is referred to as ciphertext _{C 6.} That, _{C 6} is due to the encryption key _{^{pk (r × x h × f}} B) × (-r -1 × x N-h) = f B ··· ( Formula 74)
Is the ciphertext.

Next, the encryption inner product calculation unit 144 in the verification auxiliary device 140
A first template C ₁ = (c _1,0 , c _1,1 ) included in the collation target template (C ₁ , C ₂ ) received in step C13;
Based on the generated ciphertext C ₆ = (c _6,0 , c _6,1 ),
c _7,0 = c _1,0 × c _6,0 (Formula 75-1)
c _7,1 = c _1,0 × c _6,1 + c _1,1 × c _6,0 (Formula 75-2)
c _7,2 = c _1,1 × c _6,1 (Formula 75-3)
Calculate
_{(C 7,0, c 7,1, c} 7,2) ··· ( Equation 76)
The a ciphertext _{C 7} (step C21). That is, C ₇ is a ciphertext of f _A × f _{B with} the encryption key pk. Step C21 the calculation ciphertext _{C 7 = (c 7,0, c} 7,1, c 7,2) is referred to as "encrypted inner product". As described above, the constant term of f _A × f _B is equal to the inner product <A, B> = Σ _{i = 0 to n−1} a _i × b _i of the registration vector A and the authentication vector B.

Next, the query generation unit 145 in the verification assisting device 140
A second template C ₂ = (c _2,0 , c _2,1 ) included in the collation target template (C ₁ , C ₂ ) received in step C13;
A second response C ₅ = (c _5,0 , c _5,1 ) included in the response (C ₄ , C ₅ ) received in step C20;
· Encryption generated in step C21 the inner product _{C 7 = (c 7,0, c} 7,1, c 7,2) and, based on,
c _8,0 = c _2,0 + c _5,0 + -2 × c _7,0 (Formula 77-1)
c _8,1 = c _2,1 + c _5,1 -2 × c _7,1 (Formula 77-2)
_{c 8,2 = -2 × c 7,2 ···} ( Formula 77-3)
Calculate _Let (c _8,0 , c _8,1 , c _8,2 ) be the ciphertext C ₈ (step C22). That is, C ₈ is (Σ _{i = 0 to n−1} a _i ² ) + (Σ _{i = 0 to n−1} b _i ² ) −2 × f _A × f _B. (Formula 78)
Is the ciphertext. The calculated ciphertext C ₈ = (c _8,0 , c _8,1 , c _8,2 ) is called a “query”.

As described above, the constant term of f _A × f _B is equal to the inner product <A, B> = Σ _{i = 0 to n−1} a _i × b _i of the registration vector A and the authentication vector B. Therefore, C ₈ is a polynomial ciphertext having a constant term of Euclidean distance d _E (A, B) between registration vector A and authentication vector B.

Next, the verification auxiliary device 140 sends the query C ₈ = (c _8,0 , c _8,1 , c _8,2 ) to the verification device 150 (step C23).

Next, the verification device 150 receives the query _{C 8} from the verification auxiliary apparatus 140 (step C24).

The query verification unit 153 in the verification device 150
Query C ₈ = (c _8,0 , c _8,1 , c _8,2 )
Based on the secret key sk = (λ, p ₀ , p ₁ , s)
D ₁ = c _8,0 + c _8,1 × s + c _8,2 × s ² (Equation 79)
Calculate

Next, let D ₂ be the remainder of dividing D ₁ by q. If D ₂ is q / 2 or more, D ₃ = D ₂ -q. If D ₂ is smaller than q / 2, D ₃ = D ₂ (D ₂ εZ ^(q) = [−q / 2, q / 2) ∩Z).

Next, a remainder polynomial obtained by dividing D ₃ by t is D ₄ . The constant term of D ₄ and _{D 5} (step C25). The value D ₅ calculated, referred to as the "verification result". As described above, the constant term D ₅ is the Euclidean distance d _E (A, B) between the registration vector A and the authentication vector B.

Then, the matching result generation unit 154 in the verification device 150, a verification result _{D 5} and collation result d. Alternatively, the verification result and D _5, which may the result of comparing the magnitude of the predetermined threshold value as a verification result d (step C26).

The verification device 150 outputs the calculated verification result d (step C27).

Note that the processing executed by the ciphertext matching system 100 according to the third embodiment in the authentication phase is not limited to the mode illustrated in FIG. For example, steps C9 to C13 may be executed prior to step C5.

In the above description of the ciphertext matching system 100 according to the third embodiment, the polynomial f _A generated in step B2 by the first template generation unit 112 in the registration request apparatus 110 is generated according to the above equation 20 based on the registration vector A. The polynomial f _B generated by the first response generation unit 133 in the authentication requesting apparatus 130 in step C16 is a polynomial generated according to the above equation 21 based on the authentication vector.

The method for generating the two polynomials in the third embodiment is not limited to the above method. For example, the polynomial f _A generated in step B2 by the first template generation unit 112 in the registration request apparatus 110 is a polynomial generated according to the expression 21 based on the registration vector A, and the first response generation unit 133 in the authentication request apparatus 130 the polynomial f _B to generate at step C16, may be a polynomial generated according based formula 20 in the authentication vector.

[Description of effects]
Next, effects related to the ciphertext matching system 100 according to the third exemplary embodiment will be described.

According to the ciphertext matching system 100 according to the third exemplary embodiment, a user who requests authentication can safely implement 1: 1 authentication by performing authentication by presenting his / her own living body and identifier. Is possible. That is, it has the following two effects.

According to the ciphertext matching system 100 according to the third exemplary embodiment, the registration vector extracted by the registration request device 110 is encrypted on the registration request device 110 and sent to the storage device 120. The authentication vector extracted by the authentication requesting device 130 is encrypted on the authentication requesting device 130 and sent to the verification assisting device 140.

The ciphertext can be decrypted by the verification device 150 having a decryption key, but the data received by the verification device 150 is a ciphertext of the Euclidean distance between the registration vector and the authentication vector. The value is not disclosed.

Therefore, according to the ciphertext matching system 100 according to the third exemplary embodiment, a value other than the distance between the registered vector and the authentication vector is not leaked to a device other than the device that extracts each vector, and the registered vector It is possible to calculate the distance between the authentication vectors.

Further, according to the ciphertext matching system 100 according to the third exemplary embodiment, even when authenticating with the same registration vector, the process using the random number selected in step C5 is performed.

Therefore, even if the communication content of the verification process is leaked, the distance equal to the distance at the time of the leaked verification is calculated by resending the leaked content or sending data created using the leaked content Or a small value cannot be calculated.

In particular, when the ciphertext matching system 100 according to the third exemplary embodiment is used for authentication that accepts when the distance is smaller than the threshold, an attacker who does not know the registration vector is not accepted. The property, ie, resistance to spoofing attacks.

Furthermore, the ciphertext matching system 100 according to the third exemplary embodiment is configured using an encryption method described in Non-Patent Document 1, which is an encryption method capable of high-speed processing. Therefore, high-speed collation processing is possible.

Further, in the ciphertext matching system 100 according to the third exemplary embodiment, the verification device 150 having the decryption key can be modified so as not to disclose the Euclidean distance between the registration vector and the authentication vector. It is. For example, by applying the same method as the method described in Non-Patent Document 4, the verification device 150 having a decryption key can be transformed into a method that cannot calculate the Euclidean distance between the registration vector and the authentication vector. A method that does not disclose the Euclidean distance between the registration vector and the authentication vector for the verification device 150 having the decryption key means that the verification device 150 having the decryption key calculates the value of the registration vector even under special circumstances. Can be prevented. For this reason, higher safety can be achieved.

[Fourth Embodiment]
Next, a fourth exemplary embodiment will be described. The fourth exemplary embodiment is a case where the encryption scheme shown in Non-Patent Document 1 is used in the ciphertext matching system 200 shown in FIG. 5 referred to in the description of the second exemplary embodiment. . In the following, characteristic parts according to the fourth exemplary embodiment will be mainly described, and description of the same parts as those of the second exemplary embodiment will be omitted as appropriate.

The fourth exemplary embodiment is configured using an encryption method described in Non-Patent Document 1 and having homomorphism with respect to addition and information. The configuration of the fourth exemplary embodiment uses the following characteristics of the encryption method of Non-Patent Document 1.

The parameters received by the encryption method key generation algorithm of Non-Patent Document 1 include an integer N and a prime number t.

The encryption algorithm of the encryption method of Non-Patent Document 1 receives, as a message, an N−1 order polynomial in which each coefficient is smaller than t. For an N−1th order polynomial f with each coefficient smaller than t, there is not necessarily f ⁻¹ satisfying f × f ⁻¹ = 1. That is, the reverse element does not necessarily exist in the message encrypted by the encryption method of Non-Patent Document 1.

On the other hand, since t is a prime number, with respect to an arbitrary integer r greater than or equal to 1 and less than t, modulo t, r × r ⁻¹ = 1 (Equation 80)
There is an integer r ⁻¹ that satisfies 1 and less than t.

Further, h is an integer of 0 to N-1. For r and h
(R × x ^h ) × (r ⁻¹ × (−x ^N−h )) = 1 (Formula 81)
Holds.

Therefore, for any integer r greater than or equal to 1 and less than t and integer h greater than or equal to 0 and less than or equal to N−1, r × x ^h is a message that can be encrypted using the encryption scheme of Non-Patent Document 1, and the inverse element −r ⁻¹ × x ^N−h .

[Description of configuration]
The configuration of the fourth exemplary embodiment is the same as the configuration of the ciphertext matching system 200 according to the second exemplary embodiment shown in FIG.
[Description of operation]
Next, the operation of the ciphertext matching system 200 according to the fourth exemplary embodiment will be described.

Next, the operation in the ciphertext matching system 200 according to the fourth exemplary embodiment is roughly divided into a preparation phase, a registration phase, and a verification phase, as in the second exemplary embodiment. . First, an overview of processing in each phase will be described.

In the preparation phase, an encryption key and a decryption key are mainly generated using the received security parameters.

In the registration phase, a template in which the extracted registration vector is encrypted is created and stored mainly using the encryption key generated in the preparation phase.

In the verification phase, the distance between the newly extracted authentication vector and one or more registered vectors is mainly calculated using the decryption key generated in the preparation phase.

Next, the process executed by the ciphertext matching system 200 in each phase described above will be described in detail. The preparation phase of the fourth exemplary embodiment follows the flowchart of FIG. 6 showing an example of the processing of the preparation phase executed by the ciphertext matching system 200 according to the second exemplary embodiment. With reference to FIG. 6, a process executed in the preparation phase by the collation system 200 according to the fourth exemplary embodiment will be described.

The key generation unit 251 in the verification device 250 has a set of four parameters λ = (N, q, t, σ) (Expression 82)
Receive. Where N is an integer of 2 冪, q is a prime number congruent to 1 modulo 2N, t is a positive integer smaller than q, and σ is a standard deviation of a certain discrete Gaussian distribution on an N−1 order polynomial.

Next, two N−1 order polynomials s and e are generated according to an N-dimensional discrete Gaussian distribution with a standard deviation of σ. Next, an N−1 order polynomial p _{1 in} which each coefficient is smaller than q is randomly generated.

Next, p ₀ = − (p ₁ × s + t × e) (Expression 83)
Calculate
(Λ, p ₀ , p ₁ ) as an encryption key (public key) pk,
Let (λ, p ₀ , p ₁ , s) be a decryption key (secret key) sk (step D1).

The key generation unit 251 discloses the encryption key pk in the ciphertext verification system 200 (step D2). The key generation unit 251 stores the decryption key sk in the decryption key storage unit 252 (step D3).

Note that the processing executed in the preparation phase by the ciphertext matching system 200 according to the fourth exemplary embodiment is not limited to the mode illustrated in FIG.

The registration phase of the fourth exemplary embodiment follows the flowchart of FIG. 7 showing an example of the registration phase process executed by the ciphertext matching system 200 according to the second exemplary embodiment. With reference to FIG. 7, a description will be given of processing executed in the registration phase by the collation system 200 according to the fourth exemplary embodiment.

The registration information extraction unit 211 in the registration requesting apparatus 210 receives biometric information (referred to as a registration vector) A = (a ₀ ,..., A _L−1 ) (formula 84)
Is extracted (step E1).

Next, the first template generation unit 212 in the registration request apparatus 210 generates a registration vector A generated from the registration vector A = (a ₀ ,..., A _L−1 ) according to the following expression 85 (the above expression 20). each i-th (i = 0, ..., L -1) component _{a i} a i following L-1 degree polynomial _{f a = Σ i = 0 ~} L-1 a i × with the coefficients of the terms ^{x i} · a .. (Formula 85)
Is generated.

Next, the parameter σ included in the encryption key pk = (λ, p ₀ , p ₁ ) disclosed by the verification apparatus 250 in step D2 of the preparation phase is used, and 3 according to an N-dimensional discrete Gaussian distribution with a standard deviation of σ. Two N-1th order polynomials u ₁ , g ₁ and f ₁ are generated.

Next, based on the N−1 order polynomials u ₁ , g ₁ and f ₁ , t, p ₀ , p ₁ included in the encryption key pk, and the generated polynomial f _A , the following two polynomials:
c _1,0 = p ₀ × u ₁ + t × g ₁ + f _A (Expression 86-1)
c _1,1 = p ₁ × u ₁ + t × f ₁ (Expression 86-2)
Calculate _Let (c _1,0 , c _1,1 ) be the ciphertext C ₁ (step E2). That is, C ₁ is a ciphertext of f _{A with} the encryption key pk. The calculated ciphertext C ₁ = (c _1,0 , c _1,1 ) is called a “first template”.

Next, the second template generation unit 213 in the registration requesting device 210 calculates the sum of squares Σ _{i = 0 to L−1} a _i ^{2 of the} components of the registration vector A (Expression 87).
Calculate

Next, the parameter σ included in the encryption key pk = (λ, p ₀ , p ₁ ) disclosed by the verification apparatus 250 in step D2 of the preparation phase is used, and 3 according to an N-dimensional discrete Gaussian distribution with a standard deviation of σ. Generate two N−1 degree polynomials u ₂ , g ₂ and f ₂ .

Next, N−1 degree polynomials u ₂ , g _2, and f ₂ , t, p ₀ , p ₁ included in the encryption key pk, and generated values Σ _{i = 0 to L−1} a _i ² , Based on the following two polynomials,
c _2,0 = p ₀ × u ₂ + t × g ₂ + (Σ _{i = 0 to L−1} a _i ² ) (Equation 88-1)
c _2,1 = p ₁ × u ₂ + t × f ₂ (Formula 88-2)
Calculate _Let (c _2,0 , c _2,1 ) be the ciphertext C ₂ (step E3). That is, C ₂ is a ciphertext of Σ _{i = 0 to L−1} a _i ^{2 with} the encryption key pk. The calculated ciphertext C ₂ = (c _2,0 , c _2,1 ) is called a “second template”.

Next, the template generation unit 214 in the registration requesting device 210 obtains the first template c ₁ = (c _1,0 , c _1,1 ) and the second template C ₂ = (c _2,0 , c _2,1 ). In summary, the template (C ₁ , C ₂ ) is used (step E4).

The registration requesting device 210 sends the template to the storage device 220 (step E5).

Next, the storage device 220 receives the template (C ₁ , C ₂ ) from the registration request device 210 (step E6).

The identifier assigning unit 221 in the storage device 220 determines a registered identifier id that is an identifier unique to the received template (step E7).

Storage device 220 sends registration identifier id to registration request device 210 (step E8).

Next, the registration request device 210 receives the registration identifier id from the storage device (step E9). For example, the registration requesting device 210 displays the received registration identifier id on a user interface (UI) such as a display (step E10). Alternatively, the registration requesting device 210 may store the received registration identifier id in an IC (integrated_circuit) card such as an employee ID card or an identifier card. *

Next, the registration data generation unit 222 in the storage device 220 summarizes the template (C ₁ , C ₂ ) and the registration identifier id, and registers data ((C ₁ , C ₂ ), id) (Equation 89)
(Step E11).

The registration data generation unit 222 in the storage device 220 stores the registration data ((C ₁ , C ₂ ), id) in the registration data storage unit 223 (step E12).

Note that the processing executed in the registration phase by the ciphertext matching system 200 according to the fourth exemplary embodiment is not limited to the mode illustrated in FIG. For example, step E11 and step E12 may be executed prior to step E8.

An example of the process of the authentication phase of the fourth exemplary embodiment follows the flowchart of FIG. 8 showing an example of the process executed by the ciphertext matching system 200 according to the second exemplary embodiment. With reference to FIG. 8, a description will be given of processing executed by the verification system 200 according to the fourth exemplary embodiment in the authentication phase.

The authentication request generation unit 231 in the authentication request device 230 generates an authentication request (step F1).

The authentication requesting device 230 sends an authentication request to the verification assisting device 240 (step F2).

The verification auxiliary device 240 receives the authentication request from the authentication requesting device 230 (step F3).

Next, the challenge auxiliary generation unit 241 in the verification auxiliary device 240 randomly selects an integer r smaller than t and an integer h smaller than N-1. The selected values are collected and used as challenge assistance (r, h) (step F4).

Next, the challenge generation unit 242 in the verification assisting device 240 calculates the polynomial r × x ^h (Expression 90) from the challenge assist (r, h).
Is calculated.

Next, using the parameter σ included in the encryption key pk = (λ, p ₀ , p ₁ ) disclosed by the verification device 250 in step D2 of the preparation phase, according to an N-dimensional discrete Gaussian distribution with a standard deviation of σ, Three N−1 degree polynomials u ₃ , g ₃ and f ₃ are generated.

Next, based on the three N−1 degree polynomials u ₃ , g _3, and f ₃ , t, p ₀ , p ₁₋ including the encryption key, and the polynomial r × x ^h , the following two polynomials ,
c _3,0 = p ₀ × u ₃ + t × g ₃ + (r × x ^h ) (Formula 91-1)
c _3,1 = p ₁ × u ₃ + t × f ₃ (Formula 91-2)
Calculate _Let (c _3,0 , c _3,1 ) be the ciphertext C ₃ (step F5). That is, C ₃ is an r × x ^h ciphertext with the encryption key pk. The calculated ciphertext C ₃ = (c _3,0 , c _3,1 ) is called a “challenge”. Verification auxiliary apparatus 240, sends the challenge _{C 3} to the authentication request unit 230 (step F6).

Next, the registration data request generation unit 243 in the verification auxiliary device 240 generates a registration data request (step F7).

The collation assisting device 240 sends a registration data request to the storage device 220 (step F8).

Next, the storage device 220 receives a registration data request from the verification auxiliary device 240 (step F9).

The storage device 220 sends a part or all (M) of registration data among one or a plurality of registration data stored in the registration data storage unit 223 to the verification assisting device 240 (step F10). . However, each registration data is a set of a template and a registration identifier.

The collation assisting device 240 receives M pieces of registered data from the storage device 220 (step F11).

In the following, each j-th (j = 1,..., M) registered data is represented as ((C _{j, 1} , C _{j, 2} ), id _j ) (Equation 92)
It expresses.

In addition, templates (C _{j, 1} , C _{j, 2} ) included in each j-th (j = 1,..., M) registration data ((C _{j, 1} , C _{j, 2} ), id _j ) are: It is assumed that it is generated from the registration vector _Aj .

The first template C _{j, 1} included in each j-th (j = 1,..., M) registration data ((C _{j, 1} , C _{j, 2} ), id _j ) is obtained from the registration vector A _j. Cipher text Enc (pk, f _{A, j} ) = (c _{j, 1,0} , c _{j, 1,1} ) of the generated polynomial f _{A, j} (Equation 93)
Suppose that

Further, the second template C _{j, 2} included in each j-th (j = 1,..., M) registration data ((C _{j, 1} , C _{j, 2} ), id _j ) is stored in the registration vector A _j . Sum of squares of each component Σ _{i = 0 to n−1} a _{j, i} ² (Equation 94)
Ciphertext Enc (pk, Σ _{i = 0 to n−1} a _{j, i} ² ) = (c _{j, 2,0} , c _{j, 2,1} ) (Equation 95)
Suppose that

The authentication requesting device 230 receives a challenge from the verification assisting device 240 (step F12).

Next, the authentication information extraction unit 232 in the authentication requesting device 230 obtains biometric information (referred to as “authentication vector”) from the biometric subject to authentication.
B = (b ₀ ,..., B _L−1 ) (Equation 96)
Is extracted (step F13).

Next, the first response generation unit 233 in the authentication requesting device 230 generates each i-th (i = 0,..., L−1) component of the authentication vector B generated according to the following expression 97 (the above expression 20). b _i polynomials with additive regarding the inverse -b _i of the coefficient of n-i following section _{f B = -Σ i = 0 ~} n-1 b i × x n-i ··· ( formula 97)
Is generated.

However, when the degree of the polynomial is N or more,
x ^N = -1, x ^{N + 1} = -x, ...
To make the polynomial less than or equal to the (N−1) th order. The same applies to the following calculations.

Next, based on the challenge C ₃ = (c _3,0 , c _3,1 ) received in step F12 and the generated polynomial f _B ,
c _4,0 = f _B × c _3,0 (Formula 98-1)
c _4,1 = f _B × c _3,1 (Formula 98-2)
Calculate _Let (c _4,0 , c _4,1 ) be the ciphertext C ₄ (step F14). That is, C ₄ is an encrypted text of r × x ^h × f _{B with} the encryption key pk. C ₄ = (c _4,0 , c _4,1 ) is called a “first response”.

Next, the second response generation unit 234 in the authentication requesting device 230 obtains the sum of squares Σ _{i = 0 to L−1} b _i ^{2 of the} components of the authentication vector B (Equation 99).
Calculate

Next, in step A2 of the preparation phase, the parameter σ included in the encryption key pk = (λ, p ₀ , p ₁ ) disclosed by the verification device 250 is used, and the standard deviation is σ according to the N-dimensional discrete Gaussian distribution. Three N-1th order polynomials u ₅ , g ₅ and f ₅ are generated.

Next, three N−1 degree polynomials u ₅ , g _5, and f ₅ , t, p ₀ , and p ₁ included in the encryption key pk, and generated values Σ _{i = 0 to L−1} b _i ² And the following two polynomials,
c _5,0 = p ₀ × u ₅ + t × g ₅ + (Σ _{i = 0 to L−1} b _i ² ) (Equation 100-1)
c _5,1 = p ₁ × u ₅ + t × f ₅ (Equation 100-2)
Calculate _Let (c _5,0 , c _5,1 ) be the ciphertext C ₅ (step F15). That is, C ₅ is Σ _{i = 0 to L−1} b _i ² depending on the encryption key pk.
Is the ciphertext. The ciphertext C ₅ = (c _5,0 , c _5,1 ) calculated in step F15 is referred to as a “second response”.

Next, the response generation unit 235 in the authentication requesting device 230 obtains the first response C ₄ = (c _4,0 , c _4,1 ) and the second response C ₅ = (c _5,0 , c _5,1 ). In summary, responses (C ₄ , C ₅ ) are set (step F16).

The authentication requesting device 230 sends the response (C ₄ , C ₅ ) to the verification assisting device 240 (step F17).

Next, the verification assisting device 240 receives the response (C ₄ , C ₅ ) from the authentication requesting device 230 (step F18).

Next, the encryption inner product calculation unit 244 in the verification assisting device 240 uses the challenge assist (r, h) generated in Step F4,
−r ⁻¹ × x ^N−h (Formula 101)
Calculate Where r ^-1 modulo t
r × r ⁻¹ = 1 (Formula 102)
1 or more and less than t.

Next, the encrypted inner product calculation unit 244 in the verification assisting device 240 obtains the first response C ₄ = (c _4,0 , c _4,1 ) included in the response (C ₄ , C ₅ ) received in step F18. a ^{-r -1} × ^{x N-h} which generated, based on,
^{_{c 6,0 = (- r -1 ×}} x N-h) × c 4,0 ··· ( Formula 103-1)
^{_{c 6,1 = (- r -1 ×}} x N-h) × c 4,1 ··· ( Formula 103-2)
Calculate
(C _6,0 , c _6,1 ) (Formula 104)
A and ciphertext _{C 6.} That, _{C 6} is due to the encryption key _{^{pk (r × x h × f}} B) × (-r -1 × x N-h) = f B ··· ( Formula 105)
Is the ciphertext.

Next, the encryption inner product calculation unit 244 in the verification assisting device 240, for each j (j = 1,..., M), out of the M registration data received in step F11,
a first template C _{j, 1} = (c _{j, 1,0} , c _{j, 1,1} ) included in the j-th registered data ((C _{j, 1} , C _{j, 2} ), id _j );
Based on the generated ciphertext C ₆ = (c _6,0 , c _6,1 ),
c _{j, 7,0} = c _{j, 1,0} × c _6,0 (Formula 106-1)
c _{j, 7,1} = c _{j, 1,0} × c _6,1 + c _{j, 1,1} × c _6,0 (Equation 106-2)
c _{j, 7,2} = c _{j, 1,1} × c _6,1 (Formula 106-3)
Calculate

For each j (j = 1, ..., M)
_{(C j, 7,0, c j} , 7,1, c j, 7,2) ··· ( Formula 107)
Is the ciphertext C _{j, 7} (step F19). That is, for each j (j = 1,..., M), C _{j, 7} is a ciphertext of f _{A, j} × f _{B with} the encryption key pk.

Each j (j = 1, ..., M) for the calculated ciphertext _{C j, 7 = (c j} , 7,0, c j, 7,1, c j, 7,2) "Encryption inner product" Call it.

Incidentally, as described above, each of j (j = 1, ..., M) _{for, f A,} inner product of the constant term of the _j × _{f B} is the registered vectors _{A j} and an authentication vector B _<A j ,B> = Σ _{i = 0 to n−1} a _{j, i} × b _i is equal to _i .

Next, the query generation unit 245 in the verification assisting device 240 for each j (j = 1,..., M)
Of the M registration data received in step F11,
a second template C _{j, 2} = (c _{j, 2,0} , c _{j, 2,1} ) included in the j-th registered data ((C _{j, 1} , C _{j, 2} ), id _j );
A second response C ₅ = (c _5,0 , c _5,1 ) included in the response (C ₄ , C ₅ ) received in step F18;
Step j-th encrypted inner product generated by the F19 _{C j,} 7 ₌ a _{(c j, 7,0, c j} , 7,1, c j, 7,2), based on,
c _{j, 8,0} = c _{j, 2,0} + c _5,0 + -2 × c _{j, 7,0} (Formula 108-1)
c _{j, 8,1} = c _{j, 2,1} + c _5,1 −2 × c _{j, 7,1} (Formula 108-2)
c _{j, 8,2} = −2 × c _{j, 7,2} (Formula 108-3)
Calculate

For each j (j = 1,..., M), (c _{j, 8,0} , c _{j, 8,1} , c _{j, 8,2} ) is set as ciphertext C _{j, 8} (step F20).

That is, for each j (j = 1,..., M), C _{j, 8} is (Σ _{i = 0 to n−1} a _{j, i} ² ) + (Σ _{i = 0 to n−} ) according to the encryption key pk. ₁ b _i ² ) -2 × f _{A, j} × f _B
... (Formula 109)
Is the ciphertext.

For each j (j = 1,..., M), the calculated ciphertext C _{j, 8} = (c _{j, 8,0} , c _{j, 8,1} , c _{j, 8,2} ) (Formula 110) )
Is called a “query”.

Incidentally, as described above, each of j (j = 1, ..., M) _{for, f A,} inner product of the constant term of the _j × _{f B} is the registered vectors _{A j} and an authentication vector B _<A j ,B> = Σ _{i = 0 to n−1} a _{j, i} × b _i is equal to _i .

Therefore, for each j (j = 1,..., M), C _{j, 8} is a polynomial ciphertext having a constant term of Euclidean distance d _E (A _j , B) between registration vector A _j and authentication vector B. is there.

Next, the verification data generation unit 246 in the verification assisting device 240 performs the following for each j (j = 1,..., M).
The query C _{j, 8} = (c _{j, 8,0} , c _j generated in step F20 using the second template included in the jth registration data among the M pieces of registration data received in step F11 _{, 8,1} , c _{j, 8,2} ),
Of the M pieces of registration data received in step F11, the registration identifier id _j included in the j-th registration data,
The j-th verification data (C _{j, 8} , id _j ) is assumed (step F21).

Next, the verification assisting device 240 sends M pieces of verification data to the verification device 250 (step F22).

Next, the verification device 250 receives M pieces of verification data from the verification auxiliary device 240 (step F23).

The query verification unit 253 in the verification device 250 performs the following for each j (j = 1,..., M).
Of the M pieces of verification data received in step F23, the query C _{j, 8} = (c _{j, 8,0} , c _{j, 8,} included in the _jth verification data (C _{j, 8} , id _j ) ₁ , c _{j, 8,2} ),
Based on the secret key (decryption key) sk = (λ, p ₀ , p ₁ , s),
D _{j, 1} = c _{j, 8,0} + c _{j, 8,1} × s + c _{j, 8,2} × s ² (Equation 111)
Calculate

Next, for each j (j = 1,..., M), the remainder obtained by dividing D _{j, 1} by q is D _{j, 2} .

Next, for each j (j = 1,..., M), if D _{j, 2} is equal to or greater than q / 2, then D _{j, 3} = D _{j, 2-} q. If D _{j, 2} is smaller than q / 2, then D _{j, 3} = D _{j, 2} . This is a remainder operation to [−q / 2, q / 2) modulo D of q.

Next, for each j (j = 1,..., M), a remainder polynomial obtained by dividing D _{j, 3} by t is D _{j, 4} . The constant term of D _{j, 4} is set to D _{j, 5} (step F24). For each j (j = 1,..., M), D _{j, 5} is called a “verification result”.

As described above, for each j (j = 1,..., M), D ₅ generated from the j-th verification data among the M verification data is the Euclidean distance d between the registration vector A _j and the authentication vector B. _E (A _j , B).

Next, the verification result generation unit 254 in the verification device 250, for each j (j = 1,..., M), out of M verification data,
The verification result D _{j, 5} generated in step F24 based on the query included in the jth verification data;
The registration identifier id _j included in the j-th verification data is collected and used as the j-th matching result (D _{j, 5} , id _j ). Or the collation result generation part 254 in the verification apparatus 250 is M among verification data about each j (j = 1, ..., M).
A result d _j that compares the verification result id _j generated in step F24 from the query included in the j-th verification data with a predetermined threshold;
The registration identifier id _j included in the j-th verification data may be collected and used as the j-th collation result (d _j , id _j ) (step F25).

The verification device 250 outputs the calculated M verification results (step F26).

Note that the processing executed by the ciphertext matching system 200 according to the fourth exemplary embodiment in the authentication phase is not limited to the mode illustrated in FIG. For example, steps F9 to F13 may be executed prior to step F5.

In the above description of the ciphertext matching system 200 according to the fourth exemplary embodiment, the polynomial f _A generated in step B2 by the first template generation unit 212 in the registration request apparatus 210 is based on the registration vector A. It is assumed that the polynomial f _B generated by the first response generation unit 233 in the authentication requesting device 130 in step C16 is a polynomial generated according to the above equation 21 based on the authentication vector.

The method of generating the two polynomials in the fourth exemplary embodiment is not limited to the above method. For example, the polynomial f _A generated by the first template generation unit 212 in the registration request device 210 in step B 2 is a polynomial generated according to the above equation 21 based on the registration vector A, and the first response generation unit 233 in the authentication request device 230. There polynomial f _B to generate at step F16, or as a polynomial generated according to the formula 20 based on the authentication vector.
[Description of effects]

Next, effects related to the ciphertext matching system 200 according to the fourth exemplary embodiment will be described.

According to the ciphertext verification system 200 according to the fourth exemplary embodiment, a user who requests authentication does not present his / her identifier, and verifies all registered information and information used for authentication. It is possible to safely implement 1: N authentication. That is, it has the following two effects.

According to the ciphertext matching system 200 according to the fourth exemplary embodiment, the registration vector extracted by the registration requesting device 210 is encrypted on the registration requesting device 210 and sent to the storage device 220. The authentication vector extracted by the authentication requesting device 230 is encrypted on the authentication requesting device 230 and sent to the verification assisting device 240. The ciphertext can be decrypted by the verification device 250 having a decryption key, but the data received by the verification device 250 is a ciphertext of the Euclidean distance between the registration vector and the authentication vector. The value is not disclosed.

Therefore, according to the ciphertext matching system 200 according to the fourth exemplary embodiment, a value other than the distance between the registration vector and the authentication vector is not leaked to a device other than the device that extracts each vector, It is possible to calculate the distance between the authentication vectors.

Also, according to the ciphertext matching system 200 according to the fourth exemplary embodiment, even when authenticating with the same registration vector, processing using the random number selected in step C5 is performed. Therefore, even if the communication content of the verification process is leaked, the distance equal to the distance at the time of the leaked verification is calculated by resending the leaked content or sending data created using the leaked content Or a small value cannot be calculated.

In particular, when the ciphertext matching system 200 according to the fourth exemplary embodiment is used for authentication that accepts when the distance is smaller than the threshold, an attacker who does not know the registered vector is not accepted. The property, ie, resistance to spoofing attacks.

Furthermore, the ciphertext matching system 200 according to the fourth exemplary embodiment is configured using an encryption method described in Non-Patent Document 1, which is an encryption method capable of high-speed processing. Therefore, high-speed collation processing is possible.

Furthermore, in the ciphertext matching system 200 according to the fourth exemplary embodiment, the verification device 250 having the decryption key can be modified so as not to disclose the Euclidean distance between the registration vector and the authentication vector. For example, by applying the same method as the method described in Non-Patent Document 4, the verification device 250 having a decryption key can be transformed into a method that cannot calculate the Euclidean distance between the registration vector and the authentication vector. A method that does not disclose the Euclidean distance between the registration vector and the authentication vector for the verification device 250 having the decryption key means that the verification device 250 having the decryption key calculates the value of the registration vector even under special circumstances. Can be prevented. For this reason, higher safety can be achieved.

Although not particularly limited, as an application example of the present invention, for example, biometric authentication using a multi-value vector as a feature amount can be mentioned.

For example, the input data in the registration phase and the input data in the verification phase are biometric information (feature vectors) obtained from biometric information obtained from fingerprints or veins. In this case, by applying the present invention, 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 the biometric information is kept secret. It can be determined whether the distance between the two pieces of biological information is equal to or less than a threshold value.

In particular, it is known that biometric information cannot always stably acquire the same data, and the data acquired from the same person is similar (data with a small distance between each element can be acquired). Can be assumed. For this reason, the present invention is useful for biometric authentication and the like.

In addition, each disclosure of the above non-patent literature shall be incorporated into this book with reference. Within the scope of the entire disclosure (including claims) of the present invention, the embodiments and examples can be changed and adjusted based on the basic technical concept. Various 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 claims of the present invention. . That is, the present invention of course includes various variations and modifications that could be made by those skilled in the art according to the entire disclosure including the claims and the technical idea.

100, 200 Ciphertext collation system 110, 210 Registration request device 111, 211 Registration information extraction unit 112, 212 First template generation unit 113, 213 Second template generation unit 114, 214 Template generation unit 120, 220 Storage devices 121, 221 Identifier assignment unit 122, 222 Registration data generation unit 123, 223 Registration data storage unit 124 Registration data search unit 130, 230 Authentication request device 131, 231 Authentication request generation unit 132, 232 Authentication information extraction unit 133, 233 First response generation unit 134, 234 Second response generation unit 135, 235 Response generation unit 140, 240 Verification assistant device 141, 241 Challenge auxiliary generation unit 142, 242 Challenge generation unit 143, 243 Registration data request generation unit 144, 244 Encryption inner product calculation Units 145 and 245 Query generation units 150 and 250 Verification devices 151 and 251 Key generation units 152 and 252 Decryption key storage units 153 and 253 Query verification units 154 and 254 Verification result generation unit 246 Verification data generation unit

Claims (10)

Including a registration requesting device, a verification assisting device, an authentication requesting device, and a verification device;
The verification device calculates an encryption key and decryption key pair of a homomorphic encryption method capable of polynomial operation, and publishes the encryption key,
The registration request device includes:
Registration information that is a numeric vector is polynomialized,
The registration information that has been polynomialized is encrypted using the encryption key,
The verification assisting device is:
Upon receiving an authentication request from the authentication requesting device, one coefficient and its order are selected at random, and a polynomial in which coefficients other than the order coefficient are set to 0 is generated,
Sending a challenge consisting of ciphertext encrypted with the encryption key to the polynomial to the authentication requesting device,
The authentication requesting device includes:
The authentication information, which is a numeric vector, is polynomialized,
Based on the authentication information that has been polynomialized and the challenge from the verification assisting device, using the encryption key, the product of the authentication information that has been polynomialized and the polynomial used to generate the challenge Calculate the ciphertext,
The ciphertext of the product of the authentication information polynomialized and the polynomial used to generate the challenge is sent as the response to the verification assisting device,
The verification assisting device is:
When receiving a response from the authentication requesting device, based on the response, challenge assistance consisting of the one coefficient and its order, and the registration information encrypted by the registration requesting device, the encryption key is used. , Calculating a ciphertext of the distance between the registration information and the authentication information,
Sending the ciphertext of the distance between the registration information and the authentication information to the verification device;
The verification device includes:
The encrypted text of the distance between the registration information and the authentication information received from the verification assisting device is decrypted using the decryption key to calculate the distance,
A ciphertext matching system, wherein the calculated distance or a comparison result between the distance and a predetermined threshold is output as a matching result. A storage device;
The storage device
A storage unit;
An identifier giving unit that gives an identifier to the encrypted registration information received from the registration requesting device;
A registration data generating unit that stores registration data consisting of a pair of the encrypted registration information and the identifier in the storage unit;
In response to a registration data request from the verification assisting device, out of the registration data stored in the storage unit, encrypted registration information that is paired with an identifier included in the registration data request, A registered data search unit to be sent to the verification assisting device;
With
The verification assisting device is:
A registration data request included in the authentication request received from the authentication requesting device and including an authentication identifier corresponding to the authentication information is sent to the storage device;
Receiving the encrypted registration information corresponding to the authentication identifier from the storage device;
Calculating a ciphertext of a distance between the registration information and the authentication information based on the response received from the authentication requesting device, the challenge assistance, and the encrypted registration information received from the storage device. The ciphertext matching system according to claim 1, wherein: A storage device;
The storage device
A storage unit;
An identifier giving unit that gives an identifier to the encrypted registration information received from the registration requesting device;
A registration data generating unit for storing in the storage unit registration data consisting of a set of the identifier and the encrypted registration information;
With
In response to a registration data request from the verification assisting device, one or a plurality of registered data stored in the storage unit is transmitted to the verification assisting device, part or all of the registration data,
The verification assisting device is:
Receiving one or more registration data from the storage device;
For each registration data received from the storage device,
Based on the response received from the authentication requesting device, the challenge, and the encrypted registration information included in the registration data, a ciphertext of a distance between the encrypted registration information and the authentication information is calculated. ,
About the registration data, a set of the ciphertext of the calculated distance between the registration information and the authentication information and an identifier included in the registration data is used as verification data,
Sending one or more of the generated verification data to the verification device;
The verification device includes:
Receiving one or more verification data from the verification assistant device;
About the verification data,
Decrypting the ciphertext of the distance between the registration information and the authentication information contained in the verification data using the decryption key to calculate the distance;
A comparison result between the calculated distance and a predetermined threshold value, or a set of the calculated distance and an identifier included in the verification data is set as a verification result, and the verification result is output. The ciphertext matching system according to claim 1. The registration request device includes:
Generates an L-1 degree polynomial from the registration information, which is a numeric vector, with the i-th component of the registration information (where i is a non-negative integer less than L-1 and L is a positive integer greater than 2) as a coefficient of the i-th term. Then, the authentication requesting device converts the inverse element of the i-th component (where i is a non-negative integer less than or equal to L-1) of the authentication information, which is a numerical vector, into a term of Ni order (N is a positive integer greater than L). Generate an Nth order polynomial with coefficients of, or
The registration requesting device uses the inverse element of the i-th component (where i is a non-negative integer less than or equal to L-1) of the registration information, which is a numeric vector, in terms of the order of Ni order (N is a positive integer greater than L). An N-th order polynomial is generated as a coefficient, and the authentication requesting apparatus generates an i-th component of authentication information that is a numerical vector (where i is a non-negative integer not greater than L-1 and L is a positive integer not less than 2). The ciphertext matching system according to claim 1, wherein an L−1 order polynomial is generated as a coefficient of the term. A ciphertext verification method by at least one computer,
Calculate a pair of encryption key and decryption key of a homomorphic encryption method capable of polynomial operation, and publish the encryption key,
When registering registration information,
Registration information that is a numeric vector is polynomialized,
The registration information that has been polynomialized is encrypted using the encryption key,
In the auxiliary verification process,
When receiving an authentication request, one coefficient and its order are selected at random,
Generating a polynomial in which the coefficients other than the coefficient of the order are 0;
Sending a challenge consisting of ciphertext encrypted using the encryption key to the request source of the authentication request, the polynomial,
In the authentication request source,
The authentication information, which is a numeric vector, is polynomialized,
Based on the authentication information that has been polynomialized and the challenge from the verification auxiliary process, the encryption of the product of the authentication information that has been polynomialized and the polynomial that was used to generate the challenge, using the encryption key Calculate the sentence,
The ciphertext of the product of the polynomial authentication information and the polynomial used to generate the challenge is sent as the response to the verification assisting process,
In the verification auxiliary process,
When receiving a response from the authentication request source, based on the response, challenge assistance consisting of the one coefficient and its order, and the encrypted registration information, the registration information is Calculate ciphertext of authentication information distance,
Send the ciphertext of the distance between the registration information and the authentication information to the verification destination,
In the verification destination,
The encrypted text of the distance between the registration information and the authentication information received from the verification assisting process is decrypted using the decryption key to calculate the distance,
A ciphertext matching method, characterized by outputting the calculated distance or a comparison result between the distance and a predetermined threshold value as a matching result. A verification assisting device that acquires the encryption key published by a verification device that calculates a pair of encryption key and decryption key of a homomorphic encryption method capable of polynomial operation,
When an authentication request is received from the authentication requesting device, one coefficient and its order are selected at random, a polynomial with coefficients other than the order coefficient set to 0 is generated, and the polynomial is encrypted using the encryption key. A challenge generation unit that sends a challenge made of encrypted ciphertext to the authentication requesting device;
The authentication information, which is a numerical vector, is polynomialized, and based on the challenge, a ciphertext of a product of the authentication information polynomialized and the polynomial used to generate the challenge is calculated using the encryption key, and the polynomial The ciphertext of the product of the authentication information and the polynomial used to generate the challenge is received as a response from the authentication requesting device,
Based on the response, challenge assistance consisting of the one coefficient and its degree, and registration information encrypted in a registration request device and stored in a storage device, using the encryption key, A query generation unit that calculates a ciphertext of a distance between the registration information and the authentication information, and sends the ciphertext of the distance between the registration information and the authentication information to a verification device;
With
In the verification device, the distance between the registration information and the authentication information is decrypted using the decryption key to calculate the distance, and the calculated distance or the distance and a predetermined threshold value are calculated. A collation auxiliary device that outputs a comparison result as a collation result. An authentication requesting device that obtains the encryption key from a verification device that calculates a pair of encryption key and decryption key of a homomorphic encryption method capable of polynomial operation and publishes the encryption key,
An authentication information extraction unit that polynomializes authentication information that is a numerical vector;
An authentication request generator for generating an authentication request to be transmitted to the verification auxiliary device;
With
Upon receipt of the authentication request, one coefficient and its order are selected at random, a polynomial with a coefficient other than the order coefficient as 0 is generated, and the polynomial is encrypted using the encryption key. Receiving the challenge from the verification assisting device that sends a challenge consisting of a sentence to the authentication requesting device;
Based on the authentication information polynomialized by the authentication request generation unit and the challenge, encryption of the product of the authentication information polynomialized using the encryption key and the polynomial used to generate the challenge A response generation unit that calculates a sentence and sends the ciphertext of a product of the authentication information that has been polynomialized and the polynomial used to generate the challenge as a response to the verification assistant device;
The verification assisting device uses the encryption key based on the response, challenge assistance consisting of the one coefficient and its order, and polynomialized registration information encrypted by the registration requesting device. An authentication requesting device that calculates a ciphertext of a distance between registration information and authentication information, and sends the ciphertext of a distance between the registration information and the authentication information to a verification device. When an authentication request is received from the authentication requesting device, one coefficient and its order are selected at random, a polynomial in which coefficients other than the order coefficient are set to 0 is generated, and the polynomial is encrypted using an encryption key When the challenge composed of ciphertext is sent to the authentication requesting device and a response is received from the authentication requesting device, the response, challenge assistance consisting of the one coefficient and its order, and the registration requesting device are encrypted and stored. A verification device connected to a verification assisting device that calculates a ciphertext of the distance between the registration information and the authentication information using the encryption key based on the polynomialized registration information stored in the device. And
A key generation unit that calculates a pair of the encryption key and the decryption key of a homomorphic encryption method capable of polynomial operation and publishes the encryption key;
When the ciphertext of the distance between the registration information and the authentication information is received from the verification assisting device, the ciphertext of the distance between the registration information and the authentication information is decrypted using the decryption key to calculate the distance A query validator;
A collation result generation unit that outputs the calculated distance or a comparison result between the distance and a predetermined threshold as a collation result;
Verification device with A computer that constitutes a verification assisting device connected to a verification device connected to an authentication requesting device connected to a verification device that calculates a pair of encryption keys and decryption keys of a homomorphic encryption method capable of polynomial operation and discloses the encryption key,
Upon receiving an authentication request from the authentication requesting device, one coefficient and its order are randomly selected,
Generating a polynomial in which the coefficients other than the coefficient of the order are 0;
A process of sending a challenge consisting of a ciphertext obtained by encrypting the polynomial using the encryption key to the authentication requesting device;
The authentication information, which is a numerical vector, is polynomialized, and based on the challenge, a ciphertext of a product of the authentication information polynomialized and the polynomial used to generate the challenge is calculated using the encryption key, and the polynomial Processing to receive a response from the authentication requesting device that outputs the ciphertext of the product of the authentication information and the polynomial used to generate the challenge as a response;
Upon receiving a response from the authentication requesting device, the response, challenge assistance consisting of the one coefficient and its order, and polynomial registration information encrypted by the registration requesting device and stored in the storage device, Based on the encryption key, calculating a ciphertext of the distance between the registration information and the authentication information, and sending the ciphertext of the distance between the registration information and the authentication information to the verification device;
A program that executes Obtain an encryption key published by a verification device that calculates a pair of encryption key and decryption key of a homomorphic encryption method capable of polynomial operation,
Upon receipt of the authentication request, one coefficient and its order are selected at random, a polynomial in which a coefficient other than the coefficient of the order is 0 is generated, and the polynomial is encrypted using the encryption key. To the authentication requesting device, the response received from the authentication requesting device, challenge assistance consisting of the one coefficient and its order, and the polynomialized registration information encrypted by the registration requesting device. Based on the encryption key, the ciphertext of the distance between the registration information and the authentication information is calculated, and the ciphertext of the distance between the registration information and the authentication information is connected to a verification auxiliary device that sends the ciphertext to the verification device A computer constituting the authentication requesting device,
Processing to generate the authentication request and send it to the verification assistant device;
Receiving a challenge from the verification assisting device;
The authentication information that is a numerical vector is polynomialized, and the authentication information that is polynomialized using the encryption key based on the authentication information that is polynomialized and the challenge received from the verification auxiliary device, and generation of the challenge Calculate the ciphertext of the product with the polynomial used in
A process of sending the ciphertext of the product of the authentication information polynomialized and the polynomial used to generate the challenge as the response to the verification assisting device;
A program that executes

Images