Secret data matching device, computer-readable recording medium storing program for updating secret data, and secret data updating method

A secret data matching device includes a memory unit for storing a first secret vector obtained by concealing a first data set and a key data using a determination matrix; an obtaining unit for obtaining a second secret vector by concealing a second data set using the determination matrix; a calculating unit for calculating a residue vector which is a residue when the determination matrix is a modulus, from a difference between the first and second secret vectors; a determination unit for determining whether the first and second data sets are approximate based on the residue vector; an extracting unit for extracting the key data from the residue vector when the first data set and the second data set are approximate; a creating unit for generating a third secret vector by combining the key data and the second secret vector; and a storing unit for storing the third secret vector.

CROSS-REFERENCE TO RELATED APPLICATION

This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2014-133046, filed on Jun. 27, 2014, the entire contents of which are incorporated herein by reference.

FIELD

The embodiments discussed herein are relate to a secret data matching device, a computer-readable recording medium storing program for updating secret data, and a secret data updating method.

BACKGROUND

Biometric authentication is a technique for enabling individual authentication using information about the physical characteristics and the behavioral characteristics of a human. Human physical characteristics include fingerprints, veins, irises, and the face for example. Behavioral characteristics include handwriting and gait for example. Biometric information called a template is obtained beforehand and authentication is carried out by comparing the obtained biometric information and information obtained by a sensor during matching.

Recently, a biometric authentication technique has been seen in which a template that has undergone some type of conversion is stored in a database and used in comparison without recovering, during the matching, the original template obtained. This biometric authentication technique is called “template protection-type biometric authentication”. A system that uses this template protection-type biometric authentication technique does not permit the use of a leaked template and is able to inhibit access to a leaked template by changing the conversion method when a converted template has been leaked.

A template protecting method called key binding is known among the template protection-type biometric authentication techniques. The key binding method is a method for protecting a template and a key unique to a user by binding the template that indicates the biometric information and the key. When registering biometric information with the key binding method, the user inputs the biometric information and the user's unique key and a server registers the information, as a secure template in a database, in which the biometric information and the key are bound. When matching the biometric information, the user inputs the biometric information and the server matches the input biometric information and the secure template and extracts the user's unique key when the information and the secure template are near enough.

A technique in which the key binding method is achieved through lattice element adding is known as one technique for implementing the key binding method (see Yuka SUGIMURA, Masaya YASUDA, Shigefumi YAMADA, Narishige ABE, Takashi SHINZAKI, “A proposal of key binding technology using lattice masking”, ISEC-IEICE Technical Report, Information and Communication system security, vol. 113, no. 135, pp. 297-304). With this technique, a secure template that differs according to each system may be created from the same biometric information and key and unconcealed biometric information does not have to be transmitted to the server during registration and during matching.

Another technique for implementing the key binding method is known that involves methods such as fuzzy commitment or fuzzy vault that make use of an error-correcting code technique. Fuzzy commitment and fuzzy vault are known to share a common portion of auxiliary information created from the template and the user's unique key for the same biometric information. Fuzzy commitment and fuzzy vault are known to involve transmitting unconcealed biometric information to the server during registration and during matching.

SUMMARY

According to an aspect of the invention, a secret data matching device includes a memory unit configured to store a first secret vector obtained by concealing a first data set and a key data using a first linear combination and a first random number, the first linear combination being composed of row vectors in a determination matrix which is generated by attaching a random number vector as a last column to a matrix, the matrix including diagonal elements of a threshold for determining whether two sets of data are approximate and a threshold related to the key data; an obtaining unit configured to obtain a second secret vector obtained by concealing a second data set using a second linear combination of the row vectors of the determination matrix and a second random number; a calculating unit configured to calculate a residue vector which is a residue when the determination matrix is a modulus, from a difference between the first secret vector stored in the memory unit and the second secret vector obtained by the obtaining unit; a determination unit configured to determine whether the first data set and the second data set are approximate based on the residue vector calculated by the calculating unit; an extracting unit configured to extract the key data from the residue vector when the first data set and the second data set are determined as approximate as a result of the determination by the determination unit; a creating unit configured to generate a third secret vector by adding the key data extracted by the extracting unit to the second secret vector obtained by the obtaining unit; and a storing unit configured to store the third secret vector created by the creating unit in the memory unit.

DESCRIPTION OF EMBODIMENTS

Biometric information proper to an individual and with few changes in the characteristics is selected as the biometric information to be used for biometric authentication. However, in general, the level of similarity between the biometric information used during the matching and the template registered at first gradually decreases over time. This decrease occurs due to long-term changes of the physical characteristics and the behavioral characteristics. This decrease may also occur due to operation habituation on the device used for obtaining the physical characteristics or the behavioral characteristics during matching. In order not to decrease similarity in the level, the template is updated at fixed periods or in response to indications of a decrease in the level of similarity. Methods for updating the template include a method for repeating the procedure used during first registration.

However, there is a problem in that the biometric information is not be updated securely or easily in the conventional techniques for implementing the key binding method.

For example, when conducting the method for repeating the procedure used in the first registration, the server is unable to easily update the biometric information because the user proceeds to a location dedicated to registering the biometric information and repeats the procedures for obtaining the biometric information at a fixed period or whenever there is an indication that the level of similarity has decreased.

Fuzzy commitment and fuzzy vault involve transmitting unconcealed biometric information to the server during registration and thus the server is unable to update the biometric information securely.

Although unconcealed biometric information is not transmitted to the server during registration or matching in the key binding method using lattice element adding, the server is unable to update the biometric information easily because the procedures from the first registration are repeated.

The above problem is not limited to updating biometric information and the same problem occurs when updating numerical information such as position information or confidential information.

Accordingly, it is desired to securely and easily update biometric information with the key binding method with respect to the template protection-type biometric authentication technique.

Hereinafter follows an explanation of embodiments of a secret data matching device, a secret data updating program, and a secret data updating method disclosed herein with reference to the drawings. The secret data matching device uses the key binding method among the template protection-type biometric authentication techniques. The present disclosure is not limited by the embodiments disclosed herein.

(Configuration of Secret Data Matching System)

FIG. 1is a view for explaining an example of a functional configuration of a secret data matching system according to a first embodiment. As illustrated inFIG. 1, a secret data matching system9includes client terminals1,2and a secret data matching device3. A database330is included in the secret data matching device3. The secret data matching device3and the client terminals1and2are connected over a network.

