JP6567979B2 - Similar information search method, server device, and similar information search system - Google Patents

Description

  The present invention relates to a method, a server device, and a system for performing similar information search while concealing contents by encryption.

  In recent years, for example, there is a system that measures blood pressure at home, for example, and provides advice to users regarding eating habits by analysis on a server. In this analysis, useful advice with a real feeling can be given to the user by giving advice by referring not only to the person's past information but also to other similar cases. In searching for similar cases in the server, it is desirable to conceal the information of the user and the information of other cases to be referred to by encryption from the viewpoint of privacy protection. Patent Document 1, Patent Document 2 and Patent Document 3 disclose techniques for performing a similarity search with encryption.

JP 2014-126865 A JP 2014-126866 A Japanese Patent No. 5542474

Shigeo Mitsunari, “Cryptographic Technology to Support the Cloud”, 2015.3.34. gitub D. Boneh, E .; -J. Goh, K .; Nissim, “Evaluating 2-DNF Formulas on Ciphertexts”, TCC05, 2005.

  However, in the conventional similarity search, in the encryption using the common key or the public key, the similarity search is performed with the server device being encrypted. Since it is the terminal device that has the key for decrypting this encrypted feature quantity, the terminal device receives and decrypts the similarity value transmitted by the server device, and the similarity value and the terminal device reference characteristics It is determined whether or not the distance calculated from the quantity and the feature quantity matches. If they do not match, the same operation is performed again. For this reason, the number of communications between the terminal device and the server device increases, and the processing calculation when decrypting the data encrypted by the terminal device increases.

  The present invention solves such a problem, and a similar information search method, a server device, and a similar information search system that reduce the processing calculation of the terminal device and reduce the number of times of communication between the server device and the terminal device. The purpose is to provide.

  In order to solve the above problem, one aspect of a similar information search method is a similar information search method in which a server device searches for similar information based on information provided from the terminal device and provides the similar information to the terminal device, The server device receives a feature value receiving step of receiving an encrypted feature value, which is an encrypted feature value, from the terminal device, and the server device encrypts a similar value indicating a similar degree from the terminal device. A similarity value receiving step of receiving an encrypted similarity value, which is converted information, the reference feature amount for at least one of a plurality of reference feature amounts, and the encryption received by the server device A distance calculating step for calculating an encryption distance indicating a degree of similarity with a feature amount, and the server device, wherein the calculated encryption distance is received by the server device. A determination step for determining whether or not to match, and a reference that is data corresponding to the reference feature value used for calculating the encryption distance when the server device is determined to match in the determination step Generating encrypted reference data that is information obtained by encrypting data, and transmitting the generated encrypted reference data to the terminal device.

  A similar information search system according to an aspect of the present invention is a server device that searches for similar information based on information provided from a terminal device and provides the similar information to the terminal device. An encrypted distance that indicates the degree of similarity between the received encrypted feature quantity and the reference feature quantity for at least one of a plurality of reference feature quantities. The encryption distance calculation unit to be calculated and an encryption similarity value that is information obtained by encrypting the similarity indicating the degree of similarity are received, and whether the received encryption similarity value matches the calculated encryption distance Reference data that is data corresponding to the reference feature value used for calculating the encryption distance when it is determined that the reference similarity value extraction unit and the reference similarity value extraction unit match each other. Encrypted information To generate encrypted reference data, and a cryptographic reference data extraction unit that transmits to the terminal device the generated the encrypted reference data.

  ADVANTAGE OF THE INVENTION According to this invention, the processing calculation of a terminal device can be reduced in weight, and the frequency | count of communication with a server apparatus and a terminal device can reduce.

3 is a block diagram illustrating an overall image of a service provided by the information management system in Embodiment 1. FIG. 3 is a block diagram illustrating an example in which a device manufacturer corresponds to a data center operating company in Embodiment 1. FIG. FIG. 3 is a block diagram illustrating an example in which both or one of the device manufacturer and the management company corresponds to the data center operating company in the first embodiment. 1 is a block diagram showing an overall configuration of a similar information search system in Embodiment 1. FIG. 3 is a block diagram showing a configuration of a user terminal device in Embodiment 1. FIG. 1 is a block diagram illustrating a configuration of a data operation device in Embodiment 1. FIG. 3 is a diagram illustrating an example of a reference feature amount storage unit in the data arithmetic device in Embodiment 1. FIG. 6 is a diagram illustrating an example of a reference data storage unit in the data arithmetic device in Embodiment 1. FIG. FIG. 6 is a sequence diagram showing an operation of the similar information search system in the first embodiment. 3 is a diagram illustrating an example of a data format between a user terminal and a data device in Embodiment 1. FIG. 3 is a diagram illustrating an example of a data format between a user terminal and a data device in Embodiment 1. FIG. 6 is a diagram illustrating an example of display of a user terminal device in the first embodiment. FIG. 6 is a diagram illustrating an example of display of a user terminal device in the first embodiment. FIG. 5 is a graph illustrating an example of calculating time and feature amounts displayed by the user terminal device in the first embodiment. 6 is a block diagram illustrating a configuration of a user terminal device in Embodiment 2. FIG. 6 is a block diagram illustrating a configuration of a data arithmetic device in Embodiment 2. FIG. FIG. 10 is a sequence diagram showing the operation of the similar information search system in the second embodiment. It is a block diagram which shows the structure of the data arithmetic unit in the case of acquiring statistical reference data in another modification. It is a block diagram which shows the whole image of the service which the information management system in the service type 1 (in-house data center type | mold cloud service) provides. It is a block diagram which shows the whole image of the service which the information management system in the service type 2 (IaaS use type cloud service) provides. It is a block diagram which shows the whole image of the service which the information management system in the service type 3 (PaaS use type cloud service) provides. It is a block diagram which shows the whole image of the service which the information management system in the service type 4 (SaaS utilization type cloud service) provides.

