WO2013072947A1 - Secret character string search system - Google Patents

Abstract

When a user uses a web search engine to execute a search, there is a privacy problem wherein the user's interest, preference or other information becomes known to the search engine from a keyword provided thereto as a search query. In response to such a privacy problem, an approach using encryption technology has been proposed in non-patent document 1, but a user-specifiable keyword is specified as a search string. Moreover, the expansion of a group of said specifiable keywords will be accompanied by the problem of an increase in communication volume between the user and the web search engine. To solve said problems, the present invention uses additively homomorphic encryption and a Burrows-Wheeler transform to secretly calculate whether or not there is a hit for a search. A character string using a Burrows-Wheeler transform enables the use of any character string as a keyword, and when the length of the search character string is fixed, the communication volume is fixed, enabling the problems to be solved.

Description

Secret string search system

The present invention relates to a character string search system in which a user who performs a character string search on a plurality of documents held by a server executes a search process while concealing the character string to be searched from the server.

In recent years, on the Internet, many people use search engines to acquire information that they are interested in.

As a search method, for example, there is a technique as described in Non-Patent Document 1. Specifically, for a document X of length n × n, a function (f, g) having a character string as a range is used, where (f, g) is applied to an arbitrary character string W. , W has the property that g (W) −f (W) ≧ 0 only when W is a partial character string of X. Character string W = w (l) w (l−1)... W (0 ) Exists as a partial character string. As described in Non-Patent Document 1, the function values f (W) and g (W) are calculated from the function values f (W (0)) and w (1) to the function value f (w (1) w (0). )) Is calculated, and the function value f (w (2) w (1) w (0)) is calculated from the function values f (w (1) w (0)) and w (2), and so on. Function value f (W) = f (w (l) w (l−1)... W (0)) is recursively calculated from f (w (l−1)... W (0)) and w (l). Similarly, for g (w) = g ((w (l) w (l-1)... W (0)), the function value of the (i-1) th character and w (i) Can be recursively calculated as function arguments, and the function values f (W) and g (W) can be obtained by l recursive calculations each for the length l of the character string.

However, although the search service is convenient, there is a problem that the search engine knows the user's hobbies, preferences and other information from the keywords provided by the user as a search query. For this reason, a countermeasure plan using cryptographic technology is necessary. For example, Non-Patent Document 2 describes an additive homomorphic encryption method (an encryption method in which an encryption function from a plaintext space to a ciphertext space has additive homomorphism).

P. Ferragina and G. Manzini, Opportunistic Data Structures with Applications. P. Paillier, Public-Key Cryptossystems Based on Composite Degree Residuity Classes.

The technology described in Non-Patent Document 1 cannot be applied to simply encrypted documents. (I-1) This is because the calculation result of the character i is output in an encrypted form, so that the function value cannot be calculated and the i-th character cannot be calculated.

The present invention is for solving the above-mentioned problem, and in a public key cryptosystem having additive homomorphism, a search character string W = w (l) w (l−1). A user terminal that generates an encrypted query of (0) and transmits the encrypted query to the server, and an arithmetic process having homomorphism with respect to the encrypted query received from the user terminal and the document to be searched. A computer system including a server that executes and returns a search processing result, which is a calculation result, to the user terminal. The user terminal searches for a search character string W = w (l) w (l−1)... W (0 ) Using the public key of the public key cryptosystem having the additive homomorphism for the 0th character w (0) of Is sent to the server, and the server receives the 0th character received from the user terminal. The 0th character search process is executed for Eri, the 0th character search process result as a search result is generated, the 0th character search process result is transmitted to the user terminal, and the user terminal receives from the server The 0th character search process result is subjected to the 0th character decryption process using the public key cryptosystem private key having the additive homomorphism, and the search result for the 0th character w (0) is obtained. Obtain the first character search process result and the first character w (1) using the public key of the public key cryptosystem having the additive homomorphism, Generate a query, send the first character query to the server, the server executes the first character search process for the first character query received from the user terminal, the first character search processing result that is the search result The first character search processing result is transmitted to the user terminal, and the server receives from the user terminal. The first character search process is executed for the first character query, the first character search process result as the search result is generated, and the first character search process result is transmitted to the user terminal. The first character decryption process is performed on the first character search processing result received from the public key cryptosystem private key having the additive homomorphism, and the 1st to 0th characters w (1) The search result for w (0) is obtained, and the user terminal recursively with respect to an integer m less than or equal to l in the same procedure below.
Using the public key encryption method public key having the additive homomorphism for the m-1 character search processing result and the m character w (m), the m character query that is an encryption query is The m-th character query is generated and transmitted to the server. The server executes the m-th character search process for the m-th character query received from the user terminal, and the m-th character search process result as a search result is obtained. The m-th character search processing result is generated and transmitted to the user terminal, and the user terminal transmits the private key of the public key cryptosystem having the additive homomorphism to the m-th character search processing result received from the server. Is used to execute the m-th character decoding process to obtain the search result for the 0th character w (m) ... w (1) w (0) from m, and the user terminal performs this procedure from the lth character to the 0th character. Execute until the search result for w (l) ... w (1) w (0) is obtained, and the 0th character w (l) ... w (1 ) A process for determining whether the search result is compatible or non-conforming is executed for the search result for w (0).

In the user / server secret character string search system embodying the present invention, the user can search while keeping the contents of the search query secret from the server, and can solve the privacy problem caused by providing the search keyword.

It is a figure which shows the structural example of the confidential search system in this embodiment. It is a figure which shows the structural example of the client terminal in this embodiment. It is a figure which shows the structural example of the secret calculation server in this embodiment. It is the data transmission / reception at the time of service between a user terminal and a server, and the processing flow of a program. It is a continuation of FIG. It is a processing flow of secret key / public key generation (S100). It is a processing flow of search parameter generation (S200). It is a processing flow of 0th character query generation (S300). It is a processing flow of the 0th character search (S400). It is a processing flow of 0th character decoding (S500). It is a processing flow of m-th character query generation (S600,900,1300). It is a processing flow of m-th character search (S700, 1100, 1400). It is a processing flow of m-th character decoding (S800, 1200, 1500). It is a processing flow of search result judgment (S1600).

Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
In the present embodiment, the user searches for a document including a specific character string W as a partial character string with respect to a plurality of documents X (1), X (2),. Configure the download method. At this time, the user may search for the method of the bellows wheeler described in Non-Patent Document 1 using homomorphic encryption while communicating with the server.
Hereinafter, the system configuration of this embodiment will be described with reference to FIGS. 1 to 3.

FIG. 1 is a schematic diagram of a secret character string search system according to an embodiment of the present invention. As shown in the figure, the secret string search system includes a user terminal 100 and a server 200, and the user terminal 100 and the server 200 are designed to be able to transmit and receive information to and from each other via a network 300. .

FIG. 2 is a functional schematic diagram of the user terminal 100. As shown in the figure, the user terminal 100 includes a CPU 101, an auxiliary storage device 102, a memory 103, a tamper resistant storage device 105, a display device 106, an input / output interface 107, and a communication device 108. Connected and configured at 104. The auxiliary storage device 102 stores program codes. The program code is loaded into the memory 103 and executed by the CPU 101.

FIG. 3 is a functional schematic diagram of the server 200. As shown in the figure, the server 200 includes a CPU 201, an auxiliary storage device 202, a memory 203, a display device 206, an input / output interface 207, and a communication device 208 connected by an internal signal line 204. . The auxiliary storage device 202 stores program codes and documents X (1), X (2),..., X (m) to be searched. The program code is loaded into the memory 203 and executed by the CPU 201.
Hereinafter, for the document X having a length of n × n held by the server 200 using FIGS. 4 to 13, the user 100 sets the character string W = w (l) w (l−1). A procedure for determining whether or not (0) is included or W is concealed will be described. By performing this procedure for all the documents held by the server 200, the user 100 can know which document contains W among the documents held by the server.
Terms used in this embodiment are defined.
(1) Public Key Cryptography The public key cryptosystem used in this embodiment is a scheme having additivity between ciphertexts in addition to asymmetry with respect to normal encryption and decryption as described in Non-Patent Document 2, for example. Have In other words, a ciphertext that is the sum of two ciphertexts can be calculated with public information only. Also, a secret key / public key generation processing program that is predetermined by this encryption method is used.
(2) Security parameter λ
The security parameter is a parameter input when generating a secret key / public key of an encryption method, and an attacker needs to calculate 2 times or more times when the encryption method is broken. For example, if λ = 80, the encryption scheme is secure against an attacker having a computing power of 2 to the 80th power.

(3) Burrow Wheeler (BW) Conversion Function In this embodiment, the Burrow Wheeler (BW) conversion function described in Non-Patent Document 1 is used. The character string after BW conversion of document X [n] is represented by BW (X) [n].
(4) Alphabet In this embodiment, all documents in which the set of all characters is represented by Σ = {a (1), a (2),..., A (s)} and the element a (i) is called an alphabet. X [n], character string W = w (l) w (l-1)... W (1) w (0) is an array having alphabet as elements, and n and l are the lengths of each.
Also, the subscript i of each alphabet a (i) is called a lexicographic order of a (i). For example, a normal alphabet set {a, b, c,..., Z} may be used as Σ.
(5) Function (f (W), g (W))
In the present embodiment, when a partial character string of X is arranged in a lexicographic order with respect to a document X and a character string W as shown in Non-Patent Document 1, the character string starts from W. A pointer to the start point of the line, and g (W)) is a pointer to the end point of the line where the character string starts from W when the substrings of X are arranged in lexicographic order. Non-Patent Document 1 describes f (W) = sp and g (W) = ep. Further, from Non-Patent Document 1, f (aW) and g (aW) are f (aW) = C (a) + O (a, f (W) -1) for alphabet a and character string W, It can be calculated recursively using g (aW) = C (a) + O (a, g (W))-1 and f (W), g (W), which is one character less. At this time, a necessary and sufficient condition for W to be a partial character string of X is g (W) −f (W) ≧ 0.
Where C (a): the number of characters in the string X [n] whose dictionary order is truly smaller than a,
O (a, i): The number of a existing from BW (X) [0] to BW (X) [i].