The secret data matching system9conceals a client's biometric data and a client's characteristic key data based on special random numbers (lattice element) called lattice masking and registers in the database330first secret data which is obtained by the concealing. When the client requests the matching of the biometric data, the secret data matching system9conceals the biometric data to be matched based on a different lattice element to obtain second secret data. The secret data matching system9determines whether the biometric data corresponding to the first secret data and the biometric data corresponding to the second secret data are approximate by applying a mapping specific to lattice theory to a difference between the first secret data and the second secret data. When the both biometric data are determined to be approximate, the secret data matching system9extracts the key data from the first secret data and creates third secret data by adding together the extracted key data and the second secret data used during authentication. The secret data matching system9then registers the created third secret data in the database330in place of the first secret data. That is, the secret data matching system9conceals the biometric information of a client requested to be matched to obtain secret data, and updates and registers the first secret data using the obtained secret data. For ease of explanation in the embodiment, the client terminal1represents the terminal of the client registering the biometric data, and the client terminal2represents the terminal requesting the matching of the biometric data. The client terminal1may be present as a plurality of terminals. The client terminal2may be present as a plurality of terminals.

Details of updating the secret data in which the biometric data of the client and the key data unique to the client are concealed in the secret data matching system9will be explained hereinbelow.

The client terminal1includes a registration requesting unit11and a secret data creating unit12. A key112is represented by numerical values for example in the embodiments.

The registration requesting unit11issues a request to the secret data matching device3to register biometric data111and the key112. For example, the registration requesting unit11receives the biometric data111and the key112from an external terminal. The registration requesting unit11then issues a request to the secret data matching device3for registration of the received biometric data111and the key112. The external terminal may be a terminal coupled over the network.

The biometric data111is data of the physical characteristics or the behavioral characteristics of the client. Fingerprints, veins, irises, and the face are examples of physical characteristic data. Handwriting and gait are examples of behavioral characteristic data. In the embodiment, the biometric data111is represented by a vector having components of the n-dimension. The key112is key data that the client desires to register with the biometric data. A key112is represented by numerical values for example in the embodiments.

The registration requesting unit11receives from the secret data matching device3a linear combination (lattice element) corresponding to an approximate determination matrix331described below as a response to the registration request, and outputs the received lattice element to the secret data creating unit12. The registration requesting unit11receives, from the secret data creating unit12, the secret data in which the biometric data111and the key112are concealed and issues a request to the secret data matching device3to register the secret data.

The secret data creating unit12creates secret data in which the biometric data111and the key112are concealed.

For example, the secret data creating unit12creates a (n+2)-dimensional vector in which “0” is attached as the last component of the combination data of the biometric data111and the key112with regard to the biometric data111and the key112. That is, the secret data creating unit12creates the (n+2)-dimensional vector by attaching a one dimensional component of the key112and “0” as a (n+2)nd component to the n-dimensional component of the biometric data111. As an example, T is assumed to indicate the n-dimensional component of the biometric data111and K is assumed to indicate the one dimensional component of the key112. As a result, the secret data creating unit12creates (T, K, 0) as the (n+2)-dimensional vector.

Obtaining the linear combination (lattice element) from the registration requesting unit11, the secret data creating unit12creates a random number. The secret data creating unit12creates a secret vector in which the created (n+2)-dimensional vector is added to the product of the linear combination (lattice element) and the random number. As an example, when the random number is r1and the lattice element is b1, the secret vector is represented by (T, K, 0)+r1×b1. The secret data creating unit12then outputs the created secret vector to the registration requesting unit11as the secret data.

The client terminal2includes a matching requesting unit21and a secret data creating unit22.

The matching requesting unit21issues a request to the secret data matching device3to match the biometric data. The biometric data to be matched is matching data211. In the embodiments, the matching data211is represented by a vector having an n-dimensional component. The matching requesting unit21receives from the secret data matching device3the linear combination (lattice element) corresponding to the approximate determination matrix331described below as a response to the matching request, and outputs the received lattice element to the secret data creating unit22. Receiving the secret data in which the biometric data211is concealed from the secret data creating unit22, the matching requesting unit21issues a request to the secret data matching device3to match the secret data. The lattice element received from the secret data matching device3is different from the lattice element received by the registration requesting unit11in the client terminal1during registration.

The secret data creating unit22creates the secret data in which the biometric data211is concealed.

For example, the secret data creating unit22creates an (n+2)-dimensional vector in which “0” is attached as the last component and as the component before the last component in the matching data211. That is, the secret data creating unit22creates an (n+2)-dimensional vector in which “0” is attached to the n-dimension component of the matching data211as the (n+1)st component and the (n+2)nd component. As an example, the matching data211is assumed to be Q which indicates the n-dimensional component. As a result, the secret data creating unit22creates (Q, 0, 0) as the (n+2)-dimensional vector.

The secret data creating unit22obtains the linear combination (lattice element) from the matching requesting unit21to create a random number. The secret data creating unit22then creates a secret vector as a secret data by adding the created (n+2)-dimensional vector to the product of the linear combination (lattice element) and the random number. As an example, when the random number is r2and the lattice element is b2, the secret vector would be represented as (Q, 0, 0)+r2×b2. The secret data creating unit22then outputs the created secret vector to the matching requesting unit21as the secret data. While the method for creating the random number may involve the use of any method, the various parameters are preferably different so that the random numbers created for the client terminals1and2are not the same.

The secret data matching device3includes a registration unit31, an matching determining unit32, and a storage unit33. The registration unit31creates the belowmentioned approximate determination matrix331and registers the created approximate determination matrix in the database330of the storage unit33. The registration unit31registers the secret data subject to the registration request in the database330of the storage unit33. The matching determining unit32matches the secret data in which the matching data subject to the matching request is concealed and the registered secret data to determine whether the data are approximate or not. When it is determined that the data are approximate, the matching determining unit32uses the secret data in which the matching data subject to the matching request is concealed to update the previously registered secret data.

The storage unit33is a storage device such as a hard disk or an optical disk. The storage unit33may be a semiconductor memory that allows data to be rewritten such as a random access memory (RAM), a read-only memory (ROM), a flash memory, a non-volatile static random access memory (NVSRAM).

The storage unit33stores the database330. The approximate determination matrix331and secret data332are stored in the database330. A single piece of the secret data332is stored for each user. The approximate determination matrix331is registered by the registration unit31as described below. The secret data332is registered by the registration unit31as described below and is updated by the matching determining unit32as described below. Details of the approximate determination matrix331are described below.

The registration unit31includes a random number creating unit311, an approximate determination matrix creating unit312, an approximate determination matrix registration unit313, and a secret data registration unit314.

The random number creating unit311creates random numbers to be used for creating the approximate determination matrix331and outputs the created random numbers to the approximate determination matrix creating unit312. The random numbers used for creating the approximate determination matrix331are a random numbers that are attached respectively as the last column and the next to the final column of a square matrix which indicates a threshold set of an approximation range when creating the approximate determination matrix331. The threshold set of the approximation range is a numerical value set indicated by the client as the approximation range and each value in the threshold set represents information which represents length of each of the dimensional directions as vectors of the approximation range. For example, when the threshold set of the approximation range is “e, f, g,” the random number creating unit311creates random numbers “h, i, j” that satisfy e/2≧h, f/2≧i, and g/2≧j and optional random numbers “k, l”.

