WO2025063010A1 - Secret search system, data management server, and secret search method - Google Patents

Abstract

According to the present invention, a data provision terminal transmits, to a data management server, an encrypted keyword including a first vector based on a random vector and a public key, and a second vector obtained by rounding components of a vector generated on the basis of the random vector and a hash value of a registered keyword to higher-order bits. A data utilization terminal generates a search query on the basis of a hash value of a search keyword and a secret key, and transmits the search query to the data management server. The data management server determines whether the search keyword matches the registered keyword on the basis of the number of components included in a first range among at least some components of a vector obtained by subtracting the product of the first vector and the search query from the second vector.

Description

Confidential search system, data management server, and confidential search method Incorporation by Reference

This application claims priority to Japanese Patent Application No. 2023-158312, filed on September 22, 2023, the contents of which are incorporated herein by reference.

The present invention relates to a confidential search system, a data management server, and a confidential search method.

In recent years, big data analysis, which extracts previously unknown and useful knowledge from huge amounts of data, has been attracting attention. In addition, various types of information analysis are being widely recognized as an increasingly important activity, with companies collecting data from outside the company as well as their own, and using it for marketing and business efficiency. On the other hand, there have been frequent incidents and accidents in which information, including personal information of customers, has been leaked, which has become a social problem.

Therefore, research is being focused on technologies that use highly secure encryption technology while still allowing some processing to be done while the data remains encrypted. One such technology is searchable encryption, which can determine whether multiple ciphertexts match their corresponding plaintexts without the need to decrypt the ciphertexts.

Searchable encryption is broadly divided into two types: symmetric key and public key. While symmetric key encryption is highly efficient in terms of search speed and ciphertext size, it requires the use of a private key during encryption, which can make key management difficult when there are many data providers. With public key encryption, encryption can be performed using public parameters without using a private key, making it unnecessary to provide a private key to data providers and facilitating key management. The following non-patent document 1 describes public key searchable encryption.

R. Behnia, M. O. Ozmen, and A. A. Yavuz, “Lattice-based public key searchable encryption from experimental perspectives,” IEEE Transactions on Dependable and Secure Computing 17.6, pp. 1269-1282, 2018. [Retrieved July 3, 2023], Internet: https://eprint.iacr.org/2017/1215.pdf

For example, consider a situation where a data provider stores data in the cloud, and data users search the stored data for data linked to specific keywords. To prevent the cloud provider from misusing the information or leaking information from the cloud to third parties, the data must be encrypted before the search process is carried out. Furthermore, when there are multiple data providers, it is desirable to use a public key system, which allows for easy key management.

However, the public key scheme is significantly less efficient than the common key scheme. The public key searchable encryption scheme described in Non-Patent Document 1 uses a lattice structure, resulting in a large ciphertext size. Therefore, one aspect of the present invention is to realize a public key searchable encryption scheme that is fast and has a small ciphertext size.

In order to solve the above problem, one embodiment of the present invention employs the following configuration: A confidential search system includes a data management server, a data utilization terminal, and a data provision terminal, the data provision terminal holds a registered keyword and a public key, randomly extracts a plurality of vectors, calculates a first hash value of the registered keyword based on a predetermined hash function, generates a first vector based on a vector included in the plurality of vectors and the public key, rounds the components of the vector generated based on a vector included in the plurality of vectors and the first hash value to a predetermined number of most significant bits to generate a second vector, and transmits an encrypted keyword including the first vector and the second vector to the data management server, the data utilization terminal receives a search key, and The data utilization terminal holds a word and a private key corresponding to the public key, calculates a second hash value of the search keyword based on the predetermined hash function, generates a third vector based on the second hash value and the private key, and transmits the third vector to the data management server as a search query. The data management server calculates at least some of the components of a vector obtained by subtracting the product of the first vector and the third vector from the second vector, and determines a search result as to whether the search keyword matches the registered keyword based on the number of components included in a first range among the at least some of the calculated components, and transmits data based on the search result to the data utilization terminal.

According to one aspect of the present invention, it is possible to realize a public key searchable encryption method that is fast and has a small ciphertext size.

　Problems, configurations and advantages other than those mentioned above will become clear from the description of the embodiments below.

1 is a block diagram showing a configuration example of a confidential search system according to a first embodiment. 2 is a block diagram showing a configuration example of a data management server according to the first embodiment; FIG. 2 is a block diagram showing a configuration example of a data utilization terminal according to the first embodiment. FIG. 3 is a block diagram showing a configuration example of a data providing terminal according to the first embodiment; FIG. FIG. 11 is a sequence diagram illustrating an example of a process for generating and distributing public parameters and an encryption key according to the first embodiment. 11 is a sequence diagram showing an example of encryption and transmission processing for keywords and data, creation and transmission processing of a search query, and search and data transmission processing in the first embodiment. FIG. 11 is a flowchart illustrating an example of a process for generating public parameters and a private key according to the first embodiment. 11 is a flowchart illustrating an example of an encrypted keyword generation process according to the first embodiment. 11 is a flowchart illustrating an example of a search query generation process according to the first embodiment. 11 is a flowchart illustrating an example of a search process according to the first embodiment. 4A to 4C are diagrams illustrating examples of data configurations of keywords, confidential data, and public data stored in a data providing terminal in the first embodiment. 4A to 4C are diagrams illustrating examples of data configurations of encrypted keywords, public data, and encrypted data stored in the data management server in the first embodiment. 11 is a diagram showing an example of a data configuration of hit data obtained by a search process in the first embodiment. FIG.

