Secret character string calculation system, method and apparatus, and non-transitory recording medium

Abstract

A registration apparatus generates shares by secret sharing of a character string with a plurality of modulus and sends the shares to a plurality of server apparatuses to be stored therein. A retrieval apparatus sends shares generated by secret sharing of a retrieval character string with the plurality of modulus to the plurality of server apparatuses. The plurality of server apparatuses execute a subroutine for shares of the each registration character string stored in a storage unit and for each of the plurality of modulus, reconstruct an execution result, and determine whether or not to return the shares of the registration character string stored in the storage unit as a retrieval result. A retrieval apparatus reconstructs shares returned from the plurality of server apparatuses and obtains a retrieval result in which the retrieval character string hits, from the reconstructed result by the Chinese remainder theorem.

Claims

1. A secret character string calculation system comprising: a registration apparatus; a retrieval apparatus; and a plurality of server apparatuses, wherein the registration apparatus comprises: a first processor; and a first memory coupled to the first processor and storing program instructions executable by the first processor, wherein the first processor is configured to generate shares by secret sharing of a registration character string, with a plurality of modulus, and send the shares generated to the plurality of server apparatuses, respectively, wherein the retrieval apparatus comprises: a second processor; and a second memory coupled to the second processor and storing program instructions executable by the second processor, wherein the second processor is configured to generate shares by secret sharing of a retrieval character string with the plurality of modulus, and send the shares generated to the plurality of server apparatuses, respectively, wherein each of the plurality of server apparatuses comprises: a third processor; a third memory coupled to the third processor and storing program instructions executable by the third processor; and a storage unit that stores the shares sent from the registration apparatus, wherein the third processor is configured to execute a predetermined operation processing for the shares of each character string stored in the storage unit and for each of the plurality of modulus, reconstruct an execution result of the operation processing, and determine, based on a reconstruction result of the execution result, whether or not to return the shares of the registration character string stored in the storage unit, as a retrieval result, when the each of the plurality of server apparatuses receives the shares from the retrieval apparatus, and wherein the second processor included in the retrieval apparatus is further configured to reconstruct shares returned from the plurality of server apparatuses, and reconstruct, using the Chinese remainder theorem, a retrieval result from the reconstructed result of the shares.

2. The secret character string calculation system according to claim 1, wherein the registration character string is a=a[1] . . . a[n], and the retrieval character string is b=b[1] . . . b[m] (where is a concatenation operator, m and n are respective number of words of b and a such that m<n), wherein the third processor included in the server apparatus, as the predetermined operation processing, executes a first multiparty computation protocol to calculate shares of a value which is 1 or 0 depending on whether or not the share of the (j+k)th word of the registration character string matches the kth word of the retrieval character string, for each j (j=1, . . . , nm) and for each k (k=1, . . . , m), sums, for k=1 to m, the shares calculated by the first multiparty computation protocol with the modulus, for each j (j=1, . . . , nm), executes a second multiparty computation protocol to calculate shares of a value which is 0 or 1 depending on whether or not the summed share is 0, for each j (j=1, . . . , nm), subtracts the number of words of the retrieval character string and a sum of the shares calculated by the second multiparty computation protocol from the number of words of the registration character string with the modulus, and outputs a result obtained by multiplying the subtracted value by a share obtained by a random number generating multiparty computation protocol with the modulus.

3. The secret character string calculation system according to claim 2, wherein the third processor included in the server apparatus, as the first multiparty computation protocol, executes a multiparty computation protocol that the kth word of the retrieval character string subtracted from the share of the (j+k)th word of the registration character string with the modulus is modular exponentiated by the Carmichael function value of the modulus, and the third processor, as the second multiparty computation protocol, executes a multiparty computation protocol to modular-exponentiate the sum of shares by a Carmichael function value of the modulus.

4. A method for performing a secret character string calculation by a computer system including a plurality of server apparatuses, the method comprising: generating shares by secret sharing of a registration character string with a plurality of modulus and sending the shares to the plurality of server apparatuses, respectively, to have the shares stored in the plurality of server apparatuses; sending shares generated by secret sharing of a retrieval character string with the plurality of modulus to the plurality of server apparatuses; the plurality of server apparatuses each calling a subroutine for the stored shares of each registration character string and for each of the plurality of modulus, to execute an operation processing, reconstruct an execution result of the operation processing, and determine, based on a reconstruction result of the execution result, whether or not to return the stored shares of the registration character string as a retrieval result; and reconstructing the shares returned from the plurality of server apparatuses, and reconstructing, using the Chinese remainder theorem, a retrieval result from the reconstructed result of the shares.

5. The method according to claim 4, wherein the registration character string is a=a[1] . . . a[n], the retrieval character string is b=b[1] . . . b[m] ( is a concatenation operator, m and n are respective number of words of b and a such that m<n), wherein the subroutine called by the server apparatus for each j (j=1, . . . , nm) and for each k (k=1, . . . , m), executes a first multiparty computation protocol to calculate shares of a value which is 1 or 0 depending on whether or not the share of the (j+k)th word of the registration character string matches the kth word of the retrieval character string for each j and each k, sums for k=1 to m, the shares calculated by the first multiparty computation protocol for each j, executes a second multiparty computation protocol to calculate shares of a value to be 0 or 1 depending on whether or not the summed share is 0, for each j (j=1, . . . , nm), subtracts the number of words of the retrieval character string and a sum of the shares calculated by the second multiparty computation protocol from the number of words of the registration character string with the modulus, and outputs a result obtained by multiplying the subtracted value by a share obtained by a random number generating multiparty computation protocol with the modulus.

6. The method according to claim 5, wherein in the subroutine, the first multiparty computation protocol executes a multiparty computation protocol that the kth word of the retrieval character string subtracted from the share of the (j+k)th word of the registration character string with the modulus is modular exponentiated by the Carmichael function value of the modulus, and the second multiparty computation protocol executes a multiparty computation protocol to modular-exponentiate the sum of shares by a Carmichael function value of the modulus.