(Knowledge that became the basis of the invention)
There is a method of performing a similar search with encryption. However, in this case, although the server side calculates the encrypted distance, it does not have a corresponding secret key, so it cannot be determined whether it matches the specified similarity value. In order to perform the determination, decryption using the secret key of the user terminal is necessary, and the amount of calculation and the amount of communication are large to realize in the user terminal.

  In order to solve such a problem, a similar information search method is a similar information search method in which a server device searches for similar information based on information provided from the terminal device and provides the similar information to the terminal device, The server device receives a feature value receiving step of receiving an encrypted feature value, which is an encrypted feature value, from the terminal device, and the server device encrypts a similar value indicating a similar degree from the terminal device. A similarity value receiving step of receiving an encrypted similarity value, which is converted information, the reference feature amount for at least one of a plurality of reference feature amounts, and the encryption received by the server device A distance calculating step for calculating an encryption distance indicating a degree of similarity with a feature amount, and the server device, wherein the calculated encryption distance is received by the server device. A determination step for determining whether or not to match, and a reference that is data corresponding to the reference feature value used for calculating the encryption distance when the server device is determined to match in the determination step Generating encrypted reference data that is information obtained by encrypting data, and transmitting the generated encrypted reference data to the terminal device.

  According to this configuration, the server device receives the encrypted feature value and the encrypted similarity value from the terminal device, and the server device calculates the encryption distance from the encrypted feature value and the encrypted similarity value. Then, if the encrypted distance matches the encrypted similarity value, the server device generates encrypted reference data and transmits it to the terminal device. For this reason, compared with the case where the terminal device determines whether or not the encryption distance and the encryption similarity value match, this similarity information search method reduces the processing calculation of the terminal device.

  Further, in this server device, when the encrypted distance and the encrypted similarity value match, encrypted reference data is generated, and the generated encrypted reference data is transmitted to the terminal device. For this reason, compared with the case where a terminal device judges whether an encryption distance and an encryption similarity value correspond, the frequency | count of communication with a server apparatus and a terminal device does not increase easily.

  Therefore, in this similar information search method, the processing calculation of the terminal device can be reduced, and the number of communications between the server device and the terminal device can be reduced.

  In the similar information search method, in the similarity value receiving step, a plurality of encrypted similarity values that are information obtained by encrypting each of a plurality of similar values indicating a plurality of similar degrees are received. The distance calculation step, the determination step, and the reference data transmission step are executed for each of the received plurality of encrypted similarity values.

  According to this configuration, the processing calculation of the terminal device is further reduced, and the number of communications between the server device and the terminal device is further reduced.

  In the similar information search method, the encryption distance may be a Euclidean distance between the reference feature value and the encrypted feature value.

  According to this configuration, the similar information search method can be made more specific.

  The similar information search method further includes a key reception step in which the server device receives a key conversion value that is information obtained by converting a secret key held by the terminal device using a predetermined function. Then, a conversion similarity value that is information obtained by converting the similarity value with the predetermined function is received as the encryption similarity value. In the determination step, the encryption distance is calculated using the key conversion value as the determination. A conversion distance is generated by decoding, and it is determined whether or not the generated conversion distance matches the conversion similarity value.

  According to this configuration, even if a user performs a search based on the same information for a stochastic cipher including a random number, the encrypted feature values do not have the same value. For this reason, according to this similarity value search method, the confidentiality of the information searched by the user can be further enhanced in transmission from the user terminal device to the data operation device and also in the data operation device. As a result, using probabilistic encryption makes it difficult to analyze the ciphertext frequency and the like, thereby improving safety.

  In the similar information retrieval method, the predetermined function is a one-way function.

  According to this configuration, since the key for decryption is converted using a one-way function, it is difficult for the server device to obtain the key itself. For this reason, in the similar information search method, the confidentiality of information for the user is easily protected.

  Further, in this similar information retrieval method, the terminal device further acquires the data, calculates a feature amount indicating a feature of the data from the acquired data, and encrypts the calculated feature amount to encrypt the encrypted feature amount. A feature value transmitting step of generating a generated feature value and transmitting the generated encrypted feature value to the server device; and the terminal device sets a similarity value indicating a degree of similarity and encrypts the set similarity value A similar value transmission step of generating the encrypted similarity value and transmitting the generated encrypted similarity value to the server device, and the terminal device receives the encrypted reference data from the server device, Decrypting the received encrypted reference data.

  According to this configuration, the terminal device can obtain similar information from the server device by performing the feature amount transmission step, the similarity value transmission step, and the decoding step. Therefore, whether the server device calculates the encryption distance between the reference feature value and the encrypted feature value, and the terminal device that has received the encrypted similarity value from the server device performs the decryption, does the encrypted similarity value match? Compared with the case of determining whether or not, in this similar information search method, the processing calculation of the terminal device is reduced. That is, the terminal device does not determine whether or not the encryption distance matches the encryption similarity value. For this reason, the processing calculation of a terminal device reduces, and the frequency | count of communication with a server apparatus and a terminal device can reduce.

  In this similar information search method, the encrypted feature value, the encrypted similarity value, and the reference feature value are encrypted by a homomorphic encryption method.

  According to this configuration, the homomorphic encryption method is an encryption method that cannot be decrypted by the server device, and the key used at this time is the public key of the terminal device. For this reason, the confidentiality of the information searched by the user can be enhanced in transmission from the terminal device to the server device and also in the server device.

  In order to solve such a problem, the server device searches for similar information based on information provided from the terminal device and provides the similar information to the terminal device. The encrypted feature quantity that is the received feature quantity is received, and the encryption distance indicating the degree of similarity between the received encrypted feature quantity and the reference feature quantity for at least one of the plurality of reference feature quantities is calculated. A distance calculation calculation unit that receives the encrypted similarity value that is information obtained by encrypting the similarity value indicating the degree of similarity, and whether or not the received encrypted similarity value matches the calculated encryption distance When it is determined that the reference similar value extraction unit and the reference similar value extraction unit match, reference data that is data corresponding to the reference feature amount used for calculating the encryption distance is encrypted. Dark information Generates referential data, and a cryptographic reference data extraction unit that transmits to the terminal device the generated the encrypted reference data.

  In order to solve such a problem, the similar information search system searches for similar information based on the terminal device and information provided from the terminal device and provides the similar information to the terminal device. The server apparatus of description is provided.

  Also with this configuration, the server device receives the encrypted feature value and the encrypted similarity value from the terminal device, and the server device calculates the encryption distance from the encrypted feature value and the encrypted similarity value. Then, if the encrypted distance matches the encrypted similarity value, the server device generates encrypted reference data and transmits it to the terminal device. For this reason, compared with the case where the terminal device determines whether or not the encryption distance and the encryption similarity value match, the similarity information search method reduces the processing calculation of the terminal device.

  Further, in this server device, when the encryption distance and the encryption similarity value match, only the encrypted reference data is generated and the generated encrypted reference data is transmitted to the terminal device. For this reason, the frequency | count of communication with a server apparatus and a terminal device cannot increase easily.

  Therefore, in the server device and the similar information search system, the processing calculation of the terminal device can be reduced, and the number of communications between the server device and the terminal device can be reduced.

  Note that each of the embodiments described below shows a specific example of the present invention. Numerical values, shapes, components, steps, order of steps and the like shown in the following embodiments are merely examples, and are not intended to limit the present invention. In addition, among the constituent elements in the following embodiments, constituent elements that are not described in the independent claims indicating the highest concept are described as optional constituent elements. In all the embodiments, the contents can be combined.

  Each of the embodiments described below shows a specific example of the present invention. Numerical values, shapes, components, steps, order of steps and the like shown in the following embodiments are merely examples, and are not intended to limit the present invention. In addition, among the constituent elements in the following embodiments, constituent elements that are not described in the independent claims indicating the highest concept are described as optional constituent elements. In all the embodiments, the contents can be combined.

(Overview of services provided)
First, an overview of services provided by the information management system according to the present embodiment will be described with reference to FIGS. 1A, 1B, and 1C.

  FIG. 1A is a block diagram showing an overall image of services provided by the information management system in the first exemplary embodiment. FIG. 1B is a block diagram illustrating an example in which the device manufacturer corresponds to a data center operating company in the first exemplary embodiment. FIG. 1C is a block diagram illustrating an example in which one or both of the device manufacturer and the management company correspond to the data center operating company in the first exemplary embodiment.

  The information management system includes a group 1000, a data center operating company 1110, and a service provider 1120.

  The group 1000 is, for example, a company, an organization, or a household, and the scale is not limited. The group 1000 includes a plurality of devices 1101 including a first device and a second device, and a home gateway 1102. The plurality of devices 1101 include devices that can be connected to the Internet (for example, smartphones, personal computers (PCs) or televisions) and devices that cannot be connected to the Internet by themselves (for example, lighting, washing machines, refrigerators, and the like). Including. The plurality of devices 1101 may include devices that can be connected to the Internet via the home gateway 1102 even if they cannot be connected to the Internet by themselves. The user 1010 uses a plurality of devices 1101 in the group 1000.

  The data center operating company 1110 includes a cloud server 1111. The cloud server 1111 is a virtualization server that cooperates with various devices via the Internet. The cloud server 1111 mainly manages huge data (big data) that is difficult to handle with a normal database management tool or the like. The data center operating company 1110 performs management of data, management of the cloud server 1111, management of the data center that performs them. Details of services performed by the data center operating company 1110 will be described later.

  Here, the data center operating company 1110 is not limited to a company that only manages data or manages the cloud server 1111. For example, as shown in FIG. 1B, when a device manufacturer that develops or manufactures one of a plurality of devices 1101 performs data management or cloud server 1111 management, the device manufacturer This corresponds to the data center operating company 1110. The data center operating company 1110 is not limited to one company. For example, as shown in FIG. 1C, when the device manufacturer and the management company jointly or share the management of data or the cloud server 1111, both or one of them corresponds to the data center operating company 1110. .

  The service provider 1120 includes a server 1121. The server 1121 referred to here includes, for example, a memory in a personal PC regardless of the scale. In addition, the service provider 1120 may not include the server 1121.

  In the above information management system, the home gateway 1102 is not essential. For example, when the cloud server 1111 performs all data management, the home gateway 1102 becomes unnecessary. In addition, in the information management system, there are cases where there is no device that cannot be connected to the Internet by itself, as in the case where all devices in the home are connected to the Internet.

  Next, the flow of information in the information management system will be described.

  First, the first device or the second device of the group 1000 transmits each log information to the cloud server 1111 of the data center operating company 1110. The cloud server 1111 accumulates log information of the first device or the second device (arrow 1131 in FIG. 1A). Here, the log information is information indicating, for example, driving conditions or operation dates / times of the plurality of devices 1101. For example, the log information includes TV viewing history, recorder recording reservation information, washing machine operation date / time, amount of laundry, refrigerator opening / closing date / time, refrigerator opening / closing frequency, etc. Various information that can be acquired from various devices may be included. Note that the log information may be provided directly to the cloud server 1111 from the plurality of devices 1101 itself via the Internet. The log information may be temporarily accumulated in the home gateway 1102 from a plurality of devices 1101 and provided to the cloud server 1111 from the home gateway 1102.

  Next, the cloud server 1111 of the data center operating company 1110 provides the collected log information to the service provider 1120 in a certain unit. Here, the fixed unit may be a unit that can organize and provide the information collected by the data center operating company 1110 to the service provider 1120, or may be a unit that the service provider 1120 requests. In addition, although the information is provided in a fixed unit, it may not be a fixed unit, and the amount of information to be provided may change depending on the situation. Log information is stored in the server 1121 held by the service provider 1120 as necessary (arrow 1132 in FIG. 1A).

  Then, the service provider 1120 organizes the log information into information suitable for the service provided to the user, and provides the information to the user. The user to whom information is provided may be a user 1010 using a plurality of devices 1101 or an external user 1020. As a method for providing information to the users 1010 and 1020, for example, information may be provided directly to the users 1010 and 1020 from the service provider 1120 (arrows 1133 and 1134 shown by broken lines in FIG. 1A). As a method for providing information to the user 1010, for example, the information may be provided to the user 1010 via the cloud server 1111 of the data center operating company 1110 again (arrows 1135 and 1136 in FIG. 1A). . Further, the cloud server 1111 of the data center operating company 1110 may organize the log information into information suitable for the service provided to the user 1020 and provide the information to the service provider 1120.

  Note that the user 1010 may be the same as or different from the user 1020.