(6) PIR, PBR protocol In this embodiment, when a user downloads a document that hits a search from a server to a document X (1), X (2),. PIR and PBR protocols as described in the patent literature (C. Gentry and Z. Ramzan, Single-Database Private Information Retrieval with Cosdant Communication Rate.) Are used. At this time, it is possible to keep secret to the server which document has been downloaded by the user.

FIGS. 4 and 5 are data transmission / reception and program processing flows between the user terminal 100 and the server 200 at the time of service.
The user terminal 100 executes private key / public key generation processing (S100),
An encryption public key and a decryption secret key are generated, the generated secret key is stored in the tamper resistant area 105, and the generated public key is transmitted to the server 200 (D100).

The server 200 executes search parameter generation processing (S200) for the document X that is held, and generates parameters to be used during the search.

Next, the user 100 executes the 0th character query generation process (S300) for the character string W = w (l) w (l-1)... W (1) w (0) to obtain the 0th character query. Is transmitted to the server 200 (D200).

Next, the server 200 that has received the 0th character query (D200) executes the 0th character search process (S400), generates the 0th character search result, and transmits the 0th character search result to the user 100 ( D300).

Next, the user 100 that has received the 0th character search result (D300) executes the 0th character decoding process (S500), and obtains the search results up to the 0th character.