7. A server apparatus comprising: a processor; a memory coupled to the processor and storing program instructions executable by the processor; a transceiver configured to receive shares sent from a registration apparatus that generates the shares by secret sharing of a registration character string with a plurality of modulus, to a plurality of server apparatuses; and a storage unit configured to store the received shares of the registration character string, wherein the processor is configured to execute a predetermined operation processing for the shares of each character string stored in the storage unit and for each of the plurality of modulus, reconstruct an execution result, and determine, based on a reconstruction result of the execution result, whether or not to return the shares of the registration character string stored in the storage unit as a retrieval result, when the transceiver receives shares from a retrieval apparatus that sends the shares by secret sharing of a retrieval character string with the plurality of modulus to the plurality of server apparatuses, and wherein the transceiver sends the shares of the retrieval result to the retrieval apparatus that is operable to reconstruct, using the Chinese remainder theorem, a retrieval result from a reconstructed result of the shares returned from each of the server apparatuses.

8. The server apparatus according to claim 7, wherein the registration character string is a=a[1] . . . a[n], the retrieval character string is b=b[1] . . . b[m] (where is a concatenation operator, m and n are respective number of words of b and a such that m<n), wherein the processor, as the predetermined operation processing, executes a first multiparty computation protocol to calculate shares of a value which is 1 or 0 depending on whether or not the share of the (j+k)th word of the registration character string matches the kth word of the retrieval character string, for each j (j=1, . . . , nm) and for each k (k=1, . . . , m), sums for k=1 to m, the shares calculated by the first multiparty computation protocol with the modulus, for each the j, executes a second multiparty computation protocol to calculate shares of a value which is 0 or 1 depending on whether or not the summed share is 0, subtracts the number of words of the retrieval character string and a sum of the shares calculated by the second multiparty computation protocol from the number of words of the registration character string with the modulus, and outputs a result obtained by multiplying the subtracted value by a share obtained by a random number generating multiparty computation protocol with the modulus.

9. The server apparatus according to claim 8, wherein the processor, as the first multiparty computation protocol, executes a multiparty computation protocol that the kth word of the retrieval character string subtracted from the share of the (j+k)th word of the registration character string with the modulus is modular exponentiated by the Carmichael function value of the modulus, and the processor, as the second multiparty computation protocol, executes a multiparty computation protocol to modular-exponentiate the sum of shares by a Carmichael function value of the modulus.

10. A non-transitory computer-readable recording medium having stored thereon a program that, upon execution by a computer constituting a server apparatus, causes the server apparatus to execute processing comprising: receiving shares, and storing the shares in a storage unit, the shares being sent from a registration apparatus that generates the shares by secret sharing of a registration character string with a plurality of modulus and sends the shares to a plurality of server apparatuses; and performing a retrieval response calculation including executing a predetermined operation processing for the shares of the registration character string stored in the storage unit and for each of the plurality of modulus, reconstructing an execution result of the operation processing, and determining, based on a reconstruction result of the execution result, whether or not to return the shares of the registration character string stored in the storage unit as a retrieval result, wherein the shares of the retrieval result, determined by said determining to be returned, are sent to a retrieval apparatus that is operable to reconstruct, using the Chinese remainder theorem, a retrieval result from a reconstructed result of the shares returned from each of the server apparatuses.

11. A retrieval apparatus comprising: a processor; a memory coupled to the processor and storing program instructions executable by the processor; and a transceiver configured to communicatively connect to a plurality of server apparatuses that receive from a registration apparatus that generates shares by secret sharing of a registration character string with a plurality of modulus, wherein the processor is configured to generate shares by secret sharing of a retrieval character string with the plurality of modulus, and the transceiver sends the shares generated to the plurality of server apparatuses, respectively, wherein the plurality of server apparatuses each executes a predetermined operation processing for the shares of each character string stored in the each storage unit and for each of the plurality of modulus, reconstructs an execution result of the operation processing, and determines, based on a reconstruction result of the execution result, whether or not to return the shares of the registration character string stored in the storage unit, as a retrieval result, wherein the processor is further configured to reconstruct shares returned from the plurality of server apparatuses, and reconstruct, using the Chinese remainder theorem, a retrieval result from the reconstructed result of the shares.

12. The non-transitory computer-readable recording medium according to claim 10, wherein the registration character string is a=a[1] . . . a[n], the retrieval character string is b=b[1] . . . b[m] (where is a concatenation operator, m and n are respective number of words of b and a such that m<n), wherein the retrieval response calculation processing, as the predetermined operation processing, executes a first multiparty computation protocol to calculate shares of a value which is 1 or 0 depending on whether or not the share of the (j+k)th word of the registration character string matches the kth word of the retrieval character string, for each j (j=1, . . . , nm) and for each k (k=1, . . . , m), sums for k=1 to m, the shares calculated by the first multiparty computation protocol with the modulus, for each the j, executes a second multiparty computation protocol to calculate shares of a value which is 0 or 1 depending on whether or not the summed share is 0, subtracts the number of words of the retrieval character string and a sum of the shares calculated by the second multiparty computation protocol from the number of words of the registration character string with the modulus, and outputs a result obtained by multiplying the subtracted value by a share obtained by a random number generating multiparty computation protocol with the modulus.

13. The non-transitory computer-readable recording medium according to claim 12, wherein in the retrieval response calculation processing, the first multiparty computation protocol executes a multiparty computation protocol that the kth word of the retrieval character string subtracted from the share of the (j+k)th word of the registration character string with the modulus is modular exponentiated by the Carmichael function value of the modulus, and the second multiparty computation protocol executes a multiparty computation protocol to modular-exponentiate the sum of shares by a Carmichael function value of the modulus.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a diagram illustrating a configuration example of an example embodiment of the present invention.