(Embodiment 1)
Here, as an embodiment of the present invention, a similar information search system according to the present invention will be described with reference to the drawings.

1.1 Overall Configuration of Similar Information Search System FIG. 2 is a block diagram showing the overall configuration of the similar information search system in the first embodiment.

  As illustrated in FIG. 2, the similar information search system 10 is based on a user terminal device 100 (an example of a terminal device) that requests a search from the data arithmetic device 200 and information provided from the user terminal device 100. A data computing device 200 (which is an example of a server device) that retrieves similar information and provides it to the user terminal device 100.

  The user terminal device 100 and the data arithmetic device 200 are provided one by one, but there are a plurality of each, for example, a plurality of user terminal devices 100 may be connected to one data arithmetic device 200, The data arithmetic device 200 may be connected to one user terminal device 100. Further, the connection form between the devices may be any of a wired Internet line, wireless communication, dedicated communication, and the like. Note that the similar information search system 10 does not necessarily require real-time communication. For example, the user terminal device 100 collects sensed information and similar search requests to some extent and then transmits them together to the data arithmetic device. May be.

1.2 User Terminal Device FIG. 3 is a block diagram showing the configuration of the user terminal device in the first embodiment.

  As illustrated in FIG. 3, the user terminal device 100 requests a search from a data arithmetic device that searches for similar information. The user terminal device 100 includes a sensing unit 101, a feature amount calculation unit 102, a feature amount encryption unit 103, a similar value setting unit 104, a similar value encryption unit 105, a reference data using unit 106, a decryption unit 107, and a key storage unit 108. doing.

  It is assumed that the feature amount encryption unit 103, the similarity value encryption unit 105, and the decryption unit 107 are respectively connected to locations illustrated by A, B, and C of the data arithmetic device 200 (shown in FIG. 4). For example, the user terminal device 100 senses information about the user such as the user's blood pressure, facial color, and CT scan information, and extracts a feature amount indicating the characteristics of the acquired data. Then, the data calculation device requests reference data (data corresponding to a reference feature amount, which will be described later) of symptoms similar to the feature amount from the data calculation device, and uses the obtained reference data for the service to the user. . In addition, when the user terminal device 100 senses information related to the user, it is assumed that the user terminal device 100 obtains a predetermined consent from the user. Procedures such as obtaining consent are outside the scope of the present invention.

1.2.1 Sensing unit The sensing unit 101 senses a user. The sensed data is, for example, vital data such as a user's blood pressure and body temperature, image data such as a user's face image, data obtained by echo or CT scan, and voice / answer data. The sensed data may be user position information (GPS (Global Positioning System) information) or shopping history information.

1.2.2 Feature Quantity Calculation Unit The feature quantity calculation unit 102 calculates a feature quantity from the data acquired by the sensing unit 101. The feature amount calculated here may be, for example, principal components of characteristic parameters in image information such as a face, or data such as the position, area, and width of a certain region. Further, the feature amount may be a coefficient obtained by converting a tendency corresponding to the time axis from the history information into a polynomial, for example. Further, the feature amount may be a numerical value or a vector value in which numerical values are arranged.

1.2.3 Feature Quantity Encryption Unit The feature quantity encryption unit 103 generates an encrypted feature quantity by encrypting the feature quantity indicating the data feature calculated by the feature quantity calculation unit 102. The feature amount encryption unit 103 transmits the generated encrypted feature amount to the data arithmetic device. Here, as a method for performing encryption, it is assumed that homomorphic encryption that enables calculation for searching for similar information while the feature amount is encrypted by the data operation device is used. When concealing the feature quantity from the data arithmetic device, the public key of the user terminal device 100 stored in the key storage unit 108 described later is used.

1.2.4 Similar Value Setting Unit The similar value setting unit 104 sets a similar value indicating the degree of similarity when searching. The similarity value here is a value indicating how close the feature amount is to be searched in the data arithmetic apparatus. For example, the data arithmetic device calculates the Euclidean distance between the feature quantity and the reference feature quantity, and sets a certain value D as a similarity value when searching for a value whose value is less than a certain value D. Alternatively, all values of 0, 1,..., D−1 that are similar values of a certain value D may be set. Alternatively, the similarity value may be set for each vector value of the feature amount.

1.2.5 Similar Value Encryption Unit The similar value encryption unit 105 generates an encrypted similarity value by encrypting a similarity value indicating the degree of similarity. The similar value encryption unit 105 transmits the generated encrypted similar value to the data arithmetic device. The encrypted similarity value is used to determine a similarity value with the encrypted feature amount in an encrypted state and extract a reference ID that meets the determination condition in the data processing device.

1.2.6 Decryption Unit The decryption unit 107 is information obtained by encrypting reference data (similarity search result) generated from the encrypted feature value and the encrypted similarity value by the search of similar information by the user terminal device 100. Is received from the data processing device. Then, the decryption unit 107 decrypts the received encrypted reference data.

1.2.7 Reference Data Utilization Unit The reference data utilization unit 106 uses the reference data obtained by the decryption unit 107. For example, the reference data utilization unit 106 displays the reference data as a graph or a statistical value on the user terminal, or uses this information to provide advice on lifestyle improvement or recommended meals to the user. Or

1.2.8 Key Storage Unit The key storage unit 108 stores keys used for the feature amount encryption unit 103, the similarity value encryption unit 105, and the decryption unit 107. The encryption method and key used in each may be the same or different. For example, the key used by the feature value encryption unit 103 and the similar value encryption unit 105 is the public key of the user terminal device 100 of the homomorphic encryption method (the corresponding private key is also stored in the key storage unit) and decrypted. The key used in the unit 107 may be a secret key of the user terminal device 100 of a public key encryption method that is not a homomorphic encryption method (a corresponding public key is shared with the data processing device). The key used in the decryption unit 107 may be a secret key of the user terminal device 100 having the same homomorphic encryption as the key used in the feature amount encryption unit 103.

1.3 Data Arithmetic Device FIG. 4 is a block diagram showing the configuration of the data arithmetic device in the first embodiment.

  As illustrated in FIG. 4, the data arithmetic device 200 searches for similar information based on information provided from the user terminal device (in response to a search request from the user), and provides the searched information to the user terminal device. To do. The data arithmetic device 200 includes a reference feature amount storage unit 201, an encrypted distance calculation unit 202, a reference similarity value extraction unit 203, an encrypted reference data extraction unit 204, and a reference data storage unit 205. It is assumed that the encrypted distance calculation unit 202, the reference similarity value extraction unit 203, and the encrypted reference data extraction unit 204 are connected to locations illustrated in the user terminal device 100 (FIG. 3), respectively.

1.3.1 Reference feature amount storage (FIG. 5A)
FIG. 5A is a diagram illustrating an example of a reference feature amount storage unit in the data arithmetic device according to Embodiment 1. FIG. 5A illustrates an example of the reference feature amount stored in the reference feature amount storage unit 201.

  As shown in FIG. 5A, the reference feature quantity storage unit 201 stores a reference feature quantity Yi to be searched when the data arithmetic device performs a similarity search. The identifier ID corresponds to i, and the reference feature amount is described as Yi. The identifier ID and the reference feature amount are stored in a pair in the reference feature amount storage unit 201. 5A, identifier IDs are 1, 2,..., And reference feature amounts Y1, Y2,... Corresponding to each identifier ID are stored. In this example, each reference feature amount is represented by a vector value. The reference feature amount may be encrypted and stored.

1.3.2 Encrypted Distance Calculation Unit The encrypted distance calculation unit 202 receives an encrypted feature quantity that is a feature quantity encrypted by the homomorphic encryption method from the user terminal device. The encrypted distance calculation unit 202 uses the encrypted value of the distance indicating the degree of similarity between the received encrypted feature quantity and the reference feature quantity for at least one of the plurality of reference feature quantities, as a feature quantity and a reference feature. The amount is calculated with encryption. That is, the encrypted distance calculation unit 202 calculates the distance between the feature value generated by the user terminal device and the reference feature value stored in the data calculation device 200. Specifically, the encryption distance calculation unit 202 encrypts the encrypted feature quantity received from the user terminal device and the reference feature quantity received from the reference feature quantity storage unit 201, and calculates the distance while each is encrypted. To do. Then, the encrypted distance calculation unit 202 outputs the encrypted distance (encrypted distance) to the reference similarity value extraction unit 203. The distance is a Euclidean distance between the reference feature quantity and the feature quantity. The distance may be, for example, an absolute value of a difference when each feature amount is a numerical value, or an absolute value of a difference between corresponding vector elements when each feature amount is a vector having a numerical value as an element. May be added. Further, the encryption distance may be a cosine similarity obtained by multiplying and summing each vector element. Specifically, in a vector whose elements are numerical values, the feature quantity is (x1, x2, x3,... Xn) and the reference feature quantity is (y11, y12, y13,... Y1n). ), The distance obtained by adding the absolute values of the vector element differences is represented by Σ | xi−y1i |, the cosine similarity is represented by Σxi × y1i, and the Euclidean distance is Σ (xi−y1i). ) ^ 2 The encryption distance calculation unit 202 uses a homomorphic encryption method in order to perform these calculations while encrypting the feature quantity and the reference feature quantity. In homomorphic cryptography operations, calculation may be performed for each element of the vector value, or in order to speed up the calculation, the vector value of the feature value is mapped to a polynomial with each coefficient of the polynomial, and the homomorphic encryption is performed. The distance may be calculated by calculation between polynomials.