Next, the user 100 generates a first character query for the character string W = w (l) w (l-1)... W (1) w (0) and the result of the 0th character decoding process (S500). The process (S600) is executed, and the first character query is transmitted to the server 200 (D400).

Next, the server 200 that has received the first character query (D200) executes the first character search process (S700), generates the first character search result, and transmits the first character search result to the user 100 ( D500).

Next, the user 100 that has received the first character search result (D500) executes the first character decoding process (S800) and obtains the search results up to the first character.

Next, the user 100 generates a second character query for the character string W = w (l) w (l-1)... W (1) w (0) and the result of the first character decoding process (S800). The process (S900) is executed, and the second character query is transmitted to the server 200 (D600).

Next, the server 200 that has received the second character query (D600) executes the second character search process (S1100), generates a second character search result, and transmits the second character search result to the user 100 ( D700).

Next, the user 100 that has received the first character search result (D500) executes the first character decoding process (S800) and obtains the search result up to the second character.

In the same manner, search processing is performed up to the (l-1) th character, and the search results up to the (l-1) th character are obtained.

Next, the user 100 performs the l-th character query on the character string W = w (l) w (l−1)... W (1) w (0) and the result of the (l−1) -th character decoding process. The generation process (S1300) is executed, and the l-th character query is transmitted to the server 200 (D800).