(2) FIG. 2 is a diagram illustrating an operation procedure of an example embodiment of the present invention.

(3) FIG. 3 is a diagram illustrating an operation procedure of an example embodiment of the present invention.

DETAILED DESCRIPTION

(4) Example embodiments of the present invention will be described. As described above, the MPC protocol for general algorithms is very inefficient. The present embodiment can realize efficient retrieval by efficiently designing a retrieval algorithm F.

(5) It is known that a cause of deterioration in efficiency of the MPC protocol lies in multiplication. That is, the more the retrieval algorithm F contains multiplication, the less efficient the MPC protocol for calculating the necessary value F(x[1], . . . , X[n]) becomes.

(6) Therefore, in the present example embodiment, in order to improve the efficiency of the MPC protocol, such an algorithm is realized that executes retrieval with multiplication reduced as much as possible.

(7) Although not particularly limited thereto, a character string handled in the embodiment is such a string obtained by arranging a plurality of units, each of which is called word. It is assumed that word is a bit string of W bits (where W is a predetermined positive integer, for example, 8, 16, 32, etc.).

(8) A case where a character string a=a[1] . . . a[n] stored in a database contains a retrieval character string b=b[1] . . . b[m] as a substring, is regarded as a hits retrieval condition b, where represents a concatenation of character strings. a[1] to a[n], b[1] to b[m] are words.

(9) A necessary and sufficient condition that a hits the retrieval condition b is given below.

(10) There is some j{1, . . . nm} such that:
a[j+1]=b[1], and . . . , and a[j+m]=b[m] (6)

(11) In order to present a method for performing retrieval, the condition that a hits retrieval condition b is rewritten to another condition.

(12) A function G is defined below.
G(x)=0 if x=0
G(x)=1 if x0 (7)
(That is, if x=0 then G(x)=0, if not x=0 then G(x)=1.)

(13) Then, the above condition (formula (6)) is equivalent to the following:

(14) Assuming
c[j,k]=G(a[j+k]b[k]), and
u[j]=c[j,1]+ . . . +c[j,m],
there is some j{1, . . . nm} such that
u[j]=0 mod X (8)
where X is an integer (a concrete value will be described later).

(15) In the MPC protocol, the computation of mod X is used. The above (8) is denoted as
u[j]=0 mod X(where mod X is added).

(16) If X takes a value larger than 2{circumflex over ()}W ({circumflex over ()} is an exponentiation operator: equivalent to 2.sup.W) and log.sub.2 n, logarithm with 2 as a base, it is easy to ascertain that a necessary and sufficient condition that u[j]=0 is
u[j]=0 mod X (9)

(17) Using the above function G, a condition that there exists some j{1, . . . , nm} such that u[j]=0 is equivalent to the following.

(18) Assuming d[j]=G(u[j]),
(nmd[1]d[2] . . . d[nm])0 mod X (10)

(19) The reason for using mod X is the same as above.

(20) When it is assumed that the following algorithm is denoted as F.sub.X(a, b), it can seen that whether a hits retrieval condition b is determined by whether F.sub.X(a, b)=hit or not (a subscript of F.sub.X specifies that mod X is used in the algorithm).

(21) Step 1:

(22) Compute the following:

(23) For j=1, . . . , nm, and k=1, . . . , m,
c[j,k]=G(a[j+k]b[k])mod X (11)
Step 2:

(24) Compute the following:

(25) For j=1, . . . , nm,
u[j]=c[j,1]+ . . . +c[j,m] mod X (12)
Step 3:

(26) Compute the following:

(27) For j=1, . . . , nm,
d[j]=G(u[j]) (13)
Step 4:

(28) Compute the following:
e=(nmd[1] . . . d[nm])(random number)mod X (14)
Step 5:

(29) Output:
If e=0 mod X then no hit,
If e0 mod X then hit (15)

(30) In Step 4, a random number is multiplied in order to prevent information leakage to an attacker, from the value of e, when creating a MPC protocol which computes F.sub.X later.

(31) As described earlier, the more the function F.sub.X uses multiplication, the slower the speed of the MPC protocol to compute F.sub.X becomes.

(32) In the above algorithm F.sub.X(a, b), multiplication is not used. Therefore, it is efficient. The function G of the subroutine may be realized by multiplying as less as possible.

(33) Let (x) be the Carmichael function and H(x, X) be defined as below.
H(x,X)=x{circumflex over ()}(X)mod X (16)

(34) From the definition of the Carmichael function (x), H (x, X) takes the following values.
If x=0, then H(x,X)=0 mod X,
If x0, then H(x,X)=1 mod X (17)

(35) Therefore, H(x, X) can be used as the subroutine G(x) of F.sub.X(a, b).

(36) As described above, X must be larger than the bit length W of the word. Therefore, when H(x, X) is used as G(x), the efficiency decreases when W is a large value. For example, if int type 32 bits of the C language is 1 word (W=32), 2{circumflex over ()}W=2{circumflex over ()}32=4,294,967,296, which is a large value and inefficient.

(37) Therefore, by further improving F.sub.X(a, b), this problem is avoided.

(38) For improvement, X is chosen to satisfy
X=.sub.pSp (18).

(39) Here, the set S is a set of integers satisfying mutually prime p and q for arbitrary p, qS. Therefore, X is a product of mutually prime integers p, q, . . . contained in the set S.

(40) Then, let's consider the following algorithm I.sub.X (a, b).

(41) <Algorithm I.sub.X (a, b)>

(42) For each pS, F.sub.p (a, b) is executed (H(x, p) is used as the subroutine G(x)).

(43) Let e[p] be an output of F.sub.p(a, b).

(44) Output:

(45) for all pS,
if e[p]=0 mod p, then no hit,
if e[p]0 mod p, then hit

(46) Since X=.sub.pS p, for any pS, the Carmichael function (p) is a submultiple of (X). That is, X contains p as a divisor, and from the definition of the Carmichael function (equation (2)), it can be seen that (p) is a divisor of (X).