1.3.3 Reference Similar Value Extraction Unit The reference similar value extraction unit 203 receives the encrypted similarity value from the similarity value encryption unit. The encrypted similarity value is information obtained by encrypting a similarity value indicating the degree of similarity. The encrypted information is preferably encrypted by a homomorphic encryption method.

  The reference similarity value extraction unit 203 uses the encrypted similarity value received from the similarity value encryption unit and the encryption distance received from the encryption distance calculation unit 202 to determine whether the distance and the similarity value match. (The fact that the encrypted distance and the encrypted similarity value match is the same as the distance and the similarity value match). When it is determined that the distance and the similarity value match, the reference similarity value extraction unit 203 extracts the identifier ID of the corresponding reference feature amount. The reference similarity value extraction unit 203 does not extract the identifier ID of the corresponding reference feature value when it is determined that the encryption similarity value and the encryption distance do not match.

1.3.4 Reference data storage (FIG. 5B)
FIG. 5B is a diagram illustrating an example of a reference data storage unit in the data arithmetic device in the first exemplary embodiment. FIG. 5B shows an example of the identifier ID and reference data stored in the reference data storage unit.

  As shown in FIG. 5B, the reference data storage unit 205 stores reference data to be searched for the data arithmetic device to perform a similar search. The identifier ID and the reference data are stored in pairs in the reference data storage unit. In the reference data storage unit 205, identifier IDs 1, 2,... I are stored, and reference data Z1, Z2,. The identifier ID corresponds to i, and the reference data is described as Zi. As reference data, for example, a history of illness or treatment (reference data in FIG. 5B) corresponding to a feature value indicating the tendency of blood pressure measurement values (reference feature value in FIG. 5A), or a feature value indicating user position information. It may be a history of purchased products (reference data in FIG. 5B) corresponding to (reference feature amount in FIG. 5A). In the example of FIG. 5B, a user with an identifier ID of 1 accumulates a history of illnesses and treatments such as hospitalization for cerebral infarction in October 2013, and a user with an identifier ID of 2 accumulates treatment for diabetes in February 1999. ing. The reference data may be encrypted and stored.

1.3.5 Encrypted Reference Data Extraction Unit The encrypted reference data extraction unit 204 generates encrypted reference data when the reference similarity value extraction unit 203 determines that they match. The encrypted reference data is information obtained by encrypting the reference data that is data corresponding to the reference feature amount used for calculating the encryption distance. The encrypted reference data extraction unit 204 transmits the generated encrypted reference data to the decryption unit of the user terminal device. Specifically, the encrypted reference data extraction unit 204 extracts the reference data corresponding to the identifier ID extracted by the reference similarity value extraction unit 203 from the reference data storage unit 205, and uses this as the decryption unit of the user terminal device. Send. The encrypted reference data extracting unit 204 encrypts and transmits the data on the communication path during transmission. In addition, you may anonymize before encryption so that the corresponding user cannot be specified from reference data. Further, the data arithmetic device 200 may obtain statistical information such as average and frequency from a plurality of extracted reference data, encrypt this, and transmit it to the decrypting unit of the user terminal device.

1.4 Operation of Similar Information Search System 1.4.1 Operation Overview The operation of the similar information search system 10 will be described with reference to FIG.

  FIG. 6 is a sequence diagram showing the operation of the similar information search system in the first embodiment.

  As shown in FIG. 6, in step S101, the user terminal device 100 acquires information by a sensing unit.

  In step S102, the feature amount calculation unit 102 calculates a feature amount X from information sensed by the sensing unit. For example, the feature quantity X may be an m-order vector whose elements are numerical values as follows.

  X = (x1, x2,..., Xm)

  In step S <b> 103, the similarity value setting unit sets a similarity value that serves as a determination criterion when searching. For example, in the case of searching for data that is less than the distance D, the distances 0, 1, 2,..., D-1 are set as similar values.

  In step S104, the feature amount encryption unit acquires data, and generates an encrypted feature amount by encrypting a feature amount indicating the feature of the data using the homomorphic encryption method from the acquired data. The similar value encryption unit generates an encrypted similar value by encrypting the similar value using a homomorphic encryption method. The homomorphic encryption method is an encryption method that cannot be decrypted by the data arithmetic device 200, and the key used at this time is the public key of the user terminal device 100.

Assuming that the encryption function is Enc, the encrypted feature quantity is
Ex = (Enc (x1), Enc (x2),..., Enc (xm)), and the encrypted encrypted similarity value is
Enc (0), Enc (1), ..., Enc (D-1)
It can be expressed as.

  In step S <b> 105, the user terminal device 100 indicates the encrypted feature value and the encrypted similarity value, and requests similar reference data that satisfies the condition. That is, the encrypted feature value is transmitted to the encryption distance calculation unit, and the encrypted similarity value is transmitted to the reference similarity value extraction unit (step S102, step S104, and step S105 are examples of the feature value transmission step, step S103 to step S103. S105 is an example of a similar value transmission step).

  Specifically, the encryption distance calculation unit receives the encrypted feature amount that is the feature amount encrypted by the homomorphic encryption method from the feature amount encryption unit (feature amount reception step). The reference similarity value extraction unit receives an encrypted similarity value that is information obtained by encrypting a similarity value indicating the degree of similarity from the similarity value encryption unit (similar value reception step). The encrypted similarity value that is encrypted information is preferably encrypted by a homomorphic encryption method.

  In the similarity value receiving step, a plurality of encrypted similarity values that are information obtained by encrypting each of a plurality of similar values indicating a plurality of similar degrees may be received.

  In step S106, the data arithmetic device 200 selects the reference feature value Yi = (yi1, yi2,..., Yim) from the reference feature value storage unit of the i-th identifier ID.

In step S107, the encrypted distance calculation unit indicates the degree of similarity between the encrypted reference feature quantity and the encrypted feature quantity received by the data arithmetic device 200 for at least one of the plurality of reference feature quantities. Calculate distance encrypted. The encrypted reference feature is
Ey = (Enc (yi1), Enc (yi2), ..., Enc (yim))
It can be expressed as. Note that the reference feature amount encrypted for at least one of the plurality of reference feature amounts is preferably encrypted by the homomorphic encryption method.

  The encryption distance calculation unit calculates and adds the difference between each vector of the feature quantity X and the reference feature quantity Yi, and calculates the following encryption distance EDi using the property of the homomorphic encryption method.

  EDi = Enc (| x1-yi1 | + | x2-yi2 | + .. + | xm-yim |)

  Step S107 is an example of a distance calculation step. In the above description, the absolute value of the difference between the vector elements is accumulated and used as the encryption distance. In addition, the data arithmetic device 200 may execute the distance calculation step for each of the plurality of encrypted similarity values.

  In step S108, the reference similarity value extraction unit confirms whether the condition is satisfied using the encryption distance and the encryption similarity value (an example of a determination step). That is, the determination step determines whether or not the calculated encryption distance matches the encrypted similarity value received by the data arithmetic device 200. Note that the data arithmetic device 200 may execute the determination step for each of the plurality of encrypted similarity values.

  As an example of the confirmation method, it is confirmed whether or not the encryption distance EDi matches any of the encryption functions Enc (0), Enc (1),..., Enc (D-1). If they match, the contents of the encryption function Enc with the encryption distance EDi, that is, the distance between the feature quantity and the reference feature quantity, | x1-yi1 | + | x2-yi2 | + .. + | xm -Ym | means that each of the distances 0, 1,.

  If they do not match (is not satisfied), the next identifier ID is selected and the process returns to step S106.

  If it matches (or satisfies) any of them, the reference similarity value extraction unit records the identifier ID at this time because the distance between these feature values is less than the similarity value D in step S109. Then, step S106 to step S109 are repeated for each identifier ID in the reference feature quantity storage unit.

  In step S110, the encrypted reference data extraction unit is information obtained by encrypting the reference data that is data corresponding to the reference feature amount used for calculating the encryption distance when it is determined that they match in the determination step. Generate encrypted reference data. That is, in step S110, the encrypted reference data extraction unit extracts reference data corresponding to all identifier IDs extracted in step S109 from the reference data storage unit, and encrypts the reference data using the public key of the user terminal device 100. To do.

  In step S111, the encrypted reference data extraction unit transmits the generated encrypted reference data to the user terminal device (steps S110 and S111 are examples of a reference data transmission step). The encrypted reference data extraction unit may execute a reference data transmission step for each of the plurality of encrypted similarity values.

  In step S112, the composite unit receives the encrypted reference data from the encrypted reference data extraction unit. Then, the user terminal device 100 decrypts the encrypted reference data received from the data arithmetic device 200 and uses the reference data (an example of a decryption step).