The approximate determination matrix creating unit312creates the approximate determination matrix331for performing the approximation determination. The created approximate determination matrix331is created in such a way so as to be different for each system that contains a secret data matching device3.

For example, the approximate determination matrix creating unit312creates a diagonal matrix in which values in the threshold set indicating the approximation range are set as diagonal components and the other components are set as “0”. As an example, when the biometric data subject to the determination is information having an n number of components, that is, when the biometric data111is the n-dimensional information, the approximate determination matrix creating unit312creates the diagonal matrix of n×n. The approximate determination matrix creating unit312then sets a threshold of the key112to an element of the (n+1) row and the (n+1) column. The threshold of the key112is information that indicates the allowable maximum value of the key set by the client.

The approximate determination matrix creating unit312creates a (n+2)×n matrix in which the next to last row and the last row in which all the elements are “0” are attached to the created n×n diagonal matrix. The approximate determination matrix creating unit312creates a random number vector having the number of components equal to n (number of rows in the diagonal matrix). The approximate determination matrix creating unit312creates a random number vector having the number of components which is equal to 2+the n number of columns of the diagonal matrix as the final row number. The random numbers created by the random number creating unit311are set as the components of the random number vector. The secret data matching device3creates a (n+2)×(n+2) square matrix in which the random number vector is attached as the approximate determination matrix331.

The approximate determination matrix registration unit313registers the approximate determination matrix331created by the approximate determination matrix creating unit312in the database330.

The approximate determination matrix331is explained with reference toFIG. 2.FIG. 2illustrates an example of an approximate determination matrix. An example in which the biometric data and the approximation range are expressed with 3-dimensional numerical values will be explained in the example inFIG. 2. As illustrated inFIG. 2, an approximate determination matrix V corresponding to the approximate determination matrix331is a matrix in which a key threshold and random number vectors are added to a matrix for approximate determination in the range indicated by the dotted line.

The matrix for approximate determination has thresholds, as diagonal elements, for specifying the lengths as the vectors in the dimensional directions of the approximation range. In the example inFIG. 2, the length as the vector in the X-axis direction of the approximation range is “20”, the length as the vector in the Y-axis direction is “10”, and the length as the vector in the Z-axis direction is “14”. That is, the matrix for approximate determination illustrated inFIG. 2is a matrix for determining whether the two sets of biometric data are included in the range of “±10” in the X-axis direction, “±5” in the Y-axis direction, and “±7” in the Z-axis direction.

“0, 0, 0” are attached to the fourth row for key padding. Moreover, “7, 4, 5, 20000” are attached to the fourth column as a combination of the random number vectors “7, 4, 5” and the key threshold “20000”. “0, 0, 0, 0” are attached to the fifth row which is the last row. The random number vectors “5, 3, −2, −42, 123” are attached to the fifth column which is the last column. While the approximation range is specified with 3-dimensional numerical values in the example inFIG. 2, the embodiment is not limited in this way and numerical values of any dimension may be used.

Returning toFIG. 1, the secret data registration unit314registers the secret data in the database330. The registered secret data corresponds to the template to be protected in the key binding method.

For example, when a request for registration is received form the client terminal1, the secret data registration unit314creates random numbers for the linear combination corresponding to the approximate determination matrix331. As an example, the secret data registration unit314obtains the row vectors v1, v2, . . . , vn+2each of which has the n+2 number of components corresponding to the approximate determination matrix331. The secret data registration unit314then selects suitable integers d1, d2, . . . , dn+2for the respective row vectors v1, v2, . . . , vn+2. The secret data registration unit314calculates n+2-dimensional vectors expressed by the sum of the products of the row vectors and the integers, that is by d1×v1+d2×v2+ . . . +dn+2×vn+2, as the linear combination. This linear combination is the “lattice element”. The secret data registration unit314selects different sets of the integers d1, d2, . . . , dn+2for each set of biometric data to calculate the linear combination which is the sum of the products of the selected sets of the integers and the row vectors of the approximate determination matrix331.

The secret data registration unit314further delivers the calculated linear combination, that is the lattice element, to the client terminal1as the response to the registration request. When the registration request for the secret data332is received from the client terminal1, the secret data registration unit314registers the secret data332subject to the registration request in the database330.

The matching determining unit32includes a matching request receiving unit321, a computing unit322, an approximate determination unit323, a key extracting unit324, an update secret data creating unit325, and a secret data updating unit326.

Upon receiving a matching request from the client terminal2, the matching request receiving unit321creates random numbers (lattice element) for the linear combination corresponding to the approximate determination matrix331. The creation of the random numbers for the linear combination is carried out in the same way as by the secret data registration unit314and therefore an explanation will be omitted. The lattice element created by the matching request receiving unit321is created so as to be different from the lattice element created by the secret data registration unit314during registration.

The matching request receiving unit321delivers the calculated linear combination, that is the lattice element, to the client terminal2as a response to the matching request. When a request is issued from the client terminal2for matching of the secret data in which the matching data211is concealed, the matching request receiving unit321outputs the secret data subject to the matching request to the computing unit322.

The computing unit322calculates a difference vector indicating the difference between the secret data332(secret vector) registered in the database330and the secret data in which the matching data211is concealed received from the client terminal2. The computing unit322then calculates the calculated difference vector to obtain a residue vector as the residue when the approximate determination matrix331is used as the modulus. As an example, when the difference vector is z and the approximate determination matrix331is V, the residue vector is expressed as “z mod V”. “z mod V” is equivalent to (z−[z×V−1]×V). “V−1” represents the inverse matrix of the matrix V. “[z×V−1]” represents a vector rounded to the nearest integer with respect to each dimension of the vector “z×V−1”. The computing unit322outputs the calculated residue vector to the approximate determination unit323.

When the last component of the residue vector is found to be “0” when determining whether the last component of the residue vector received from the computing unit322is “0” or not, the approximate determination unit323determines that the biometric data111of the registration side and the matching data211are approximate. When the last component of the residue vector is not “0”, the approximate determination unit323determines that the biometric data111of the registration side and the matching data211are not approximate.

When the biometric data111and the matching data211are determined as approximate, the key extracting unit324extracts the (n+1)st component in the residue vector as the key112unique to the user. The key extracting unit324then transmits the extracted key112to the client terminal that has requested the matching. When the biometric data111and the matching data211are determined not to be similar to each other, the key extracting unit324transmits the fact that the data are not approximate to the client terminal2, that is, the fact that the identification failed.

