INFORMATION MATCHING SYSTEM AND INFORMATION MATCHING METHOD

Abstract

In order to provide an information matching system achieving an information matching scheme that takes a lower cost and uses secure biometric information, the information matching system includes a concealment apparatus, a decryption apparatus, and a similarity calculating apparatus. The concealment apparatus transmits, to the similarity calculating apparatus, concealed information including information concealing obtained matching information by linear conversion using random numbers. The similarity calculating apparatus calculates, from obtained one or more pieces of registration information and the concealed information received from the concealment apparatus, a concealed similarity which is a value concealing a similarity between the matching information and the registration information, and to transmit the calculated concealed similarity to the decryption apparatus. The decryption apparatus calculates the similarity between the matching information and the registration information from the concealed similarity received from the similarity calculating apparatus, using the random numbers used by the concealment apparatus.

Claims

1. An information matching system comprising: a concealment apparatus including a memory storing instructions and one or more processors configured to execute the instructions; a decryption apparatus including a memory storing instructions and one or more processors configured to execute the instructions; and a similarity calculating apparatus including a memory storing instructions and one or more processors configured to execute the instructions, wherein the concealment apparatus is configured to transmit, to the similarity calculating apparatus, concealed information including information concealing obtained matching information by linear conversion using random numbers, the similarity calculating apparatus is configured to calculate, from obtained one or more pieces of registration information and the concealed information received from the concealment apparatus, a concealed similarity which is a value concealing a similarity between the matching information and the registration information, and to transmit the calculated concealed similarity to the decryption apparatus, and the decryption apparatus is configured to calculate the similarity between the matching information and the registration information from the concealed similarity received from the similarity calculating apparatus, using the random numbers used by the concealment apparatus.

2. The information matching system according to claim 1, further comprising: an information identifying apparatus including a memory storing instructions and one or more processors configured to execute the instructions, wherein the similarity calculating apparatus is configured to further generate a transformation key and an inverse transformation key, and calculate a concealed similarity that is a value concealing a transformed value of the similarity between the matching information and the registration information from the obtained one or more pieces of registration information, the concealed information received from the concealment apparatus, and the transformation key to transmit the calculated concealed similarity to the decryption apparatus, the decryption apparatus is configured to calculate a transformed similarity that is a transformed value of the similarity between the matching information and the registration information from a concealed transformed similarity calculated by the similarity calculating apparatus using the random numbers used by the concealment apparatus, and transmit the calculated transformed similarity to the information identifying apparatus, and the information identifying apparatus is configured to calculate a similarity from the transformed similarity received from the decryption apparatus using the inverse transformation key.

3. The information matching system according to claim 1, wherein the concealment apparatus is configured to, before obtaining the matching information, transmit concealed random numbers concealing the obtained random numbers to the similarity calculating apparatus, the similarity calculating apparatus is configured to calculate a first concealed similarity from the obtained one or more pieces of registration information and the concealed random numbers received from the concealment apparatus, and transmit the calculated first concealed similarity in advance to the decryption apparatus, the concealment apparatus is configured to transmit, after obtaining the matching information, concealed matching information concealing the obtained matching information by linear conversion using random numbers to the similarity calculating apparatus, the similarity calculating apparatus is configured to calculate a second concealed similarity from the obtained one or more pieces of registration information and the concealed matching information received from the concealment apparatus, and transmit the calculated second concealed similarity to the decryption apparatus, and the decryption apparatus is configured to calculate a similarity between the matching information and the registration information from the first concealed similarity and the second concealed similarity using the random numbers used by the concealment apparatus.

4. The information matching system according to claim 3, further comprising: an information identifying apparatus including a memory storing instructions and one or more processors configured to execute the instructions, wherein the similarity calculating apparatus is configured to, before the concealment apparatus obtains the matching information, generate a transformation key and an inverse transformation key, calculate a first concealed transformed similarity from the obtained one or more pieces of registration information, the concealed random numbers received from the concealment apparatus, and the transformation key, and transmit the calculated first concealed transformed similarity in advance to the decryption apparatus, and after the concealment apparatus obtains the matching information, calculate a second concealed transformed similarity from the obtained one or more pieces of registration information, the concealed matching information received from the concealment apparatus, and the transformation key, and transmit the calculated second concealed transformed similarity to the decryption apparatus, the decryption apparatus is configured to calculate a transformed similarity that is a transformed value of the similarity between the matching information and the registration information from the first concealed transformed similarity and the second concealed transformed similarity calculated by the similarity calculating apparatus using the random numbers used by the concealment apparatus, and transmit the calculated transformed similarity to the information identifying apparatus, and the information identifying apparatus is configured to calculate a similarity from the transformed similarity using the inverse transformation key.

5. The information matching system according to claim 2, wherein the information identifying apparatus is configured to identify the registration information matching the matching information based on the calculated similarity.

6. The information matching system according to claim 1, wherein the concealment apparatus is configured to use two random numbers a and b, and a random number s that is a vector having a dimension the same as matching information x that is a vector to conceal the matching information in a form of ax−bs.

7. The information matching system according to claim 1, wherein the concealment apparatus is configured to use one random number b and two random number vectors s and t each having a dimension the same as matching information x that is a vector to conceal the matching information in a form of x−bs−t.

8. An information matching method comprising, in an information matching system including a concealment apparatus, a decryption apparatus, and a similarity calculating apparatus: transmitting, by the concealment apparatus, to the similarity calculating apparatus, concealed information including information concealing obtained matching information by linear conversion using random numbers; calculating, by the similarity calculating apparatus, from obtained one or more pieces of registration information and the concealed information received from the concealment apparatus, a concealed similarity which is a value concealing a similarity between the matching information and the registration information, and to transmit the calculated concealed similarity to the decryption apparatus; and calculating, by the decryption apparatus, the similarity between the matching information and the registration information from the concealed similarity received from the similarity calculating apparatus, using the random numbers used by the concealment apparatus.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0041] FIG. 1 is a diagram for describing an overview of an example embodiment;

[0042] FIG. 2 is a block diagram illustrating a configuration of an information matching system (homomorphic encryption system) according to a first example embodiment;

[0043] FIG. 3 is a flow diagram illustrating an operation of the information matching system according to the first example embodiment;

[0044] FIG. 4 is a block diagram illustrating a configuration of an information matching system according to a second example embodiment;

[0045] FIG. 5 is a flow diagram illustrating an operation of the information matching system according to the second example embodiment;

[0046] FIG. 6 is a block diagram illustrating a configuration of an information matching system according to a third example embodiment;

[0047] FIG. 7 is a flow diagram illustrating an operation of a preliminary calculation process of the information matching system according to the third example embodiment;

[0048] FIG. 8 is a flow diagram illustrating an operation of a main calculation process of the information matching system according to the third example embodiment;

[0049] FIG. 9 is a block diagram illustrating a configuration of an information matching system according to a fourth example embodiment;

[0050] FIG. 10 is a flow diagram illustrating an operation of a preliminary calculation process of the information matching system according to the fourth example embodiment;

[0051] FIG. 11 is a flow diagram illustrating an operation of a main calculation process of the information matching system according to the fourth example embodiment; and

[0052] FIG. 12 is a diagram illustrating an example of a hardware configuration of a concealment apparatus.

DESCRIPTION OF THE EXAMPLE EMBODIMENTS

[0053] First, an overview of an example embodiment will be described. Note that reference signs in the drawings provided in the overview are for the sake of convenience for each element as an example to promote better understanding, and description of the overview is not to impose any limitations. Note that, in the Specification and drawings, elements to which similar descriptions are applicable are denoted by the same reference signs, and overlapping descriptions may hence be omitted.

[0054] The information matching system according to an embodiment includes a concealment apparatus 10, a decryption apparatus 20, and a similarity calculating apparatus 30 (see FIG. 1). The concealment apparatus 10 transmits, to the similarity calculating apparatus 30, concealed information including information concealing obtained matching information by linear conversion using random numbers. The similarity calculating apparatus 30 calculates, from obtained one or more pieces of registration information and the concealed information received from the concealment apparatus 30, a concealed similarity which is a value concealing the similarity between the matching information and the registration information, and to transmit the calculated concealed similarity to the decryption apparatus 20. The decryption apparatus 20 calculates the similarity between the matching information and the registration information from the concealed similarity received from the similarity calculating apparatus 30, using the random numbers used by the concealment apparatus 10.

[0055] The information matching system achieves concealment of the matching information by a linear conversion using the random numbers. Here, the linear conversion is a process a load on which is lower than that of an additive homomorphic encryption. For this reason, the information matching system can achieve the matching of information securely using the biometric information with a cost less than that of the case using an additive homomorphic public key cryptosystem.

[0056] Hereinafter, specific example embodiments are described in more detail with reference to the drawings.

First Example Embodiment

[0057] A first example embodiment will be described in further detail with reference to the drawings.

[Description of Configuration]

[0058] FIG. 2 is a block diagram illustrating a configuration of an information matching system 100 according to the first example embodiment. The information matching system 100 includes a concealment apparatus 110, a decryption apparatus 120, a similarity calculating apparatus 130, and an information identifying apparatus 140. However, the apparatuses included in the information matching system 100 may be configured as separate apparatuses, or may be adequately mounted on an identical apparatus depending on a usage. For example, the information matching system 100 can be realized as a client-server system by separately mounting the concealment apparatus 110 and the decryption apparatus 120 on a client, and the similarity calculating apparatus 130 and the information identifying apparatus 140 on a server.

[0059] The apparatuses illustrated in FIG. 2 (the concealment apparatus 110, the decryption apparatus 120, the similarity calculating apparatus 130, and the information identifying apparatus 140) are connected in a wired or wireless manner and configured to be communicable with each other.

[0060] The concealment apparatus 110 includes

a matching information acquiring section 111 that acquires matching information,
a random number acquiring section 113 that acquires random numbers,
a main random number transmitting section 114 that transmits main random numbers included in the random numbers acquired by the random number acquiring section 113,
a matching information concealment section 116 that conceals the matching information acquired by the matching information acquiring section 111 using the random numbers acquired by the random number acquiring section 113, and
a concealed information transmitting section 118 that transmits the concealed information generated by the matching information concealment section 116.

[0061] The decryption apparatus 120 includes

a main random number receiving section 121 that receives the main random numbers,
a concealed similarity receiving section 123 that receives the concealed similarity,
a decrypting section 124 that calculates a similarity from the main random numbers acquired by the main random number receiving section 121 and the concealed similarity received by the concealed similarity receiving section 123, and
a similarity transmitting section 125 that transmits the similarity calculated by the decrypting section 124.

[0062] The similarity calculating apparatus 130 includes

a concealed information receiving section 132 that receives the concealed information,
a registration information acquiring section 133 that acquires registration information,
a concealed similarity calculating section 137 that calculates a concealed similarity from the concealed information received by the concealed information receiving section 132 and the registration information received by the registration information acquiring section 133, and
a concealed similarity transmitting section 139 that transmits the concealed similarity calculated by the concealed similarity calculating section 137.

[0063] The information identifying apparatus 140 includes

a similarity receiving section 142 that receives the similarity, and
an information identifying section 144 that identifies information using the similarity received by the similarity receiving section 142.

[Description of Operation]

[0064] Next, with reference to FIG. 3, an entire operation of the information matching system 100 according to the present example embodiment will be described.

[0065] First, the matching information acquiring section 111 in the concealment apparatus 110 acquires matching information (step A1). Note that the matching information may be acquired in any way. For example, the matching information may be generated using a matching information acquiring function that the concealment apparatus 110 has therein, or may be acquired from outside of the concealment apparatus 110.

[0066] Next, the random number acquiring section 113 acquires random numbers (step A2). Note that the random numbers may be acquired in any way. For example, the random numbers may be generated using a random number generating function that the concealment apparatus 110 has therein, or random numbers generated outside the concealment apparatus 110 may be acquired from an external apparatus.

[0067] Next, the random number transmitting section 114 transmits main random numbers among the random numbers generated in step A2 to the decryption apparatus 120 (step A3).

[0068] Next, the main random number receiving section 121 in the decryption apparatus 120 receives the main random numbers from the concealment apparatus 110 (step A4).

[0069] Next, the matching information concealment section 116 conceals the matching information acquired in step A1 by a linear conversion using the random numbers acquired in step A2 to generate concealed information (step A5).

[0070] Next, the concealed information transmitting section 118 transmits the concealed information generated in step A5 to the similarity calculating apparatus 130 (step A6).

[0071] Next, the concealed information receiving section 132 in the similarity calculating apparatus 130 receives the concealed information from the concealment apparatus 110 (step A7).

[0072] Next, the registration information acquiring section 133 acquires registration information (step A8). The registration information may be stored anywhere. For example, a database storing the registration information may be included in the similarity calculating apparatus 130, or the registration information may be stored in an external apparatus connected with the similarity calculating apparatus 130. The registration information may include a plurality of pieces of information. In a case that a plurality of pieces of information are included, each piece of registration information is assigned with a specific identifier.

[0073] Next, the concealed similarity calculating section 137 calculates a concealed similarity from the concealed information received in step A7 and the registration information acquired in step A8 (step A9).

[0074] Note that the concealed similarity is a concealed form of the similarity between the matching information and the registration information. In the case that the registration information includes a plurality of pieces of information, the number of the calculated concealed similarities is the same as the number of the plurality of pieces of information. Each concealed similarity is assigned with a specific identifier, and which registration information the concealed similarity corresponds to can be identified by the identifier. Note that the identifier assigned to each concealed similarity may be the same as the identifier assigned to each piece of registration information.

[0075] Next, the concealed similarity transmitting section 139 transmits the concealed similarity calculated in step A9 to the decryption apparatus 120 (step A10).

[0076] Next, the concealed similarity receiving section 123 in the decryption apparatus 120 receives the concealed similarity from the similarity calculating apparatus 130 (step A11).

[0077] Next, the decrypting section 124 calculates a similarity from the main random numbers received in step A4 and the concealed similarity received in step A11 (step A12).

[0078] Note that the similarity is a similarity between the matching information and the registration information. In the case that the registration information includes a plurality of pieces of information, the number of the calculated similarities is the same as the number of the plurality of pieces of information. Each similarity is assigned with a specific identifier, and which registration information the similarity corresponds to can be identified by the identifier. Note that the identifier assigned to each similarity may be the same as the identifier assigned to each piece of registration information.

[0079] Next, the similarity transmitting section 125 transmits the similarity calculated in step A12 to the information identifying apparatus 140 (step A13).

[0080] Next, the similarity receiving section 142 in the information identifying apparatus 140 receives the similarity from the decryption apparatus 120 (step A14).

[0081] Finally, the information identifying section 144 identifies, among the similarities received in step A14, a similarity falling within a predefined acceptable range to identify registration information that is recognized to be sufficiently similar to the matching information (step A15).

[0082] Note that in a case that it is not necessary to identify the registration information recognized to be sufficiently similar to the matching information, but it is desired to check whether the registration information recognized to be sufficiently similar to the matching information is present or not, such processing may be made.

Concrete Example 1 According to First Example Embodiment

[0083] Next, a concrete example 1 of the operation of the information matching system 100 according to the present example embodiment will be described.

[0084] In this concrete example, a case that a group on elliptic curve is used will be described. Assume that a group with an order of a κ-bit prime number q on an elliptic curve E and a generator G of the group are published.

[0085] In this concrete example, a case that vectors (with a dimension number of D) are used for the matching information and the registration information will be described. Furthermore, a case that the similarity between the matching information and the registration information is calculated by use of the inner product of the two vectors will be described. Assume a case that the matching information and the registration information are determined to be sufficiently similar to each other is a case that the similarity calculated by use of the inner product of the matching information and the registration information matches any one of T values θ.sub.1, . . . , and θ.sub.τ.

[0086] In this concrete example, assume that pieces of information of N persons are registered in the database, and the pieces of the registration information of N persons are assigned with the identifiers of 1 to N.

However, a target of the present example embodiment is not limited to such cases above.

[0087] First, the matching information acquiring section 111 in the concealment apparatus 110 acquires, as the matching information, a D-dimensional vector:

x=(x.sub.1, . . . , and x.sub.D)

(step A1).