1.4.2 Feature Quantity Calculation Example As the feature quantity calculation in step S102, for example, when image data such as face and echo information is acquired by the sensing unit, a principal component of a characteristic parameter of the image information is obtained. Alternatively, it may be the position, area or width of a certain region. In addition, when blood pressure information is acquired, a trend corresponding to the time axis is represented by, for example, a polynomial from a history of blood pressure measurement information measured so far stored separately in the user terminal device 100 (not shown in FIG. 3). The coefficient may be used as a feature amount. An example of the trend polynomial corresponding to the time axis is shown in FIG.

  FIG. 9 is a graph illustrating a calculation example of the time and the feature amount displayed by the user terminal device in the first embodiment. In FIG. 9, time represents the time from the past (for example, one year ago) to the present. In FIG. 9, an approximate curve is obtained from each measured value (indicated by x) of each feature quantity, and the coefficient of the approximate curve is used as the feature quantity.

1.4.3 Calculation Example of Encrypted Distance As the calculation of the encrypted distance in step S107, in the above description, the vector value corresponding to the feature amount obtained by the user terminal device 100 and the reference feature amount in the data operation device 200 is calculated. The accumulation of the difference is obtained with encryption. The encryption distance is a Euclidean distance between the reference feature quantity and the encrypted feature quantity. In addition to this, the calculation example of the encryption distance may be, for example, a cosine similarity calculation method. However, in this case, it is preferable to use completely homomorphic encryption that can be obtained while encrypting both addition and multiplication, or limited homomorphic encryption with limited number of multiplications (Samhow homomorphic encryption).

1.4.4 Data exchange between user terminal device and data operation device (FIG. 7A, FIG. 7B)
FIG. 7A is a diagram illustrating a data format example between a user terminal and a data device in the first exemplary embodiment. FIG. 7B is a diagram showing an example of a data format between the user terminal and the data device in the first exemplary embodiment. 7A and 7B show an example of the format of data exchanged between the user terminal device 100 and the data arithmetic device 200 in step S105 and step S111. The sender identifier ID, the receiver identifier ID, and the command And data. When commands are exchanged in parallel between a plurality of user terminal devices 100 and a plurality of data arithmetic devices 200, an identifier for taking the correspondence in steps S105 and S111 may be added.

1.4.5 Display example (FIGS. 8A and 8B)
FIG. 8A is a diagram illustrating a display example of the user terminal device in the first embodiment. FIG. 8B is a diagram illustrating an example of display on the user terminal device in the first embodiment.

  FIG. 8A is an example of display on the user terminal device 100 in step S101 of FIG. Here, when the user clicks (selects) Start, the sensing unit starts and measures blood pressure. Then, the user selects whether to search for a similar case based on the recent blood pressure trend, by selecting “Yes” or “Cancel”. When the user clicks “Yes” and agrees, the user terminal device calculates the feature amount from the trend using the measured value and the recent history information. Further, when the user clicks “cancel” and does not agree, the user terminal device does not transmit information to the data calculation device so as to search for similar cases.

  FIG. 8B is an example of display in the case where the user is advised to eat or exercise using the retrieved reference similar data (in this case, a disease with a similar tendency of blood pressure fluctuation, which subsequently developed). Here, the user terminal device displays the blood pressure tendency from the past to the present and the reference similar data based on the user information. In this user terminal device, by giving advice based on user information, the advice becomes more realistic and useful for the user.

1.5 Effects of Embodiment 1 In Embodiment 1, the data operation device receives the encrypted feature value and the encrypted similarity value from the user terminal device, and the encrypted reference data extraction unit extracts the encrypted reference data. To do. Since the data arithmetic device extracts only the encrypted reference data that is less than the similarity value D and transmits it to the user terminal device, the amount of calculation of the user terminal device and the amount of communication between the data arithmetic device and the user terminal device Can be reduced. Moreover, in a user terminal device, a similar value can be set flexibly according to a user's intention.

  Further, the encrypted feature quantity is encrypted by the homomorphic encryption method and cannot be decrypted by the data arithmetic device. For this reason, in this similar information search method etc., the confidentiality of the information searched by the user can be enhanced in transmission from the user terminal device to the data calculation device and also in the data calculation device.

(Embodiment 2)
Here, as a second embodiment of the present invention, a similar information search system according to the present invention will be described with reference to the drawings. Differences between the second embodiment and the first embodiment are as follows. In the first embodiment, in step S108, the reference similarity value extraction unit determines whether or not the encryption distance matches the encryption similarity value. This is based on the premise that if the original data is the same, a deterministic encryption method that also matches the encrypted data is used. On the other hand, in the second embodiment, a random number is generated at the time of encryption, and the encrypted data including the random number is encrypted, so that even if the original data is the same, the encrypted data does not have the same value. In some cases, a stochastic encryption method is used. If the probabilistic encryption method is used, it becomes difficult to analyze from the frequency of the ciphertext and the safety can be improved. On the other hand, in the deterministic encryption method of the first embodiment, when a random number is used at the time of encryption, it is impossible to determine whether or not the encryption distance matches the encryption similarity value.

  In the second embodiment, a method capable of performing an operation for searching for similar information while being encrypted will be described in the case of using a probabilistic encryption method. Therefore, in the similar information retrieval system, a key for decryption is converted from the user terminal device and transferred to the data arithmetic device, and the distance converted by the data arithmetic device is decrypted. In the similar information search system, the element of the random number is removed by decoding, and it can be determined whether or not the conversion distance matches the conversion similarity value. In addition, since the key for decryption is converted using a one-way function, the data arithmetic device cannot obtain the key itself. In the following, differences between the second embodiment and the first embodiment will be mainly described, and the same configurations as those of the first and second embodiments will be denoted by the same reference numerals and detailed description regarding the configurations will be given. Is omitted.

2.1 User Terminal Device FIG. 10 is a block diagram illustrating a configuration of the user terminal device according to the second embodiment.

  As shown in FIG. 10, the user terminal device 100 includes a key conversion unit 109 and a similar value conversion unit 110 in addition to the configuration of the first embodiment. The block diagram of FIG. 10 to which the same reference numerals as those in FIG. 3 are assigned has the same functions as those in FIG. Assume that the feature amount encryption unit 103, the similarity value conversion unit 110, the key conversion unit 109, and the decryption unit 107 in FIG. 10 are connected to D, E, F, and G in FIG.

2.1.1 Key Conversion Unit The key conversion unit 109 calculates a key conversion value. The key conversion value is information obtained by converting the secret key of the user terminal device 100 using a one-way function. An example of a one-way function is a power operation that should be a power of a secret key. The conversion using the one-way function means that it is easy to perform a power operation from the secret key, but it is difficult to obtain the power value from the power value. Obtaining the power value from the power value results in difficulty in LOG calculation in the discrete logarithm domain.

2.1.2 Similar Value Conversion Unit The similar value conversion unit 110 converts a similar value set using the same one-way function as that used in the key conversion unit 109. In the data arithmetic device, the conversion distance (distance in the conversion area obtained by decryption using the encryption distance and the conversion decryption key), similarly, by matching with the similar value converted using the one-way function , It is determined whether or not they are similar.

2.2 Data operation device (Fig. 11)
FIG. 11 is a block diagram illustrating the configuration of the data arithmetic device according to the second embodiment.

  As shown in FIG. 11, in addition to the configuration of the first embodiment, the data arithmetic device 200 includes a conversion distance decoding unit 206 and a reference conversion similarity value extraction unit 207 instead of the reference similarity value extraction unit of the first embodiment. Is provided. Note that the block diagram of FIG. 11 to which the same reference numerals as those in FIG. 4 are assigned has the same functions as those in FIG. Further, D, E, F, and G in FIG. 11 are connected to corresponding portions in FIG.

2.2.1 Conversion distance decryption unit The conversion distance decryption unit 206 encrypts using the key conversion value, which is information obtained by converting the secret key of the user terminal device using the one-way function in the conversion area. A conversion distance obtained by decoding the conversion distance is obtained (generated). Since the homomorphic encryption method used here is a probabilistic method, a random number element is included in the encryption distance. However, the random number element is removed from the conversion distance obtained by decoding using the conversion / decryption key.

2.2.2 Reference conversion similarity value extraction unit The reference conversion similarity value extraction unit 207 determines whether or not the conversion distance and the converted conversion similarity value match in the conversion area. The reference conversion similarity value extraction unit 207 determines that the conversion distance satisfies the condition of the conversion similarity value set when the conversion distance matches any of the converted conversion similarity values, and the corresponding identifier ID To extract. If they do not match, the corresponding identifier ID is not extracted.