When the data is determined to be approximate, the update secret data creating unit325adds the key112extracted by the key extracting unit324to the secret data subject to the matching request to create secret data for updating. For example, the update secret data creating unit325adds n number of 0's and one 0 to the key112extracted by the key extracting unit324to create an expanded key vector (0, K, 0). The first 0 in the key vector represents the n-dimensional zero vector and the last 0 is a scalar. The update secret data creating unit325adds the key vector to the secret data subject to the matching request to create update secret data.

The secret data updating unit326stores the update secret data created by the update secret data creating unit325in the database330. That is, the secret data updating unit326registers the update secret data in the database330in place of the secret data332.

The theory of approximate determination executed by the matching determining unit32will be explained first. The approximate determination matrix331will be explained as approximate determination matrix V. The linear combination of v1, v2, . . . , vn+2each of which is a row vector in the approximate determination matrix V may be represented by a set L (lattice L) which has elements in a form of the linear combination d1×v1+d2×v2+ . . . +dn+2×vn+2of each row vector in the approximate determination matrix V. That is, the linear combination of the row vectors in the approximate determination matrix V correspond to any of the intersections on the lattice composed of the elements of the set L.

A secret vector H in which the dimensional biometric data T and a key K are concealed is expressed with the following formula (1) using the lattice element b1of the set L and a random number r1. (T, K, 0) is the (n+2)-dimensional vector in which the key K and “0” as the (n+2)nd component are added to the biometric data T.
H=(T,K,0)+r1×b1(1)

The secret vector H is created by the secret data creating unit12in the client terminal1. The created secret vector H is registered by the registration requesting unit11in the database330.

A secret vector H′ in which n-dimensional matching data Q is concealed is expressed with the following formula (2) using the lattice element b2of the set L and a random number r2. (Q, 0, 0) is the (n+2)-dimensional vector in which “0” as the (n+1)st component and the (n+2)nd component are added to the matching data Q. b2and b1are different.
H′=(Q,0,0)+r2×b2(2)

The secret vector H′ is created by the secret data creating unit22in the client terminal2. The created secret vector H′ is transmitted by the matching requesting unit21to the secret data matching device3.

In this case, a difference vector z between the secret vectors H and H′ is expressed by the following formula (3).
z=H−H′=(T−Q,K,0)+r1×b1−r2×b2(3)

Because the “r1×b1−r2×b2” in the difference vector z is the difference between the products each of which is product of the element of the set L and the random number, the “r1×b1−r2×b2” is included in the elements of the set L. That is, r1×b1−r2×b2corresponds to any of the intersections on the lattice composed of the elements of the set L. When the residue vector of the approximate determination matrix V is calculated from the difference vector z, “z mod V” corresponds to mapping the difference vector z on a fundamental domain P (L) defined by the set L. As a result, when the residue vector of the approximate determination matrix V is calculated from the difference vector z, r1×b1−r2×b2may be ignored. Accordingly, when “z mod V” is calculated, the lattice portion including portions of the difference vector z other than the end in the difference vector z may be ignored and only one lattice including the end of the difference vector z is mapped on the fundamental domain P (L). That is, “z mod V” is expressed by the following formula (4).
zmodV=(T−Q,K,0)modV(4)

When the vector (T−Q, K, 0) is included in the fundamental domain P (L), that is when the biometric data T and the matching data Q are approximate, z mod V=(T−Q, K, 0). As a result, the last component of “z mod V” has a very high probability of being “0” when the biometric data T and the matching data Q are approximate.

When the vector (T−Q, K, 0) is not included in the fundamental domain P (L), that is when the biometric data T and the matching data Q are not approximate, z mod V=(T−Q, K, 0)+b when an element of the lattice belonging to the set L is b. As a result, the last component of “z mod V” has a very high probability of being a number other than “0” when the biometric data T and the matching data Q are not approximate.

According to the theory of approximate determination, the matching determining unit32calculates the residue vector of the approximate determination matrix V from the difference between the secret vectors H and H′, and performs the approximate determination of the concealed biometric data based on the last component of the calculated residue vector. The matching determining unit32then extracts the key K from the secret vector H when the data is determined as approximate based on a result of the approximate determination. The matching determining unit32outputs the extracted key K to the client terminal that has requested the matching.

(Theory of Processing for Creating the Update Secret Data)

Next, the theory of the creation of the update secret data executed by the matching determining unit32will be explained. When the biometric data T and the matching data Q are approximate, the secret data matching device3has the key K unique to the user and the secret vector H′ (=(Q, 0, 0)+r2×b2) see formula (2)) in which the n-dimensional matching data is concealed. The matching determining unit32creates the (n+2)-dimensional key vector (0, K, 0) using the key K. The first 0 in the key vector represents the n-dimensional zero-vector (having the same data structure as the biometric data) and the last 0 is a scalar.

The matching determining unit32creates update secret data H1using the following formula (5) from the secret vector H′ and the key vector.
H1=H′+(0,K,0)  (5)

The following equation (6) is obtained when the above equation (5) is transformed.
H1={(Q,0,0)+r2×b2}+(0,K,0)=(Q,K,0)+r2×b2(6)

The Q, r2, and b2in formula (6) represent the matching data211, a random number, and the lattice element, respectively. The secret vector H (=(T, K, 0)+r1×b1) expressed in formula (1) is compared here with the secret vector H1(=(Q, K, 0)+r2×b2) expressed in formula (6). It may be seen that the secret vector H1is a secret vector created from Q which is the matching data211and from the key K unique to the user. Consequently, the update of the template in the key binding method may be performed by registering the secret vector H1as the secret data in place of the secret vector H in the database330. That is, the matching determining unit32registers the secret data of the matching data Q in place of the previously registered secret data332in the database330.

(Sequence of Registration Processing for Secret Data)

Next, a sequence of the registration processing for the secret data will be explained with reference toFIG. 3.FIG. 3illustrates a sequence of secret data registration processing. The biometric data111of the client is represented as T, the key112unique to the client is represented as K, the approximate determination matrix331is represented as V, and the secret vector is represented as H inFIG. 3.

The approximate determination matrix creating unit312in the secret data matching device3creates the approximate determination matrix V (step S11). The approximate determination matrix registration unit313then registers the created approximate determination matrix V in the database330(step S12).

The registration requesting unit11in the client terminal1obtains the registration information (step S13). The registration requesting unit11obtains the biometric data T and the key K as the registration information. The registration requesting unit11then issues a request to the secret data matching device3to register the biometric data T and the key K (step S14).