In this embodiment, a confidential search system including a data management server, a data usage terminal, and a data provision terminal is described. The data usage terminal determines parameters and keys in advance, and shares at least a portion of the determined parameters and keys with the data management terminal and the data provision terminal.

The data providing terminal encrypts the keyword with a searchable cipher, and encrypts the confidential data linked to the keyword with a public key encryption method or a common key encryption method. The data providing terminal transmits the encrypted keyword, the encrypted confidential data, and the public data linked to the keyword to the data management server 100. As the data providing terminal repeats these processes, the data management server accumulates sets of encrypted keyword, encrypted data, and public data.

The data usage terminal acquires the keywords to be searched, generates a search query from the acquired keywords, and sends it to the data management server. The data management server performs a search corresponding to the received search query without decrypting the encrypted keywords. The data management server transmits encrypted data and public data corresponding to the encrypted keywords found in the search to the data usage terminal. The data usage terminal decrypts the received encrypted data, and uses the decrypted encrypted data and the received public data.

Below, an embodiment of the present invention will be described in detail with reference to the drawings. In this embodiment, the same components are generally given the same reference numerals, and repeated explanations will be omitted. It should be noted that this embodiment is merely one example for realizing the present invention, and does not limit the technical scope of the present invention.

<System Configuration>
1 is a block diagram showing an example of the configuration of a confidential search system. The confidential search system encrypts collected data, executes a search without decrypting the encrypted data, and uses data found in the search.

The confidential search system includes, for example, a data management server 100 installed in a data center or the like, a data usage terminal 200 used by data users, and a data provision terminal 400 used by data providers, all of which are connected via a network 300 such as the Internet and are in a state in which they can communicate with each other.

In the example shown in FIG. 1, the confidential search system includes multiple data providing terminals 400, but there is no limit to the number of data providing terminals 400 included in the confidential search system (it may be one). In other words, there is no limit to the number of data providers.

(Data management server 100)
2 is a block diagram showing an example of the configuration of the data management server 100. The data management server 100 is configured by a computer having a CPU 110, a memory 115, an auxiliary storage device 120, an input device 101, an output device 102, and a communication device 103.

CPU 110 is an example of a processor, and executes programs stored in memory 115. Memory 115 includes ROM (Read Only Memory), which is a non-volatile storage element, and RAM (Random Access Memory), which is a volatile storage element. ROM stores immutable programs (e.g., BIOS (Basic Input/Output System)). RAM is a high-speed, volatile storage element such as DRAM (Dynamic Random Access Memory), and temporarily stores programs executed by CPU 110 and data used when executing the programs.

The auxiliary storage device 120 is a large-capacity, non-volatile storage device such as a magnetic storage device (HDD (Hard Disk Drive)) or a flash memory (SSD (Solid State Drive)), and stores the programs executed by the CPU 110 and data used when the programs are executed. In other words, the programs are read from the auxiliary storage device 120, loaded into the memory 115, and executed by the CPU 110.

The input device 101 is a device, such as a keyboard or mouse, that receives input from an operator. The output device 102 is a device, such as a display device or printer, that outputs the results of program execution in a format that can be viewed by the operator.

The communication device 103 is a network interface device that controls communication with external devices according to a specific protocol. The communication device 103 may also include a serial interface such as a Universal Serial Bus (USB).

A part or all of the programs executed by the CPU 110 may be provided to the data management server 100 via a network from a removable medium (CD-ROM, flash memory, etc.) that is a non-transitory storage medium, or from an external computer equipped with a non-transitory storage device, and stored in a non-volatile auxiliary storage device 120 that is a non-transitory storage medium. For this reason, the data management server 100 should preferably have an interface for reading data from removable media. This also applies to the data utilization terminal 200 and the data provision terminal 400.

The data management server 100 is a computer system that is configured on one physical computer, or on multiple logically or physically configured computers, and may operate in separate threads on the same computer, or may operate on a virtual computer constructed on multiple physical computer resources. The same applies to the data usage terminal 200 and the data provision terminal 400.

The CPU 110 includes, for example, a search processing unit 111 which is a functional unit. The search processing unit 111 performs searches using encrypted keywords. For example, the CPU 110 functions as the search processing unit 111 by operating according to a search processing program loaded into the memory 115. The relationship between the program and the functional unit is also similar for the functional units included in the CPU 210 (described later) of the data utilization terminal 200 and the functional units included in the CPU 410 (described later) of the data provision terminal 400.

Furthermore, some or all of the functions of the functional units included in the CPU 110, the CPU 210 of the data utilization terminal 200, and the CPU 410 of the data provision terminal 400 may be realized by hardware such as an ASIC (Application Specific Integrated Circuit) or an FPGA (Field-Programmable Gate Array).

The auxiliary storage device 120 includes, for example, a ciphertext storage unit 130, a plaintext storage unit 140, and a public parameter storage unit 150, all of which are areas for storing data. The ciphertext storage unit 130 stores encrypted data 132 collected from the data providing terminal 400, and encrypted keywords 131 linked to each piece of encrypted data 132. The plaintext storage unit 140 stores public data 141 linked to each encrypted keyword 131. The public parameter storage unit 150 stores public parameters 151 required for processing by the search processing unit 111.

In addition, some or all of the information stored in the auxiliary storage device 120, the auxiliary storage device 220 of the data utilization terminal 200 (described later), and the auxiliary storage device 420 of the data provision terminal 400 (described later) may be stored in the memory 115, memory 215, and memory 415, respectively, or may be stored in an external database connected to the server or the terminal.