[0088] Next, the main random number acquiring section 113 acquires, as the random numbers, D+2 κ-bit random numbers a, b, s.sub.1, . . . , and s.sub.D (step A2). Hereinafter, among the acquired random numbers, a and b are collectedly referred to as main random numbers. D random numbers s.sub.1, . . . , and s.sub.D are expressed as a vector:

s=(s.sub.1, . . . , and s.sub.D).

[0089] Next, the main random number transmitting section 114 transmits the main random numbers (a, b) generated in step A2 to the decryption apparatus 120 (step A3).

[0090] Next, the main random number receiving section 121 in the decryption apparatus 120 receives the main random numbers (a, b) from the concealment apparatus 110 (step A4).

[0091] Next, the matching information concealment section 116 in the concealment apparatus 110 calculates,

S.sub.j=[s.sub.j]G and z.sub.j=ax.sub.j−bs.sub.j

for all j=1, . . . , and D,
from the matching information x=(x.sub.1, . . . , and x.sub.D) acquired in step A1 and
the random numbers a, b, s=(s.sub.1, . . . , and s.sub.D) acquired in step A2.
Among the calculated values, D values z.sub.1, . . . , and z.sub.D are expressed as a vector:

z=(z.sub.1, . . . , and z.sub.D).

[0092] The matching information concealment section 116 combines the calculated values to obtain the concealed information ((S.sub.1, . . . , and S.sub.D), z) (step A5).

[0093] Next, the concealed information transmitting section 118 transmits the concealed information ((S.sub.1, . . . , and S.sub.D), z) generated in step A5 to the similarity calculating apparatus 130 (step A6).

[0094] Next, the concealed information receiving section 132 in the similarity calculating apparatus 130 receives the concealed information ((S.sub.1, . . . , and S.sub.D), z) from the concealment apparatus 110 (step A7).

[0095] Next, the registration information acquiring section 133 acquires, as the registration information, N D-dimensional vectors y.sub.1, . . . , and y.sub.N (where y.sub.i, 1, . . . , and y.sub.i, D) for all i=1, . . . , and N) (step A8).

[0096] Next, the concealed similarity calculating section 137 calculates, as concealed similarities for all i=1, . . . , and N,

U.sub.i=[y.sub.i,1]S.sub.1+ . . . +[y.sub.i,D]S.sub.D and

W.sub.i=[<z,y.sub.i>]G

from the concealed information ((S.sub.1, . . . , and S.sub.D), z) received in step A7 and the registration information y.sub.1, . . . , and y.sub.N (where y.sub.1=1, . . . , and y.sub.i, D) for all i=1, . . . , and N) acquired in step A8 (step A9).
Note that because S.sub.j=[s.sub.j]G and z.sub.j=ax.sub.j−bs.sub.j are satisfied for all j=1, . . . , and D, U.sub.i and W.sub.i for all i=1, . . . , and N are also be expressed as

U.sub.i=[<s,y.sub.i>]G

and

W.sub.i=[a<x,y.sub.i>−b<s,y.sub.i>]G.

[0097] Next, the concealed similarity transmitting section 139 transmits the concealed similarities (U.sub.1, . . . , and U.sub.N, W.sub.1, . . . , and W.sub.N) calculated in step A9 to the decryption apparatus 120 (step A10).

[0098] Next, the concealed similarity receiving section 123 in the decryption apparatus 120 receives the concealed similarities (U.sub.1, . . . , and U.sub.N, W.sub.1, . . . , and W.sub.N) from the similarity calculating apparatus 130 (step A11).

[0099] Next, the decrypting section 124 calculates, as points of similarities for all i=1, . . . , and N,

[<x,y.sub.i>]G

from the main random numbers a and b received in step A4 and
the concealed similarities (U.sub.1, . . . , and U.sub.N, W.sub.1, . . . , and W.sub.N) received in step A11 (step A12).
Note that the point of similarity for all i=1, . . . , and N can be calculated as, for example, [a.sup.−1]([b]U.sub.i+W.sub.i).

[0100] Next, the similarity transmitting section 125 transmits the points of similarities ([<x, y.sub.1>]G, . . . , and [<x, y.sub.N>]G) calculated in step A12 to the information identifying apparatus 140 (step A13).

[0101] Next, the similarity receiving section 142 in the information identifying apparatus 140 receives the points of similarities ([<x, y.sub.1>]G, . . . , and [<x, y.sub.N>]G) from the decryption apparatus 120 (step A14).

[0102] At the end of the main calculation process, the information identifying section 144 identifies, among the points of similarities ([<x, y.sub.1>]G, . . . , and [<x, y.sub.N>]G) received in step A14, a point of similarity falling within a point acceptable range ([θ.sub.1]G, . . . , and [θ.sub.τ]G) corresponding to a predefined acceptable range (θ.sub.1, . . . , and θ.sub.τ) (step A15).

[0103] Note that in this concrete example, although the points of similarities are calculated in step A12 and the information is identified from the points of similarities in step A15, a similarity may be further calculated from the points of similarities in step A12, or a similarity falling within the acceptable range may be further identified in step A12, and an identifier associated with the similarity identified may be transmitted in step A13.

[0104] This concrete example describes the example in which the similarity calculating apparatus 130 orders N concealed similarities to be transmitted to the decryption apparatus 120 in an index-based order of the registration information and transmits the resultant concealed similarities in step A10, but the similarity calculating apparatus 130 may assign a new identifier to each of the concealed similarities, shuffle the concealed similarities, and transmit the resultant concealed similarities to the decryption apparatus 120. At this time, the similarity calculating apparatus 130 may further give correspondences of two types of identifiers to the information identifying apparatus 140 so that the information identifying apparatus 140 can determine an identifier of the registration information that the information identifying apparatus 140 desires to identify.

Concrete Example 2 According to First Example Embodiment

[0105] Next, a concrete example 2 of the operation of the information matching system 100 according to the present example embodiment will be described.

[0106] In this concrete example also, although a description is given assuming a case similar to the case of the concrete example 1 according to the first example embodiment, a target of the present example embodiment is not limited to these cases.

[0107] First, the matching information acquiring section 111 in the concealment apparatus 110 acquires, as the matching information, a D-dimensional vector:

x=(x.sub.1, . . . , and x.sub.D)

(step A1).

[0108] Next, the main random number acquiring section 113 acquires 2D+1 κ-bit random numbers b, s.sub.1, . . . , and s.sub.D, t.sub.1, . . . , and t.sub.D (step A2). Hereinafter, among the acquired random numbers, b is referred to as a main random number. D random numbers s.sub.1, . . . , and s.sub.D and D random numbers t.sub.1, . . . , and t.sub.D are expressed as vectors:

s=(s.sub.1, . . . , and s.sub.D) and t=(t.sub.1, . . . , and t.sub.D).

[0109] Next, the main random number transmitting section 114 transmits the main random number b generated in step A2 to the decryption apparatus 120 (step A3).

[0110] Next, the main random number receiving section 121 in the decryption apparatus 120 receives the main random number b from the concealment apparatus 110 (step A4).

[0111] Next, the matching information concealment section 116 in the concealment apparatus 110 calculates,

S.sub.j=[s.sub.j]G,T.sub.j=[t.sub.j]G, and z.sub.j=−bs.sub.j−t.sub.j

for all j=1, . . . , and D,
from the matching information x=(x.sub.1, . . . , and x.sub.D) acquired in step A1 and
b, s=(s.sub.1, . . . , and s.sub.D), and t=(t.sub.1, . . . , and t.sub.D) acquired in step A2.
Among the calculated values, D values z.sub.1, . . . , and z.sub.D are expressed as a vector:

z=(z.sub.1, . . . , and z.sub.D).

The matching information concealment section 116 combines the calculated values to let ((S.sub.1, . . . , and S.sub.D), (T.sub.1, . . . , and T.sub.D), z) be the concealed information (step A5).

[0112] Next, the concealed information transmitting section 118 transmits the concealed information ((S.sub.1, . . . , and S.sub.D), (T.sub.1, . . . , and T.sub.D), z) generated in step A5 to the similarity calculating apparatus 130 (step A6).

[0113] Next, the concealed information receiving section 132 in the similarity calculating apparatus 130 receives the concealed information ((S.sub.1, . . . , and S.sub.D), (T.sub.1, . . . , and T.sub.D), z) from the concealment apparatus 110 (step A7).

[0114] Next, the registration information acquiring section 133 acquires, as the registration information, N D-dimensional vectors y.sub.1, . . . , and y.sub.N (where y.sub.i=(y.sub.i, 1, . . . , and y.sub.i, D) for all i=1, . . . , and N) (step A8).

[0115] Next, the concealed similarity calculating section 137 calculates, as concealed similarities for all i=1, . . . , and N,

U.sub.i=[y.sub.i,1]S.sub.1+ . . . +[y.sub.i,D]S.sub.D and

V.sub.i=[y.sub.i,1]T.sub.1+ . . . +[y.sub.i,D]T.sub.D+[<z,y.sub.i>]G

from the concealed information ((S.sub.1, . . . , and S.sub.D), (T.sub.1, . . . , and T.sub.D), z) received in step A7 and
the registration information y.sub.1, . . . , and y.sub.N (where y.sub.1=(y.sub.i, 1, . . . , and y.sub.i, D) for all i=1, and N) acquired in step A8 (step A9).
Note that because S.sub.j=[s.sub.j]G, T.sub.j=[t.sub.j]G, and z.sub.j=x.sub.j−bs.sub.j−t.sub.j are satisfied for all j=1, . . . , and D,
U.sub.i and V.sub.i for all i=1, . . . , and N are also be expressed as

U.sub.i=[<s,y.sub.i>]G

and

V.sub.i=[<x,y.sub.i>−b<s,y.sub.i>]G.

[0116] Next, the concealed similarity transmitting section 139 transmits the concealed similarities (U.sub.1, . . . , and U.sub.N, V.sub.1, . . . , and V.sub.N) calculated in step A9 to the decryption apparatus 120 (step A10).

[0117] Next, the concealed similarity receiving section 123 in the decryption apparatus 120 receives the concealed similarities (U.sub.1, . . . , and U.sub.N, V.sub.1, . . . , and V.sub.N) from the similarity calculating apparatus 130 (step A11).

[0118] Next, the decrypting section 124 calculates, as points of similarities for all i=1, . . . , and N,

[<x,y.sub.i>]G

from the main random number b received in step A4 and
the concealed similarities (U.sub.1, . . . , and U.sub.N, V.sub.1, . . . , and V.sub.N) received in step A11 (step A12).
Note that the point of similarity for all i=1, . . . , and N can be calculated as, for example, [b]U.sub.i+V.sub.i+W.sub.i.

[0119] Next, the similarity transmitting section 125 transmits the points of similarities ([<x, y.sub.1>]G, . . . , and [<x, y.sub.N>]G) calculated in step A12 to the information identifying apparatus 140 (step A13).

[0120] Next, the similarity receiving section 142 in the information identifying apparatus 140 receives the points of similarities ([<x, y.sub.1>]G, . . . , and [<x, y.sub.N>]G) from the decryption apparatus 120 (step A14).

[0121] At the end of the main calculation process, the information identifying section 144 identifies, among the points of similarities ([<x, y.sub.1>]G, . . . , and [<x, y.sub.N>]G) received in step A14, a point of similarity falling within a point acceptable range ([θ.sub.1]G, . . . , and [θ.sub.τ]G) corresponding to a predefined acceptable range (θ.sub.1, . . . , and θ.sub.τ) (step A15).

[0122] Note that in this concrete example, although the points of similarities are calculated in step A12 and the information is identified from the points of similarities in step A15, a similarity may be further calculated from the points of similarities in step A12, or a similarity falling within the acceptable range may be further identified in step A12, and an identifier associated with the similarity identified may be transmitted in step A13.

[0123] This concrete example describes the example in which the similarity calculating apparatus 130 orders N concealed similarities to be transmitted to the decryption apparatus 120 in an index-based order of the registration information and transmits the resultant concealed similarities in step A10, but the similarity calculating apparatus 130 may assign a new identifier to each of the concealed similarities, shuffle the concealed similarities, and transmit the resultant concealed similarities to the decryption apparatus 120. At this time, the similarity calculating apparatus 130 may further give correspondences of two types of identifiers to the information identifying apparatus 140 so that the information identifying apparatus 140 can determine an identifier of the registration information that the information identifying apparatus 140 desires to identify.

[Description of Effect]

[0124] An effect of the present example embodiment described above is that information matching securely using the biometric information can be realized with a cost less than that of the case of using an additive homomorphic public key cryptosystem. This is because in the concealment of the matching information in step A5, the concealment is performed by the linear conversion instead of a homomorphic operation of an additive homomorphic public key cryptosystem. The linear conversion, rather than the general concealment, is applied to allow the concealed similarities and the similarities to be calculated in step A9 and step A12.

Second Example Embodiment

[Description of Configuration]

[0125] FIG. 4 is a block diagram illustrating a configuration of an information matching system 200 according to a second example embodiment. The information matching system 200 includes a concealment apparatus 210, a decryption apparatus 220, a similarity calculating apparatus 230, and an information identifying apparatus 240. However, the apparatuses included in the information matching system 200 may be configured as separate apparatuses, or may be adequately mounted on an identical apparatus as usage. For example, the information matching system 200 can be realized as a client-server system by separately mounting the concealment apparatus 210 and the decryption apparatus 220 on a client, and the similarity calculating apparatus 230 and the information identifying apparatus 240 on a server.

[0126] The apparatuses illustrated in FIG. 4 (the concealment apparatus 210, the decryption apparatus 220, the similarity calculating apparatus 230, and the information identifying apparatus 240) are connected in a wired or wireless manner and configured to be communicable with each other.

[0127] The concealment apparatus 210 includes

a matching information acquiring section 211 that acquires matching information,
a random number acquiring section 213 that acquires random numbers,
a main random number transmitting section 214 that transmits main random numbers included in the random numbers acquired by the random number acquiring section 213,
a matching information concealment section 216 that conceals the matching information acquired by the matching information acquiring section 211 using the random numbers acquired by the random number acquiring section 213, and
a concealed information transmitting section 218 that transmits the concealed information generated by the matching information concealment section 216.

[0128] The decryption apparatus 220 includes

a main random number receiving section 221 that receives the main random numbers,
a concealed transformed similarity receiving section 223 that receives the concealed transformed similarity,
a decrypting section 224 that calculates a transformed similarity from the main random numbers received by the main random number receiving section 221 and the concealed transformed similarity received by the concealed transformed similarity receiving section 223, and
a similarity transmitting section 225 that transmits the transformed similarity calculated by the decrypting section 224.

[0129] The similarity calculating apparatus 230 includes

a concealed information receiving section 232 that receives the concealed information,
a registration information acquiring section 233 that acquires registration information,
a transformation key generating section 234 that generates a transformation key and an inverse transformation key,
an inverse transformation key transmitting section 235 that transmits the inverse transformation key generated by the transformation key generating section 234,
a concealed transformed similarity calculating section 237 that calculates a concealed transformed similarity from the concealed information received by the concealed information receiving section 232, the registration information received by the registration information acquiring section 233, and the transformation key generated by the transformation key generating section 234, and
a concealed transformed similarity transmitting section 239 that transmits the concealed transformed similarity calculated by the concealed transformed similarity calculating section 237.

[0130] The information identifying apparatus 240 includes

an inverse transformation key receiving section 241 that receives an inverse transformation key,
a transformed similarity receiving section 242 that receives the transformed similarity, an inverse transforming section 243 that inversely transforms the transformed similarity received by the transformed similarity receiving section 242 using the inverse transformation key generated by the transformation key generating section 234, and
an information identifying section 244 that identifies information using the similarity calculated by the inverse transforming section 243.

[Description of Operation]

[0131] Next, with reference to FIG. 5, an entire operation of the information matching system 200 according to the present example embodiment will be described.

[0132] First, the matching information acquiring section 211 in the concealment apparatus 210 acquires matching information (step B1). Note that the matching information may be acquired in any way. For example, the matching information may be generated using a matching information acquiring function that the concealment apparatus 210 has therein, or may be acquired from outside of the concealment apparatus 210.