2.3 Operation of Similar Information Retrieval System The operation of the similar information retrieval system 10 according to the second embodiment will be described with reference to the sequence diagram shown in FIG.

  FIG. 12 is a sequence diagram showing the operation of the similar information search system in the second embodiment.

  As shown in FIG. 12, in step S101, the user terminal device 100 acquires information by a sensing unit.

  In step S102, the feature amount calculation unit 102 calculates a feature amount X from information sensed by the sensing unit. For example, the feature quantity X may be an m-order vector in which each element is a numerical value as follows.

  X = (x1, x2,..., Xm)

  In step S <b> 103, the similarity value setting unit determines a similarity value that is a determination criterion when searching. For example, in the case of searching for data that is less than the distance D, the distances 0, 1, 2,.

  In step S104, the feature amount encryption unit obtains data from the sensing unit via the feature amount calculation unit, and encrypts the feature amount indicating the feature of the data by using the homomorphic encryption method from the obtained data. Generate a feature value. Further, the similarity value conversion unit obtains a one-way function value of the similarity value. That is, the similarity value conversion unit generates a conversion similarity value by converting a similarity value as an encryption similarity value by a homomorphic encryption method. The homomorphic encryption method is an encryption method that cannot be decrypted by the data arithmetic device 200. The key used at this time is the public key of the user terminal device 100. In the second embodiment, unlike the first embodiment, the homomorphic encryption method is a probabilistic encryption method including a random number element.

Here, if the encryption function is Enc1, the encryption feature amount is
E1x = (Enc1 (x1), Enc1 (x2), ..., Enc1 (xm))
It expresses. Further, if the one-way function for converting the similarity value is F, the conversion similarity value (one-way function value) is
F (0), F (1), ..., F (D-1)
It can be expressed as.

  In step S113, the key conversion unit calculates a key conversion value F (s) that is information obtained by converting the secret key s held by the user terminal device 100 with a predetermined function. The predetermined function is a one-way function. The key conversion unit calculates a key conversion value that is an operation value (for example, a power value of s) of the secret key s as necessary.

  In step S <b> 105, the user terminal device 100 indicates the encrypted feature value, the conversion similarity value, and the key conversion value, and requests similar reference data that satisfies the condition. That is, the user terminal device 100 transmits the encrypted feature value, the conversion similarity value, and the key conversion value to the data arithmetic device 200, and the data arithmetic device 200 receives them (Step S102, Step S104, Step S113, and Step S105). An example of the feature reception step, Step S103, Step S104, Step S113, and Step S105 are an example of a similar value reception step, and Step S113 and Step S105 are an example of a key reception step).

  Specifically, the feature amount encryption unit transmits the encrypted feature amount to the encryption distance calculation unit, and the encryption distance calculation unit receives (an example of a feature amount reception step). Further, the similarity value conversion unit transmits the conversion similarity value to the conversion distance decoding unit, and the conversion distance decoding unit receives (an example of a similar value reception step). Further, the key conversion unit transmits the key conversion value to the reference conversion similarity value extraction unit, and the reference conversion similarity value extraction unit receives (an example of a key reception step).

  In the similarity value receiving step, the data arithmetic device 200 uses a plurality of transformed similarity values that are information obtained by encrypting each of a plurality of similar values indicating a plurality of similar degrees with a one-way function as an encrypted similarity value. May be received.

  In step S106, the data arithmetic device 200 selects the reference feature value Yi = (yi1, yi2,..., Yim) from the reference feature value storage unit of the i-th identifier ID.

In step S107, the encryption distance calculation unit calculates the distance between the reference feature amount encrypted by the encryption function Enc1 and the encrypted feature amount while encrypting them (an example of a distance calculation step). The encrypted reference feature is
E1y = (Enc1 (yi1), Enc1 (yi2), ..., Enc1 (yim))
It can be expressed as. As a result, the encryption distance calculation unit can calculate the encryption distance ED1i using the property of the homomorphic encryption method if the difference between the vectors of the feature quantity X and the reference feature quantity Yi is obtained and added.

  ED1i = Enc1 (| x1-yi1 | + | x2-yi2 | + .. + | xm-yim |)

  In the above description, the absolute value of the difference between the vector elements is the distance obtained by accumulating.

In step S114, the conversion distance decryption unit decrypts the encrypted distance in the conversion area using the key conversion value. As a result of decryption,
F (| x1-yi1 | + | x2-yi2 | + .. + | xm-yim |) is obtained (this value is referred to as a conversion distance). The encryption distance ED1i includes a random number generated at the time of encryption, and the output of the encryption function Enc1 does not match even if the input is the same. On the other hand, the outputs of the one-way function F match when the inputs are the same.

  In step S108, the conversion distance decryption unit generates the conversion distance by decrypting the encrypted distance using the key conversion value. The reference conversion similarity value extraction unit determines whether the generated conversion distance matches the conversion similarity value (step S108 is an example of a determination step). That is, the reference conversion similarity value extraction unit checks whether the conversion distance matches any of the conversion similarity values F (0), F (1),..., F (D−1). If they match, the contents of the one-way function F, that is, the distance between the feature quantity and the reference feature quantity, | x1-yi ||| 2-2-yi |||||||||||| It means that the distance is any one of 0, 1,.

  If they do not match (is not satisfied), the reference conversion similarity value extraction unit selects the next identifier ID and returns to step S106.

  If it matches (or satisfies) any of them, in step S109, the reference conversion similarity value extraction unit records the identifier ID at this time. Then, step S106 to step S109 are repeated for each identifier ID in the reference feature quantity storage unit.

  In step S110, the encrypted reference data extraction unit extracts reference data corresponding to all the identifier IDs extracted in S109 from the reference data storage unit, and encrypts the reference data using the public key of the user terminal device 100. That is, the encrypted reference data extraction unit encrypts the reference data, which is data corresponding to the reference feature amount used for calculating the encryption distance, when it is determined in step S108 (determination step) that they match. Encrypted reference data is generated.

  In step S111, the encrypted reference data extraction unit transmits the generated encrypted reference data to the user terminal device 100 (steps S110 and S111 are examples of a reference data transmission step).

  In step S112, the decryption unit receives encrypted reference data, which is information obtained by encrypting the reference data generated from the encrypted feature value and the encrypted similarity value, from the data arithmetic device 200. The decryption unit receives the encrypted reference data (similarity search result) transmitted from the encrypted reference data extraction unit, decrypts it, and uses the reference data (an example of a decryption step).

2.3.1 Specific Calculation Example for Ring LWE (Learning With Errors) As a specific example of Enc1, key generation, encryption, decryption, and ciphertext multiplication of a homomorphic encryption method using ring LWE This will be described below. The ring LWE is described in Chapter 13 of Non-Patent Document 1.

  Key generation: n is configured as a power of 2, and p is configured as a prime number such that p-1 is a multiple of 2n. Let t be a prime number smaller than p. Let Rt = (Z / tZ) [x] / (x ^ n + 1) be a plaintext space. Here, Z means an integer, and Rt is a remainder field obtained by dividing a polynomial whose coefficient is an integer equal to or less than t by (x ^ n + 1). Also, the secret key s is arbitrarily selected, e is arbitrarily selected, and a1 is arbitrarily selected from Rp. Then, (a0 = − (a1 × s + t × e), a1) is a public key.

Encryption: The plaintext m (εRt) is encrypted using the public key (a0, a1) as follows. Choose e1, e2, e3 arbitrarily,
Enc1 (m) = (m + a0 × e1 + t × e3, a1 × e1 + t × e2)

  Decryption: The ciphertext c = (c0, c1,..., Ck) is decrypted using the secret key s as follows.

Dec1 (c) = c0 * s ^ 0 + c1 * s ^ 1 + c2 * s ^ 2 + ... + ck * s ^ k (εRq)
Dec1 (c) is m + t × e4 (where | t × e4 | <p / 2).

  Multiplication of ciphertext: Multiplication of ciphertext c = (c0, c1,..., Ck) and ciphertext d = (d0, d1,..., Dl) is h = (h0, h1,..., hk + 1).

Where hi is
Σcj × di−j = c0 × di + c1 × di−1 +... + Ci × d0
Ask for.

  Ciphertext addition: Ciphertext c = (c0, c1,..., Ck) and ciphertext d = (d0, d1,..., Dl) have the same length by adding 0 to the shorter vector. After that, each element is added to obtain.

  Using the encryption function Enc1 described above, specific calculation of the sequence of FIG. 12 is shown below.

  In step S104, the feature amount encryption unit includes the encrypted feature amount and the conversion similarity value as follows. Here, r is an arbitrary random number.

E1x = (Enc1 (x1), Enc1 (x2), ..., Enc1 (xm))
F (0) = r ^ 0, F (1) = r ^ 1, F (D-1) = r ^ D-1

  In step S113, the key conversion unit obtains the next key conversion value F (s).

  F (s) = r ^ s, F (s ^ 2) = r ^ (s ^ 2), ..., F (s ^ k) = r ^ (s ^ k)

  In step S106, the encrypted reference feature values are as follows.

  E1y = (Enc1 (y1), Enc1 (y2), ..., Enc1 (ym))

In step S107, the encryption distance calculation unit obtains the encryption distance EDi using the encrypted feature quantity E1x and the encrypted reference feature quantity E1y. By homomorphism in addition and multiplication of the encryption function Enc1
ED1i = Enc1 (distance between feature quantity X and reference feature quantity Yi)
Is required. The encryption distance ED1i is set to (c0, c1,..., Ck).

  In step S114, the conversion distance decryption unit calculates the following using the encrypted distance ED1i and the key conversion value F (s).