In this embodiment, the information used by the confidential search system may be expressed in any data structure, regardless of the data structure. For example, the information may be stored in a data structure appropriately selected from a table, a list, a database, or a queue.

(Data utilization terminal 200)
3 is a block diagram showing an example of the configuration of the data utilization terminal 200. The data utilization terminal 200 is configured by a computer having a CPU 210, a memory 215, an auxiliary storage device 220, an input device 201, an output device 202, and a communication device 203, for example.

The hardware explanations of the CPU 210, memory 215, auxiliary storage device 220, input device 201, output device 202, and communication device 203 are omitted because they are similar to the hardware explanations of the CPU 110, memory 115, auxiliary storage device 120, input device 101, output device 102, and communication device 103, respectively.

The CPU 210 includes, for example, a search query generation processing unit 211, a data decryption processing unit 212, a parameter generation processing unit 213, and a key generation processing unit 214, all of which are functional units. The search query generation processing unit 211 generates a search query 231 corresponding to a keyword input via the input device 201. The data decryption processing unit 212 performs a decryption process on encrypted data received from the data management server 100. The parameter generation processing unit 213 generates public parameters 241 including a public key, and a private key 242 corresponding to the public key. The key generation processing unit 214 generates a data encryption key, which will be described later, and a data decryption key 243 corresponding to the data encryption key.

The auxiliary storage device 220 includes a search query storage unit 230 and a key storage unit 240, both of which are areas for storing data. The search query storage unit 230 stores a search query 231 generated by the search query generation processing unit 211 (the search query 231 is stored in association with a corresponding keyword). The key storage unit 240 stores public parameters 241, a private key 242 used for processing by the search query generation processing unit 211, and a data decryption key 243 used for processing by the data decryption processing unit 212.

(Data providing terminal 400)
4 is a block diagram showing an example of the configuration of the data providing terminal 400. The data providing terminal 400 is configured by a computer having a CPU 410, a memory 415, an auxiliary storage device 420, an input device 401, an output device 402, and a communication device 403, for example.

The hardware explanations of the CPU 410, memory 415, auxiliary storage device 420, input device 401, output device 402, and communication device 403 are omitted because they are similar to the hardware explanations of the CPU 110, memory 115, auxiliary storage device 120, input device 101, output device 102, and communication device 103, respectively.

The CPU 410 includes, for example, a keyword encryption processing unit 411 and a data encryption processing unit 412, both of which are functional units. The keyword encryption processing unit 411 performs encryption processing on the keyword 441. The data encryption processing unit 412 performs encryption processing on the confidential data 442.

The auxiliary storage device 420 includes a parameter storage unit 430 and a data storage unit 440, both of which are areas for storing data. The parameter storage unit 430 stores public parameters 431 used in processing by the keyword encryption processing unit 411, and a data encryption key 432 used in processing by the data encryption processing unit 412.

Keywords 441, confidential data 442, and public data 443 are stored in the data storage unit 440, linked to one another. The data storage unit 440 also stores encrypted keywords 444 created by the keyword encryption processing unit 411, and encrypted data 445 created by the data encryption processing unit 412.

<Sequence diagram and flow chart>
(Data collection, data encryption, confidential search processing, and decryption of received search results)
FIG. 5 is a sequence diagram showing an example of a process for generating and distributing public parameters and an encryption key by the data utilization terminal 200. As shown in FIG.

The parameter generation processing unit 213 of the data utilization terminal 200 generates public parameters and a private key, stores the generated public parameters as public parameters 241 in the key storage unit 240, and stores the generated private key as private key 242 in the key storage unit 240 (S101). Details of the process of generating the public parameters and private key in step S101 will be described later with reference to FIG. 7.

In the example of FIG. 5, the data utilization terminal 200 generates the public parameters, but the public parameters other than the public key h described below may be generated by the data management server 100 or any of the data providing terminals 400, or may be generated by a device external to the confidential search system.

The parameter generation processing unit 213 transmits the public parameters generated in step S201 to the data management server 100 and each data providing terminal 400 (S102). The search processing unit 111 of the data management server 100 receives the public parameters from the data utilization terminal 200, and stores the received public parameters in the public parameter storage unit 150 as public parameters 151 (S103).

The keyword encryption processing unit 411 of each data providing terminal 400 receives the public parameters from the data using terminal 200, and stores the received public parameters as public parameters 431 in the parameter storage unit 430 of the data providing terminal 400 (S104).

The key generation processing unit 214 of the data utilization terminal 200 generates a data encryption key and a data decryption key, and stores the generated data decryption key in the key storage unit 240 as the data decryption key 243 (S105). The key generation processing unit 214 generates the data encryption key and the data decryption key using a known public key cryptosystem or a known common key cryptosystem. When generating the data encryption key and the data decryption key using a public key cryptosystem, the key generation processing unit 214 generates the data decryption key as a private key and the data encryption key as a public key.

The key generation processing unit 214 transmits the generated data encryption key to each data providing terminal 400 (S106). The keyword encryption processing unit 411 of each data providing terminal 400 receives the data encryption key from the data utilization terminal 200, and stores the received data encryption key in the parameter storage unit 430 of the data providing terminal 400 as the data encryption key 432 (S107).

FIG. 6 is a sequence diagram showing an example of encryption and transmission processing of keywords and data by the data providing terminal 400, creation and transmission processing of a search query by the data using terminal 200, and search and data transmission processing by the data management server 100.