[0133] Next, the random number acquiring section 213 acquires random numbers (step B2). Note that the random numbers may be acquired in any way. For example, the random numbers may be generated using a random number generating function that the concealment apparatus 210 has therein, or random numbers generated outside the concealment apparatus 210 may be acquired from an external apparatus.

[0134] Next, the random number transmitting section 214 transmits main random numbers among the random numbers generated in step B2 to the decryption apparatus 220 (step B3).

[0135] Next, the main random number receiving section 221 in the decryption apparatus 220 receives the main random numbers from the concealment apparatus 210 (step B4).

[0136] Next, the matching information concealment section 216 in the concealment apparatus 210 conceals the matching information acquired in step B1 by a linear conversion using the random numbers acquired in step B2 to generate concealed information (step B5).

[0137] Next, the concealed information transmitting section 218 transmits the concealed information generated in step B5 to the similarity calculating apparatus 230 (step B6).

[0138] Next, the concealed information receiving section 232 in the similarity calculating apparatus 230 receives the concealed information from the concealment apparatus 210 (step B7).

[0139] Next, the registration information acquiring section 233 acquires registration information (step B8). The registration information may be stored anywhere. For example, a database storing the registration information may be included in the similarity calculating apparatus 230, or the registration information may be stored in an external apparatus connected with the similarity calculating apparatus 230. The registration information may include a plurality of pieces of information. In a case that a plurality of pieces of information are included, each piece of registration information is assigned with a specific identifier.

[0140] Next, the transformation key generating section 234 acquires the random numbers to generate a transformation key and an inverse transformation key based on the random number (step B9). Note that the random numbers may be acquired in any way. For example, the random numbers may be generated using a random number generating function that the similarity calculating apparatus 230 has therein, or random numbers generated outside the similarity calculating apparatus 230 may be acquired from an external apparatus.

[0141] Next, the inverse transformation key transmitting section 235 transmits the inverse transformation key generated in step B9 to the information identifying apparatus 240 (step B10).

[0142] Next, the inverse transformation key receiving section 241 in the information identifying apparatus 240 receives the inverse transformation key from the similarity calculating apparatus 230 (step B11).

[0143] Next, the concealed transformed similarity calculating section 237 in the similarity calculating apparatus 230 calculates a concealed transformed similarity from the concealed information received in step B7, the registration information acquired in step B8, and the transformation key generated in step B9 (step B12).

[0144] Note that the concealed transformed similarity is a concealed form of a value which is a transformed form of the similarity between the matching information and the registration information using the transformation key. In the case that the registration information includes a plurality of pieces of information, the number of the calculated concealed transformed similarities is the same as the number of the plurality of pieces of information. Each concealed transformed similarity is assigned with a specific identifier, and which registration information the concealed transformed similarity corresponds to can be identified by the identifier. Note that the identifier assigned to each concealed transformed similarity may be the same as the identifier assigned to each piece of registration information.

[0145] Next, the concealed transformed similarity transmitting section 239 transmits the concealed transformed similarity calculated in step B12 to the decryption apparatus 220 (step B13).

[0146] Next, the concealed transformed similarity receiving section 223 in the decryption apparatus 220 receives the concealed transformed similarity from the similarity calculating apparatus 230 (step B14).

[0147] Next, the decrypting section 224 calculates a transformed similarity from the main random numbers received in step B4 and the concealed transformed similarity received in step B14 (step B15).

[0148] Note that the transformed similarity is a transformed form of the similarity between the matching information and the registration information using the transformation key. In the case that the registration information includes a plurality of pieces of information, the number of the calculated transformed similarities is the same as the number of the plurality of pieces of information. Each transformed similarity is assigned with a specific identifier, and which registration information the transformed similarity corresponds to can be identified by the identifier. Note that the identifier assigned to each transformed similarity may be the same as the identifier assigned to each piece of registration information.

[0149] Next, the similarity transmitting section 225 transmits the transformed similarity calculated in step B15 to the information identifying apparatus 240 (step B16).

[0150] Next, the transformed similarity receiving section 242 in the information identifying apparatus 240 receives the transformed similarity from the decryption apparatus 220 (step B17).

[0151] Next, the inverse transforming section 243 inversely transforms the transformed similarity received in step B17 using the inverse transformation key received in step B11 to calculate a similarity (step B18).

[0152] Note that the similarity is a similarity between the matching information and the registration information. In the case that the registration information includes a plurality of pieces of information, the number of the calculated similarities is the same as the number of the plurality of pieces of information. Each similarity is assigned with a specific identifier, and which registration information the similarity corresponds to can be identified by the identifier. Note that the identifier assigned to each similarity may be the same as the identifier assigned to each piece of registration information.

[0153] Finally, the information identifying section 244 identifies, among the similarities calculated in step B18, a similarity falling within a predefined acceptable range to identify registration information that is recognized to be sufficiently similar to the matching information (step B19).

[0154] Note that in a case that it is not necessary to identify the registration information recognized to be sufficiently similar to the matching information, but it is desired to check whether the registration information recognized to be sufficiently similar to the matching information is present or not, such processing may be made.

Concrete Example 1 According to Second Example Embodiment

[0155] Next, a concrete example 1 of the operation of the information matching system 200 according to the present example embodiment will be described.

[0156] In this concrete example, a case that a group on elliptic curve is used will be described. Assume that a group with an order of a κ-bit prime number q on an elliptic curve E and a generator G of the group are published.

[0157] In this concrete example, a case that vectors (with a dimension number of D) are used for the matching information and the registration information will be described. Furthermore, a case that the similarity between the matching information and the registration information is calculated by use of the inner product of the two vectors will be described. Assume a case that the matching information and the registration information are determined to be sufficiently similar to each other is a case that the similarity calculated by use of the inner product of the matching information and the registration information matches any one of T values θ.sub.1, . . . , and θ.sub.τ.

[0158] In this concrete example, assume that pieces of information of N persons are registered in the database, and the pieces of the registration information of N persons are assigned with the identifiers of 1 to N. However, a target of the present example embodiment is not limited to such cases above.

[0159] First, the matching information acquiring section 211 in the concealment apparatus 210 acquires, as the matching information, a D-dimensional vector:

x=(x.sub.1, . . . , and x.sub.D)

(step B1).

[0160] Next, the main random number acquiring section 213 acquires, as the random numbers, D+2 κ-bit random numbers a, b, s.sub.1, . . . , and s.sub.D (step B2). Hereinafter, among the acquired random numbers, a and b are collectedly referred to as main random numbers. D random numbers s.sub.1, . . . , and s.sub.D are expressed as a vector:

s=(s.sub.1, . . . , and s.sub.D).

[0161] Next, the main random number transmitting section 214 transmits the main random numbers (a, b) generated in step B2 to the decryption apparatus 220 (step B3).

[0162] Next, the main random number receiving section 221 in the decryption apparatus 220 receives the main random numbers (a, b) from the concealment apparatus 210 (step B4).

[0163] Next, the matching information concealment section 216 in the concealment apparatus 210 calculates,

S.sub.j=[s.sub.j]G and z.sub.j=ax.sub.j−bs.sub.j

for all j=1, . . . , and D,
from the matching information x=(x.sub.1, . . . , and x.sub.D) acquired in step B1 and
the random numbers a, b, and s=(s.sub.1, . . . , and s.sub.D) acquired in step B2.
Among the calculated values, D values z.sub.1, . . . , and z.sub.D are expressed as a vector:

z=(z.sub.1, . . . , and z.sub.D).

The matching information concealment section 216 combines the calculated values to let ((S.sub.1, . . . , and S.sub.D), z) be the concealed information (step B5).

[0164] Next, the concealed information transmitting section 218 transmits the concealed information ((S.sub.1, . . . , and S.sub.D), z) generated in step B5 to the similarity calculating apparatus 230 (step B6).

[0165] Next, the concealed information receiving section 232 in the similarity calculating apparatus 230 receives the concealed information ((S.sub.1, . . . , and S.sub.D), z) from the concealment apparatus 210 (step B7).

[0166] Next, the registration information acquiring section 233 acquires, as the registration information, N D-dimensional vectors y.sub.1, . . . , and y.sub.N (where y.sub.i=(y.sub.i, 1, . . . , and y.sub.i, D) for all i=1, . . . , and N) (step B8).

[0167] Next, the transformation key generating section 234 acquires D κ-bit random numbers r.sub.1, . . . , and r.sub.N to let (r.sub.1, . . . , and r.sub.N) be the transformation keys and ((r.sub.1).sup.−1, . . . , and (r.sub.N).sup.−1) be the inverse transformation keys (step B9).

[0168] Next, the inverse transformation key transmitting section 235 transmits the inverse transformation keys ((r.sub.1).sup.−1, . . . , and (r.sub.N).sup.−1) generated in step B9 to the information identifying apparatus 240 (step B10).

[0169] Next, the inverse transformation key receiving section 241 in the information identifying apparatus 240 receives the inverse transformation keys ((r.sub.1).sup.−1, . . . , and (r.sub.N).sup.−1) from the similarity calculating apparatus 230 (step B11).

[0170] Next, the concealed transformed similarity calculating section 237 calculates, as concealed transformed similarities for all i=1, . . . , and N,

U.sub.i=[r.sub.i]([y.sub.i,1]S.sub.1+ . . . +[y.sub.i,D]S.sub.D) and

W.sub.i=[r.sub.i<z,y.sub.i>]G

from the concealed information ((S.sub.1, . . . , and S.sub.D), z) received in step B7,
the registration information y.sub.1, . . . , and y.sub.N (where y.sub.i=(y.sub.i, 1, . . . , and y.sub.i, D) for all i=1, . . . , and N) acquired in step B8, and
the transformation keys (r.sub.1, . . . , and r.sub.N) generated in step B9 (step B12).
Note that because S.sub.j=[s.sub.j]G and z.sub.j=ax.sub.j−bs.sub.j are satisfied for all j=1, . . . , and D,
U.sub.i and W.sub.i for all i=1, . . . , and N are also be expressed as

U.sub.i=[r.sub.i<s,y.sub.i>]G

and

W.sub.i=[r.sub.i(a<x,y.sub.i>−b<s,y.sub.i>)]G.

[0171] Next, the concealed transformed similarity transmitting section 239 transmits the concealed transformed similarities (U.sub.1, . . . , and U.sub.N, W.sub.1, . . . , and W.sub.N) calculated in step B12 to the decryption apparatus 220 (step B13).

[0172] Next, the concealed transformed similarity receiving section 223 in the decryption apparatus 220 receives the concealed transformed similarities (U.sub.1, . . . , and U.sub.N, W.sub.1, . . . , and W.sub.N) from the similarity calculating apparatus 230 (step B14).

[0173] Next, the decrypting section 224 calculates, as transformed similarities for all i=1, . . . , and N,

A.sub.i=[r.sub.i<x,y.sub.i>]G

from the main random numbers a and b received in step B4 and
the concealed transformed similarities (U.sub.1, . . . , and U.sub.N, W.sub.1, . . . , and W.sub.N) received in step B14 (step B15).
Note that the transformed similarity for all i=1, . . . , and N can be calculated as, for example,

[a.sup.−1]([b]U.sub.i+W.sub.i).

[0174] Next, the similarity transmitting section 225 transmits the transformed similarities (A.sub.1, . . . , and A.sub.N) calculated in step B15 to the information identifying apparatus 240 (step B16).

[0175] Next, the transformed similarity receiving section 242 in the information identifying apparatus 240 receives the transformed similarities (A.sub.1, . . . , and A.sub.N) from the decryption apparatus 220 (step B17).

[0176] Next, the inverse transforming section 243 calculates, as points of similarities for all i=1, . . . , and N,

[<x,y.sub.i>]G

from the inverse transformation keys ((r.sub.1).sup.−1, . . . , and (r.sub.N).sup.−1) received in step B11 and the transformed similarities (A.sub.1, . . . , and A.sub.N) received in step B17 (step B18).
Note that the point of similarity for all i=1, . . . , and N can be calculated as, for example,

[(r.sub.i).sup.−1](A.sub.i).

[0177] At the end of the main calculation process, the information identifying section 244 identifies, among the points of similarities ([<x, y.sub.1>]G, . . . , and [<x, y.sub.N>]G) calculated in step B18, a point of similarity falling within a point acceptable range ([θ.sub.1]G, . . . , and [θ.sub.τ]G) corresponding to a predefined acceptable range (θ.sub.1, . . . , and θ.sub.τ) (step B19).

[0178] This concrete example describes the example in which the similarity calculating apparatus 230 orders N concealed similarities to be transmitted to the decryption apparatus 220 in an index-based order of the registration information and transmits the resultant concealed similarities in step B13, but the similarity calculating apparatus 230 may assign a new identifier to each of the concealed similarities, shuffle the concealed similarities, and transmit the resultant concealed similarities to the decryption apparatus 220. At this time, the similarity calculating apparatus 230 may further give correspondences of two types of identifiers to the information identifying apparatus 240 so that the information identifying apparatus 240 can determine an identifier of the registration information that the information identifying apparatus 240 desires to identify.

Concrete Example 2 According to Second Example Embodiment

[0179] Next, a concrete example 2 of the operation of the information matching system 200 according to the present example embodiment will be described.

[0180] In this concrete example also, although a description is given assuming a case similar to the case of the concrete example 1 according to the second example embodiment, a target of the present example embodiment is not limited to these cases.

[0181] First, the matching information acquiring section 211 in the concealment apparatus 210 acquires, as the matching information, a D-dimensional vector:

x=(x.sub.1, . . . , and x.sub.D)

(step B1).

[0182] Next, the main random number acquiring section 213 acquires 2D+1 κ-bit random numbers b, s.sub.1, . . . , and s.sub.D, t.sub.1, . . . , and t.sub.D (step B2). Hereinafter, among the acquired random numbers, b is referred to as a main random number. D random numbers s.sub.1, . . . , and s.sub.D and D random numbers t.sub.1, . . . , and t.sub.D are expressed as vectors:

s=(s.sub.1, . . . , and s.sub.D) and t=(t.sub.1, . . . , and t.sub.D).

[0183] Next, the main random number transmitting section 214 transmits the main random number b generated in step B2 to the decryption apparatus 220 (step B3).

[0184] Next, the main random number receiving section 221 in the decryption apparatus 220 receives the main random number b from the concealment apparatus 210 (step B4).

[0185] Next, the matching information concealment section 216 in the concealment apparatus 210 calculates,

S.sub.j=[s.sub.j]G,T.sub.j=[t.sub.j]G,z.sub.j=x.sub.j−bs.sub.j−t.sub.j

for all j=1, . . . , and D,
from the matching information x=(x.sub.1, . . . , and x.sub.D) acquired in step B1 and
random numbers b, s=(s.sub.1, . . . , and s.sub.D), and t=(t.sub.1, . . . , and t.sub.D) acquired in step B2.
Among the calculated values, D values z.sub.1, . . . , and z.sub.D are expressed as a vector:

z=(z.sub.1, . . . , and z.sub.D).

The matching information concealment section 216 combines the calculated values to let ((S.sub.1, . . . , and S.sub.D), (T.sub.1, . . . , and T.sub.D), z) be the concealed information (step B5).

[0186] Next, the concealed information transmitting section 218 transmits the concealed information ((S.sub.1, . . . , and S.sub.D), (T.sub.1, . . . , and T.sub.D), z) generated in step B5 to the similarity calculating apparatus 230 (step B6).

[0187] Next, the concealed information receiving section 232 in the similarity calculating apparatus 230 receives the concealed information ((S.sub.1, . . . , and S.sub.D), (T.sub.1, . . . , and T.sub.D), z) from the concealment apparatus 210 (step B7).

[0188] Next, the registration information acquiring section 233 acquires, as the registration information, N D-dimensional vectors y.sub.1, . . . , and y.sub.N (where y.sub.i=i, . . . , and y.sub.i, D) for all i=1, . . . , and N) (step B8).

[0189] Next, the transformation key generating section 234 acquires D κ-bit random numbers r.sub.1, . . . , and r.sub.N to let (r.sub.1, . . . , and r.sub.N) be the transformation keys and ((r.sub.1).sup.−1, . . . , and (r.sub.N).sup.−1) be the inverse transformation keys (step B9).