The secret data registration unit314that receives the registration request from the client terminal1in the secret data matching device3creates a random number lattice vector (step S15). The secret data registration unit314calculates the linear combination which is expressed by the sum of the products of the row vectors in the approximate determination matrix V and the appropriate integers. The calculated linear combination is the random number lattice vector b1and is the lattice element. The secret data registration unit314then transmits the calculated random number lattice vector (lattice element) b1to the client terminal1(step S16).

The secret data creating unit12in the client terminal1creates the registration information (step S17). The secret data creating unit12creates the vector (T, K, 0) in which “0” is added to the combined data (T, K) of the biometric data T and the key K.

The secret data creating unit12then conceals the registration information (step S18). The secret data creating unit12creates the secret vector H in which the created vector (T, K, 0) is added to the product of the random number lattice vector (lattice element) b1and the random number. When the random number is r1, the secret vector H is expressed by (T, K, 0)+r1×b1.

The registration requesting unit11transmits to the secret data matching device3the secret vector H in order to request the registration of the secret vector H which is the registration information concealed by the secret data creating unit12(step S19). As a result, the secret vector H is registered in the database330of the secret data matching device3.

(Sequence of Updating Processing for Secret Data)

Next, a sequence of the updating processing for the secret data will be explained with reference toFIG. 4.FIG. 4illustrates a sequence of secret data updating processing according to the first embodiment. The matching data211of the client is represented as Q, the key112unique to the client is represented as K, the approximate determination matrix331is represented as V, and the secret vector is represented as H and H′ inFIG. 4.

The matching requesting unit21in the client terminal2obtains the matching information (step S21). The matching requesting unit21obtains the matching data Q as the matching information. The matching requesting unit21then issues a request to the secret data matching device3for matching of the matching data Q (step S22).

The matching request receiving unit321in the secret data matching device3that received the matching request from the client terminal2obtains the approximate determination matrix V from the database330(step S23). The matching request receiving unit321creates the random number lattice vector (step S24). The matching request receiving unit321calculates the linear combination that is expressed by the sum of the products of the appropriate integers and the row vectors of the read approximate determination matrix V. The calculated linear combination is the random number lattice vector b2and is the lattice element. The matching request receiving unit321then transmits the calculated random number lattice vector (lattice element) b2to the client terminal2(step S25). b2and b1are different.

The computing unit322in the secret data matching device3obtains the secret vector H from the database330(step S28). The approximate determination unit323then uses the residue vector calculated from the difference vector of the secret vector H′ for which matching is requested and the obtained secret vector H to perform the matching processing while the vectors T and Q are still concealed (step S29). The approximate determination unit323determines whether the last component of the residue vector is “0”. When the last component of the residue vector is “0”, the approximate determination unit323determines that the biometric data T that is the source of the registration and the matching data Q are approximate. When the last component of the residue vector is not “0”, the approximate determination unit323determines that the biometric data T that is the source of the registration and the matching data Q are not approximate.

When the data is determined to be approximate, the key extracting unit324extracts the key K unique to the user from the residue vector (step S30). The key extracting unit324then transmits the extracted key K to the client terminal2that requested the matching (step S31).

The update secret data creating unit325then creates the key vector for the update secret registration information from the key K extracted by the key extracting unit324(step S32). The update secret data creating unit325attaches n number of 0's and one 0 to the key K to create an expanded key vector (0, K, 0).

The secret data updating unit326transmits the update secret registration information created by the update secret data creating unit325to the database330(step S34). The secret data updating unit326discards the protected secret registration information (secret vector) H in the database330and registers alternatively the update secret registration information (secret vector) H1.

(Advantages of the First Embodiment)

According to the first embodiment, the secret data matching device3registers in the database330the first secret vector obtained by concealing the biometric data and the key based on a first random number and a first linear combination that uses the row vectors of the approximate determination matrix331. The secret data matching device3obtains the second secret vector obtained by concealing the matching data based on a second random number and a second linear combination that uses the row vectors of the approximate determination matrix331. The secret data matching device3then calculates the residue vector which is the residue obtained by applying the approximate determination matrix331as a modulus to the difference of the first secret vector and the second secret vector. The secret data matching device3determines whether the biometric data and the matching data are approximate based on the calculated residue vector and extracts the key from the residue vector when the biometric data and the matching data are approximate. The secret data matching device3adds the extracted key to the second secret vector obtained by concealing the matching data to create the third secret vector. The secret data matching device3registers the created third secret vector in the database330. As a result, the secret data matching device3may update securely and easily the biometric data in the key binding method. That is, the secret data matching device3obtains the second secret vector in which the biometric data used during the matching is concealed and thus may obtain securely the biometric data. The secret data matching device3uses the obtained second secret vector and the previously registered key to create and register secret vector in which the biometric data used during the matching is newly concealed. As a result, the secret data matching device3may update securely and easily the biometric data of the user.

According to the first embodiment, the secret data matching device3erases the first secret vector and adds the third secret vector. As a result, the secret data matching device3may update easily the most recent biometric data of the user.

The previous discussion examined a case in which the secret data332stored as one set of data per user is updated to the secret data in which the matching data is concealed during matching in the secret data matching device3according to the first embodiment. However, the secret data matching device3is not limited in this way, and a plurality of sets of the secret data332may be stored per one user and more secret data in which the matching data is concealed during matching may be added.

A case will be discussed in which the secret data matching device3in a second embodiment adds more secret data in which the matching data is concealed during matching so as to store a plurality of sets of the secret data332per one user.

(Configuration of Secret Data Authentication System)

FIG. 5is a view for explaining an example of a functional configuration of a secret data matching system according to the second embodiment. Configurations similar to those of the secret data matching system9illustrated inFIG. 1are illustrated with the same reference numerals, and explanations of duplicated configurations and operations will be omitted. The first and second embodiments differ from each other due to changes of a computing unit322A, an approximate determination unit323A, a key extracting unit324A, and a secret data updating unit326A. The first and second embodiments also differ due to the fact that a plurality of sets of secret data332is stored per one user. As an example, the secret data332is stored as h (where h is a natural number) number of sets per one user.

The computing unit322A calculates h number of difference vectors indicating the difference between the plurality of sets of secret data3321 to h(secret vectors) registered in the database330and the secret data of the concealed matching data211received from the client terminal2. The computing unit322A then calculates, from the calculated h number of difference vectors, h number of residue vectors which indicate the residues when the approximate determination matrix331is used as the modulus. As an example, when the difference vector is z1and the approximate determination matrix331is V, the residue vectors are expressed as “z1mod V” with regard to the secret data3321. The computing unit322A outputs the calculated h number of residue vectors to the approximate determination unit323A.

The approximate determination unit323A determines whether the last components of the h number of residue vectors received from the computing unit322A are “0”. When any of the last components of the residue vectors are “0”, the approximate determination unit323A determines that the matching data211and the secret data1 to h332are approximate. When none of the last components of the residue vectors are “0”, the approximate determination unit323A determines that the matching data211and the secret data332are not approximate.