Next, the server 200 that has received the l-th character query (D900) executes an l-th character search process (S1400), generates an l-th character search result, and transmits the l-th character search result to the user 100 ( D1500).

Next, the user 100 that has received the first character search result (D1500) executes the first character decoding process (S800), and obtains the search result up to the first character.

Next, the user 100 performs search result determination processing (S1600) for the first character search result (D1500), and determines whether or not the character string W exists in the document X. Then, the determination result (success or failure) is output to the display device 106.

FIG. 6 is a processing flow of private key / public key generation processing (S100) executed by the user terminal 100 in the data transmission / reception at the service of FIG. 4 and the processing flow of the program.
The user terminal 100 sets the security parameter λ and generates a secret key sk and a public key pk using a key generation algorithm with the security parameter λ as an argument (S201).

FIG. 7 is a processing flow of search parameter generation processing (S200) executed by the server 200 in the data transmission / reception at the service of FIG. 4 and the processing flow of the program.

The server 200 uses the BW conversion function with the document X [n × n] of length n × n as an argument to convert the character array BW (X) [n × n] of X [n × n] into BW. Calculate (S201).
Next, for each alphabet a, the server 200
Value C (a): {number of characters in the character string X [n] whose dictionary order is truly smaller than a} is calculated (S202).
Next, the server 200 converts the (i, j) component B (X) (i, j) of the n-order square matrix B (X) to B (X) (i, j) = BW (X) [n (i -1) + (j-1)], and a search matrix B (X) is calculated (S203).
Next, the server 200 sets the value σ (a, i): from the first row of the n-order square matrix B (X) to (i−1) for each alphabet a and integers i = 1, 2,. ) The number of a existing up to the line is calculated (S204).
Next, the server 200 calculates a search result (f (a), g (a)) when a is searched at the 0th character for each alphabet a (S205).
Next, the server 200 outputs the calculated C (a), B (X), σ (a, i), (f (a), g (a)) and ends the process.

FIG. 8 is a processing flow of the data transmission / reception at the time of the service of FIG. 4 and the 0th character query generation processing (S300) executed by the user terminal 100 in the processing flow of the program.
The user terminal 100 determines that the search character string W = w (l) w (l−1)... W (1) w (0) has the length s and the kth component for the 0th character w (0). 1 and other vectors 0 (w (0)) = (0, 0,... 0, 1, 0,..., 0) are generated. However, the dictionary order of w (0) is k (S301).
Next, each component of the vector τ (w (0)) = (0, 0,..., 0, 1, 0,... 0) is obtained using the public key pk generated in the secret key / public key generation process (S100). Let E (τ (w (0))) be the encrypted encrypted character vector. E (τ (w (0))) = (E (0), E (0), ... E (0), E (1), E (0), ..., E (0)) (S302) The generated encrypted character vector is output with E (τ (w (0))) and the process ends.

FIG. 9 is a processing flow of data transmission / reception at the time of service of FIG. 4 and a 0th character search process (S400) executed by the server 200 in the processing flow of the program.
The server 200 receives E (τ (w (0))) = (E (0), E (0),... E (0), E (1), E (0),. ) For each i component E (τ (w (0))) i is calculated using the additivity of encryption method E, and the additivity of encryption method E is further calculated. Use to add the values calculated for all i. That is, Σf (a) i · E (τ (w (0))) i is calculated, but this ciphertext is E (f (w (0))) due to the configuration (S401).
Next, the server 200 receives the received E (τ (w (0))) = (E (0), E (0),... E (0), E (1), E (0), ..., E (0)), using the additivity of encryption method E, g (a (i)) times each i component E (τ (w (0))) i Calculate and add all the calculated values for i using the additivity of encryption method E. That is, Σg (a) i · E (τ (w (0))) i is calculated. This ciphertext is E (g (w (0))) according to the construction method (S402).
Next, the server 200 outputs the calculated (E (f (w (0))), E (g (w (0)))) and ends the process.