[0190] Next, the inverse transformation key transmitting section 235 transmits the inverse transformation keys ((r.sub.1).sup.−1, . . . , and (r.sub.N).sup.−1) generated in step B9 to the information identifying apparatus 240 (step B10).

[0191] Next, the inverse transformation key receiving section 241 in the information identifying apparatus 240 receives the inverse transformation keys ((r.sub.1).sup.−1, . . . , and (r.sub.N).sup.−1) from the similarity calculating apparatus 230 (step B11).

[0192] Next, the concealed transformed similarity calculating section 237 calculates, as concealed transformed similarities for all i=1, . . . , and N,

U.sub.i=[r.sub.i]([y.sub.i,1]S.sub.1+ . . . +[y.sub.i,D]S.sub.D) and

V.sub.i=[r.sub.i]([y.sub.i,1]T.sub.1+ . . . +[y.sub.i,D]T.sub.D+[<z,y.sub.i>]G)

from the concealed information ((S.sub.1, . . . , and S.sub.D), (T.sub.1, . . . , and T.sub.D), z) received in step B7,
the registration information y.sub.1, . . . , and y.sub.N (where y.sub.i=(y.sub.i, 1, . . . , and y.sub.i, D) for all i=1, and N) acquired in step B8, and
the transformation keys (r.sub.1, . . . , and r.sub.N) generated in step B9 (step B12).
Note that because S.sub.j=[s.sub.j]G, T.sub.j=[t.sub.j]G, and z.sub.j=x.sub.j−bs.sub.j−t.sub.j are satisfied for all j=1, . . . , and D,
U.sub.i and V.sub.i for all i=1, . . . , and N are also be expressed as

U.sub.i=[r.sub.i<s,y.sub.i>]G

and

V.sub.i=[r.sub.i(<x,y.sub.i>−b<s,y.sub.i>)]G.

[0193] Next, the concealed transformed similarity transmitting section 239 transmits the concealed transformed similarities (U.sub.1, . . . , and U.sub.N, V.sub.1, . . . , and V.sub.N) calculated in step B12 to the decryption apparatus 220 (step B13).

[0194] Next, the concealed transformed similarity receiving section 223 in the decryption apparatus 220 receives the concealed transformed similarities (U.sub.1, . . . , and U.sub.N, V.sub.1, . . . , and V.sub.N) from the similarity calculating apparatus 230 (step B14).

[0195] Next, the decrypting section 224 calculates, as transformed similarities for all i=1, . . . , and N,

A.sub.i=[r.sub.i<x,y.sub.i>]G

from the main random number b received in step B4 and
the concealed transformed similarities (U.sub.1, . . . , and U.sub.N, V.sub.1, . . . , and V.sub.N) received in step B14 (step B15).
Note that the transformed similarity for all i=1, . . . , and N can be calculated as, for example,

[b]U.sub.i+V.sub.i.

[0196] Next, the similarity transmitting section 225 transmits the transformed similarities (A.sub.1, . . . , and A.sub.N) calculated in step B15 to the information identifying apparatus 240 (step B16).

[0197] Next, the transformed similarity receiving section 242 in the information identifying apparatus 240 receives the transformed similarities (A.sub.1, . . . , and A.sub.N) from the decryption apparatus 220 (step B17).

[0198] Next, the inverse transforming section 243 calculates, as points of similarities for all i=1, . . . , and N,

[<x,y.sub.i>]G

from the inverse transformation keys ((r.sub.1).sup.−1, . . . , and (r.sub.N).sup.−1) received in step B11 and
the transformed similarities (A.sub.1, . . . , and A.sub.N) received in step B17 (step B18).
Note that the point of similarity for all i=1, . . . , and N can be calculated as, for example, [(r.sub.i).sup.−1](A.sub.i).

[0199] At the end of the main calculation process, the information identifying section 244 identifies, among the points of similarities ([<x, y.sub.1>]G, . . . , and [<x, y.sub.N>]G) calculated in step B18, a point of similarity falling within a point acceptable range ([θ.sub.i]G, . . . , and [θτ]G) corresponding to a predefined acceptable range (θ.sub.1, . . . , and θ.sub.τ) (step B19).

[0200] This concrete example describes the example in which the similarity calculating apparatus 230 orders N concealed similarities to be transmitted to the decryption apparatus 220 in an index-based order of the registration information and transmits the resultant concealed similarities in step B13, but the similarity calculating apparatus 230 may assign a new identifier to each of the concealed similarities, shuffle the concealed similarities, and transmit the resultant concealed similarities to the decryption apparatus 220. At this time, the similarity calculating apparatus 230 may further give correspondences of two types of identifiers to the information identifying apparatus 240 so that the information identifying apparatus 240 can determine an identifier of the registration information that the information identifying apparatus 240 desires to identify.

[Description of Effect]

[0201] An effect of the present example embodiment described above is, similar to the first example embodiment, that the information matching securely using the biometric information can be realized with the cost less than that of the case of using an additive homomorphic public key cryptosystem. This is because in the concealment of the matching information in step B5, the concealment is performed by the linear conversion instead of a homomorphic operation of an additive homomorphic public key cryptosystem. The linear conversion, rather than the general concealment, is applied to allow the concealed transformed similarities and the transformed similarities to be calculated in steps B12 and B15.

[0202] Furthermore, the present example embodiment has an effect that the present example embodiment can be executed without leaking the value of the similarity to the decryption apparatus 220, even in a case that the decryption apparatus 220 has information related to a random number other than the main random number, such as a case that the concealment apparatus 210 and the decryption apparatus 220 are mounted on the same apparatus. This is because the decryption apparatus 220 acquires the similarity that is transformed based on the transformation key generated by the similarity calculating apparatus 230.

Third Example Embodiment

[Description of Configuration]

[0203] FIG. 6 is a block diagram illustrating a configuration of an information matching system 300 according to a third example embodiment. The information matching system 300 includes a concealment apparatus 310, a decryption apparatus 320, a similarity calculating apparatus 330, and an information identifying apparatus 340. However, the apparatuses included in the information matching system 300 may be configured as separate apparatuses, or may be adequately mounted on an identical apparatus as usage. For example, the information matching system 300 can be realized as a client-server system by separately mounting the concealment apparatus 310 and the decryption apparatus 320 on a client, and the similarity calculating apparatus 330 and the information identifying apparatus 340 on a server.

[0204] The apparatuses illustrated in FIG. 6 (the concealment apparatus 310, the decryption apparatus 320, the similarity calculating apparatus 330, and the information identifying apparatus 340) are connected in a wired or wireless manner and configured to be communicable with each other.

[0205] The concealment apparatus 310 includes

a matching information acquiring section 311 that acquires matching information,
a preliminary random number acquiring section 312 that acquires random numbers used for preliminary calculation,
a main random number acquiring section 313 that acquires random numbers used for main calculation,
a main random number transmitting section 314 that transmits the main random numbers acquired by the main random number acquiring section 313,
a random number concealment section 315 that conceals the random numbers acquired by the preliminary random number acquiring section 312,
a matching information concealment section 316 that conceals the matching information acquired by the matching information acquiring section 311 using the random numbers
acquired by the main random number acquiring section 313,
a concealed random number transmitting section 317 that transmits the concealed random numbers generated by the random number concealment section 315, and
a concealed matching information transmitting section 318 that transmits the concealed matching information generated by the matching information concealment section 316.

[0206] The decryption apparatus 320 includes

a main random number receiving section 321 that receives the main random numbers,
a first concealed similarity receiving section 322 that receives a first concealed similarity,
a second concealed similarity receiving section 323 that receives a second concealed similarity,
a decrypting section 324 that calculates a similarity from the main random numbers received by the main random number receiving section 321, the first concealed similarity received by the first concealed similarity receiving section 322, and the second concealed similarity received by the second concealed similarity receiving section 323, and
a similarity transmitting section 325 that transmits the similarity calculated by the decrypting section 324.

[0207] The similarity calculating apparatus 330 includes

a concealed random number receiving section 331 that receives the concealed random numbers,
a concealed matching information receiving section 332 that receives the concealed matching information,
a registration information acquiring section 333 that acquires registration information,
a first concealed similarity calculating section 336 that calculates the first concealed similarity from the concealed random numbers received by the concealed random number receiving section 331 and the registration information received by the registration information acquiring section 333,
a second concealed similarity calculating section 337 that calculates the second concealed similarity from the concealed matching information received by the concealed matching information receiving section 332 and the registration information received by the registration information acquiring section 333,
a first concealed similarity transmitting section 338 that transmits the first concealed similarity calculated by the first concealed similarity calculating section 336, and
a second concealed similarity transmitting section 339 that transmits the second concealed similarity calculated by the second concealed similarity calculating section 337.

[0208] The information identifying apparatus 340 includes

a similarity receiving section 342 that receives the similarity, and
an information identifying section 344 that identifies information using the similarity received by the similarity receiving section 342.

[Description of Operation]

[0209] Next, with reference to FIGS. 7 and 8, an entire operation of the information matching system 300 according to the present example embodiment will be described. The processes performed in the information matching system 300 can be divided into two processes, a preliminary calculation process and a main calculation process. Hereinafter, each of operation examples of the processes will be descried. FIG. 7 is a flow diagram illustrating the preliminary calculation process of the information matching system 300. The preliminary calculation process is performed as described below by the concealment apparatus 310, the decryption apparatus 320, and the similarity calculating apparatus 330.

[0210] First, the preliminary random number acquiring section 312 in the concealment apparatus 310 acquires preliminary random numbers which are the random numbers used for the preliminary calculation process (step C1). Note that the random numbers may be acquired in any way. For example, the random numbers may be generated using a random number generating function that the concealment apparatus 310 has therein, or random numbers generated outside the concealment apparatus 310 may be acquired from an external apparatus.

[0211] Next, the random number concealment section 315 conceals the preliminary random numbers acquired in step C1 to generate concealed random numbers (step C2).

[0212] Next, the concealed random number transmitting section 317 transmits the concealed random numbers generated in step C2 to the similarity calculating apparatus 330 (step C3).

[0213] Next, the concealed random number receiving section 331 in the similarity calculating apparatus 330 receives the concealed random numbers from the concealment apparatus 310 (step C4).

[0214] Next, the registration information acquiring section 333 acquires registration information (step C5). The registration information may be stored anywhere. For example, a database storing the registration information may be included in the similarity calculating apparatus 330, or the registration information may be stored in an external apparatus connected with the similarity calculating apparatus 330. The registration information may include a plurality of pieces of information. In a case that a plurality of pieces of information are included, each piece of registration information is assigned with a specific identifier.

[0215] Next, the first concealed similarity calculating section 336 calculates a first concealed similarity from the concealed random numbers received in step C4 and the registration information acquired in step C5 (step C6).

[0216] Note that the first concealed similarity is a concealed form of the similarity between the concealed random numbers and the registration information. In the case that the registration information includes a plurality of pieces of information, the number of the calculated first concealed similarities is the same as the number of the plurality of pieces of information. Each first concealed similarity is assigned with a specific identifier, and which registration information the first concealed similarity corresponds to can be identified by the identifier. Note that the identifier assigned to each first concealed similarity may be the same as the identifier assigned to each piece of registration information.

[0217] Next, the first concealed similarity transmitting section 338 transmits the first concealed similarity calculated in step C6 to the decryption apparatus 320 (step C7).

[0218] Finally, the first concealed similarity receiving section 322 in the decryption apparatus 320 receives the first concealed similarity from the similarity calculating apparatus 330 (step C8).

[0219] Note that a procedure of the above process is an example. For example, the order of steps C4 and C5 may be exchanged.

[0220] FIG. 8 is a flow diagram illustrating the main calculation process of the information matching system 300. The main calculation process is performed as described below by the concealment apparatus 310, the decryption apparatus 320, the similarity calculating apparatus 330, and the information identifying apparatus 340.

[0221] First, the matching information acquiring section 311 in the concealment apparatus 310 acquires matching information (step D1). Note that the matching information may be acquired in any way. For example, the matching information may be generated using a matching information acquiring function that the concealment apparatus 310 has therein, or matching information generated outside the concealment apparatus 310 may be acquired from an external apparatus.

[0222] Next, the main random number acquiring section 313 acquires main random numbers which are random numbers used for the main calculation (step D2). Note that the random numbers may be acquired in any way. For example, the random numbers may be generated using a random number generating function that the concealment apparatus 310 has therein, or random numbers generated outside the concealment apparatus 310 may be acquired from an external apparatus.

[0223] Next, the main random number transmitting section 314 transmits the main random numbers acquired in step D2 to the decryption apparatus 320 (step D3).

[0224] Next, the main random number receiving section 321 in the decryption apparatus 320 receives the main random numbers from the concealment apparatus 310 (step D4).

[0225] Next, the matching information concealment section 316 conceals the matching information acquired in step D1 by a linear conversion using the preliminary random numbers acquired in step C1 and the main random numbers acquired in step D2 to generate concealed matching information (step D5).

[0226] Next, the concealed matching information transmitting section 318 transmits the concealed matching information generated in step D5 to the similarity calculating apparatus 330 (step D6).

[0227] Next, the concealed matching information receiving section 332 in the similarity calculating apparatus 330 receives the concealed matching information from the concealment apparatus 310 (step D7).

[0228] Next, the second concealed similarity calculating section 337 calculates a second concealed similarity from the registration information acquired in step C5 and the concealed matching information received in step D7 (step D8).

[0229] Note that the second concealed similarity is a concealed form of the similarity between the concealed matching information and the registration information. In the case that the registration information includes a plurality of pieces of information, the number of the calculated second concealed similarities is the same as the number of the plurality of pieces of information. Each second concealed similarity is assigned with a specific identifier, and which registration information the second concealed similarity corresponds to can be identified by the identifier. Note that the identifier assigned to each second concealed similarity may be the same as the identifier assigned to each piece of registration information.

[0230] Next, the second concealed similarity transmitting section 339 transmits the second concealed similarity calculated in step D8 to the decryption apparatus 320 (step D9).

[0231] Next, the second concealed similarity receiving section 323 in the decryption apparatus 320 receives the second concealed similarity from the similarity calculating apparatus 330 (step D10).

[0232] Next, the decrypting section 324 calculates a similarity from the first concealed similarity received in step C8 and the second concealed similarity received in step D10 using the main random numbers received in step D4 (step D11).

[0233] Note that the similarity is a similarity between the matching information and the registration information. In the case that the registration information includes a plurality of pieces of information, the number of the calculated similarities is the same as the number of the plurality of pieces of information. Each similarity is assigned with a specific identifier, and which registration information the similarity corresponds to can be identified by the identifier. Note that the identifier assigned to each similarity may be the same as the identifier assigned to each piece of registration information.

[0234] Next, the similarity transmitting section 325 transmits the similarity calculated in step D11 to the information identifying apparatus 340 (step D12).

[0235] Next, the similarity receiving section 342 in the information identifying apparatus 340 receives the similarity from the decryption apparatus 320 (step D13).

[0236] Finally, the information identifying section 344 identifies, among the similarities received in step D13, a similarity falling within a predefined acceptable range to identify registration information that is recognized to be sufficiently similar to the matching information (step D14).

[0237] Note that in a case that it is not necessary to identify the registration information recognized to be sufficiently similar to the matching information, but it is desired to check whether the registration information recognized to be sufficiently similar to the matching information is present or not, such processing may be made.

Concrete Example 1 According to Third Example Embodiment

[0238] Next, a concrete example 1 of the operation of the information matching system 300 according to the present example embodiment will be described.

[0239] In this concrete example, a case that a group on elliptic curve is used will be described. Assume that a group with an order of a κ-bit prime number q on an elliptic curve E and a generator G of the group are published.

[0240] In this concrete example, a case that vectors (with a dimension number of D) are used for the matching information and the registration information will be described. Furthermore, a case that the similarity between the matching information and the registration information is calculated by use of the inner product of the two vectors will be described. Assume a case that the matching information and the registration information are determined to be sufficiently similar to each other is a case that the similarity calculated by use of the inner product of the matching information and the registration information matches any one of T values θ.sub.1, . . . , and θ.sub.τ.