The keyword encryption processing unit 411 of each data providing terminal 400 generates an encrypted keyword 444 by encrypting the keyword 441 stored in the data storage unit 440 of the data providing terminal 400 using the public parameters 431, and the data encryption processing unit 412 of each data providing terminal 400 generates encrypted data 445 by encrypting the confidential data 442 (linked to the keyword 441) stored in the data storage unit 440 of the data providing terminal 400 using the data encryption key 432 (S201). Details of the process of generating the encrypted keyword 444 in step S201 will be described later with reference to FIG. 8.

The data encryption processing unit 412 of each data providing terminal 400 transmits the encryption keyword 444 generated in step S201, the encrypted data 445, and the public data 443 linked to the encryption keyword 444 to the data management server 100 (S202).

The data management server 100 receives the encryption keyword, encrypted data, and public data from each data providing terminal 400, links the received data to the data providing terminal 400 that sent it, and stores the received encryption keyword in the ciphertext memory unit 130 as the encryption keyword 131, stores the received encrypted data in the ciphertext memory unit 130 as the encrypted data 132, and stores the received public data in the plaintext memory unit 140 as the public data 141 (S203).

If the data providing terminal 400 holds multiple keywords 441, the processes of steps S201 to S203 are executed for each keyword 441 (and the confidential data 442 and public data 443 linked to that keyword 441).

The search query generation processing unit 211 of the data utilization terminal 200 acquires the keywords to be searched, for example, via input to the input device 201 (S204). The search query generation processing unit 211 generates a search query 231 corresponding to the keywords acquired in step S204 (S205), and transmits it to the data management server 100 (S206). Details of the search query generation processing in step S205 will be described later with reference to FIG. 9.

The search processing unit 111 of the data management server 100 searches the encrypted keywords 131 stored in the ciphertext storage unit 130 for an encrypted keyword that corresponds to the search query received from the data utilization terminal 200, and extracts the encrypted data and public data linked to the encrypted keyword found in the search from the ciphertext storage unit 130 and the plaintext storage unit 140 (S207). Details of the search process in step S207 will be described later with reference to FIG. 10.

The search processing unit 111 transmits the extracted encrypted data and public data to the data utilization terminal 200 (S208). The data decryption processing unit 212 of the data utilization terminal 200 decrypts the encrypted data received from the data management server 100 using the data decryption key 243, and displays the decrypted encrypted data and the public data received from the data management server 100 on the output device 202, for example, to allow the data user to use them (S209).

Note that each keyword 441 of the data providing terminal 400 may be linked to only one of the confidential data 442 or the public data 443. For example, for a keyword 441 linked only to the confidential data 442, the process of transmitting the public data 443 included in step S202, the process of saving the public data 141 included in step S203, the process of extracting the public data 141 included in step S207, and the process of transmitting the public data 141 included in step S208 are omitted.

Furthermore, for example, for a keyword 441 linked only to public data 443, the process of generating encrypted data 445 included in step S201, the process of transmitting encrypted data 445 included in step S202, the process of saving encrypted data 132 included in step S203, the process of extracting encrypted data 132 included in step S207, the process of transmitting encrypted data 132 included in step S208, and the process of decrypting and using the encrypted data included in step S209 are omitted.

(Generation of public parameters and private keys)
7 is a flowchart showing an example of the process of generating public parameters and a private key in step S101. The parameter generation processing unit 213 of the data utilization terminal 200 sets parameters N, q, N', α, m, and L according to a predetermined required security level (S301).

where N is a natural number of a power of 2, q is a prime number, N' is a natural number of a power of 2 not greater than N, m is a natural number not greater than N', L is a natural number not greater than log ₂ q, 0<α<1/2 is a real number, and the parameter generation processing unit 213 sets these parameters according to these conditions and a predetermined security level. Note that the higher the security level is set, the larger N is, and the smaller q is when N is fixed. For example, N can be 1024 or 2048, and q can be a prime number greater than ²¹⁸ and less than ²³⁰ .

The parameter generation processing unit 213 randomly generates short f, g ∈ Z[X]/(X ^N +1) (S302) and calculates the public key h = f ^-1 g mod q (S303). However, the length of any original Z[X]/(X ^N +1) is defined by (a 0 2 + a ₁ 2 + ... + a _{N-1 2 ) 1/2 by equating a = a 0 + a 1 X} ^{+ ... +} a N- ₁ X N-1 ∈ ^Z [X]/(X ^N ₊₁ ) with the N-dimensional vector ⁽ _{a 0} , a ₁ , ..., a _N-1 ⁾ . It is desirable that the length of each of ^the short f, g ∈ Z[X]/(X ^N +1) is 1.2(q/2) ^1/2 or less. Furthermore, Z[X]/(X ^N +1) is a remainder ring of the integer coefficient polynomial ring, and will hereinafter be denoted as R.

The parameter generation processing unit 213 calculates F, G∈R with short lengths that satisfy f*G-F*g=q (where "*" indicates multiplication on R) (S304). Specifically, for example, the parameter generation processing unit 213 searches for and finds one or more combinations of F and G that satisfy f*G-F*g=q using the method described in Non-Patent Document 1, and identifies, from among the combinations found, F and G with the shortest total length of F and G in step S304.