FIG. 10 is a processing flow of data transmission / reception at the time of service in FIG. 4 and a 0th character decoding process (S500) executed by the user terminal 100 in the processing flow of the program.
The user terminal 100 obtains the secret key sk generated in (S100) from the 0th character search processing result (D300) E (f (w (0))), E (g (w (0))) received from the server. To obtain f (w (0)) and g (w (0)).
Next, f (w (0)) and g (w (0)) are output and the process is terminated.

FIG. 11 is executed by the user terminal 100 in the data transmission / reception and program processing flow in FIG.
It is a processing flow of m-th character query generation processing (S600, 900, 1300).

The user terminal 100 sets m ≠ 0 for the m-th character w (m) of the search character string W = w (l) w (l−1)... W (1) w (0). A vector τ (w (m)) = (0, 0,..., 0, 1, 0,. However, the dictionary order of w (m) is k (S601).

Next, the user terminal 100 uses the public key pk generated in the secret key / public key generation process (S100) to generate a vector τ (w (m)) = (0, 0,... 0, 1, 0,... 0). Let E (τ (w (m))) be an encrypted character vector obtained by encrypting each component of. E (τ (w (m))) = (E (0), E (0),... E (0), E (1), E (0),..., E (0)) (S602) .

Next, for the m-1st character decoding processing result f (w (m-1) ... w (0)), f (w (m-1) ... w (0))-1 = n (i- 1) Find i, j to be + (j-1) (S603).

Next, the user terminal 100 sets the encrypted vector pair V (k) = (u (k), v (k)) only when k = ord (w (m)) (u (k), v (k)). ) = (E (Xi), E (Yj)) k ≠ ord (w (m)), (u (k), v (k)) = (E (0), E (0)) .
However, E (Xi) is an encrypted vector obtained by encrypting each component of a vector of length n in which the (i-1) component is 1 and the others are 0, and E (Yj) is the 1st component to the jth component Is an encrypted vector obtained by encrypting each component of a vector of length n with 1 as the other component and 0, and E (0) is an encrypted vector obtained by encrypting each component of the 0 vector of length n. (S604).

Next, as in (S603), the user terminal 100 performs g (w (m-1) ... w on the m-1st character decoding process result g (w (m-1) ... w (0)). (0)) = n (i′−1) + (j′−1) i ′ and j ′ are obtained.

Next, as in (S604), the user terminal 100 uses the encrypted vector pair V ′ (k) = (u ′ (k), v ′ (k)) for i ′, j ′, w (m). Is generated.

Next, the user terminal 100 uses the generated encrypted character vector as E (τ (w (m))) and the encrypted vector pair V (k) = (u (k), v (k)), V ′ (k ) = (U ′ (k), v ′ (k)), (k = 1... S) (i, i ′) is output and the process is terminated.

FIG. 12 is a processing flow of data transmission / reception at the time of service in FIGS. 4 and 5 and m-th character search processing (S700, 1100, 1400) executed by the server 200 in the processing flow of the program.

The server 200 receives E (τ (w (m))) = (E (0), E (0),... E (0), E (1), E (0),. ) For each i component E (τ (w (m))) i is calculated using the additivity of the encryption method E, and further, the additivity of the encryption method E is used. Add all the calculated values for i. That is, Σf (a) i · E (τ (w (m))) i is calculated. This ciphertext is E (f (w (m))) (S701).

Next, the server 200 performs E (σ (a (k)) for each received encrypted vector pair V (k) = (u (k), v (k)), (k = 1... S). , I−1)) = Σσ (a (k), t) · u (k) t (summing at t), i = 1... N is fixed, and Σv (k) j , (B (X) (i, j) = a (k) is summed with j), and the calculated value is summed with k = 1 ... s.
Let E (z (1)) ... E (z (n)). A ciphertext obtained by adding E (f (w (m))) calculated in (S1101) to E (z (i)) and E (σ (a (k), i-1)) is E (Φ (I)) (S702).