(47) Since x{circumflex over ()}(p) is 1 or 0, the following holds.
H(x,X)=x{circumflex over ()}(X)=x{circumflex over ()}(p)=H(x,p)mod p (19)

(48) Therefore, from the Chinese Remainder Theorem, the output of I.sub.X(a, b) is equal to the output of F.sub.X(a, b). Moreover, in the algorithm I.sub.X(a, b) of the embodiment,
H(x,p)=x{circumflex over ()}(p)mod p (20)
is computed instead of H(x, X) of F.sub.X(a, b).

(49) Since the (p) is smaller than (X), the computation of
H(x,p)=x{circumflex over ()}(p)mod p
is more efficient than the computation of
H(x,X)=x(X)mod X.

(50) Therefore, the above algorithm I.sub.X(a, b) solves the above-described problem (the efficiency of F.sub.X(a, b) is poor).

(51) Therefore, in the present embodiment, an MPC protocol for executing the algorithm I.sub.X(a, b) is created. The following describes an embodiment.

(52) <Apparatus Configuration>

(53) FIG. 1 is a diagram for explaining a configuration example of a system according to an embodiment of the present invention. Referring to FIG. 1, the system of the embodiment includes a registration apparatus 1, a retrieval apparatus 2, N server apparatuses 3-1, . . . , 3-N. The registration apparatus 1 may be a separate apparatus from the retrieval apparatus 2 or may be the same apparatus. Further, the registration apparatus 1 and the retrieval apparatus 2 may coincide with any one of the server apparatuses 3-1, . . . , 3-N.

(54) The registration apparatus 1 includes a registration character string share generation unit 11 and a communication unit 12. The registration apparatus 1 registers character strings a[1], a[2], . . . in the server apparatuses 3-1, . . . , 3-N.

(55) The registration apparatus 1 that registers the character string a[1], a[2], . . . may be different for each character string or may be the same. In FIG. 1, it is assumed that all a[1], a[2], . . . are registered by the same registration apparatus 1 and the t-th character string is registered. It is a matter of course that processing and control of part or all of the parts of the registration apparatus 1 may be implemented by program control.

(56) The retrieval apparatus 2 includes a retrieval character string share generation unit 21, a communication unit 22, and a reconstruction unit 23. The retrieval apparatus 2 retrieves character strings stored in the server apparatuses 3-1, . . . , 3-N. In FIG. 1, one retrieval apparatus 2 performs all retrieval. However, the retrieval apparatus 2 may be different for each retrieval character string b. It is a matter of course that processing and control of part or all of the parts of the retrieval apparatus 2 may be implemented by program control.

(57) The server apparatus 3- (=1, . . . , N) includes a communication unit 31-, a data storage unit 32-, and a retrieval response calculation unit 33-. Processing and control of part or all of the parts of the server 3- may, as a matter of course, be implemented by program control.

(58) The following describes an outline of operations of the registration apparatus 1, the retrieval apparatus 2, and the server apparatuses 3-1, . . . , 3-N in the present embodiment.

(59) The registration apparatus 1 computes shares of a[t] using the registration character string share generation unit 11 and sends the shares to the server apparatuses 3-1, . . . , 3-N by using the communication unit 12.

(60) The server apparatuses 3-1, . . . , 3-N receive the shares using the communication units 31-1, . . . , 31-N of the server apparatuses and store the received shares in the data storage units 32-1, . . . , 32-N, respectively.

(61) The details of the above procedure will be described in <Registration method> which will be described later.

(62) When retrieving data registered in the server apparatuses 3-1, . . . , 3-N, the retrieval apparatus 2 computes shares of a retrieval character string using the retrieval character string share generation unit 21 and sends the shares of the retrieval character string to the server apparatuses 3-1, . . . , 3-N respectively by using the communication unit 22.

(63) The server apparatuses 3-1, . . . , 3-N respectively determine data to be returned, while communicating with each other by using the retrieval response calculation units 33-1, . . . , 33-N. The server apparatuses 3-1, . . . , 3-N respectively send the shares of the retrieval response to the retrieval apparatus 2 by using the communication units 33-1, . . . , 33-N.

(64) The retrieval apparatus 2 receives the shares using the communication unit 22, and reconstructs a retrieval result from the shares by using the reconstruction unit 23.

(65) Details of the above procedure will be described in <Retrieval method> later described.

(66) This embodiment relates to the retrieval of character strings, and it is assumed that character strings registered by the registration apparatus in the server apparatus are all composed of n words. It is assumed that each word is a bit string of W bits.

(67) Let be a security parameter. The larger is, the more secure it becomes, but the less efficient it is. Therefore, it is necessary to select an appropriate . Although not particularly limited, it is recommended that be set to 160, for example.

(68) Let S be a set of integers satisfying the following two properties:
For arbitrary p,qS, p and q are mutually prime. (21)
.Math.2{circumflex over ()}W, log.sub.2 n.sub.pSp (22)

(69) If the above conditions (21) and (22) are satisfied, S may be any set. For example, as a set S, small prime numbers such as 2, 3, 5, . . . may be collected until the above condition (inequality (22)) is satisfied.

(70) Let Access be an access structure on the set {1, . . . N} and let (Share, Reconst) be an Access-secure secret sharing scheme.

(71) <Registration Method>

(72) Let a[t] be a character string and let the ith word of a[t] be denoted as a[t, i]. The symbol represents concatenation of character strings. From the definition, it can be defined as
a[t]=a[t,1] . . . a[t,n] (23).

(73) A method in which the registration apparatus 1 registers the character string a[t] in the server apparatuses 3-1, . . . , 3-N will be described.

(74) Step 1:

(75) For each i=1, . . . , n, each pS, the registration character string share generation unit 11 of the registration apparatus 1 executes
Share(a[t,i],N,p) (24)
and obtains its output (shares)
x[t,i,1,p], . . . ,x[t,i,N,p] (25).
Step 2:
For each i=1, . . . , n, each =1, . . . , N, each pS, the registration apparatus 1 sends the share x[t, i, , p] to the server apparatus 3-j via the communication unit 12.
Step 3:
For each =1, . . . , N, each pS, the server apparatus 3- stores
x[t,1,,p] . . . x[t,n,a,p] (26).
( is a concatenation operator).
<Retrieval Method>
When
a=a[1] . . . a[n],b=b[1] . . . b[m] (27)
is a character string, a includes b as a partial character string means that, as described above, some i{0, . . . , nm} exists and
all of a[i+1]=b[1], . . . ,a[i+m]=b[m] (28)
hold true.

(76) FIG. 2 is a diagram for explaining the procedure of the embodiment. With reference to FIG. 2, the procedure that the retrieval apparatus 2 retrieves for b=b[1] . . . b[m]

(77) as a partial character string from a character string group registered in the server apparatuses 3-1, . . . , 3-N will be described.

(78) Step 1:

(79) The retrieval character string share generation unit 11 of the retrieval apparatus 2 generates shares of the retrieval character string b and sends the shares to the server apparatuses 3-1, . . . , 3-N (201 in FIG. 2). Step 1 consists of the following steps.
Step 1.1:
For each pS, each k=1, . . . , m, the retrieval character string share generation unit 21 of the retrieval apparatus 2 executes
Share(b[k],N,p) (29)
and obtains the output (share of retrieval character string):
y[k,1], . . . ,y[k,N] (30).
Step 1.2:
For each =1, . . . , N, each k=1, . . . , m, the retrieval apparatus 2 sends the share y[k, ] of the retrieval character string to the server apparatus 3-.
Step 2:
The server apparatuses 3-1, . . . , 3-N each determine a response by execution of a subroutine (202 in FIG. 2). Step 2 consists of the following four steps 2.1 to 2.4 (omitted in FIG. 2).
Step 2.1:
For each t=1, 2, . . . , each pS, the following is executed:
Step 2.1.1:
For each =1, . . . , N, the server apparatus 3- reads the share of the registration character string x[t, j, , p].
Step 2.1.2:
The server apparatus 3-1 obtains x[t,1,1,p] . . . x[t,n,1,p] as an input, the server apparatus 3-2 obtains x[t,1,2,p] . . . x[t,n,2,p] as an input, . . . , and the server apparatus 3-N obtains x[t,1,N,p] . . . x[t,n,N,p] as an input, and each calls a subroutine which is described later, using the share of the retrieval character string y[k, ](k=1, . . . , m, =1, . . . , N).

(80) Each of the server apparatuses 3-1, . . . , 3-N obtains
e[t,1,p], . . . ,e[t,N,p] (31)
as an output of the subroutine.
Step 2.2:
For each t=1, 2, . . . , each pS, the server apparatuses 3-1, . . . , 3-N disclose e[t, 1, p], . . . , e[t, N, p], respectively.

(81) However, for example, when the server apparatus 3- is an unauthorized server apparatus, the server apparatus 3- may not necessarily disclose e[t, , p]. Therefore, there may be a case wherein the number of items of the disclosed data is less than the number N of the server apparatuses.

(82) Step 2.3:

(83) For each t=1, 2, . . . , for each pS, let
E[t]={|the server apparatus 3- disclosed e[t,,p]} (32),
and
in the case of
E[t]Access (33)
(when E [t] is included in a set Access),
the server apparatuses 3-1, . . . , 3-N each execute
Reconst(e[t,1,p], . . . ,e[t,N,p]) (34),
and obtain f[t, p] as its output.

(84) On the other hand, if it is not the case of E[t]Access, the retrieval procedure fails, and the retrieval procedure ends here.

(85) Step 2.4:

(86) For each t=1, 2, . . . , for each =1, . . . , N, the following step 2.4.1 is executed.

(87) Step 2.4.1:

(88) If there is pS such that
f[t,p]0 mod p (35)
the server apparatus 3- sends
x[t,1,,p] . . . x[t,n,,p] (36)
to the retrieval apparatus 2.

(89) However, since an unauthorized server apparatus does not always send x[t,1, ,p] . . . x[t,n, ,p] to the retrieval apparatus 2, the number of items of data that the retrieval apparatus 2 receives may be less than the number N of the server apparatuses.

(90) Step 3:

(91) The retrieval apparatus 2 reconstructs the retrieval result by the Chinese remainder theorem as follows (203 in FIG. 2).

(92) Step 3.1:

(93) For each t=1, 2, . . . , each pS, let
X[t]={|the server apparatus 3- has sent x[t,1,,p] . . . x[t,n,,p] to the retrieval apparatus 2} (37).
Step 3.2:
In the case of
X[t]Access (38)
the following steps are performed.
Step 3.2.1:
For each pS, the retrieval apparatus 2 executes for each j=1, . . . n:
Reconst((x[t,j,,p]).sub.aX[t]) (39)
and obtains g[t,j,p] as an output
Step 3.2.2:
ChineseRemainder((g[t,j,p]).sub.pS) (40)
is executed and a[t, j] is obtained as its output.
Step 3.2.3:
Let
a[t]=a[t,1] . . . a[t,n] (41),
and the t-th data a[t] is outputted regarded as retrieved.

(94) In Step 3, a subroutine is executed for each t=1, 2, . . . , for each pS, so that the subroutine is executed for (number of t)(number of p) times. These subroutines may be done in parallel or concurrently, or may be performed sequentially one by one.

(95) <Subroutine>

(96) FIG. 3 is a diagram explaining procedures of the subroutine. With reference to FIG. 3, processing (operation processing) of a subroutine will be described.