r ^ c0 + F (s) ^ c1 + .. + F (s ^ k) ^ ck

  From the above, this value is r ^ Dec1 (ED1i). Dec1 (ED1i) indicating the power of the calculated value is a distance between the feature quantity X and the reference feature quantity Yi.

  In step S108, the value obtained above and the conversion similarity value F (0) = r ^ 0, F (1) = r ^ 1,..., F (D-1) = r ^ (D-1) Each is compared (determines whether or not they match). If the conversion distance matches the conversion similarity value, it is determined that the reference feature amount satisfies the similarity condition because the feature amount X and the reference feature amount Yi are any one of the distances 0 to (D-1). Note that although the unidirectional function for obtaining the power of r may strictly match the function output of different inputs (referred to as a collision), it is assumed here that it can be almost ignored in terms of probability.

2.3.2 Specific Calculation Example for BGN Cipher As a second specific example of the encryption function Enc1, key generation, encryption, decryption, and ciphertext multiplication for BGN encryption will be described below. BNG encryption is described in Non-Patent Document 2.

  Key generation: q1 and q2 are prime numbers, respectively, and N = q1 × q2 is obtained. Let G and G ′ be a finite cyclic group for information with order N, and generate G generator g and h = u ^ q2 (where u is the generator of G). Also, e is G × G → G ′ pairing. Pairing is a function in which e (u ^ a, v ^ b) = e (u, v) ^ (ab) holds for an arbitrary u, vεG and a, bε integer.

  Of these, the secret key is q1, and the public key is (N, e, g, h).

Encryption: Encryption of plaintext mε {0,1,..., T} (T <q2) (where plaintext space is sufficient to solve the discrete logarithm problem) is the public key (N, e, g, h) are used as follows. Select a random number r arbitrarily,
Enc1 (m) = (g ^ m) × (h ^ r) = c
Is a ciphertext.

  Decryption: The ciphertext c is decrypted as follows using the secret key q1.

Dec1 (c) = c ^ q1
Dec1 (c) is (g ^ m) ^ q1 * (h ^ r) ^ q1
= (G ^ q1) ^ m * u ^ (Nr)
= (G ^ q1) ^ m
From here, the discrete logarithm problem is solved and m is decoded.

  Multiplication of ciphertext: Multiplicative homomorphism between ciphertext E (m1) of m1 and ciphertext E (m2) of m2 is satisfied, g1 = e (g, g), h1 = e (G, h).

  If u = g ^ α, h = u ^ 2 = g ^ αq2. At this time, a ciphertext for m1m2 can be created from E1 (m1) and E1 (m2) as follows.

E1 (m1) = (g ^ m1) × (h ^ r1)
E1 (m2) = (g ^ m2) × (h ^ r2)
e (E1 (m1), E1 (m2)) h1 ^ r = (g1 ^ (m1m2)) h1 ^ r3εG ′

  Here, r3 = m1r2 + r2m1 + αq2r1r2 + r.

  Addition of ciphertext: The following additive homomorphism is satisfied between the ciphertext E1 (m1) of m1 and the ciphertext E1 (m2) of m2. That is, a ciphertext for m1 + m2 can be created from the ciphertext E1 (m1) and the ciphertext E1 (m2).

  E1 (m1) × E1 (m2) = (g ^ (m1 + m2)) × h ^ (r1 + r2) = E1 (m1 + m2)

  Using the encryption function Enc1 described above, specific calculation of the sequence of FIG. 12 is shown below.

  In step S104, the encrypted feature amount and the conversion similarity value are as follows. Here, r is an arbitrary random number.

E1x = (Enc1 (x1), Enc1 (x2), ..., Enc1 (xm))
F (0) = g1 ^ Q, F (1) = g1 ^ (2Q),..., F (D-1) = g1 ^ ((D-1) Q)

  In step S113, the key conversion unit generates an arbitrary random number R and obtains the next key conversion value.

  F (s) = R × q1 = Q

  In step S106, the encrypted reference feature values are as follows.

  E1y = (Enc1 (y1), Enc1 (y2), ..., Enc1 (ym))

  In step S107, the encryption distance calculation unit obtains the encryption distance EDi using the encrypted feature quantity E1x and the encrypted reference feature quantity E1y. The following formula is satisfied by the homomorphism in the addition and multiplication of Enc1.

ED1i = Enc1 (distance between x and y)
Is required. Note that the distance between x and y may be, for example, a difference between them, or may be a cosine similarity (x1y1 + x2y2 + .. + xmym) using only one-time multiplicative homomorphism.

  Note that ED1i has a format of (g1 ^ (distance between x and y)) x (h ^ r4) and includes a random number element.

  In step S114, the following is calculated using the encryption distance ED1i and the key conversion value.

(ED1i) ^ F (s) = ((g1 ^ (distance between x and y)) * (h ^ r4)) ^ (R * q1)
= (G1 ^ (distance between x and y)) ^ Q
= (G1 ^ Q) ^ (distance between x and y)

In step S108, the transform distance decoding unit obtains the values F (0) = g1 ^ Q, F (1) = g1 ^ (2Q),..., F (D-1) = g1 ^ ((D− 1) Q)
Are compared. If any one of these values is established, it is determined that the reference feature amount satisfies the similarity condition because the feature amount X and the reference feature amount Yi are any one of the distances 0 to (D-1). To do.

2.4 Effects of Second Embodiment In the second embodiment, the user terminal device transmits the data to the data arithmetic device using the stochastic encryption including a random number, so that the security can be enhanced. Further, the data arithmetic device receives the encrypted feature value, the encrypted similarity value, and the key conversion value from the user terminal device, and extracts the encrypted reference data. Since the data calculation device extracts only similar data less than the similarity value D and transmits it to the user terminal device, the calculation amount of the user terminal device and the communication amount between the data calculation device and the user terminal device are reduced. Can do. Moreover, in a user terminal device, a similar value can be set flexibly according to a user's intention.

  In addition, for a probabilistic encryption including a random number, even if the user performs a search based on the same information, the encrypted feature amounts do not have the same value. For this reason, according to this similarity value search method and the like, the confidentiality of the information searched by the user can be further enhanced in transmission from the user terminal device to the data operation device and also in the data operation device. As a result, using probabilistic encryption makes it difficult to analyze the ciphertext frequency and the like, thereby improving safety.

(Other variations)
Although the present invention has been described based on the above-described embodiments, it is needless to say that the present invention is not limited to the above-described embodiments. The following cases are also included in the present invention.

  (1) In the first and second embodiments, the feature amount is described as a vector, but it may be a numerical value. Further, this numerical value may be mapped.

  (2) In Embodiments 1 and 2, the similarity value is a continuous value less than D, but may be a perfect match (that is, the similarity value is only zero) or a discrete value, for example.

  (3) FIG. 13 is a block diagram showing a configuration of a data operation device when statistical reference data is acquired in another modification.

  As shown in FIG. 13, an encrypted reference data statistic unit 209 for obtaining a statistical value is added. In the first and second embodiments, the data arithmetic device encrypts the reference data and transmits the encrypted reference data to the user terminal device. It may be obtained and transmitted to the user terminal device. In this case, it is difficult to specify the user who has the reference data even if the reference data leaks outside by presenting the statistical value that is not the reference data itself to the user terminal device. For this reason, it becomes the structure which considered privacy protection.

  (4) In the first and second embodiments, the reference feature amount storage unit and the reference data storage unit in the data arithmetic apparatus each store data in plain text, but may be encrypted. In this case, data can be extracted from the reference data storage unit and decrypted for use, which improves safety. Further, the data arithmetic device may store data encrypted with the public key of the user terminal device. In this case, encryption distance calculation and reference data to the user terminal device can be sent as they are.

  (5) In the first and second embodiments, the public key and private key of the user terminal device are stored in the key storage unit. For example, when the user uses the user key, it can be attached to the user terminal device. A medium other than the user terminal device may be used.

  (6) In the first and second embodiments, the public key and secret key of the user terminal device are used as the key of the user terminal device. However, a key for each user may be stored in the key storage unit. In this case, authentication is performed between the user and the user terminal device, and when the authentication is successful, the key that matches the specific user can be selected and used from the key storage unit. In the example of the data format shown in FIG. 7, the user identifier ID is used instead of the user terminal device identifier ID.

  (7) In the first and second embodiments, the feature amount calculation unit may have a database, accumulate information sensed for each user, and calculate a feature amount from information sensed in the past. In this case, as a method for identifying the user, for example, the user terminal device may authenticate the user by inputting the identifier ID.

  (8) In the first and second embodiments, in the data arithmetic device, the feature amount calculation unit may calculate the feature amount by acquiring information sensed in the past from a database of another medium. In this case, the user identifier ID may be held in another medium and read by the user terminal device.

  (9) In the first and second embodiments, the data calculation device searches for reference data (in this case, for example, a medical history or a treatment history) of a user who has a similar tendency from the feature amount with respect to vital data such as blood pressure. However, the feature amount and the reference data are not limited to this case. For example, a feature amount may be calculated from data indicating an action range using GPS or the like, and reference data (for example, a purchase history or a history of eating places) of a user having a similar tendency may be searched from the feature amount.

  (10) In Embodiments 1 and 2, the user terminal device encrypts the similar value and transmits it to the data operation device, but this encryption may be performed on the data operation device side. That is, the similar value encryption unit of the user terminal device may be provided in the data arithmetic device. In addition, when it is not necessary to keep the similarity value secret, it is not necessary to encrypt it.

  (11) In the first and second embodiments, the data arithmetic device includes the reference data storage unit, but another device different from the data arithmetic device may include the reference data storage unit. In this case, the identifier ID extracted as the similarity value of the feature amount may be notified to another device different from the data calculation device, and the reference data corresponding to the other device may be calculated.

  (12) In Embodiments 1 and 2, all of the reference data corresponding to the identifier ID extracted as being similar to the feature value is transmitted to the user terminal device, but it is not always necessary to transmit all of the reference data. That is, the data arithmetic device may pick up a part of the reference data and send the picked up part of the reference data to the user terminal device.

  In addition, the data arithmetic device confirms whether or not all identifier IDs in the reference data storage unit are similar by using similarity values 0 to D-1 (as shown in FIGS. 12 and 16). For example, it is possible to repeatedly confirm that all the identifier IDs are first confirmed with a similarity value of 0 and then confirmed with a similarity value of 1, and sequentially check up to the similarity value D-1 (nesting). Good. If any of the confirmations matches, the corresponding identifier ID is extracted.

  Further, for example, the data arithmetic device determines in advance the maximum number of encrypted reference data to be transmitted to the user terminal device, and while the data arithmetic device shown in FIGS. The method may be such that the repetition is interrupted when the predetermined number is reached, the reference data is extracted and encrypted for the extracted identifier ID, and the encrypted reference data is returned to the user terminal device.

  In addition, the technique demonstrated in the said aspect may be implement | achieved in the following cloud service types, for example. However, the types of cloud services in which the technology described in the above aspect is realized are not limited to these.