[0241] In this concrete example, assume that pieces of information of N persons are registered in the database, and the pieces of the registration information of N persons are assigned with the identifiers of 1 to N.

However, a target of the present example embodiment is not limited to such cases above.

[0242] In the preliminary calculation process, first, the preliminary random number acquiring section 312 in the concealment apparatus 310 acquires, as preliminary random numbers, D κ-bit random numbers s.sub.1, . . . , and s.sub.D (step C1). Hereinafter, the preliminary random numbers are expressed as a vector:

s=(s.sub.1, . . . , and s.sub.D).

[0243] Next, the random number concealment section 315 generates, as concealed random numbers,

S.sub.1=[s.sub.1]G, . . . , and S.sub.D=[s.sub.D]G

(step C2).

[0244] Next, the concealed random number transmitting section 317 transmits the concealed random numbers (S.sub.1, . . . , and S.sub.D) generated in step C2 to the similarity calculating apparatus 330 (step C3).

[0245] Next, the concealed random number receiving section 331 in the similarity calculating apparatus 330 receives the concealed random numbers (S.sub.1, . . . , and S.sub.D) from the concealment apparatus 310 (step C4).

[0246] Next, the registration information acquiring section 333 acquires, as the registration information, N D-dimensional vectors y.sub.1, . . . , and y.sub.N (where y.sub.i=(y.sub.i, 1, . . . , and y.sub.i, D) for all i=1, . . . , and N) (step C5).

[0247] Next, the first concealed similarity calculating section 336 calculates, as first concealed similarities for all i=1, . . . , and N,

U.sub.i=[<s,y.sub.i>]G

from the concealed random numbers (S.sub.1, . . . , and S.sub.D) received in step C4 and
the registration information y.sub.i= . . . , and y.sub.i, D) for all i=1, . . . , and N acquired in step C5 (step C6).
Note that the first concealed transformed similarity for all i=1, . . . , and N can be calculated by, for example,

([y.sub.i,1]S.sub.1+ . . . +[y.sub.i,D]S.sub.D).

[0248] Next, the first concealed similarity transmitting section 338 transmits the first concealed similarities (U.sub.1, . . . , and U.sub.N) calculated in step C6 to the decryption apparatus 320 (step C7).

[0249] In the preliminary calculation process, finally, the first concealed similarity receiving section 322 in the decryption apparatus 320 receives the first concealed similarities (U.sub.1, . . . , and U.sub.N) from the similarity calculating apparatus 330 (step C8).

[0250] In the main calculation process, first, the matching information acquiring section 311 in the concealment apparatus 310 acquires, as the matching information, a D-dimensional vector:

x=(x.sub.1, . . . , and x.sub.D)

(step D1).

[0251] Next, the main random number acquiring section 313 acquires, as main random numbers, κ-bit random numbers a and b (step D2).

[0252] Next, the main random number transmitting section 314 transmits the main random numbers (a, b) generated in step D2 to the decryption apparatus 320 (step D3).

[0253] Next, the main random number receiving section 321 in the decryption apparatus 320 receives the main random numbers (a, b) from the concealment apparatus 310 (step D4).

[0254] Next, the matching information concealment section 316 in the concealment apparatus 310 calculates

z.sub.j=ax.sub.j−bs.sub.j

for all j=1, . . . , and D,
from the preliminary random number s=(s.sub.1, . . . , and so) acquired in step C1,
the matching information x=(x.sub.1, . . . , and x.sub.D) acquired in step D1, and
the main random numbers a and b acquired in step D2,
to obtain the concealed matching information z=(z.sub.1, . . . , and z.sub.D) (step D5).

[0255] Next, the concealed matching information transmitting section 318 transmits the concealed matching information z generated in step D5 to the similarity calculating apparatus 330 (step D6).

[0256] Next, the concealed matching information receiving section 332 in the similarity calculating apparatus 330 receives the concealed matching information z from the concealment apparatus 310 (step D7).

[0257] Next, the second concealed similarity calculating section 337 calculates, as second concealed similarities for all i=1, . . . , and N,

W.sub.i=[<z,y.sub.i>]G

from the registration information y.sub.1, . . . , and y.sub.N (where y.sub.i=(y.sub.i, 1, . . . , and y.sub.i, D) for all i=1, . . . , and N) acquired in step C5, and
the concealed matching information z=(z.sub.1, . . . , and z.sub.D) received in step D7 (step D8).
Note that because z.sub.j=ax.sub.j−bs.sub.j is satisfied for all j=1, . . . , and D, the second concealed similarities for all i=1, . . . , and N may be expressed as

W.sub.i=[(a<x,y.sub.i>−b<s,y.sub.i>)]G.

[0258] Next, the second concealed similarity transmitting section 339 transmits the second concealed similarities (W.sub.1, . . . , and W.sub.N) calculated in step D8 to the decryption apparatus 320 (step D9).

[0259] Next, the second concealed similarity receiving section 323 in the decryption apparatus 320 receives the second concealed similarities (W.sub.1, . . . , and W.sub.N) from the similarity calculating apparatus 330 (step D10).

[0260] Next, the decrypting section 324 calculates, as points of similarities for all i=1, . . . , and N,

[<x,y.sub.i>]G

from the first concealed similarities (U.sub.1, . . . , and U.sub.N) received in step C8,
the main random numbers a and b received in step D4, and
the second concealed transformed similarities (W.sub.1, . . . , and W.sub.N) received in step D10 (step D11).
Note that the point of similarity for all i=1, . . . , and N can be calculated as, for example,

[a.sup.−1]([b]U.sub.i+W.sub.i).

[0261] Next, the similarity transmitting section 325 transmits the points of similarities ([<x, y.sub.1>]G, . . . , and [<x, y.sub.N>]G) calculated in step D11 to the information identifying apparatus 340 (step D12).

[0262] Next, the similarity receiving section 342 in the information identifying apparatus 340 receives the points of similarities ([<x, y.sub.1>]G, . . . , and [<x, y.sub.N>]G) from the decryption apparatus 320 (step D13).

[0263] At the end of the main calculation process, the information identifying section 344 identifies, among the points of similarities ([<x, y.sub.1>]G, . . . , and [<x, y.sub.N>]G) received in step D13, a point of similarity falling within a point acceptable range ([θ.sub.1]G, . . . , and [θ.sub.τ]G) corresponding to a predefined acceptable range (θ.sub.1, . . . , and θ.sub.τ) (step D14).

[0264] Note that in this concrete example, although the points of similarities are calculated in step D11 and the information is identified from the points of similarities in step D14, a similarity may be further calculated from the points of similarities in step D11, or a similarity falling within the acceptable range may be further identified in step D11, and an identifier associated with the similarity identified may be transmitted in step D12.

[0265] This concrete example describes the example in which the similarity calculating apparatus 330 orders N concealed similarities to be transmitted to the decryption apparatus 320 in an index-based order of the registration information and transmits the resultant concealed similarities in step D9, but the similarity calculating apparatus 330 may assign a new identifier to each of the concealed similarities, shuffle the concealed similarities, and transmit the resultant concealed similarities to the decryption apparatus 320. At this time, the similarity calculating apparatus 330 may further give correspondences of two types of identifiers to the information identifying apparatus 340 so that the information identifying apparatus 340 can determine an identifier of the registration information that the information identifying apparatus 140 desires to identify.

Concrete Example 2 According to Third Example Embodiment

[0266] Next, a concrete example 2 of the operation of the information matching system 300 according to the present example embodiment will be described.

[0267] In this concrete example also, although a description is given assuming a case similar to the case of the concrete example 1 according to the third example embodiment, a target of the present example embodiment is not limited to these cases.

[0268] In the preliminary calculation process, first, the preliminary random number acquiring section 312 in the concealment apparatus 310 acquires, as preliminary random numbers, 2D κ-bit random numbers s.sub.1, . . . , and s.sub.D, t.sub.1, . . . , and t.sub.D (step C1). Hereinafter, the preliminary random numbers are expressed as vectors:

s=(s.sub.1, . . . , and s.sub.D) and t=(t.sub.1, . . . , and t.sub.D).

[0269] Next, the random number concealment section 315 generates, as concealed random numbers,

S.sub.1=[s.sub.1]G, . . . , and S.sub.D=[s.sub.D]G,T.sub.1=[t.sub.1]G, . . . , and T.sub.D=[t.sub.D]G

(step C2).

[0270] Next, the concealed random number transmitting section 317 transmits the concealed random numbers (S.sub.1, . . . , and S.sub.D, T.sub.1, . . . , and T.sub.D) generated in step C2 to the similarity calculating apparatus 330 (step C3).

[0271] Next, the concealed random number receiving section 331 in the similarity calculating apparatus 330 receives the concealed random numbers (S.sub.1, . . . , and S.sub.D, T.sub.1, . . . , and T.sub.D) from the concealment apparatus 310 (step C4).

[0272] Next, the registration information acquiring section 333 acquires, as the registration information, N D-dimensional vectors y.sub.1, . . . , and y.sub.N (where y.sub.i=(y.sub.i, 1, . . . , and y.sub.i, D) for all i=1, . . . , and N) (step C5).

[0273] Next, the first concealed similarity calculating section 336 calculates, as first concealed similarities for all i=1, . . . , and N,

U.sub.i=[<s,y.sub.i>]G and U.sub.i=[<t,y.sub.i>]G

from the concealed random numbers (S.sub.1, . . . , and S.sub.D, T.sub.1, . . . , and T.sub.D) received in step C4, and
the registration information y.sub.i=(y.sub.i, 1, . . . , and y.sub.i, D) for all i=1, . . . , and N acquired in step C5 (step C6).
Note that the first concealed similarity for all i=1, . . . , and N can be calculated by, for example,

U.sub.i=[y.sub.i,1]S.sub.1+ . . . +[y.sub.i,D]S.sub.D and

V.sub.i=[y.sub.i,1]T.sub.1+ . . . +[y.sub.i,D]T.sub.D.

[0274] Next, the first concealed similarity transmitting section 338 transmits the first concealed similarities (U.sub.1, . . . , and U.sub.N, V.sub.1, . . . , and V.sub.N) calculated in step C6 to the decryption apparatus 320 (step C7).

[0275] In the preliminary calculation process, finally, the first concealed similarity receiving section 322 in the decryption apparatus 320 receives the first concealed similarities (U.sub.1, . . . , and U.sub.N, V.sub.1, . . . , and V.sub.N) from the similarity calculating apparatus 330 (step C8).

[0276] In the main calculation process, first, the matching information acquiring section 311 in the concealment apparatus 310 acquires, as the matching information, a D-dimensional vector:

x=(x.sub.1, . . . , and x.sub.D)

(step D1).

[0277] Next, the main random number acquiring section 313 acquires, as main random numbers, κ-bit random number b (step D2).

[0278] Next, the main random number transmitting section 314 transmits the main random number b generated in step D2 to the decryption apparatus 320 (step D3).

[0279] Next, the main random number receiving section 321 in the decryption apparatus 320 receives the main random number b from the concealment apparatus 310 (step D4).

[0280] Next, the matching information concealment section 316 in the concealment apparatus 310 calculates

z.sub.j=x.sub.j−bs.sub.j−t.sub.j

for all j=1, . . . , and D,
from the preliminary random number s=(s.sub.1, . . . , and s.sub.D, t.sub.1, . . . , and t.sub.D) acquired in step C1,
the matching information x=(x.sub.1, . . . , and x.sub.D) acquired in step D1, and
the main random number b acquired in step D2,
to obtain the concealed matching information z=(z.sub.1, . . . , and z.sub.D) (step D5).

[0281] Next, the concealed matching information transmitting section 318 transmits the concealed matching information z generated in step D5 to the similarity calculating apparatus 330 (step D6).

[0282] Next, the concealed matching information receiving section 332 in the similarity calculating apparatus 330 receives the concealed matching information z from the concealment apparatus 310 (step D7).

[0283] Next, the second concealed similarity calculating section 337 calculates, as second concealed similarities for all i=1, . . . , and N,

W.sub.i=[<z,y.sub.i>]G

from the registration information y.sub.1, . . . , and y.sub.N (where y=(y.sub.1, 1, . . . , and y.sub.i, D) for all i=1, . . . , and N) acquired in step C5 and
the concealed matching information z=(z.sub.1, . . . , and z.sub.D) received in step D7 (step D8).
Note that because z.sub.j=z.sub.j−bs.sub.j−t.sub.j is satisfied for all j=1, . . . , and D, the second concealed similarities for all i=1, . . . , and N may be expressed as

W.sub.i=[<x,y.sub.i>−b<s,y.sub.i>−<t,y.sub.i>]G.

[0284] Next, the second concealed similarity transmitting section 339 transmits the second concealed similarities (W.sub.1, . . . , and W.sub.N) calculated in step D8 to the decryption apparatus 320 (step D9).

[0285] Next, the second concealed similarity receiving section 323 in the decryption apparatus 320 receives the second concealed similarities (W.sub.1, . . . , and W.sub.N) from the similarity calculating apparatus 330 (step D10).

[0286] Next, the decrypting section 324 calculates, as points of similarities for all i=1, . . . , and N,

[<x,y.sub.i>]G

from the first concealed similarities (U.sub.1, . . . , and U.sub.N, V.sub.1, . . . , and V.sub.N) received in step C8,
the main random number b received in step D4, and
the second concealed similarities (W.sub.1, . . . , and W.sub.N) received in step D10 (step D11).
Note that the point of similarity for all i=1, . . . , and N can be calculated as, for example,

[b]U.sub.i+V.sub.i+W.sub.i.

[0287] Next, the similarity transmitting section 325 transmits the points of similarities ([<x, y.sub.1>]G, . . . , and [<x, y.sub.N>]G) calculated in step D11 to the information identifying apparatus 340 (step D12).

[0288] Next, the similarity receiving section 342 in the information identifying apparatus 340 receives the points of similarities ([<x, y.sub.1>]G, . . . , and [<x, y.sub.N>]G) from the decryption apparatus 320 (step D13).

[0289] At the end of the main calculation process, the information identifying section 344 identifies, among the points of similarities ([<x, y.sub.1>]G, . . . , and [<x, y.sub.N>]G) received in step D13, a point of similarity falling within a point acceptable range ([θ.sub.1]G, . . . , and [θ.sub.τ]G) corresponding to a predefined acceptable range (θ.sub.1, . . . , and θ.sub.τ) (step D14).

[0290] Note that in this concrete example, although the points of similarities are calculated in step D11 and the information is identified from the points of similarities in step D14, a similarity may be further calculated from the points of similarities in step D11, or a similarity falling within the acceptable range may be further identified in step D11, and an identifier associated with the similarity identified may be transmitted in step D12.

[0291] This concrete example describes the example in which the similarity calculating apparatus 330 orders N concealed similarities to be transmitted to the decryption apparatus 320 in an index-based order of the registration information and transmits the resultant concealed similarities in step D9, but the similarity calculating apparatus 330 may assign a new identifier to each of the concealed similarities, shuffle the concealed similarities, and transmit the resultant concealed similarities to the decryption apparatus 320. At this time, the similarity calculating apparatus 330 may further give correspondences of two types of identifiers to the information identifying apparatus 340 so that the information identifying apparatus 340 can determine an identifier of the registration information that the information identifying apparatus 340 desires to identify.

[Description of Effect]

[0292] An effect of the present example embodiment described above is, similar to the first and second example embodiments, that the information matching securely using the biometric information can be realized with the cost less than that of the case of using an additive homomorphic public key cryptosystem. This is because in the concealment of the matching information in step D5, the concealment is performed by the linear conversion instead of a homomorphic operation of an additive homomorphic public key cryptosystem. The linear conversion, rather than the general concealment, is applied to allow the second concealed similarities and the similarities to be calculated in steps D8 and D11.

[0293] Furthermore, the present example embodiment has also an effect that the cost taken after acquiring the matching information can be reduced. This is because in the present example embodiment, a process not depending on the matching information is the preliminary calculation process, and thus, such process can be executed before acquiring the matching information.

Fourth Example Embodiment

[Description of Configuration]