(97) In the server apparatus 3-1, the subroutine inputs x[t,1,1,p] . . . x[t,n,1,p], y[k,1,p](k=1, . . . , m) . . . , and in the server apparatus 3-N, the subroutine inputs x[t,1,N,p] . . . x[t,n,N,p], y[k,N,p](k=1, . . . , m) and performs the following steps 1 to 3. Note that y[k, , p] is the share in the retrieval character string generated for each pS, each k=1, . . . , m.

(98) Step 1:

(99) Compute the share c[t,j,k,1,p], . . . , c[t,j,k,N,p] on whether or not the share of a[t, j+k] matches the retrieval character string b[k] (301 in FIG. 3).

(100) Step 1 (301 in FIG. 3) of the subroutine consists of steps 1.1 and 1.2 (not shown in FIG. 3).

(101) Step 1.1:

(102) For each =1, . . . , N, each j=1, . . . , nm, each k=1, . . . , m, the server apparatus 3- computes
z[t,j,k,,p]=x[t,j+k,,p]y[j,,p] mod p (42)
Step 1.2:
For each j=1, . . . , nm, each k=1, . . . , m, the server apparatuses 3-1, . . . , 3-N respectively receive
(z[t,j,k,1,p],(p)), . . . ,(z[t,j,k,N,p],(p)) (43)
as an input and execute the modular exponentiation MPC protocol. Note that (p) is a Carmichael function (a{circumflex over ()}(p)=1 mod p for a disjoint a with p).