The parameter generation processing unit 213 outputs public parameters (N, q, h, N', α, m, L) including the parameters set in step S301 and the public key generated in step S303, and a private key (f, g, F, G) including the values generated in step S302 and the values calculated in step S304 (S305).

(Keywords encryption)
8 is a flowchart showing an example of the encrypted keyword generation process included in step S201. The keyword encryption processing unit 411 of the data providing terminal 400 randomly extracts N-dimensional vectors r, e ₁ , e ₂ ∈ R/qR with short length (norm) (S401), where R/qR is a remainder ring of R, and will be denoted as _Rq hereinafter.

In step S401, the keyword encryption processing unit 411 may randomly extract r, e ₁ , and e ₂ , which are short N-dimensional vectors, from N-dimensional vectors (having a length of N ^1/2 or less) whose components are 1, 0, or −1, for example. It is preferable to execute the process of step S401 every time a different keyword 441 is encrypted, that is, it is preferable to extract a different combination of r, e ₁ , and e ₂ for each keyword 441.

The keyword encryption processing unit 411 calculates a hash value t=H(w) _∈Rq of the keyword w to be encrypted (S402). Note that H() is a predetermined hash function, and H() is shared in advance between the data utilization terminal 200 and all the data providing terminals 400.

The keyword encryption processing unit 411 calculates u=r*h+ _e1 and v=r*t+ _e2 (S403). The keyword encryption processing unit 411 rounds each component of v to only the most significant L bits (S404). That is, in step S404, the keyword encryption processing unit 411 replaces v with the value obtained by multiplying the integer closest to 2 ^-L v by 2 ^L. The processing in step S404 makes it possible to reduce the ciphertext size.

The keyword encryption processing unit 411 outputs the combination (u, v) of u calculated in step S403 and v calculated in step S404 as an encrypted keyword (S405). Note that in the method described in Non-Patent Document 1, a hash value for v is further calculated and added to the encrypted keyword, but in this embodiment, since the hash value is not necessary, the amount of calculation required for the calculation process of the hash value is reduced, and the size of the encrypted keyword can be further reduced.

In step S102, the data utilization terminal 200 transmits all of the public parameters to each data providing terminal 400. However, it is also possible to transmit only the parameters (e.g., N, q, h) used in steps S401 to S405 from the public parameters to each data providing terminal 400, and each data providing terminal 400 stores the parameters as public parameters 431.

(Search query generation process)
9 is a flowchart showing an example of the search query generation process in step S205. The search query generation processing unit 211 of the data utilization terminal 200 acquires a keyword W to be searched, for example, via an input to the input device 201 (S501).

The search query generation processing unit 211 determines whether a search query corresponding to the keyword W acquired in step S501 is stored in the search query storage unit 230 (S502). If the search query generation processing unit 211 determines that a search query 231 corresponding to the keyword W is stored in the search query storage unit 230 (S502: YES), it outputs the corresponding search query 231 (S503) and ends the search query generation process.

If the search query generation processing unit 211 determines that the search query 231 corresponding to the keyword W is not stored in the search query storage unit 230 (S502: NO), the search query generation processing unit 211 generates a search query in the following procedure. First, the search query generation processing unit 211 calculates the hash value T=H(W) of the keyword W (S504).

The search query generation processing unit 211 uses a private key (f, g, F, G) to extract vectors s', _s∈Rq with short lengths (norms) that satisfy s'+s*h=T from a predetermined discrete Gaussian distribution (S505). Specifically, for example, in step S505, the search query generation processing unit 211 employs the method described in Non-Patent Document 1 to be able to extract, from the predetermined discrete Gaussian distribution, a combination of s' and s that satisfies s'+s*h=T and in which the lengths of the vectors s' and s are short, each of which is approximately a(Nq) ^1/2 (for example, a is a value that is approximately 1 or more and 4 or less, and is determined by parameters employed in the method described in Non-Patent Document 1), using the private key.

The search query generation processing unit 211 associates the keyword W acquired in step S501 with the search query s extracted in step S505 and stores them in the search query storage unit 230 (S506). The search query generation processing unit 211 outputs the search query s (S507) and ends the search query generation process.

Note that the process of extracting vectors s', s from the discrete Gaussian distribution in step S505 includes a random extraction process. Therefore, if the process of step S505 is executed multiple times for the same keyword W, a different search query s may be obtained each time the process of step S505 is executed. In order to prevent different search queries s from being generated from the same keyword W, the processes of steps S502, S503, and S506 are executed. That is, the search query s generated from the keyword W is linked to the keyword and saved, and when the same keyword W is specified again, the saved search query s is obtained without generating a new search query s.

Furthermore, the randomness of the extraction process in step S505 may be removed by replacing it with a deterministic process such as a process using a pseudo-random function. In this case, the processes in steps S502, S503, and S506 may be omitted, i.e., the same keyword as the keyword that previously generated a search query in step S501 may be reacquired, and a search query may be generated again from the same keyword.

(Search process)
10 is a flowchart showing an example of the search process in step S207. The search processing unit 111 of the data management server 100 executes the processes of steps S602 to S604 for each encrypted keyword 131 stored in the ciphertext storage unit 130 (S601).

The search processing unit 111 calculates N' components out of the N components of the N-dimensional vector v-u*s for the encrypted keyword (u, v), and regards each of the calculated N' components as an integer in the range of -q/2 to q/2 among integers that are congruent modulo q (S602). Note that the search processing unit 111 may calculate, for example, any N' components out of the N components of the N-dimensional vector v-u*s, or may calculate N' components at equal intervals.

The search processing unit 111 determines whether the number of components that fall within the range of -αq and αq (inclusive) is m or more out of the N' components that were deemed to be integers in the range of -q/2 to q/2 in step S602 (S603).

If the search processing unit 111 determines that m or more of the N' components are included in the range (S603: YES), it determines that the keyword corresponding to the search query s matches the keyword corresponding to the encrypted keyword 131, and adds the encrypted data 132 and public data 141 linked to the encrypted keyword 131 to the hit data (S604).

If the search processing unit 111 determines that less than m components out of the N' components are included in the range (S603: NO), it determines that the keyword corresponding to the search query s does not match the keyword corresponding to the encrypted keyword 131, and therefore does not execute the process of step S604.

After performing the processes from step S602 to step S605 for all encrypted keywords 131 (S606), the search processing unit 111 outputs all encrypted data 132 and public data 141 that were added to the hit data in step S604 (S607).

In the search process of FIG. 10, unlike the method described in Non-Patent Document 1, the search processing unit 111 does not calculate a hash value, and therefore the speed of the search process can be improved. In particular, when N' is smaller than N, the search processing unit 111 performs the processes of steps S603 and S604 only for some components of v-u*s, and therefore the search speed can be further improved.

As shown in the search process in FIG. 10, the larger m is and the smaller α is, the lower the hit rate in the search process (the probability that some hit data will be obtained for search query s), but the false hit rate (the probability that incorrect hit data will be obtained for search query s) also decreases. On the other hand, the smaller m is and the larger α is, the higher the hit rate in the search process, but the false hit rate also increases. In this way, m and α should be set taking into account the hit rate in the search, etc.

10, since only N' components out of the N components of v-u*s are calculated in step S602, the keyword encryption processing unit 411 may calculate in advance only N' components out of the N components of v=r*t+ _e2 in step S403, and a vector in which only the calculated N' components are arranged may be used as v in the processing from step S404 onwards. This can speed up the encrypted keyword generation process and further reduce the size of the encrypted keyword.

In this case, the data providing terminal 400 must also receive N' as a public parameter from the data using terminal 200. Furthermore, in step S602, the search processing unit 111 only needs to calculate v-u*s for the N' components of the encrypted keyword 131 calculated in step S403. Note that which components are the N' components to be calculated in steps S403 and S602 may be determined in advance, or information indicating which N' components are the ones calculated in step S403 may be notified to the data management server 100 from the data providing terminal 400.

In step S102, the data utilization terminal 200 transmits all of the public parameters to the data management server 100. However, it is also possible to transmit only the parameters (e.g., N', m, α, q) used in steps S601 to S606 from the public parameters to the data management server 100, and the data management server 100 stores these parameters as public parameters 151.

FIGS. 11A to 11C are diagrams showing examples of the data configuration of data handled in this embodiment. FIG. 11A is a diagram showing examples of the data configuration of keywords 441, confidential data 442, and public data 443 held by the data providing terminal 400. As shown in FIG. 11A, the name of the disease (of the patient), which is an example of keyword 441, the name of the hospital (of the hospital providing the data), which is an example of public data 443, and the age (of the patient), which is an example of confidential data 442, are linked and stored in the auxiliary storage device 420.

In step S201, each disease name is encrypted using public parameters 431 to generate an encryption keyword 444, and each age is encrypted using a data encryption key 432 to generate encrypted data 445. In step S202, the encrypted disease name, encrypted age, and (unencrypted) hospital name are sent to the data management server 100.

FIG. 11B is a diagram showing an example of the data configuration of the encryption keyword 131, public data 141, and encrypted data 132 held by the data management server 100. As shown in FIG. 11B, in step S203, the encrypted disease name received by the data management server 100 from each data providing terminal 400 is linked as the encryption keyword 131, the encrypted age as the encrypted data 132, and the (unencrypted) hospital name as the public data 141, and these are stored in the auxiliary storage device 120. In the example of FIG. 11B, for ease of viewing, the values in the disease name and age fields are shown in plain text, but the values in the disease name and age fields are written as ciphertext.

FIG. 11C is a diagram showing an example of the data structure of hit data obtained by a search process by the data management server 100. In step S205, a search query is generated from the keyword "Disease X" by the data usage terminal 200, and in step S207, a search process is performed on the data in FIG. 11B using the search query, resulting in the hit data in FIG. 11C.

The hit data in FIG. 11C is data extracted from the data in FIG. 11B by linking public data 141 corresponding to the encrypted keyword 131 corresponding to the keyword "X disease" with encrypted data 132 corresponding to the encrypted keyword 131 corresponding to the keyword "X disease". In the example in FIG. 11C, the values in the age field are shown in plain text for ease of viewing, but the values in the age field are written as cipher text. In step S208, the hit data in FIG. 11C is transmitted to the data utilization terminal 200.

Example 2 describes a use case in which the confidential search system in Example 1 is applied to a questionnaire compilation. The data providers who use the data providing terminals 400 are the respondents to the questionnaire, and the data users who use the data using terminals 200 are the implementers of the questionnaire.

The data usage terminal 200 creates questions for a survey and answer options for the questions, for example, in accordance with input to the input device 201, and transmits these to each data providing terminal 400. Each answer option in the survey is an example of a keyword 441.

Each data providing terminal 400 accepts a selection for an option, for example according to input to the input device 401, encrypts the selected option in step S201 to generate an encryption keyword 444, and transmits the encryption keyword 444 to the data management server 100 in step S202. However, if multiple options are selected as answers to a question, each data providing terminal 400 encrypts each of the selected options and transmits them to the data management server 100.

In step S204, the data usage terminal 200 accepts input of a search keyword corresponding to the options to be tabulated via input to the input device 201, and in step S205 generates a search query 231 corresponding to the search keyword and transmits it to the data management server 100. In step S207, the data management server 100 executes a search using the search query 231 on all (encrypted) survey results (a set of encrypted keywords 131) received from each data provision terminal 400, and transmits the number of hits to the data usage terminal 200.

In this way, in this embodiment, neither confidential data 442 nor public data 443 is linked to keyword 441, i.e., encrypted data 445 is not generated, and data management server 100 does not hold encrypted data 132 and public data 141. As in this embodiment, data management server 100 can also transmit information indicating the hit results of a search using a search query (the number of hits in this embodiment) to data utilization terminal 200, rather than transmitting encrypted data 132 and public data 141 corresponding to encrypted keyword 131 that was found by a search using a search query to data utilization terminal 200.

The present invention is not limited to the above-described embodiments, but includes various modified examples. For example, the above-described embodiments have been described in detail to clearly explain the present invention, and are not necessarily limited to those having all of the configurations described. It is also possible to replace part of the configuration of one embodiment with the configuration of another embodiment, and it is also possible to add the configuration of another embodiment to the configuration of one embodiment. It is also possible to add, delete, or replace part of the configuration of each embodiment with other configurations.

Furthermore, the above-mentioned configurations, functions, processing units, processing means, etc. may be realized in hardware, in part or in whole, for example by designing them as integrated circuits. Furthermore, the above-mentioned configurations, functions, etc. may be realized in software, by a processor interpreting and executing a program that realizes each function. Information on the programs, tables, files, etc. that realize each function can be stored in a memory, a recording device such as a hard disk or SSD (Solid State Drive), or a recording medium such as an IC card, SD card, or DVD.

Furthermore, the control lines and information lines shown are those considered necessary for the explanation, and do not necessarily show all control lines and information lines on the product. In reality, it can be assumed that almost all components are interconnected.

Claims (11)

A confidential search system, comprising:
The system includes a data management server, a data utilization terminal, and a data provision terminal,
The data providing terminal includes:
Hold the registered keyword and the public key,
Randomly extract multiple vectors,
Calculating a first hash value of the registered keyword based on a predetermined hash function;
generating a first vector based on a vector included in the plurality of vectors and the public key;
generating a second vector by rounding a component of a vector generated based on a vector included in the plurality of vectors and the first hash value to a predetermined number of most significant bits;
Sending an encryption keyword including the first vector and the second vector to the data management server;
The data utilization terminal includes:
Holding a search keyword and a private key corresponding to the public key;
calculating a second hash value of the search keyword based on the predetermined hash function;
generating a third vector based on the second hash value and the private key;
Transmitting the third vector as a search query to the data management server;
The data management server includes:
Calculating at least some components of a vector obtained by subtracting the product of the first vector and the third vector from the second vector;
determining a search result as to whether the search keyword matches the registered keyword based on the number of components included in a first range among the at least a portion of the calculated components;
The confidential search system transmits data based on the search results to the data utilization terminal. The confidential search system according to claim 1,
N is a natural number of a power of 2, q is a prime number, N' is a natural number of a power of 2 or less than N, m is an integer less than N', L is an integer less than log ₂ q, α is a real number satisfying 0<α<1/2, f and g are elements of Z[X]/(X ^N +1)=R,
The public key is h=f ⁻¹ g mod q,
the private key is (f, g, F, G),
F and G satisfy f*G-F*g=q,
The data providing terminal includes:
Extract r, e ₁ , e ₂ ∈ R/qR as the plurality of vectors;
Calculate the first hash value t=H(w) of the registered keyword w based on the predetermined hash function H();
Generate u=r*h+ _e1 as the first vector;
Calculating some or all of the components of r*t+ _e2 , and generating a vector v as the second vector by rounding each component of the vector composed of the calculated components to L bits;
Transmitting (u, v) as the encrypted keyword to the data management server;
The data utilization terminal includes:
Calculate the second hash value T=H(W) of the search keyword W;
Generate s′, s∈R/qR that satisfies s′+s*h=T based on the private key;
Transmitting the generated s to the data management server as the search query, which is the third vector;
The data management server includes:
Calculate the N' components of v-u*s;
A confidential search system that determines that the search keyword matches the registered keyword when the number of components included in the first range of -αq or more and αq or less is m or more among the N' components of the calculated v-u*s. The confidential search system according to claim 2,
The data providing terminal calculates N' components of r*t+ _e2 , and generates a vector as the second vector v by rounding each component of the vector consisting of the calculated N' components to L bits;
The data management server calculates vu*s only for the same N' components as the N' components that are the subject of calculation of r*t+ _e2 . The confidential search system according to claim 2,
The data utilization terminal includes:
Determine N, q, N′, m, and L;
Randomly generate f and g;
generating said public key h;
Calculate F and G such that f*G-F*g=q;
Generate public parameters (N, q, h, N′, m, L) and the private keys (f, g, F, G);
A confidential search system that transmits at least a portion of the public parameters to the data management server and the data providing terminal. A data management server,
A processor and a memory,
The memory includes:
Holding the encrypted keyword and the search query;
the encrypted keyword includes a first vector and a second vector;
the first vector is a vector generated based on a vector included in a plurality of randomly extracted vectors and a public key;
the second vector is a vector generated by rounding a component of a vector generated based on a vector included in the plurality of vectors and a first hash value to a predetermined number of most significant bits,
the first hash value is a hash value of a registered keyword calculated based on a predetermined hash function,
the search query is a third vector generated based on the second hash value and a private key corresponding to the public key;
the second hash value is a hash value of the search keyword calculated based on the predetermined hash function,
The processor,
Calculating at least some components of a vector obtained by subtracting the product of the first vector and the third vector from the second vector;
determining a search result as to whether the search keyword matches the registered keyword based on the number of components included in a first range among the at least a portion of the calculated components;
A data management server outputs data based on the search results. 6. The data management server according to claim 5,
N is a natural number of a power of 2, q is a prime number, N' is a natural number of a power of 2 or less than N, m is an integer less than N', L is an integer less than log ₂ q, α is a real number satisfying 0<α<1/2, f and g are elements of Z[X]/(X ^N +1)=R,
The public key is h=f ⁻¹ g mod q,
the private key is (f, g, F, G),
F and G satisfy f*G-F*g=q,
The plurality of vectors are r, e ₁ , e ₂ ∈ R/qR;
the first hash value is a hash value t=H(w) of the registered keyword w based on the predetermined hash function H(),
The first vector is u=r*h+ _e1 ,
The second vector is a vector v obtained by rounding each component of a vector consisting of some or all of the components of r*t+ _e2 to L bits,
the encryption keyword is (u, v),
the second hash value is a hash value T=H(W) of the search keyword W,
the third vector is s in s′, s∈R/qR, where s′+s*h=T, generated based on the private key;
The processor,
Calculate the N' components of v-u*s;
A data management server that determines that the search keyword matches the registered keyword if, among the N' components of the calculated v-u*s, there are m or more components that fall within the first range that is greater than or equal to -αq and less than or equal to αq. 7. The data management server according to claim 6,
The second vector v is a vector obtained by rounding each component of a vector consisting of N' components of r*t+ _e2 to L bits,
The processor calculates vu*s only for the same N' components as those used for the calculation of r*t+ _e2 . A data management server. A confidential search method using a confidential search system, comprising:
The confidential search system includes a data management server, a data utilization terminal, and a data provision terminal,
the data providing terminal holds a registered keyword and a public key;
the data utilization terminal holds a search keyword and a private key corresponding to the public key;
The confidential search method includes:
The data providing terminal randomly extracts a plurality of vectors;
the data providing terminal calculates a first hash value of the registered keyword based on a predetermined hash function;
the data providing terminal generates a first vector based on a vector included in the plurality of vectors and the public key;
the data providing terminal generates a second vector by rounding a component of a vector generated based on a vector included in the plurality of vectors and the first hash value to a predetermined number of most significant bits;
the data providing terminal transmits an encrypted keyword including the first vector and the second vector to the data management server;
the data utilization terminal calculates a second hash value of the search keyword based on the predetermined hash function;
the data utilization terminal generates a third vector based on the second hash value and the private key;
the data utilization terminal transmits the third vector as a search query to the data management server;
the data management server calculates at least some components of a vector obtained by subtracting a product of the first vector and the third vector from the second vector;
the data management server determines a search result as to whether the search keyword matches the registered keyword based on a number of components included in a first range among the at least a portion of the calculated components;
The data management server transmits data based on the search results to the data utilization terminal. The confidential search method according to claim 8,
N is a natural number of a power of 2, q is a prime number, N' is a natural number of a power of 2 or less than N, m is an integer less than N', L is an integer less than log ₂ q, α is a real number satisfying 0<α<1/2, f and g are elements of Z[X]/(X ^N +1)=R,
The public key is h=f ⁻¹ g mod q,
the private key is (f, g, F, G),
F and G satisfy f*G-F*g=q,
The confidential search method includes:
The data providing terminal extracts r, e ₁ , e ₂ ∈R/qR as the plurality of vectors;
the data providing terminal calculates the first hash value t=H(w) of the registered keyword w based on the predetermined hash function H();
The data providing terminal generates u=r*h+ _e1 as the first vector,
the data providing terminal calculates some or all of the components of r*t+ _e2 , and generates a vector as the second vector v by rounding each component of a vector consisting of the calculated components to L bits;
the data providing terminal transmits (u, v) as the encrypted keyword to the data management server;
The data utilization terminal calculates the second hash value T=H(W) of the search keyword W,
The data utilization terminal generates s', s∈R/qR that satisfies s'+s*h=T based on the private key,
the data utilization terminal transmits the generated s to the data management server as the search query, which is the third vector;
The data management server calculates N' components of v-u*s;
The confidential search method, in which the data management server determines that the search keyword matches the registered keyword if, among the N' components of the calculated v-u*s, there are m or more components that fall within the first range that is greater than or equal to -αq and less than or equal to αq. The confidential search method according to claim 9,
The data providing terminal calculates N' components of r*t+ _e2 , and generates a vector v as the second vector by rounding each component of the vector consisting of the calculated N' components to L bits;
The data management server calculates v−u*s only for the same N′ components as those used in the calculation of r*t+ _e2 . The confidential search method according to claim 9,
The data utilizing terminal determines N, q, N′, m, and L;
The data utilizing terminal randomly generates f and g;
The data utilization terminal generates the public key h,
The data utilizing terminal calculates F and G that satisfy f*G-F*g=q,
The data utilization terminal generates public parameters (N, q, h, N′, m, L) and the private key (f, g, F, G);
The data utilization terminal transmits at least a portion of the public parameters to the data management server and the data providing terminal.

Images