When the matching data211and the secret data332are determined to be approximate each other, the key extracting unit324A extracts the (n+1)st components of the residue vectors determined as having “0” as the last component thereof as the key112unique to the user. The key extracting unit324A then transmits the extracted key112to the client terminal2that has requested the matching. When the matching data211and the secret data332are determined not to be approximate each other, the key extracting unit324A transmits the fact that the data are not approximate (the fact that the authentication failed) to the client terminal2.

When the data is determined to be approximate, the update secret data creating unit325adds the key112extracted by the key extracting unit324A to the secret data subject to the matching request to create update secret data.

The secret data updating unit326A adds the update secret data created by the update secret data creating unit325with regard to the matching data211to the database330. That is, the secret data updating unit326A adds the update secret data in the database330as new secret data3321+1.

(Sequence of Updating Processing for Secret Data)

Next, a sequence of the updating processing for the secret data will be explained with reference toFIG. 6.FIG. 6illustrates a sequence of secret data updating processing according to the second embodiment. The matching data211of the client is represented as Q, the key112unique to the client is represented as K, the approximate determination matrix331is represented as V, and the secret vectors are represented as H′, H1 to h, h+1inFIG. 6.

The processing from when the client terminal2obtains the matching data Q as the matching information until the client terminal2creates the secret vector H′ in which the matching data Q is concealed as the secret matching information and transmits the secret vector H′ to the secret data matching device3(steps S21to S27) is the same as the processing discussed with reference toFIG. 4. Therefore further explanation will be omitted.

The computing unit322A in the secret data matching device3that receives the secret vector H′ from the client terminal2obtains the secret vectors H1, H2, . . . Hhfrom the database330(step S41). The secret data matching device3receives user identification data (ID), which is a user identifier, and the secret vector H′ from the client terminal2. The computing unit322A obtains the secret vectors H1, H2, . . . Hhcorresponding to the user ID from the database330.

The approximate determination unit323A then uses the h number of residue vectors calculated from the difference between the secret vector H′ for which matching is requested and the obtained secret vectors H1 to hto perform the matching processing while the vectors are still concealed (step S42). The approximate determination unit323A determines whether the last components of the h number of residue vectors are “0”. When any of the last components of the residue vectors are “0”, the approximate determination unit323A determines that the matching data Q and the secret vectors H1 to hare approximate. When none of the last components of the residue vectors are “0”, the approximate determination unit323A determines that the matching data Q and the secret vectors H1 to hare not approximate.

When the data is determined to be approximate, the key extracting unit324A extracts the key K unique to the user from any one of the residue vectors determined as having “0” as the last components thereof (step S43). The key extracting unit324A then transmits the extracted key K to the client terminal2that requested the matching (step S44).

The update secret data creating unit325then creates the key vector for the update secret registration information from the key K extracted by the key extracting unit324A (step S45). The update secret data creating unit325attaches n number of 0's and one 0 to the key K to create an expanded key vector (0, K, 0).

The secret data updating unit326A transmits the update secret registration information created by the update secret data creating unit325to the database330(step S47). The secret data updating unit326A adds the update secret registration information (secret vector) Hh+1to the database330in addition to the secret registration information (secret vectors) H1, H2, . . . , Hh.

(Advantages of the Second Embodiment)

According to the second embodiment, the secret data matching device3registers in the database330the first secret vector obtained by concealing the biometric data and the key based on a first random number and a first linear combination that uses the row vectors of the approximate determination matrix331. The secret data matching device3obtains the second secret vector obtained by concealing the matching data based on a second random number and a second linear combination that uses the row vectors of the approximate determination matrix331. The secret data matching device3then calculates the residue vector which is the residue obtained by applying the approximate determination matrix331as a modulus to the difference of the first secret vector and the second secret vector. The secret data matching device3determines whether the biometric data and the matching data are approximate based on the calculated residue vector and extracts the key from the residue vector when the biometric data and the matching data are approximate. The secret data matching device3adds the extracted key to the second secret vector obtained by concealing the matching data to create the third secret vector. The secret data matching device3further adds the created third secret vector to the database330. As a result, the secret data matching device3may securely and easily add the biometric data using the key binding method. Consequently, the secret data matching device3may use a plurality of secret vectors to carry out the approximate determination and further improve the accuracy of the approximate determination because the secret vectors in which the biometric data is concealed are also added.

The previous discussion examined a case in which the secret data332stored as one set of data per user is updated to the secret data in which the matching data is concealed during matching in the secret data matching device3according to the first embodiment. However, the secret data matching device3is not limited in this way, and secret data obtained by combining a plurality of sets of biometric data (including matching data) may be stored per one user and secret data in which the matching data is concealed during matching may be combined and the combined secret data may be updated.

Accordingly, a case will be explained in which the secret data matching device3according to a third embodiment stores secret data obtained by combining a plurality of sets of secret data per one user, and then combines the secret data in which the matching data is concealed during matching and updates the combined secret data.

(Configuration of Secret Data Matching System)

FIG. 7is a view for explaining an example of a functional configuration of a secret data matching system according to a third embodiment. Configurations similar to those of the secret data matching system9illustrated inFIG. 1are illustrated with the same reference numerals, and explanations of duplicated configurations and operations will be omitted. The first embodiment and the third embodiment differ due to changes of a computing unit322B, an approximate determination unit323B, an update secret data combining unit325B, and a secret data updating unit326B. The first and third embodiments differ due to the addition of a secret data composite number333to the storage unit33. The secret data332according to the third embodiment is secret data obtained by combining a plurality of sets of biometric data per one user. The secret data composite number333represents composite numbers of the biometric data.

The computing unit322B reads out the secret data332(secret vector) and the secret data composite number333from the database330. The computing unit322B calculates a difference vector indicating the difference between the read secret data332(secret vector) and the secret data of the concealed matching data211received from the client terminal2. The computing unit322B calculates a difference vector zcindicating the difference between the secret data332(secret vector) and the secret data of the concealed matching data211received from the client terminal2using the following formula (7). Hc represents the secret vector indicating the secret data332and h represents the secret data composite number333. H′ is the secret vector indicating the secret data in which the matching data211is concealed.
zc=Hc−h×H′(7)

The h is multiplied by H′ because Hc is the secret vector indicating the secret data in which h number of sets of the biometric data is combined.

The computing unit322B then calculates a residue vector which is the residue obtained by applying the approximate determination matrix331as the modulus to the calculated difference vector. As an example, when the difference vector is zcand the approximate determination matrix331is V, the residue vector is expressed as “zcmod V”. “zcmod V” is equivalent to (zc−[zc×V−1]×V). “V−1” represents the inverse matrix of the matrix V. The computing unit322B outputs the calculated residue vector to the approximate determination unit323B.