[0294] FIG. 9 is a block diagram illustrating a configuration of an information matching system 400 according to a fourth example embodiment. The information matching system 400 includes a concealment apparatus 410, a decryption apparatus 420, a similarity calculating apparatus 430, and an information identifying apparatus 440. However, the apparatuses included in the information matching system 400 may be configured as separate apparatuses, or may be adequately mounted on an identical apparatus as usage. For example, the information matching system 400 can be realized as a client-server system by separately mounting the concealment apparatus 410 and the decryption apparatus 420 on a client, and the similarity calculating apparatus 430 and the information identifying apparatus 440 on a server.

[0295] The apparatuses illustrated in FIG. 9 (the concealment apparatus 410, the decryption apparatus 420, the similarity calculating apparatus 430, and the information identifying apparatus 440) are connected in a wired or wireless manner and configured to be communicable with each other.

[0296] The concealment apparatus 410 includes

a matching information acquiring section 411 that acquires matching information,
a preliminary random number acquiring section 412 that acquires random numbers used for preliminary calculation,
a main random number acquiring section 413 that acquires random numbers used for main calculation,
a main random number transmitting section 414 that transmits the main random numbers acquired by the main random number acquiring section 413,
a random number concealment section 415 that conceals the random numbers acquired by the preliminary random number acquiring section 412,
a matching information concealment section 416 that conceals the matching information acquired by the matching information acquiring section 411 using the random numbers acquired by the main random number acquiring section 413,
a concealed random number transmitting section 417 that transmits the concealed random numbers generated by the random number concealment section 415, and
a concealed matching information transmitting section 418 that transmits the concealed matching information generated by the matching information concealment section 416.

[0297] The decryption apparatus 420 includes

a main random number receiving section 421 that receives the main random numbers,
a first concealed transformed similarity receiving section 422 that receives a first concealed transformed similarity,
a second concealed transformed similarity receiving section 423 that receives a second concealed transformed similarity,
a decrypting section 424 that calculates a transformed similarity from the main random numbers received by the main random number receiving section 421, the first concealed transformed similarity received by the first concealed transformed similarity receiving section 422, and the second concealed transformed similarity received by the second concealed transformed similarity receiving section 423, and
a similarity transmitting section 425 that transmits the transformed similarity calculated by the decrypting section 424.

[0298] The similarity calculating apparatus 430 includes

a concealed random number receiving section 431 that receives the concealed random numbers,
a concealed matching information receiving section 432 that receives the concealed matching information,
a registration information acquiring section 433 that acquires registration information,
a transformation key generating section 434 that generates a transformation key and an inverse transformation key,
an inverse transformation key transmitting section 435 that transmits the inverse transformation key generated by the transformation key generating section 434,
a first concealed transformed similarity calculating section 436 that calculates a first concealed transformed similarity from the concealed random numbers received by the concealed random number receiving section 431, the registration information received by the registration information acquiring section 433, and the transformation key generated by the transformation key generating section 434,
a second concealed transformed similarity calculating section 437 that calculates a second concealed transformed similarity from the concealed matching information received by the concealed matching information receiving section 432, the registration information received by the registration information acquiring section 433, and the transformation key generated by the transformation key generating section 434,
a first concealed transformed similarity transmitting section 438 that transmits the first concealed transformed similarity calculated by the first concealed transformed similarity calculating section 436, and
a second concealed transformed similarity transmitting section 439 that transmits the second concealed transformed similarity calculated by the second concealed transformed similarity calculating section 437.

[0299] The information identifying apparatus 440 includes

an inverse transformation key receiving section 441 that receives an inverse transformation key,
a transformed similarity receiving section 442 that receives the transformed similarity,
an inverse transforming section 443 that inversely transforms the transformed similarity received by the transformed similarity receiving section 442 using the inverse transformation key generated by the transformation key generating section 434, and
an information identifying section 444 that identifies information using the similarity calculated by the inverse transforming section 443.

[Description of Operation]

[0300] Next, with reference to FIGS. 10 and 11, an entire operation of the information matching system 400 according to the present example embodiment will be described. The processes performed in the information matching system 400, similar to the information matching system 300, can be divided into two processes, a preliminary calculation process and a main calculation process. Hereinafter, each of operation examples of the processes will be descried.

[0301] FIG. 10 is a flow diagram illustrating the preliminary calculation process of the information matching system 400. The preliminary calculation process is performed as described below by the concealment apparatus 410, the decryption apparatus 420, and the similarity calculating apparatus 430.

[0302] First, the preliminary random number acquiring section 412 in the concealment apparatus 410 acquires preliminary random numbers which are the random numbers used for the preliminary calculation process (step E1). Note that the random numbers may be acquired in any way. For example, the random numbers may be generated using a random number generating function that the concealment apparatus 410 has therein, or random numbers generated outside the concealment apparatus 410 may be acquired from an external apparatus.

[0303] Next, the random number concealment section 415 conceals the preliminary random numbers acquired in step E1 to generate concealed random numbers (step E2).

[0304] Next, the concealed random number transmitting section 417 transmits the concealed random numbers generated in step E2 to the similarity calculating apparatus 430 (step E3).

[0305] Next, the concealed random number receiving section 431 in the similarity calculating apparatus 430 receives the concealed random numbers from the concealment apparatus 410 (step E4).

[0306] Next, the registration information acquiring section 433 acquires registration information (step E5). The registration information may be stored anywhere. For example, a database storing the registration information may be included in the similarity calculating apparatus 430, or the registration information may be stored in an external apparatus connected with the similarity calculating apparatus 430. The registration information may include a plurality of pieces of information. In a case that a plurality of pieces of information are included, each piece of registration information is assigned with a specific identifier.

[0307] Next, the transformation key generating section 434 acquires the random numbers to generate a transformation key and an inverse transformation key based on the random number (step E6). Note that the random numbers may be acquired in any way. For example, the random numbers may be generated using a random number generating function that the similarity calculating apparatus 430 has therein, or random numbers generated outside the similarity calculating apparatus 430 may be acquired from an external apparatus.

[0308] Next, the inverse transformation key transmitting section 435 transmits the inverse transformation key generated in step E6 to the information identifying apparatus 440 (step E7).

[0309] Next, the inverse transformation key receiving section 441 in the information identifying apparatus 440 receives the inverse transformation key from the similarity calculating apparatus 430 (step E8).

[0310] Next, the first concealed transformed similarity calculating section 436 in the similarity calculating apparatus 430 calculates a first concealed transformed similarity from the concealed random numbers received in step E4, the registration information acquired in step E5, and the transformation key generated in step E6 (step E9).

[0311] Note that the first concealed transformed similarity is a concealed form of a value which is a transformed form of the similarity between the concealed random number and the registration information using the transformation key. In the case that the registration information includes a plurality of pieces of information, the number of the calculated first concealed transformed similarities is the same as the number of the plurality of pieces of information. Each first concealed transformed similarity is assigned with a specific identifier, and which registration information the first concealed transformed similarity corresponds to can be identified by the identifier. Note that the identifier assigned to each first concealed transformed similarity may be the same as the identifier assigned to each piece of registration information.

[0312] Next, the first concealed transformed similarity transmitting section 438 transmits the first concealed transformed similarity calculated in step E9 to the decryption apparatus 420 (step E10).

[0313] Finally, the first concealed transformed similarity receiving section 422 in the decryption apparatus 420 receives the first concealed transformed similarity from the similarity calculating apparatus 430 (step E11).

[0314] Note that a procedure of the above process is an example. For example, the order of steps E4, E5, and step E6 may be exchanged.

[0315] FIG. 11 is a flow diagram illustrating the main calculation process of the information matching system 400. The main calculation process is performed as described below by the concealment apparatus 410, the decryption apparatus 420, the similarity calculating apparatus 430, and the information identifying apparatus 440.

[0316] First, the matching information acquiring section 411 in the concealment apparatus 410 acquires matching information (step F1). Note that the matching information may be acquired in any way. For example, the matching information may be generated using a matching information acquiring function that the concealment apparatus 410 has therein, or matching information generated outside the concealment apparatus 410 may be acquired from an external apparatus.

[0317] Next, the main random number acquiring section 413 acquires main random numbers which are random numbers used for the main calculation (step F2). Note that the random numbers may be acquired in any way. For example, the random numbers may be generated using a random number generating function that the concealment apparatus 410 has therein, or random numbers generated outside the concealment apparatus 410 may be acquired from an external apparatus.

[0318] Next, the main random number transmitting section 414 transmits the main random numbers generated in step F2 to the decryption apparatus 420 (step F3).

[0319] Next, the main random number receiving section 421 in the decryption apparatus 420 receives the main random numbers from the concealment apparatus 410 (step F4).

[0320] Next, the matching information concealment section 416 in the concealment apparatus 410 conceals the matching information acquired in step F1 by a linear conversion using the preliminary random numbers acquired in step E1 and the main random numbers acquired in step F2 to generate concealed matching information (step F5).

[0321] Next, the concealed matching information transmitting section 418 transmits the concealed matching information generated in step F5 to the similarity calculating apparatus 430 (step F6).

[0322] Next, the concealed matching information receiving section 432 in the similarity calculating apparatus 430 receives the concealed matching information from the concealment apparatus 410 (step F7).

[0323] Next, the second concealed transformed similarity calculating section 437 calculates a second concealed similarity from the registration information acquired in step E5, the transformation key generated in step E6, and the concealed matching information received in step F7 (step F8).

[0324] Note that the second concealed transformed similarity is a concealed form of a value which is a transformed form of the similarity between the concealed matching information and the registration information using the transformation key. In the case that the registration information includes a plurality of pieces of information, the number of the calculated second concealed transformed similarities is the same as the number of the plurality of pieces of information. Each second concealed transformed similarity is assigned with a specific identifier, and which registration information the second concealed transformed similarity corresponds to can be identified by the identifier. Note that the identifier assigned to each second concealed transformed similarity may be the same as the identifier assigned to each piece of registration information.

[0325] Next, the second concealed transformed similarity transmitting section 439 transmits the second concealed transformed similarity calculated in step F8 to the decryption apparatus 420 (step F9).

[0326] Next, the second concealed transformed similarity receiving section 423 in the decryption apparatus 420 receives the second concealed transformed similarity from the similarity calculating apparatus 430 (step F10).

[0327] Next, the decrypting section 424 calculates a transformed similarity from the first concealed transformed similarity received in step E11 and the second concealed transformed similarity received in step F10 using the main random numbers received in step F4 (step F11).

[0328] Note that the transformed similarity is a transformed form of the similarity between the matching information and the registration information using the transformation key. In the case that the registration information includes a plurality of pieces of information, the number of the calculated transformed similarities is the same as the number of the plurality of pieces of information. Each transformed similarity is assigned with a specific identifier, and which registration information the transformed similarity corresponds to can be identified by the identifier. Note that the identifier assigned to each transformed similarity may be the same as the identifier assigned to each piece of registration information.

[0329] Next, the similarity transmitting section 425 transmits the transformed similarity calculated in step F11 to the information identifying apparatus 440 (step F12).

[0330] Next, the transformed similarity receiving section 442 in the information identifying apparatus 440 receives the transformed similarity from the decryption apparatus 420 (step F13).

[0331] Next, the inverse transforming section 443 inversely transforms the transformed similarity received in step F13 using the inverse transformation key received in step E8 to calculate a similarity (step F14).

[0332] Note that the similarity is a similarity between the matching information and the registration information. In the case that the registration information includes a plurality of pieces of information, the number of the calculated similarities is the same as the number of the plurality of pieces of information. Each similarity is assigned with a specific identifier, and which registration information the similarity corresponds to can be identified by the identifier. Note that the identifier assigned to each similarity may be the same as the identifier assigned to each piece of registration information.

[0333] Finally, the information identifying section 444 identifies, among the similarities calculated in step F14, a similarity falling within a predefined acceptable range to identify registration information that is recognized to be sufficiently similar to the matching information (step F15).

[0334] Note that in a case that it is not necessary to identify the registration information recognized to be sufficiently similar to the matching information, but it is desired to check whether the registration information recognized to be sufficiently similar to the matching information is present or not, such processing may be made.

Concrete Example 1 According to Fourth Example Embodiment

[0335] Next, a concrete example 1 of the operation of the information matching system 400 according to the present example embodiment will be described.

[0336] In this concrete example, a case that a group on elliptic curve is used will be described. Assume that a group with an order of a κ-bit prime number q on an elliptic curve E and a generator G of the group are published.

[0337] In this concrete example, a case that vectors (with a dimension number of D) are used for the matching information and the registration information will be described. Furthermore, a case that the similarity between the matching information and the registration information is calculated by use of the inner product of the two vectors will be described. Assume a case that the matching information and the registration information are determined to be sufficiently similar to each other is a case that the similarity calculated by use of the inner product of the matching information and the registration information matches any one of T values θ.sub.1, . . . , and θ.sub.τ.

[0338] In this concrete example, assume that pieces of information of N persons are registered in the database, and the pieces of the registration information of N persons are assigned with the identifiers of 1 to N.

However, a target of the present example embodiment is not limited to such cases above.

[0339] In the preliminary calculation process, first, the preliminary random number acquiring section 412 in the concealment apparatus 410 acquires, as preliminary random numbers, D κ-bit random numbers s.sub.1, . . . , and s.sub.D (step E1). Hereinafter, the preliminary random numbers are expressed as a vector:

s=(s.sub.1, . . . , and s.sub.D).

[0340] Next, the random number concealment section 415 generates, as concealed random numbers,

S.sub.1=[s.sub.1]G, . . . , and S.sub.D=[s.sub.D]G

(step E2).

[0341] Next, the concealed random number transmitting section 417 transmits the concealed random numbers (S.sub.1, . . . , and S.sub.D) generated in step E2 to the similarity calculating apparatus 430 (step E3).

[0342] Next, the concealed random number receiving section 431 in the similarity calculating apparatus 430 receives the concealed random numbers (S.sub.1, . . . , and S.sub.D) from the concealment apparatus 410 (step E4).

[0343] Next, the registration information acquiring section 433 acquires, as the registration information, N D-dimensional vectors y.sub.1, . . . , and y.sub.N (where y.sub.i=(y.sub.i, 1, . . . , and y.sub.i, D) for all i=1, . . . , and N) (step E5).

[0344] Next, the transformation key generating section 434 acquires D κ-bit random numbers r.sub.1, . . . , and r.sub.N to obtain the transformation keys (r.sub.1, . . . , and r.sub.N) and the inverse transformation keys ((r.sub.1).sup.−1, . . . , and (r.sub.N).sup.−1) (step E6).

[0345] Next, the inverse transformation key transmitting section 435 transmits the inverse transformation keys ((r.sub.1).sup.−1, . . . , and (r.sub.N).sup.−1) generated in step E6 to the information identifying apparatus 440 (step E7).

[0346] Next, the inverse transformation key receiving section 441 in the information identifying apparatus 440 receives the inverse transformation keys ((r.sub.1).sup.−1, . . . , and (r.sub.N).sup.−1) from the similarity calculating apparatus 430 (step E8).

[0347] Next, the first concealed transformed similarity calculating section 436 in the similarity calculating apparatus 430 calculates, as first concealed transformed similarities for all i=1, . . . , and N,

U.sub.i=[r.sub.i<s,y.sub.i>]G

from the concealed random numbers (S.sub.1, . . . , and S.sub.D) received in step E4,
the registration information y.sub.1=(y.sub.i, 1, . . . , and y.sub.i, D) for all i=1, . . . , and N acquired in step E5, and
the transformation keys r.sub.i for all i=1, . . . , and N generated in step E6 (step E9).
Note that the first concealed transformed similarity for all i=1, . . . , and N can be calculated by, for example,

[r.sub.i]([y.sub.i,1]S.sub.1+ . . . +[y.sub.i,D]S.sub.D).

[0348] Next, the first concealed transformed similarity transmitting section 438 transmits the first concealed transformed similarities (U.sub.1, . . . , and U.sub.N) calculated in step E9 to the decryption apparatus 420 (step E10).

[0349] In the preliminary calculation process, finally, the first concealed transformed similarity receiving section 422 in the decryption apparatus 420 receives the first concealed transformed similarities (U.sub.1, . . . , and U.sub.N) from the similarity calculating apparatus 430 (step E11).

[0350] In the main calculation process, first, the matching information acquiring section 411 in the concealment apparatus 410 acquires, as the matching information, a D-dimensional vector:

x=(x.sub.1, . . . , and x.sub.D)

(step F1).

[0351] Next, the main random number acquiring section 413 acquires, as main random numbers, κ-bit random numbers a and b (step F2).

[0352] Next, the main random number transmitting section 414 transmits the main random numbers (a, b) generated in step F2 to the decryption apparatus 420 (step F3).

[0353] Next, the main random number receiving section 421 in the decryption apparatus 420 receives the main random numbers (a, b) from the concealment apparatus 410 (step F4).

[0354] Next, the matching information concealment section 416 in the concealment apparatus 410 calculates

z.sub.j=ax.sub.j−bs.sub.j

for all j=1, . . . , and D,
from the preliminary random number s=(s.sub.1, . . . , and s.sub.D) acquired in step E1,
the matching information x=(x.sub.1, . . . , and x.sub.D) acquired in step F1, and
the main random numbers a and b acquired in step F2,
to obtain the concealed matching information z=(z.sub.1, . . . , and z.sub.D) (step F5).

[0355] Next, the concealed matching information transmitting section 418 transmits the concealed matching information z generated in step F5 to the similarity calculating apparatus 430 (step F6).

[0356] Next, the concealed matching information receiving section 432 in the similarity calculating apparatus 430 receives the concealed matching information z from the concealment apparatus 410 (step F7).

[0357] Next, the second concealed transformed similarity calculating section 437 calculates, as second concealed transformed similarities for all i=1, . . . , and N,

W.sub.i=[r.sub.i<z,y.sub.i>]G

from the registration information y.sub.1, . . . , and y.sub.N (where y.sub.i=(y.sub.i, 1, . . . , and y.sub.i, D) for all i=1, . . . , and N) acquired in step E5,
the transformation keys (r.sub.1, . . . , and r.sub.N) generated in step E6, and
the concealed matching information z=(z.sub.1, . . . , and z.sub.D) received in step F7 (step F8).
Note that because z.sub.j=ax.sub.j−bs.sub.j is satisfied for all j=1, . . . , and D,
the second concealed transformed similarities for all i=1, . . . , and N may be expressed as

W.sub.i=[r.sub.i(a<x,y.sub.i>−b<s,y.sub.i>)]G.

[0358] Next, the second concealed transformed similarity transmitting section 439 transmits the second concealed transformed similarities (W.sub.1, . . . , and W.sub.N) calculated in step F8 to the decryption apparatus 420 (step F9).

[0359] Next, the second concealed transformed similarity receiving section 423 in the decryption apparatus 420 receives the second concealed transformed similarities (W.sub.1, . . . , and W.sub.N) from the similarity calculating apparatus 430 (step F10).

[0360] Next, the decrypting section 424 calculates, as transformed similarities for all i=1, . . . , and N,

A.sub.i=[r.sub.i<x,y.sub.i>]G

from the first concealed transformed similarities (U.sub.1, . . . , and U.sub.N) received in step E11,
the main random numbers a and b received in step F4, and
the second concealed transformed similarities (W.sub.1, . . . , and W.sub.N) received in step F10 (step F11).

[0361] Note that the transformed similarity for all i=1, . . . , and N can be calculated as, for example,

[a.sup.−1]([b]U.sub.i+W.sub.i).

[0362] Next, the similarity transmitting section 425 transmits the transformed similarities (A.sub.1, . . . , and A.sub.N) calculated in step F11 to the information identifying apparatus 440 (step F12).

[0363] Next, the transformed similarity receiving section 442 in the information identifying apparatus 440 receives the transformed similarities (A.sub.1, . . . , and A.sub.N) from the decryption apparatus 420 (step F13).

[0364] Next, the inverse transforming section 443 calculates, as points of similarities for all i=1, . . . , and N,

[<x,y.sub.i>]G

from the inverse transformation keys ((r.sub.1).sup.−1, . . . , and (r.sub.N).sup.−1) received in step E8 and
the transformed similarities (A.sub.1, . . . , and A.sub.N) received in step F13 (step F14).
Note that the point of similarity for all i=1, . . . , and N can be calculated as, for example,

[(r.sub.i).sup.−1](A.sub.i).

[0365] At the end of the main calculation process, the information identifying section 444 identifies, among the points of similarities ([<x, y.sub.1>]G, . . . , and [<x, y.sub.N>]G) calculated in step F14, a point of similarity falling within a point acceptable range ([θ.sub.1]G, . . . , and [θ.sub.τ]G) corresponding to a predefined acceptable range (θ.sub.1, . . . , and θ.sub.τ) (step F15).

[0366] This concrete example describes the example in which the similarity calculating apparatus 430 orders N concealed similarities to be transmitted to the decryption apparatus 420 in an index-based order of the registration information and transmits the resultant concealed similarities in step F9, but the similarity calculating apparatus 430 may assign a new identifier to each of the concealed similarities, shuffle the concealed similarities, and transmit the resultant concealed similarities to the decryption apparatus 420. At this time, the similarity calculating apparatus 430 may further give correspondences of two types of identifiers to the information identifying apparatus 440 so that the information identifying apparatus 440 can determine an identifier of the registration information that the information identifying apparatus 440 desires to identify.

Concrete Example 2 According to Fourth Example Embodiment

[0367] Next, a concrete example 2 of the operation of the information matching system 400 according to the present example embodiment will be described.

[0368] In this concrete example also, although a description is given assuming a case similar to the case of the concrete example 1 according to the fourth example embodiment, a target of the present example embodiment is not limited to these cases.

[0369] In the preliminary calculation process, first, the preliminary random number acquiring section 412 in the concealment apparatus 410 acquires, as preliminary random numbers, 2D κ-bit random numbers s.sub.1, . . . , and s.sub.D, t.sub.1, . . . , and t.sub.D (step E1). Hereinafter, the preliminary random numbers are expressed as vectors:

s=(s.sub.1, . . . , and s.sub.D) and t=(t.sub.1, . . . , and t.sub.D).

[0370] Next, the random number concealment section 415 generates, as concealed random numbers,

S.sub.1=[s.sub.1]G, . . . , and S.sub.D=[s.sub.D]G,T.sub.1=[t.sub.1]G, . . . , and T.sub.D=[t.sub.D]G

(step E2).

[0371] Next, the concealed random number transmitting section 417 transmits the concealed random numbers (S.sub.1, . . . , and S.sub.D, T.sub.1, . . . , and T.sub.D) generated in step E2 to the similarity calculating apparatus 430 (step E3).

[0372] Next, the concealed random number receiving section 431 in the similarity calculating apparatus 430 receives the concealed random numbers (S.sub.1, . . . , and S.sub.D, T.sub.1, . . . , and T.sub.D) from the concealment apparatus 410 (step E4).

[0373] Next, the registration information acquiring section 433 acquires, as the registration information, N D-dimensional vectors y.sub.1, . . . , and y.sub.N (where y.sub.i=(y.sub.i, 1, . . . , and y.sub.i, D) for all i=1, . . . , and N) (step E5).

[0374] Next, the transformation key generating section 434 acquires D κ-bit random numbers r.sub.1, . . . , and r.sub.N to let (r.sub.1, . . . , and r.sub.N) be the transformation keys and ((r.sub.1).sup.−1, . . . , and (r.sub.N).sup.−1) be the inverse transformation keys (step E6).

[0375] Next, the inverse transformation key transmitting section 435 transmits the inverse transformation keys ((r.sub.1).sup.−1, . . . , and (r.sub.N).sup.−1) generated in step E6 to the information identifying apparatus 440 (step E7).

[0376] Next, the inverse transformation key receiving section 441 in the information identifying apparatus 440 receives the inverse transformation keys ((r.sub.1).sup.−1, . . . , and (r.sub.N).sup.−1) from the similarity calculating apparatus 430 (step E8).

[0377] Next, the first concealed transformed similarity calculating section 436 calculates, as first concealed transformed similarities for all i=1, . . . , and N,

U.sub.i=[r.sub.i<s,y.sub.i>]G and U.sub.i=[r.sub.i<t,y.sub.i>]G

from the concealed random numbers (S.sub.1, . . . , and S.sub.D, T.sub.1, . . . , and T.sub.D) received in step E4, the registration information y.sub.i=(y.sub.i, 1, . . . , and y.sub.i, D) for all i=1, . . . , and N acquired in step E5, and
the transformation keys r.sub.i for all i=1, . . . , and N generated in step E6 (step E9).
Note that the first concealed transformed similarity for all i=1, . . . , and N can be calculated by, for example,

U.sub.i=[r.sub.i]([y.sub.i,1]S.sub.1+ . . . +[y.sub.i,D]S.sub.D) and

V.sub.i=[r.sub.i]([y.sub.i,1]T.sub.1+ . . . +[y.sub.i,D]T.sub.D).

[0378] Next, the first concealed transformed similarity transmitting section 438 transmits the concealed transformed similarities (U.sub.1, . . . , and U.sub.N, V.sub.1, . . . , and V.sub.N) calculated in step E9 to the decryption apparatus 420 (step E10).

[0379] In the preliminary calculation process, finally, the first concealed transformed similarity receiving section 422 in the decryption apparatus 420 receives the first concealed transformed similarities (U.sub.1, . . . , and U.sub.N, V.sub.1, . . . , and V.sub.N) from the similarity calculating apparatus 430 (step E11).

[0380] In the main calculation process, first, the matching information acquiring section 411 in the concealment apparatus 410 acquires, as the matching information, a D-dimensional vector:

x=(x.sub.1, . . . , and x.sub.D)

(step F1).

[0381] Next, the main random number acquiring section 413 acquires, as main random numbers, κ-bit random number b (step F2).

[0382] Next, the main random number transmitting section 414 transmits the main random number b generated in step F2 to the decryption apparatus 420 (step F3).

[0383] Next, the main random number receiving section 421 in the decryption apparatus 420 receives the main random number b from the concealment apparatus 410 (step F4).

[0384] Next, the matching information concealment section 416 in the concealment apparatus 410 calculates

z.sub.j=x.sub.j−bs.sub.j−t.sub.j

for all j=1, . . . , and D,
from the preliminary random number s=(s.sub.1, . . . , and s.sub.D, t.sub.1, . . . , and t.sub.D) acquired in step E1,
the matching information x=(x.sub.1, . . . , and x.sub.D) acquired in step F1, and
the main random number b acquired in step F2,
to obtain the concealed matching information z=(z.sub.1, . . . , and z.sub.D) (step F5).

[0385] Next, the concealed matching information transmitting section 418 transmits the concealed matching information z generated in step F5 to the similarity calculating apparatus 430 (step F6).

[0386] Next, the concealed matching information receiving section 432 in the similarity calculating apparatus 430 receives the concealed matching information z from the concealment apparatus 410 (step F7).

[0387] Next, the second concealed transformed similarity calculating section 437 calculates, as second concealed transformed similarities for all i=1, . . . , and N,

W.sub.i=[r.sub.i<z,y.sub.i>]G

from the registration information y.sub.1, . . . , and y.sub.N (where y.sub.i=(y.sub.i, 1, . . . , and y.sub.i, D) for all i=1, . . . , and N) acquired in step E5,
the transformation keys (r.sub.1, . . . , and r.sub.N) generated in step E6, and
the concealed matching information z=(z.sub.1, . . . , and z.sub.D) received in step F7 (step F8).
Note that because z.sub.j=x.sub.j−bs.sub.j−t.sub.j is satisfied for all j=1, . . . , and D, the second concealed transformed similarities for all i=1, . . . , and N may be expressed as

W.sub.i=[r.sub.i(x,y.sub.i>−b<s,y.sub.i>−<t,y.sub.i>)]G.

[0388] Next, the second concealed transformed similarity transmitting section 439 transmits the second concealed transformed similarities (W.sub.1, . . . , and W.sub.N) calculated in step F8 to the decryption apparatus 420 (step F9).

[0389] Next, the second concealed transformed similarity receiving section 423 in the decryption apparatus 420 receives the second concealed transformed similarities (W.sub.1, . . . , and W.sub.N) from the similarity calculating apparatus 430 (step F10).

[0390] Next, the decrypting section 424 calculates, as transformed similarities for all i=1, . . . , and N,

A.sub.i=[r.sub.i<x,y.sub.i>]G

from the first concealed transformed similarities (U.sub.1, . . . , and U.sub.N, V.sub.1, . . . , and V.sub.N) received in step E11,
the main random number b received in step F4, and
the second concealed transformed similarities (W.sub.1, . . . , and W.sub.N) received in step F10 (step F11).
Note that the transformed similarity for all i=1, . . . , and N can be calculated as, for example,

[b]U.sub.i+V.sub.i+W.sub.i.

[0391] Next, the similarity transmitting section 425 transmits the transformed similarities (A.sub.1, . . . , and A.sub.N) calculated in step F11 to the information identifying apparatus 440 (step F12).

[0392] Next, the transformed similarity receiving section 442 in the information identifying apparatus 440 receives the transformed similarities (A.sub.1, . . . , and A.sub.N) from the decryption apparatus 420 (step F13).

[0393] Next, the inverse transforming section 443 calculates, as points of similarities for all i=1, . . . , and N,

[<x,y.sub.i>]G

from the inverse transformation keys ((r.sub.1).sup.−1, . . . , and (r.sub.N).sup.−1) received in step E8 and the transformed similarities (A.sub.1, . . . , and A.sub.N) received in step F13 (step F14).
Note that the point of similarity for all i=1, . . . , and N can be calculated as, for example,

[(r.sub.i).sup.−1](A.sub.i).

[0394] At the end of the main calculation process, the information identifying section 444 identifies, among the points of similarities ([<x, y.sub.1>]G, . . . , and [<x, y.sub.N>]G) calculated in step F14, a point of similarity falling within a point acceptable range ([θ.sub.1]G, . . . , and [θ.sub.τ]G) corresponding to a predefined acceptable range (θ.sub.1, . . . , and θ.sub.τ) (step F15).

[0395] This concrete example describes the example in which the similarity calculating apparatus 130 orders N concealed similarities to be transmitted to the decryption apparatus 120 in an index-based order of the registration information and transmits the resultant concealed similarities in step A10, but the similarity calculating apparatus 130 may assign a new identifier to each of the concealed similarities, shuffle the concealed similarities, and transmit the resultant concealed similarities to the decryption apparatus 120. At this time, the similarity calculating apparatus 130 may further give correspondences of two types of identifiers to the information identifying apparatus 140 so that the information identifying apparatus 140 can determine an identifier of the registration information that the information identifying apparatus 140 desires to identify.

[Description of Effect]

[0396] An effect of the present example embodiment described above is, similar to the first, second, and third example embodiments, that the information matching securely using the biometric information can be realized with the cost less than that of the case of using an additive homomorphic public key cryptosystem. This is because in the concealment of the matching information in step F5, the concealment is performed by the linear conversion instead of a homomorphic operation of an additive homomorphic public key cryptosystem. The linear conversion, rather than the general concealment, is applied to allow the second concealed transformed similarities and the transformed similarities to be calculated in steps F8 and F11.

[0397] Furthermore, the present example embodiment, similar to the second example embodiment, has an effect that the present example embodiment can be executed without leaking the value of the similarity to the decryption apparatus 420, even in a case that the decryption apparatus 420 has information related to a random number other than the main random number, such as a case that the concealment apparatus 410 and the decryption apparatus 420 are mounted on the same apparatus. This is because the decryption apparatus 420 acquires the similarity that is transformed based on the transformation key generated by the similarity calculating apparatus 430.

[0398] Furthermore, the present example embodiment, similar to the third example embodiment, has also an effect that the cost taken after acquiring the matching information can be reduced. This is because in the present example embodiment, a process not depending on the matching information is the preliminary calculation process, and thus, such process can be executed before acquiring the matching information.

[0399] As described above, the techniques according to the present invention make it possible to match, at high speed, biometric information acquired by a sensor such as a camera and biometric information of one or a plurality of persons stored in a database with the both biometric information being concealed. This is effective in some cases that a manager (managing organization) of the sensor and a manager (managing organization) of the database are different from each other.