(103) The server apparatuses 3-1, . . . , 3-N respectively obtain
c[t,j,k,1,p], . . . ,c[t,j,k,N,p] (44)
as the execution result of the modular exponentiation MPC protocol.
Step 2:
The server apparatuses 3-1, . . . , 3-N compute shares d[t,j,1,p], . . . , d[t,j,N,p] as to whether or not the sum of k=1 to m of c[t,j,k,1,p], . . . c[t,j,k,N,p] is 0. Step 2 includes steps 2.1 and 2.2 (not shown in FIG. 3).
Step 2.1:
For each =1, . . . , N, each j=1, . . . , nm,
the server apparatus 3- computes
u[t,j,,p]=.sub.k=1.sup.mc[t,i,k,,p] (45)
Step 2.2:
For each j=1, . . . , nm,
the server apparatuses 3-1, . . . , 3-N respectively obtain
(u[t,j,1,p],(p),p), . . . ,(u[t,j,N,p],(p),p) (46)
as an input and execute the modular exponentiation MPC protocol.
The server apparatuses 3-1, . . . , 3-N respectively obtain
d[t,j,1,p], . . . ,d[t,j,N,p] (47)
as the execution result of the modular exponentiation MPC protocol.
Step 3:
Generate shares of the randomized difference from nm (303 in FIG. 3).
Step 3 consists of the following steps 3.1, 3.2, 3.3.
Step 3.1:
For each =1, . . . , N,
the server apparatus 3- computes
v[t,,p]=nm.sub.j=1.sup.nmd[t,j,,p] (48)
Step 3.2:
The server apparatuses 3-1, . . . , 3-N respectively perform pseudo random number generation MPC protocol using p as an input and obtain
r[t,1,p], . . . ,r[t,N,p] (49)
as outputs.
Step 3.3:
The server apparatuses 3-1, . . . , 3-N respectively receive
(v(v[t,1,p],r[t,1,p]), . . . ,(v[t,N,p],r[t,N,p]) (50)
as inputs and execute the multiplicative modulus MPC protocol, and respectively obtain
e[t,1,p], . . . ,e[t,N,p] (51).

(104) In Step 1.2, the modular exponentiation MPC protocol is executed for each j=1, . . . , nm, k=1, . . . , m, so that modular exponentiation MPC is performed for (nm)m times. However, these modular exponentiation MPCs may be performed in parallel or sequentially one by one.

(105) Likewise, in Step 2.2, the modular exponentiation MPC is performed a total of nm times, but these modular exponentiation MPCs may be performed in parallel or sequentially one by one.

(106) Furthermore, since the random number generation MPC of Step 3.2 can be executed independently from Steps 1.1, 1.2, 2.1, 2.2, and 3.1, Step 3.2 may be executed concurrently when executing Steps 1.1, 1.2, 2.1, 2.2, and 3.1, or at first Step 3.2 may be executed and then Steps 1.1, 1.2, 2.1, 2.2, and 3.1 may be executed.

(107) In addition, in Steps 1.2 and 2.2, the modular exponentiation MPC is performed using the Carmichael function value, (p), but usage of a multiple of (p), instead of (p), works correctly. Usage of the Euler function value (p), instead of (p), also works correctly.

(108) The disclosures of the above non-patent documents are incorporated herein by reference. Within the framework of the entire disclosure (including the scope of claims) of the present invention, it is possible to change/adjust the embodiment or example based on the basic technical thought further. Also, various combinations or selections of various disclosed elements (including each element of each claim, each element of each embodiment, each element of each drawing, etc.) are possible within the scope of the claims of the present invention. That is, it goes without saying that the present invention includes various modifications and modifications that could be made by those skilled in the art according to the entire disclosure including the claims, and technical ideas.

(109) The above-described embodiment is attached as follows (however, it is not limited to the following).

(110) (Supplementary Note 1)

(111) A secret character string calculation system comprising: a registration apparatus; a retrieval apparatus; and a plurality of server apparatuses,

(112) wherein the registration apparatus comprises

(113) a registration character string share generation unit configured to generate shares by secret sharing of a registration character string, with a plurality of modulus, wherein the registration apparatus sends the shares generated by the registration character string share generation unit to the plurality of server apparatuses, respectively,

(114) wherein the plurality of server apparatuses respectively store the received shares in storage units thereof,

(115) wherein the retrieval apparatus further comprises

(116) a retrieval character string share generation unit configured to generate shares by secret sharing of a retrieval character string with the plurality of modulus, wherein the retrieval apparatus sends the shares generated by the retrieval character string share generation unit to the plurality of server apparatuses, respectively,

(117) wherein the plurality of server apparatuses each comprise

(118) a retrieval response calculation unit configured to execute a predetermined operation processing for the shares of each character string stored in the each storage unit and for each of the plurality of modulus, reconstruct the execution result of the operation processing, and determine, based on the reconstruction result of the execution result, whether or not to return the shares of the registration character string stored in the storage unit, as a retrieval result, and

(119) wherein the retrieval apparatus further comprises

(120) a reconstruction unit configured to reconstruct shares returned from the plurality of server apparatuses, and reconstruct, using the Chinese remainder theorem, a retrieval result from the reconstructed result.

(121) (Supplementary Note 2)

(122) The secret character string calculation system according to Supplementary note 1, wherein the registration character string is a=a[1] . . . a[n], and the retrieval character string is b=b[1] . . . b[m] (where is a concatenation operator, m and n are respective number of words of b and a such that m<n), wherein

(123) the retrieval response calculation unit of the server apparatus, as the predetermined operation processing,

(124) executes a first multiparty computation protocol to calculate shares of a value which is 1 or 0 depending on whether or not the share of the (j+k)th word of the registration character string matches the kth word of the retrieval character string, for each j (j=1, . . . , nm) and for each k (k=1, . . . , m),

(125) sums, for k=1 to m, the shares calculated by the first multiparty computation protocol with the modulus, for each j (j=1, . . . , nm)

(126) executes a second multiparty computation protocol to calculate shares of a value which is 0 or 1 depending on whether or not the summed share is 0, for each j (j=1, . . . , nm),

(127) subtracts the number of words of the retrieval character string and a sum of the shares calculated by the second multiparty computation protocol from the number of words of the registration character string with the modulus, and

(128) outputs a result obtained by multiplying the subtracted value by a share obtained by a random number generating multiparty computation protocol with the modulus.

(129) (Supplementary Note 3)

(130) The secret character string calculation system according to Supplementary note 2, wherein, in the retrieval response calculation unit,

(131) the first multiparty computation protocol executes a multiparty computation protocol that the kth word of the retrieval character string subtracted from the share of the (j+k)th word of the registration character string with the modulus is modular exponentiated by the Carmichael function value of the modulus, and

(132) the second multiparty computation protocol executes a multiparty computation protocol to modular-exponentiate the sum of shares by a Carmichael function value of the modulus.

(133) (Supplementary Note 4)

(134) A method for performing a secret character string calculation by a computer system including a plurality of server apparatuses, the method comprising:

(135) generating shares by secret sharing of a registration character string with a plurality of modulus and sending the shares to the plurality of server apparatuses, respectively, to have the shares stored in the plurality of server apparatuses;

(136) sending shares generated by secret sharing of a retrieval character string with the plurality of modulus to the plurality of server apparatuses;

(137) the plurality of server apparatuses each calling a subroutine for the stored shares of each registration character string and for each of the plurality of modulus, to execute an operation processing, reconstruct the execution result of the operation processing, and determine, based on the reconstruction result of the execution result, whether or not to return the stored shares of the registration character string as a retrieval result; and

(138) reconstructing the shares returned from the plurality of server apparatuses, and reconstructing, using the Chinese remainder theorem, the retrieval result from the reconstructed result.

(139) (Supplementary Note 5)

(140) The method for performing a secret character string calculation according to Supplementary note 4, wherein the registration character string is a=a[1] . . . a[n], the retrieval character string is b=b[1] . . . b[m] (II is a concatenation operator, m and n are respective number of words of b and a such that m<n), wherein

(141) the subroutine called by the server apparatus for each j (j=1, . . . , nm) and for each k (k=1, . . . , m),

(142) executes a first multiparty computation protocol to calculate shares of a value which is 1 or 0 depending on whether or not the share of the (j+k)th word of the registration character string matches the kth word of the retrieval character string for each j and each k,

(143) sums for k=1 to m, the shares calculated by the first multiparty computation protocol for each j,

(144) executes a second multiparty computation protocol to calculate shares of a value to be 0 or 1 depending on whether or not the summed share is 0, for each j (j=1, . . . , nm),

(145) subtracts the number of words of the retrieval character string and a sum of the shares calculated by the second multiparty computation protocol from the number of words of the registration character string with the modulus, and

(146) outputs a result obtained by multiplying the subtracted value by a share obtained by a random number generating multiparty computation protocol with the modulus.

(147) (Supplementary Note 6)

(148) The method for performing a secret character string calculation according to Supplementary note 5, wherein in the subroutine, the first multiparty computation protocol executes a multiparty computation protocol that the kth word of the retrieval character string subtracted from the share of the (j+k)th word of the registration character string with the modulus is modular exponentiated by the Carmichael function value of the modulus, and

(149) the second multiparty computation protocol executes a multiparty computation protocol to modular-exponentiate the sum of shares by a Carmichael function value of the modulus.

(150) (Supplementary Note 7)

(151) A server apparatus comprising:

(152) a communication unit configured to receive shares sent from a registration apparatus that generates the shares by secret sharing of a registration character string with a plurality of modulus, to a plurality of server apparatuses;

(153) a storage unit configured to store the received share of the registration character string; and

(154) a retrieval response calculation unit configured to execute a predetermined operation processing for the shares of each character string stored in the storage unit and for each of the plurality of modulus, reconstruct the execution result and determine, based on the reconstruction result of the execution result, whether or not to return the shares of the registration character string stored in the storage unit as a retrieval result, when the communication unit receives shares from a retrieval apparatus that sends the shares by secret sharing of a retrieval character string with the plurality of modulus to the plurality of server apparatuses, wherein

(155) the server apparatus sends the shares of the retrieval result, via the communication unit, to the retrieval apparatus that is operable to reconstruct, using the Chinese remainder theorem, a retrieval result from a reconstructed result of the shares returned from each of the server apparatuses.

(156) (Supplementary Note 8)

(157) The server apparatus according to Supplementary note 7, wherein the registration character string is a=a[1] . . . a[n], the retrieval character string is b=b[1] . . . b[m] (where is a concatenation operator, m and n are respective number of words of b and a such that m<n), wherein

(158) the retrieval response calculation unit, as the predetermined operation processing,

(159) executes a first multiparty computation protocol to calculate shares of a value which is 1 or 0 depending on whether or not the share of the (j+k)th word of the registration character string matches the kth word of the retrieval character string, for each j (j=1, . . . , nm) and for each k (k=1, . . . , m),

(160) sums for k=1 to m, the shares calculated by the first multiparty computation protocol with the modulus, for each the j,

(161) executes a second multiparty computation protocol to calculate shares of a value which is 0 or 1 depending on whether or not the summed share is 0,

(162) subtracts the number of words of the retrieval character string and a sum of the shares calculated by the second multiparty computation protocol from the number of words of the registration character string with the modulus, and

(163) outputs a result obtained by multiplying the subtracted value by a share obtained by a random number generating multiparty computation protocol with the modulus.

(164) (Supplementary Note 9)

(165) The server apparatus according to Supplementary note 8, wherein, in the retrieval response calculation unit, the first multiparty computation protocol executes a multiparty computation protocol that the kth word of the retrieval character string subtracted from the share of the (j+k)th word of the registration character string with the modulus is modular exponentiated by the Carmichael function value of the modulus, and

(166) the second multiparty computation protocol executes a multiparty computation protocol to modular-exponentiate the sum of shares by a Carmichael function value of the modulus.

(167) (Supplementary Note 10)

(168) A non-transitory computer-readable recording medium storing therein a program causing a computer constituting a server apparatus to execute processing comprising:

(169) receiving shares and storing the shares in a storage unit, the shares being sent from a registration apparatus that generates the shares by secret sharing of a registration character string with a plurality of modulus and sends the shares to a plurality of server apparatuses;

(170) performing a retrieval response calculation including executing a predetermined operation processing for the share of the each registration character string stored in the storage unit and for each of the plurality of modulus, reconstructing the execution result of the operation processing and determining, based on the reconstruction result of the execution result, whether or not to return the shares of the registration character string stored in the storage unit as a retrieval result; and

(171) sending the shares of the retrieval result to the retrieval apparatus.

(172) (Supplementary Note 11)

(173) The non-transitory computer-readable recording medium according to Supplementary note 10, wherein the registration character string is a=a[1] . . . a[n], the retrieval character string is b=b[1] . . . b[m] (where is a concatenation operator, m and n are respective number of words of b and a such that m<n), wherein

(174) the retrieval response calculation processing, as the predetermined operation processing,

(175) executes a first multiparty computation protocol to calculate shares of a value which is 1 or 0 depending on whether or not the share of the (j+k)th word of the registration character string matches the kth word of the retrieval character string, for each j (j=1, . . . , nm) and for each k (k=1, . . . , m),

(176) sums for k=1 to m, the shares calculated by the first multiparty computation protocol with the modulus, for each the j,

(177) executes a second multiparty computation protocol to calculate shares of a value which is 0 or 1 depending on whether or not the summed share is 0,

(178) subtracts the number of words of the retrieval character string and a sum of the shares calculated by the second multiparty computation protocol from the number of words of the registration character string with the modulus, and

(179) outputs a result obtained by multiplying the subtracted value by a share obtained by a random number generating multiparty computation protocol with the modulus.

(180) (Supplementary Note 12)

(181) The non-transitory computer-readable recording medium according to Supplementary note 10, wherein, in the retrieval response calculation processing, the first multiparty computation protocol executes a multiparty computation protocol that the kth word of the retrieval character string subtracted from the share of the (j+k)th word of the registration character string with the modulus is modular exponentiated by the Carmichael function value of the modulus, and

(182) the second multiparty computation protocol executes a multiparty computation protocol to modular-exponentiate the sum of shares by a Carmichael function value of the modulus.

(183) (Supplementary Note 13)

(184) A retrieval apparatus comprising:

(185) a communication unit that connects to a plurality of server apparatuses that receive and store shares sent from a registration apparatus that generates the shares by secret sharing of a registration character string with a plurality of modulus, and

(186) a retrieval character string share generation unit that generates shares by secret sharing of a retrieval character string with the plurality of modulus, wherein the retrieval apparatus sends the shares generated by the retrieval character string share generation unit to the plurality of server apparatuses respectively via the communication unit,

(187) wherein the plurality of server apparatuses execute a predetermined operation processing for the shares of each character string stored in the storage unit and for each of the plurality of modulus, reconstruct the execution result of the operation processing and determine, based on the reconstruction result of the execution result, whether or not to return the shares of the registration character string stored in the storage unit as a retrieval result,

(188) the retrieval apparatus further comprising:

(189) a restoration apparatus configured to reconstruct shares returned from the plurality of server apparatuses and received via the communication unit, and reconstructs, using the Chinese remainder theorem, the retrieval result from the reconstructed result.

(190) (Supplementary Note 14)

(191) A non-transitory computer-readable recording medium storing therein a program causing a computer constituting a retrieval apparatus connecting to a plurality of server apparatuses that receive and store shares sent from a registration apparatus that generates the shares by secret sharing of a registration character string with a plurality of modulus, to execute:

(192) a first processing that generates shares by secret sharing of a retrieval character string with the plurality of modulus to sends the shares generated to the plurality of server apparatuses, wherein the plurality of server apparatuses execute a predetermined operation processing for the shares of each character string stored in the storage unit and for each of the plurality of modulus, reconstruct the execution result of the operation processing and determine, based on the reconstruction result of the execution result, whether or not to return the shares of the registration character string stored in the storage unit as a retrieval result; and

(193) a second processing that reconstruct the shares returned from the plurality of server apparatuses and reconstructs, using Chinese remainder theorem. the retrieval result from the reconstructed result.