When the last component of the residue vector is found to be “0” based on determination whether the last component of the residue vector received from the computing unit322B is “0” or not, the approximate determination unit323B determines that the combined biometric data and the matching data211are approximate. When the last component of the residue vector is not “0”, the approximate determination unit323B determines that the combined biometric data and the matching data211are not approximate.

When the combined biometric data and the matching data211are determined to be approximate, the key extracting unit324extracts the (n+1)st component of the residue vector as the key112unique to the user. The key extracting unit324then transmits the extracted key112to the client terminal that has requested the matching. When the combined biometric data and the matching data211are determined not to be approximate, the key extracting unit324transmits the fact that the data is not approximate (the fact that the authentication failed) to the client terminal2.

When the data is determined as approximate, the update secret data combining unit325B combines the secret data332and the secret data subject to the matching request to create the secret data for updating. As an example, the update secret data combining unit325B adds the secret data332to the secret data in which the matching data211received from the client terminal2is concealed, to create the update secret data, as indicated by the following formula (8). H′c represents a secret vector indicating the update secret data. H′ is the secret vector indicating the secret data in which the matching data211is concealed. Hc is the secret vector indicating the secret data332.
H′c=H′+Hc(8)

The secret data updating unit326B stores the update secret data created by the update secret data combining unit325B in the database330. That is, the secret data updating unit326B registers the update secret data in the database330in place of the secret data332. The secret data updating unit326B increments the number of the secret data composite number333by one.

The combining of the secret data executed by the matching determining unit32will be explained next. The secret data matching device3has the secret vector H′ (=(Q, 0, 0)+r2×b2, see formula (2)), in which the n-dimensional matching data Q is concealed and the secret data332. It is assumed that the contents of the secret vector Hc which indicates the secret data332are indicated by formula (9). That is, Hc is a secret vector in which the secret data having h number of sets of the biometric data concealed therein is combined. T1 to Th are vectors indicating the respective biometric data. K is the key unique to the client. b′ is the lattice element.
Hc=(T1+T2+ . . .Th,K,0)+b′(9)

Substituting the formula (9) and the formula (2) into formula (7), the difference vector zccalculated by the computing unit322B is expressed by formula (10).
zc=(T1+T2+ . . .Th−h×Q,K,0)+b′−h×r2×b2(10)

The computing unit322B establishes the difference vector of the difference between the totaled vectors indicating the h number of sets of biometric data and the vectors indicating the matching data multiplied h times, and thus enables the approximate determination unit323B to carry out the approximate determination in the same way as when the vectors are not combined (see formula (3)). Because b′−h×r2×b2corresponds to any intersection on the lattice, b′−h×r2×b2is ignored when the residue vector of the approximate determination matrix V from the difference vector zcis calculated.

The update secret vector H′c is expressed by formula (11) when the contents of H′ and the contents of Hc are substituted into formula (8).
H′c=(T1+T2+ . . .Th+Q,K,0)+r2×b2+b′(11)

Therefore, the update secret vector H′c becomes the secret vector which is a combination of the h+1 number of sets of the biometric data in which the matching data Q is added to the h number of sets of registered biometric data. The secret data updating unit326B registers the update secret vector H′c as the new secret data332whereby the secret data332may be updated.

(Sequence of Updating Processing for Secret Data)

Next, a sequence of the updating processing for the secret data will be explained with reference toFIG. 8.FIG. 8illustrates a sequence of secret data updating processing according to the third embodiment. The matching data211of the client is represented as Q, the key112unique to the client is represented as K, the approximate determination matrix331is represented as V, and the secret vectors are represented as H′ and Hc inFIG. 8. The secret data composite number333registered in the database330is represented as h.

The processing from when the client terminal2obtains the matching data Q as the matching information until the client terminal2creates the secret vector H′ in which the matching data Q is concealed as the secret matching information and transmits the secret vector H′ to the secret data matching device3(steps S21to S27) is the same as the processing discussed with reference toFIG. 4. Therefore further explanation will be omitted.

The computing unit322B in the secret data matching device3that receives the secret vector H′ from the client terminal2obtains the secret vector Hc and “h” which represents the secret data composite number333from the database330(step S51). The secret data matching device3receives user identification data (ID), which is a user identifier, and the secret vector H′ from the client terminal2. The computing unit322B obtains the secret vector Hc corresponding to the user ID and the “h” which indicates the secret data composite number333from the database330.

The approximate determination unit323B then uses the residue vector calculated from the difference vector of the secret vector H′ for which matching is requested and the obtained secret vector Hc to perform the matching processing while the vectors are still concealed (step S52). The approximate determination unit323B determines whether the last component of the residue vector is “0”. When the last component of the residue vector is “0”, the approximate determination unit323B determines that the combined biometric data and the matching data Q are approximate. When the last component of the residue vector is not “0”, the approximate determination unit323B determines that the combined biometric data and the matching data Q are not approximate.

When the data is determined to be approximate, the key extracting unit324extracts the key K unique to the user from the residue vector (step S53). The key extracting unit324then transmits the extracted key K to the client terminal2that requested the matching (step S54).

The secret data updating unit326B then transmits the update secret registration information created by the update secret data combining unit325B to the database330(step S57). The secret data updating unit326B discards the secret registration information (secret vector) Hc held in the database330and registers alternatively the update secret registration information (secret vector) H′c. The secret data updating unit326B increments the secret data composite number333to h+1.

(Advantages of the Third Embodiment)

According to the third embodiment, the secret data matching device3carries out the following processing when the combined biometric data and the matching data211are determined to be approximate. That is, the secret data matching device3combines the secret data332in which the combined biometric data and the matching data211subject to the matching request, to create the update secret data. The secret data matching device3adds the created update secret data to the database330and erases the secret data332. According to this configuration, the secret data matching device3registers the update secret data obtained by combining the secret data332and the secret data in which the matching data211is concealed, in place of the previously registered secret data332, and thus the biometric data may be updated securely and easily. As a result, the secret data matching device3holds the combined data of the plurality of sets of matching data that had been successfully updated in the past as the secret data, and the secret data matching device3may bring improvement in accuracy similar to the improved approximate determination carried out by the matching of one set of the secret data.