Next, the server 200 applies E (σ (a (a)) for each received encrypted vector pair V ′ (k) = (u ′ (k), v ′ (k)), (k = 1... S). (K), i′−1)) = Σσ (a (k), t) · u ′ (k) t, (summing at t), i = 1... N fixed, Σv ′ (k) j, (B (X) (i, j) = a (k) is summed with j) is calculated, and the calculated value is summed with k = 1. Let E (z ′ (1))... E (z ′ (n)). A ciphertext obtained by adding E (f (w (m))) calculated in (S1101) to E (z ′ (i)) and E (σ (a (k), i′−1)) − 1 Is set to E (Φ ′ (i)) (S703).

Next, the server 200 outputs the calculated E (Φ (1))... E (Φ (n)), E (Φ ′ (1))... E (Φ ′ (n)) and ends the processing. .

FIG. 13 is a processing flow of the m-th character decoding process (S800, 1200, 1500) executed by the user terminal 100 in the data transmission / reception and program processing flow of FIGS.

From the received E (Φ (1))... E (Φ (n)), E (Φ ′ (1))... E (Φ ′ (n)), the user terminal 100 receives E (Φ (i)) E (Φ ′ (i ′)) is taken and decrypted using the secret key sk generated in (S100), and Φ (i) = f (w (m)... W (0)), Φ ′ (i ′) = Obtain g (w (m) ... w (0)) (S801).

Next, the user terminal 100 outputs f (w (m) ... w (0)), g (w (m) ... w (0)) and ends the process.

FIG. 14 is a processing flow of the secret calculation argument generation processing (S1600) of FIG.
The user terminal 100 outputs H = g () for f (w (l) ... w (0)), g (w (l) ... w (0)), which is the output of the l-th character decoding process (S1500). w (l) ... w (0))-f (w (l) ... w (0)) + 1 (S1601).
Next, the value H calculated in (S1601) is compared with 0, and if H ≧ 1, it is assumed that the search is hit, and the search result = 1 is output,
If H ≦ 0, it is determined that there is no hit in the search, the search result = 0 is output, and the process ends (S1602).

Thus, the user can determine whether or not the character string W is included in the document X [n × n]. At this time, since the packet length of data (D100, D200, D300, D400, D500, D600, D700, D800, D900) communicated between the user terminal and the server in FIGS. 4 and 5 is a constant multiple of n, Is a constant multiple of n × l. Here, l is the length of the character string W. Therefore, by making the magnitude of l a constant, the total communication amount can be made a constant multiple of n at most. Since the communication amount when downloading all the documents X [n × n] is n × n, when n is sufficiently large, this method becomes a realistic method.

The user performs the same processing for all the documents X (1), X (2),..., X (m) held by the server, so that the user can perform the documents X (1), X (2),. , X (m) can find all documents that contain the character string W as a substring. At this time, the contents of the character string W are concealed from the server.

Next, the user obtains a document including the character string W as a partial character string by a method in a non-patent document (C. Gentry and Z. Ramzan, Single-Database Private Information Retrieval with Costentant Communication Rate.). To do.

As described above, it is possible to acquire all documents including W as a partial character string from the server while keeping the contents of the character string W secret from the server.
In addition, this invention is not limited to the above-mentioned embodiment, A various deformation | transformation is possible within the range of the summary. For example, in this embodiment, as a public key cryptosystem, a non-patent document (C. Gentry and Z. Ramzan, Single-Database Private Information Retrieval with Cost Communication Rate.
), But other public key cryptosystems having additivity to the ciphertext may be used.

In addition, although the PIR method described in Non-Patent Document 3 is used as the PIR and PBR method, other PIR and PBR methods may be used.

10 Secret String Search System 100 User Terminal (User)
101 CPU
102 Auxiliary storage device (storage device)
DESCRIPTION OF SYMBOLS 103 Memory 104 Internal signal line 105 Tamper-resistant memory | storage device 106 Display apparatus 107 I / O interface 108 Communication apparatus 200 Server (server)
201 CPU
202 Auxiliary storage device (storage device)
203 Memory 204 Internal Signal Line 206 Display Device 207 Input / Output Interface 208 Communication Device 300 Network