[0400] The techniques according to the present invention can be used for, for example, white list matching. An entrance and exit control of a building such as an office building is described as an example. A case is assumed that it is desired to check whether or not a person trying to pass through an entrance and exit gate owned by a manager (an organization) of the building is included in a list of employees of a tenant of the building or guests. In such a case, the use of the techniques according to the present invention enables the high speed matching without disclosing biometric information or the like of persons acquired at the entrance and exit gate to a tenant other than a tenant the person belongs to or is to visit by the manager (managing organization) of the building, or without disclosing biometric information or the like of the employees or the guests to the manager (the organization) or the building by each tenant.

[0401] Security check in an airport and the like is described as another example of the use of the white list matching. In an airport, passport information is used at customs, a boarding gate, or various places for shopping, and a passenger presents a passport at every place. In order to eliminate the need of presenting and checking the passport, cases of using face authentication is increasing that a passport photograph of the passenger acquired by an airline company at a check-in counter or the like is used instead of the passport. At this time, the use of the techniques according to the present invention makes it possible to identify a target passenger without disclosing facial information of the passenger between the airline company, and the customs, the boarding gate, or various places for shopping, and get only the passport information of the target passenger at each place.

[0402] The techniques according to the present invention can be used for also, for example, black list matching. Here, an example is described that a person appearing on a black list owned by an external organization is identified from among persons exist in a facility. A case is assumed that it is desired to find a person appearing on a black list of criminals or the like owned by the police or the like from among persons captured on a security camera owned by a manager (managing organization) of the facility. In such a case, the use of the present invention enables the high speed matching without disclosing facial information or the like of persons captured by the security camera in the facility to the owner (owing organization) of the black list by the manager (managing organization) of the facility, or without disclosing the black list to the manager (managing organization) of the facility.

[0403] Next, hardware of each apparatus configuring the information search system will be described. FIG. 12 is a diagram illustrating an example of a hardware configuration of the concealment apparatus 110.

[0404] The concealment apparatus 110 can be configured with an information processing apparatus (so-called, a computer), and includes a configuration illustrated in FIG. 12. For example, the concealment apparatus 110 includes a processor 31, a memory 32, an input/output interface 33, a communication interface 34, and the like. Constituent elements such as the processor 31 are connected to each other via an internal bus or the like, and are configured to be communicable with each other.

[0405] However, the configuration illustrated in FIG. 12 is not intended to limit the hardware configuration of the concealment apparatus 110. The concealment apparatus 110 may include hardware not illustrated, or need not include the input/output interface 33 as necessary. The number of processors 31 and the like included in the concealment apparatus 110 is not intended to limit to the example illustrated in FIG. 12, and for example, a plurality of processors 31 may be included in the concealment apparatus 110.

[0406] The processor 31 is, for example, a programmable device such as a central processing unit (CPU), a micro processing unit (MPU), and a digital signal processor (DSP). Alternatively, the processor 31 may be a device such as a field programmable gate array (FPGA) and an application specific integrated circuit (ASIC). The processor 31 executes various programs including an operating system (OS).

[0407] The memory 32 is a random access memory (RAM), a read only memory (ROM), a hard disk drive (HDD), a solid state drive (SSD), or the like. The memory 32 stores an OS program, an application program, and various pieces of data.

[0408] The input/output interface 33 is an interface of a display apparatus or an input apparatus (not illustrated). The display apparatus is, for example, a liquid crystal display or the like. The input apparatus is, for example, an apparatus that receives user operation, such as a keyboard and a mouse.

[0409] The communication interface 34 is a circuit, a module, or the like that performs communication with another apparatus. For example, the communication interface 34 includes a network interface card (NIC) or the like.

[0410] The function of the concealment apparatus 110 is implemented by various processing modules. Each of the processing modules is, for example, implemented by the processor 31 executing a program stored in the memory 32. The program can be recorded on a computer readable storage medium. The storage medium can be a non-transitory storage medium, such as a semiconductor memory, a hard disk, a magnetic recording medium, and an optical recording medium. In other words, the present invention can also be implemented as a computer program product. The program can be updated through downloading via a network, or by using a storage medium storing a program. In addition, the processing module may be implemented by a semiconductor chip.

[0411] Note that the decryption apparatus 120, the similarity calculating apparatus 130, and the information identifying apparatus 140 also can be configured by the information processing apparatus similar to the concealment apparatus 110, and their basic hardware structures are not different from the concealment apparatus 110, and thus, the descriptions thereof are omitted.

Example Alterations

[0412] Note that the configuration, the operation, and the like of the information matching system described in the example embodiments are merely examples, and are not intended to limit the configuration and the like of the system. For example, a database server or the like may be provided that stores the information (for example, concealed information, matching information, or the like) transmitted or received between the apparatuses to communicate the information via the database server.

[0413] In a plurality of flowcharts (sequence diagram) used in the above description, a plurality of steps (processes) are described in order, but the order of performing of the steps performed in each example embodiment is not limited to the described order. In each example embodiment, the illustrated order of processes can be changed as far as there is no problem with regard to processing contents, such as a change in which respective processes are executed in parallel, for example. The example embodiments described above can be combined in a scope that the contents do not conflict.

[0414] The whole or part of the example embodiments disclosed above can be described as, but not limited to, the following supplementary notes.

(Supplementary Note 1)

[0415] An information matching system comprises:

[0416] a concealment apparatus (10, 110, 210, 310, or 410);

[0417] a decryption apparatus (20, 120, 220, 320, or 420); and

[0418] a similarity calculating apparatus (30, 130, 230, 330, or 430), wherein

[0419] the concealment apparatus (10, 110, 210, 310, or 410) is configured to transmit, to the similarity calculating apparatus (30, 130, 230, 330, or 430), concealed information including information concealing obtained matching information by linear conversion using random numbers,

[0420] the similarity calculating apparatus (30, 130, 230, 330, or 430) is configured to calculate, from obtained one or more pieces of registration information and the concealed information received from the concealment apparatus (10, 110, 210, 310, or 410), a concealed similarity which is a value concealing a similarity between the matching information and the registration information, and to transmit the calculated concealed similarity to the decryption apparatus (20, 120, 220, 320, or 420), and

[0421] the decryption apparatus (20, 120, 220, 320, or 420) is configured to calculate the similarity between the matching information and the registration information from the concealed similarity received from the similarity calculating apparatus (30, 130, 230, 330, or 430), using the random numbers used by the concealment apparatus (10, 110, 210, 310, or 410).

(Supplementary Note 2)

[0422] The information matching system according to the supplementary note 1, further comprises:

[0423] an information identifying apparatus (140, 240, 340, or 440), wherein

[0424] the similarity calculating apparatus (30, 130, 230, 330, or 430) is configured to further generate a transformation key and an inverse transformation key, and calculate a concealed similarity that is a value concealing a transformed value of the similarity between the matching information and the registration information from the obtained one or more pieces of registration information, the concealed information received from the concealment apparatus (10, 110, 210, 310, or 410), and the transformation key to transmit the calculated concealed similarity to the decryption apparatus (20, 120, 220, 320, or 420),

[0425] the decryption apparatus (20, 120, 220, 320, or 420) is configured to calculate a transformed similarity that is a transformed value of the similarity between the matching information and the registration information from a concealed transformed similarity calculated by the similarity calculating apparatus (30, 130, 230, 330, or 430) using the random numbers used by the concealment apparatus (10, 110, 210, 310, or 410), and transmit the calculated transformed similarity to the information identifying apparatus (140, 240, 340, or 440), and

[0426] the information identifying apparatus (140, 240, 340, or 440) is configured to calculate a similarity from the transformed similarity received from the decryption apparatus (20, 120, 220, 320, or 420) using the inverse transformation key.

(Supplementary Note 3)

[0427] The information matching system according to the supplementary note 1, wherein

[0428] the concealment apparatus (10, 110, 210, 310, or 410) is configured to, before obtaining the matching information, transmit concealed random numbers concealing the obtained random numbers to the similarity calculating apparatus (30, 130, 230, 330, or 430),

[0429] the similarity calculating apparatus (30, 130, 230, 330, or 430) is configured to calculate a first concealed similarity from the obtained one or more pieces of registration information and the concealed random numbers received from the concealment apparatus (10, 110, 210, 310, or 410), and transmit the calculated first concealed similarity in advance to the decryption apparatus (20, 120, 220, 320, or 420),

[0430] the concealment apparatus (10, 110, 210, 310, or 410) is configured to transmit, after obtaining the matching information, concealed matching information concealing the obtained matching information by linear conversion using random numbers to the similarity calculating apparatus (30, 130, 230, 330, or 430),

[0431] the similarity calculating apparatus (30, 130, 230, 330, or 430) is configured to calculate a second concealed similarity from the obtained one or more pieces of registration information and the concealed matching information received from the concealment apparatus (10, 110, 210, 310, or 410), and transmit the calculated second concealed similarity to the decryption apparatus (20, 120, 220, 320, or 420), and

[0432] the decryption apparatus (20, 120, 220, 320, or 420) is configured to calculate a similarity between the matching information and the registration information from the first concealed similarity and the second concealed similarity using the random numbers used by the concealment apparatus (10, 110, 210, 310, or 410).

(Supplementary Note 4)

[0433] The information matching system according to the supplementary note 3, further comprises:

[0434] an information identifying apparatus (140, 240, 340, or 440), wherein

[0435] the similarity calculating apparatus (30, 130, 230, 330, or 430) is configured to,

[0436] before the concealment apparatus (10, 110, 210, 310, or 410) obtains the matching information, generate a transformation key and an inverse transformation key, calculate a first concealed transformed similarity from the obtained one or more pieces of registration information, the concealed random numbers received from the concealment apparatus (10, 110, 210, 310, or 410), and the transformation key, and transmit the calculated first concealed transformed similarity in advance to the decryption apparatus (20, 120, 220, 320, or 420), and

[0437] after the concealment apparatus (10, 110, 210, 310, or 410) obtains the matching information, calculate a second concealed transformed similarity from the obtained one or more pieces of registration information, the concealed matching information received from the concealment apparatus (10, 110, 210, 310, or 410), and the transformation key, and transmit the calculated second concealed transformed similarity to the decryption apparatus (20, 120, 220, 320, or 420),

[0438] the decryption apparatus (20, 120, 220, 320, or 420) is configured to calculate a transformed similarity that is a transformed value of the similarity between the matching information and the registration information from the first concealed transformed similarity and the second concealed transformed similarity calculated by the similarity calculating apparatus (30, 130, 230, 330, or 430) using the random numbers used by the concealment apparatus (10, 110, 210, 310, or 410), and transmit the calculated transformed similarity to the information identifying apparatus (140, 240, 340, or 440), and

[0439] the information identifying apparatus (140, 240, 340, or 440) is configured to calculate a similarity from the transformed similarity using the inverse transformation key.

(Supplementary Note 5)

[0440] The information matching system according to the supplementary note 2 or 4, wherein the information identifying apparatus (140, 240, 340, or 440) is configured to identify the registration information matching the matching information based on the calculated similarity.

(Supplementary Note 6)

[0441] The information matching system according to any one the supplementary notes 1 to 5, wherein the concealment apparatus (10, 110, 210, 310, or 410) is configured to use two random numbers a and b, and a random number s that is a vector having a dimension the same as matching information x that is a vector to conceal the matching information in a form of ax−bs.

(Supplementary Note 7)

[0442] The information matching system according to any one of the supplementary notes 1 to 5, wherein the concealment apparatus (10, 110, 210, 310, or 410) is configured to use one random number b and two random number vectors s and t each having a dimension the same as matching information x that is a vector to conceal the matching information in a form of x−bs−t.

(Supplementary Note 8)

[0443] An information matching method comprises, in an information matching system including a concealment apparatus (10, 110, 210, 310, or 410), a decryption apparatus (20, 120, 220, 320, or 420), and a similarity calculating apparatus (30, 130, 230, 330, or 430):

[0444] transmitting, by the concealment apparatus (10, 110, 210, 310, or 410), to the similarity calculating apparatus (30, 130, 230, 330, or 430), concealed information including information concealing obtained matching information by linear conversion using random numbers;

[0445] calculating, by the similarity calculating apparatus (30, 130, 230, 330, or 430), from obtained one or more pieces of registration information and the concealed information received from the concealment apparatus (10, 110, 210, 310, or 410), a concealed similarity which is a value concealing a similarity between the matching information and the registration information, and to transmit the calculated concealed similarity to the decryption apparatus (20, 120, 220, 320, or 420); and

[0446] calculating, by the decryption apparatus (20, 120, 220, 320, or 420), the similarity between the matching information and the registration information from the concealed similarity received from the similarity calculating apparatus (30, 130, 230, 330, or 430), using the random numbers used by the concealment apparatus (10, 110, 210, 310, or 410).

[0447] Note that the aspect of the supplementary note 8 can be expanded, similar to the aspect of the supplementary note 1, to the aspects of the supplementary notes 2 to 7.

[0448] Note that the disclosures of the cited literatures in the citation list are incorporated herein by reference. Descriptions have been given above of the example embodiments of the present invention. However, the present invention is not limited to these example embodiments. It should be understood by those of ordinary skill in the art that these example embodiments are merely examples and that various alterations are possible without departing from the scope and the spirit of the present invention.

REFERENCE SIGNS LIST

[0449] 10, 110, 210, 310, 410 Concealment Apparatus [0450] 20, 120, 220, 320, 420 Decryption Apparatus [0451] 30, 130, 230, 330, 430 Similarity Calculating Apparatus [0452] 31 Processor [0453] 32 Memory [0454] 33 Input/Output Interface [0455] 34 Communication Interface [0456] 100, 200, 300, 400 Information Matching System [0457] 111, 211, 311, 411 Matching Information Acquiring Section [0458] 113, 213 Random Number Acquiring Section [0459] 114, 214, 314, 414 Main Random Number Transmitting Section [0460] 116 Concealment Section [0461] 118, 218 Concealed Information Transmitting Section [0462] 121, 221, 321, 421 Main Random Number Receiving Section [0463] 123 Concealed Similarity Receiving Section [0464] 124, 224, 324, 424 Decrypting Section [0465] 125, 225, 325, 425 Similarity Transmitting Section [0466] 132, 232 Concealed Information Receiving Section [0467] 133, 233, 333, 433 Registration Information Acquiring Section [0468] 137 Concealed Similarity Calculating Section [0469] 139 Concealed Similarity Transmitting Section [0470] 140, 240, 340, 440 Information Identifying Apparatus [0471] 142, 342 Similarity Receiving Section [0472] 144, 244, 344, 444 Information Identifying Section [0473] 216, 316, 416 Matching Information Concealment Section [0474] 223 Concealed Transformed Similarity Receiving Section [0475] 234, 434 Transformation Key Generating Section [0476] 235, 435 Inverse Transformation Key Transmitting Section [0477] 237 Concealed Transformed Similarity Calculating Section [0478] 238 Concealed Transformed Similarity Transmitting Section [0479] 241, 441 Inverse Transformation Key Receiving Section [0480] 242, 442 Transformed Similarity Receiving Section [0481] 243, 443 Inverse Transforming Section [0482] 312, 412 Preliminary Random Number Acquiring Section [0483] 313, 413 Main Random Number Acquiring Section [0484] 315, 415 Random Number Concealment Section [0485] 317, 417 Concealed Random Number Transmitting Section [0486] 318, 418 Concealed Matching Information Transmitting Section [0487] 322 First Concealed Similarity Receiving Section [0488] 323 Second Concealed Similarity Receiving Section [0489] 331, 431 Concealed Random Number Receiving Section [0490] 332, 432 Concealed Matching Information Receiving Section [0491] 336 First Concealed Similarity Calculating Section [0492] 337 Second Concealed Similarity Calculating Section [0493] 338 First Concealed Similarity Transmitting Section [0494] 339 Second Concealed Similarity Transmitting Section [0495] 422 First Concealed Transformed Similarity Receiving Section [0496] 423 Second Concealed Transformed Similarity Receiving Section [0497] 436 First Concealed Transformed Similarity Calculating Section [0498] 437 Second Concealed Transformed Similarity Calculating Section [0499] 438 First Concealed Transformed Similarity Transmitting Section [0500] 439 Second Concealed Transformed Similarity Transmitting Section