When it is determined that the biometric data111from the registration and the matching data211are approximate in the embodiments, the key extracting unit324in the secret data matching device3extracts the key112unique to the user from the residue vector and transmits the key112to the client terminal2. The update secret data creating unit325is described as adding the extracted key112to the secret data subject to the matching request to create the update secret data. However, the update secret data creating unit325may switch to the processing to create the update secret data at a predetermined timing. The predetermined timing, for example, may be a timing after a fixed period has passed or when a decrease in the level of similarity is detected. As an example, the update secret data creating unit325determines whether the predetermined timing has been detected when the data is determined as approximate. When the predetermined timing is detected, the update secret data creating unit325adds the key112extracted by the key extracting unit324to the secret data subject to the matching request to create secret data for updating. The secret data for updating corresponds to the template to be protected in the key binding method. As a result, the secret data matching device3is able to further inhibit a decrease over time in the level of similarity between the biometric information obtained during matching and the registered template.

FIG. 9illustrates the advantage of template updating. The positions on apparatuses for obtaining specific biometric information (e.g., fingerprints) to be used in the biometric authentication are represented by the numbers 1, 2, and 3. A decrease in the level of similarity between the obtained specific biometric information and the initially registered template is represented along with the passage of time. This occurs due to long-term changes of the biometric information itself or due to operation habituation by the user on the apparatuses for obtaining the biometric information. When the decrease in the level of similarity is detected, the secret data matching device3updates the initially registered template to a new template. While the level of similarity between the obtained specific biometric information and the new template increases, the level of similarity will decrease along with the passage of time. Thus, when a decrease in the level of similarity is detected, the secret data matching device3is able to inhibit a reduction in the level of similarity by updating the new template to an even newer template.

The secret data matching device3has been explained in the embodiments as determining whether the biometric data111from the registration and the matching data211are approximate by determining whether the last component of the residue vector created during the matching is “0”. However, the secret data matching device3is not limited to the explained determination. The secret data matching device3may also determine whether the biometric data111from the registration and the matching data211are approximate by determining whether a plurality of components of the residue vector is “0”.

For example, when the biometric data subject to the determination is information having n number of components, that is, when the biometric data111is information of the n-dimension, the approximate determination matrix creating unit312creates a diagonal matrix of n×n. The approximate determination matrix creating unit312then attaches a row vector as a (n+1)st row vector, of which each component is “0”, to the n×n diagonal matrix. The approximate determination matrix creating unit312attaches a column vector formed by combining an n-dimensional random number vector and the key112threshold, to the (n+1)st column. The approximate determination matrix creating unit312then attaches a row vector as a (n+2)nd row vector, of which each component is “0”, to the created (n+1)×(n+1) matrix. The approximate determination matrix creating unit312creates the matrix (n+2)×(n+2) in which the n+2-dimensional random number vector is attached to the (n+2)th column.

The approximate determination matrix creating unit312then attaches a row vector as a (n+3)rd row vector, of which each component is “0”, to the (n+2)×(n+2) matrix. The approximate determination matrix creating unit312may create the approximate determination matrix331of (n+3)×(n+3) in which the (n+3)-dimensional random number vector is attached to the (n+3)th column.

As a result, the secret data matching device3calculates the (n+3)-dimensional residue vector using the approximate determination matrix331as the modulus by carrying out the same processing as in the embodiments. The secret data matching device3is able to carry out the approximate determination by determining whether all of the components from the (n+2)nd dimension to the (n+3)rd dimension of the residue vector are “0”. As a result, the secret data matching device3is able to improve the accuracy of the approximate determination. Similarly, the approximate determination matrix creating unit312is able to further improve the accuracy of the approximate determination by creating the approximate determination matrix331of (n+m)×(n+m) (where m is a natural number larger than 3).

The secret data matching device3may also combine as appropriate the methods described in the first to third embodiments. For example, the secret data matching device3may substitute the secret data created by the update secret data creating unit325with any of the secret data among the held plurality of sets of the secret data3321 to hwhile holding the plurality of sets of the secret data3321 to haccording to the second embodiment. The secret data matching device3may hold both the combined secret data332according to the third embodiment and the uncombined secret data332according to the first embodiment and use either one or both for identification as appropriate.

The secret data matching device3in the embodiments is described as using approximate determination of the biometric data111. However, the secret data matching device3is not limited in this way and may use secret similarity determination between confidential documents. For example, the client terminal1extracts text or a document portion having characteristics from the confidential document and creates a feature quantity vector indicating the feature quantity of the extracted portion. The client terminal1then creates the secret vector in which the created feature quantity vector and a key are concealed and registers the secret vector in the database330of the secret data matching device3by carrying out the same processing as in the embodiments. The secret data matching device3may authenticate the registered secret vector and the secret vector to be authenticated in which the feature quantity vector created by the client terminal2is concealed, by carrying out the same processing as in the embodiments.

The secret data matching device3may be realized by installing the functions such as the abovementioned registration unit31and the matching determining unit32in an information processor apparatus such as a conventional personal computer or workstation.

The constituent elements of the illustrated parts do not have to be configured physically as illustrated. In other words, the embodiments are not limited to the particular forms of distribution and integration of each part and all or some of the parts may be configured to be functionally or physically distributed or integrated in arbitrary units according to the type of load or usage conditions and the like. For example, the random number creating unit311and the approximate determination matrix creating unit312may be integrated as one unit. Conversely, the approximate determination matrix creating unit312may be distributed among a first setting unit for setting the threshold indicating the approximation range and the key threshold in the matrix, and a second setting unit for setting the random numbers. The database330may be connected as an external device to the secret data matching device3and may be connected over a network.

The processing of the various functions described in the embodiments may be realized by executing a program prepared in advance using a computer such as a personal computer or a workstation. An example of a computer for executing a secret data updating program for realizing the same functions as the secret data matching device3illustrated inFIG. 1will be explained below.FIG. 10illustrates an example of a computer for executing a secret data updating program.

As illustrated inFIG. 10, a computer200includes a CPU203for executing various arithmetic operations, an input device215for receiving inputs of data from a user, and a display control unit207for controlling a display device209. The computer200includes a drive device213for reading programs and the like from a storage medium, and a communication control unit217for transferring data with another computer over a network. The computer200includes a memory201for temporarily storing various types of information, and a HDD205. The memory201, the CPU203, the HDD205, the display control unit207, the drive device213, the input device215, and the communication control unit217are connected by a bus219.

The drive device213is a device for a removable disk210for example. The HDD205stores a secret data updating program205aand secret data update relationship information205b.

The CPU203reads the secret data updating program205aand expands and executes the secret data updating program205ain the memory201as processes. The processes correspond to the various functions of the secret data matching device3. The secret data update relationship information205bcorresponds to the approximate determination matrix331and the secret data332. The removable disk201for example stores various types of information such as the secret data updating program205a.

The secret data updating program205ais not necessarily stored in the HDD205from the start. For example, the program may be stored on a “portable physical medium” such as a flexible disk (FD), a CD-ROM, a DVD disk, a magneto-optical disc, an IC card and the like inserted into the computer200. The computer200then may read the secret data updating program205afrom the medium to execute the program.