Claims (5)

In a public key cryptosystem having additive homomorphism, an encrypted query of a search character string W = w (l) w (l-1)... W (0) is generated using a public key, and the encrypted query A user terminal that transmits a search result to the server, and a calculation process having homomorphism is performed on the encrypted query received from the user terminal and the document to be searched, and the search processing result as the calculation result is transmitted to the user terminal. A computer system including a server for replying,
The user terminal is
Using the public key of the public key cryptosystem having the additive homomorphism for the 0th character w (0) of the search character string W = w (l) w (l-1)... W (0) , Generate a zero-character query that is an encrypted query, send the zero-character query to the server,
The server executes a 0th character search process for the 0th character query received from the user terminal, generates a 0th character search process result as a search result, and the 0th character search process result is stored in the user. Send it to your device,
The user terminal performs a 0th character decryption process on the 0th character search processing result received from the server, using a public key cryptosystem private key having the additive homomorphism, The search result for the eye w (0) is acquired, and the 0th character search processing result and the public key cryptosystem public key having the additive homomorphism are used for the first character w (1). , Generating a first character query that is an encrypted query, sending the first character query to the server,
The server executes a first character search process for the first character query received from the user terminal, generates a first character search process result as a search result, and uses the first character search process result as the user Send it to your device,
The server executes a first character search process for the first character query received from the user terminal, generates a first character search process result as a search result, and uses the first character search process result as the user Send it to your device,
The user terminal is
For the first character search processing result received from the server, the first character decryption process is executed using the public key cryptosystem private key having the additive homomorphism, and the first to zeroth characters w ( 1) Get search results for w (0)
Follow the same procedure below.
Inductively for an integer m less than or equal to l
The user terminal is
For the m-1st character search processing result and the mth character w (m), using the public key cryptography public key having the additive homomorphism, the mth character query that is an encryption query is executed. Generating, sending the m-th character query to the server,
The server executes an m-th character search process for the m-th character query received from the user terminal, generates an m-th character search process result as a search result, and the m-th character search process result is the user Send it to your device,
The user terminal is
The m-th character search processing result received from the server is subjected to the m-th character decryption process using the public key cryptography secret key having the additive homomorphism, and the m-th character w ( m) ... Retrieve search results for w (1) w (0)
The user terminal is
This procedure is executed until the search results for the 0th character w (l)... W (1) w (0) are obtained from l, and for the 0th character w (l)... W (1) w (0) from l. A secret character string search system, wherein a search result matching or non-matching determination process is executed for a search result. The secret search system according to claim 1,
The user terminal, as an m-th character search query, adds each component of a vector whose component is 0 or 1 uniquely determined from the m-1 character search processing result and the m-th character w (m). A secret string search system characterized by a plurality of ciphertexts encrypted with an encryption key of public key cryptosystem having homomorphism In the secret search system according to claim 1,
The server executes the m-th character search process, and outputs, as the m-th character search process result, ciphertext E (p) with the integer p as plaintext, and the m-th character search process result is obtained up to the m-th character. Only when the search character string w (m)... W (1) w (0) exists as a partial character string of the search target document, the value of the plaintext p is an integer value of 0 or more. Search system. In the secret search system according to claim 1,
The server executes the m-th character search process, and as a result of the m-th character search process, a pair of ciphertext E (p) having the integer p as plaintext and ciphertext E (p ′) having the integer p ′ as plaintext, (E (p), E (p ′)) is output, and the m-th character search processing result is that the search character string w (m)... W (1) w (0) up to the m-th character is the search target. A secret search system in which the value of plaintext p′-p becomes an integer value of 0 or more only when it exists as a partial character string of a document. The secret search system according to claim 3,
The user terminal decrypts the l-th character search processing result E (p) received from the server with the private key of the public key cryptosystem having the additive homomorphism, and the plaintext p is 0 or more. A secret character string search system characterized by executing a determination process that makes a search result suitable for an integer value and non-conforming for a result less than 0.

Images