(Service type 1: In-house data center type cloud service)
FIG. 14 is a block diagram showing an overview of services provided by the information management system in service type 1 (in-house data center type cloud service).

  As shown in FIG. 14, in this type, the service provider 1120 acquires information from the group 1000 and provides a service to the user. In this type, the service provider 1120 has a function of a data center operating company. That is, the service provider 1120 has a cloud server 1111 that manages big data. Therefore, there is no data center operating company.

  In this type, the service provider 1120 operates and manages a data center (cloud server) 1203. The service provider 120 manages an operating system (OS) 1202 and an application 1201. The service provider 1120 provides a service using the OS 1202 and the application 1201 managed by the service provider 1120 (arrow 1204).

(Service type 2: Cloud service using IaaS)
FIG. 15 is a block diagram illustrating an overall image of a service provided by an information management system in service type 2 (IaaS-based cloud service). Here, IaaS (Infrastructure as a Service) is a cloud service provision model that provides a base for constructing and operating a computer system as a service via the Internet.

  As shown in FIG. 15, in this type, the data center operating company 1110 operates and manages a data center (cloud server) 1203. The service provider 1120 manages the OS 1202 and the application 1201. The service provider 1120 provides a service using the OS 1202 and the application 1201 managed by the service provider 1120 (arrow 1204).

(Service type 3: Cloud service using PaaS)
FIG. 16 is a block diagram showing an overall image of a service provided by the information management system in service type 3 (PaaS use type cloud service). Here, PaaS (Platform as a Service) is a cloud service provision model that provides a platform serving as a foundation for constructing and operating software as a service via the Internet.

  As shown in FIG. 16, in this type, the data center operating company 1110 manages the OS 1202 and operates and manages the data center (cloud server) 1203. The service provider 1120 manages the application 1201. The service provider 1120 provides a service using the OS 1202 managed by the data center operating company 1110 and the application 1201 managed by the service provider 1120 (arrow 1204).

(Service type 4: Cloud service using SaaS)
FIG. 17 is a block diagram showing an overall image of a service provided by the information management system in service type 4 (SaaS-based cloud service). Here, the SaaS (Software as a Service) use type cloud service includes, for example, an application 1201 provided by a platform provider who has a data center (cloud server) 1203, and a data center (cloud server) 1203. This is a cloud service provision model that has a function that can be used via a network such as the Internet by users such as companies or individuals who are not.

  As shown in FIG. 17, in this type, the data center operating company 1110 manages the application 1201, manages the OS 1202, and operates and manages the data center (cloud server) 1203. Further, the service provider 1120 provides a service using the OS 1202 and the application 1201 managed by the data center operating company 1110 (arrow 1204).

  As described above, the service provider 1120 provides the service in any of the cloud service types 1 to 4. Further, for example, the service provider or the data center operating company may develop an OS, an application, a big data database, etc., or may be outsourced to a third party.

  In addition, Embodiments 1 and 2, other modifications, and forms obtained by making various modifications conceived by those skilled in the art to the service types 1 to 4, or Embodiment 1 without departing from the spirit of the present invention 2, other modifications and forms realized by arbitrarily combining components and functions in service types 1 to 4 are also included in the present invention.

  The similarity search method according to the present invention can perform a similarity search while concealing the content of the feature amount by encryption, and can be applied to, for example, a computer system that performs a similarity search of cases and the like.

100 User terminal device (terminal device)
200 Data operation device (server device)
202 Encryption distance calculation unit 204 Encryption reference data extraction unit 207 Reference conversion similarity value extraction unit

Claims (9)

Based on information provided from a terminal device, a similar information search method in which a server device searches for similar information and provides the similar information to the terminal device,
A feature amount receiving step in which the server device receives an encrypted feature amount that is an encrypted feature amount from the terminal device;
A similarity value receiving step in which the server device receives an encrypted similarity value, which is information obtained by encrypting a similarity value indicating a degree of similarity, from the terminal device;
A distance calculating step in which the server device calculates an encryption distance indicating a degree of similarity between the reference feature amount of at least one of a plurality of reference feature amounts and the encrypted feature amount received by the server device. When,
A determination step of determining whether or not the calculated encryption distance matches the encrypted similarity value received by the server device;
Encrypted reference data that is information obtained by encrypting reference data that is data corresponding to the reference feature amount used for calculating the encryption distance when it is determined that the server device matches in the determination step. And a reference data transmission step of transmitting the generated encrypted reference data to the terminal device. In the similarity value receiving step, a plurality of encrypted similarity values which are information obtained by encrypting each of a plurality of similar values indicating a plurality of similar degrees are received,
The similar information search method according to claim 1, wherein the server device executes the distance calculating step, the determining step, and the reference data transmitting step for each of the plurality of encrypted similar values received. The similar information search method according to claim 1, wherein the encryption distance is a Euclidean distance between the reference feature quantity and the encryption feature quantity. further,
The server device includes a key receiving step of receiving a key conversion value that is information obtained by converting a secret key held by the terminal device with a predetermined function,
In the similarity value receiving step, as the encrypted similarity value, a conversion similarity value that is information obtained by converting the similarity value with the predetermined function is received;
In the determination step, as the determination, a conversion distance is generated by decrypting the encryption distance using the key conversion value, and it is determined whether or not the generated conversion distance matches the conversion similarity value. The similar information search method according to claim 1. The similar information search method according to claim 4, wherein the predetermined function is a one-way function. further,
The terminal device acquires data, calculates a feature amount indicating the feature of the data from the acquired data, generates the encrypted feature amount by encrypting the calculated feature amount, and generates the encrypted A feature amount transmitting step of transmitting a normalized feature amount to the server device;
The terminal device sets a similarity value indicating a degree of similarity, generates the encrypted similarity value by encrypting the set similarity value, and transmits the generated encrypted similarity value to the server device A value transmission step;
The similar information search method according to claim 1, wherein the terminal device includes a decrypting step of receiving the encrypted reference data from the server device and decrypting the received encrypted reference data. . The similar information search method according to claim 1, wherein the encrypted feature value, the encrypted similarity value, and the reference feature value are encrypted by a homomorphic encryption method. A server device that searches for similar information based on information provided from a terminal device and provides the similar information to the terminal device,
An encrypted feature quantity that is an encrypted feature quantity is received from the terminal device, and the degree of similarity between the received encrypted feature quantity and the reference feature quantity for at least one of a plurality of reference feature quantities An encryption distance calculation unit for calculating an encryption distance indicating
A reference similarity value that receives an encrypted similarity value, which is information obtained by encrypting a similarity value indicating a degree of similarity, and determines whether the received encrypted similarity value matches the calculated encryption distance An extractor;
Generates encrypted reference data, which is information obtained by encrypting reference data, which is data corresponding to the reference feature amount used for calculating the encryption distance, when the reference similarity value extraction unit determines that they match. And an encrypted reference data extraction unit that transmits the generated encrypted reference data to the terminal device. A terminal device;
A similar information search system comprising: the server device according to claim 8, wherein similar information is searched based on information provided from the terminal device and provided to the terminal device.

Images