Retrieval device, retrieval method, program, and recording medium

1. A retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs exact match search by secure computation in which m, n, t(i), and N are positive integers, i=1, . . . , m, j=1, . . . , N, n≤N, and t(i)≤N, the retrieval device comprising:

a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ]; and

processing circuitry configured to

receive an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtain a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x j ] and the concealed search word [k];

obtain a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtain a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j =d 1 is established when at least one of e i,j =a 1 and w j =b 1 is satisfied and y i,j =d 0 is established when both of e i,j =a 0 and w j =b 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [w];

obtain a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,N =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,N =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]; and

output the concealed match determination result [z i ] to the request device via the network,

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

2. A retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs exact match search by secure computation in which m, n, t(i), and N are positive integers, i=1, . . . , m, j=1, . . . , N, n≤N, and t(i)≤N, the retrieval device comprising:

a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ]; and

processing circuitry configured to

receive an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtain a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtain a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtain a concealed operation result [μ i ] in which an operation result μ i =(μ i,1 , . . . , μ i,N ) is concealed, the operation result μ i in which μ i,j =θ 0 is established when x i,j is a null character and μ i,j =θ 1 is established when x i,j is not a null character, θ 0 and θ 1 are elements of a set {θ 0 , θ 1 }, and θ 0 ≠θ 1 , by secure computation using the concealed search target word [x i ];

obtain a concealed operation result [v i ] in which an operation result v i (v i,1 , . . . , v i,N ) is concealed, the operation result v i in which v i,j =ρ 1 is established when both of w j =b j and μ i,j =θ 1 are satisfied and v i,j =ρ 0 is established when at least one of w j =b 0 and μ i,j =θ 0 is satisfied, ρ 0 and ρ 1 are elements of a set {ρ 0 , ρ 1 }, and ρ 0 ≠ρ 1 , by secure computation using the concealed operation result [w] and the concealed operation result [μ i ];

obtain a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j =d 1 is established when at least one of e i,j =a 1 and v i,j =ρ 1 is satisfied and y i,j =d 0 is established when both of e i,j =a 0 and v i,j =ρ 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [v i ];

obtain a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,N =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,N =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]; and

output the concealed match determination result [z i ] to the request device via the network,

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

3. A retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs prefix search by secure computation in which

m, n, t(i), and N are positive integers, i=1, . . . , m, j=1, . . . , N, n≤N, and t(i)≤N, the retrieval device comprising:

a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ]; and

processing circuitry configured to

receive an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtain a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtain a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtain a concealed operation result [u] in which an operation result u=(u 1 , . . . , u N ) is concealed, the operation result u in which u j =c 1 is established when k j is a null character and u j =c 0 is established when k j is not a null character, c 0 and c 1 are elements of a set {c 0 , c 1 }, and c 0 ≠c 1 , by secure computation using the concealed search word [k];

obtain a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j =d 1 is established when at least any one of e i,j =a 1 , w j =b 1 , and u j =c 1 is satisfied and y i,j =d 0 is established when all of e i,j =a 0 , w j =b 0 , and u j =c 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ], the concealed operation result [w], and the concealed operation result [u];

obtain a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,N =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,N =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]; and

output the concealed match determination result [z i ] to the request device via the network,

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

4. A retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs prefix search by secure computation in which

m, n, t(i), and N are positive integers, i=1, . . . , m, j=1, . . . , N, n≤N, and t(i)≤N, the retrieval device comprising:

a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ]; and

processing circuitry configured to

receive an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtain a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtain a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtain a concealed operation result [u] in which an operation result u=(u 1 , . . . , u N ) is concealed, the operation result u in which u j =c 1 is established when k j is a null character and u j =c 0 is established when k j is not a null character, c 0 and c 1 are elements of a set {c 0 , c 1 }, and c 0 ≠c 1 , by secure computation using the concealed search word [k];

obtain a concealed operation result [μ i ] in which an operation result μ i =(μ i,1 , . . . , μ i,N ) is concealed, the operation result μ i in which μ i,j =θ 0 is established when x i,j is a null character and μ i,j =θ 1 is established when x i,j is not a null character, θ 0 and θ 1 are elements of a set {θ 0 , θ 1 }, and θ 0 ≠θ 1 , by secure computation using the concealed search target word [x i ];

obtain a concealed operation result [v i ] in which an operation result v i =(v i,1 , . . . , v i,N ) is concealed, the operation result v i in which v i,j =ρ 1 is established when both of w j =b 1 and μ i,j =θ 1 are satisfied and v i,j =ρ 0 is established when at least one of w j =b 0 and μ i,j =θ 0 is satisfied, ρ 0 and ρ 1 are elements of a set {ρ 0 , ρ 1 }, and ρ 0 ≠ρ 1 , by secure computation using the concealed operation result [w] and the concealed operation result [μ i ];

obtain a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j =d 1 is established when at least any one of e i,j =a 1 , v i,j =ρ 1 , and u j =c 1 is satisfied and y i,j =d 0 is established when all of e i,j =a 0 , v i,j =ρ 0 , and u j =c 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ], the concealed operation result [u], and the concealed operation result [v i ];

obtain a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,N =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,N =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]; and

output the concealed match determination result [z i ] to the request device via the network,

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

5. A retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs exact match search by secure computation in which

m, n, t(i), N, and N(i) are positive integers, N>N(i), i=1, . . . , m, j=1, . . . , N, j(i)=1, . . . , N(i), j″(i)=N(i)+1, . . . , N, n≤N, and t(i)≤N(i), the retrieval device comprising:

a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ]; and

processing circuitry configured to

receive an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtain a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N(i) ) is concealed, the operation result e i in which e i,j(i) =a 1 is established when x i,j(i) is k j(i) and e i,j(i) =a 0 is established when x i,j(i) is not k j(i) , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtain a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N(i) ) is concealed, the operation result w in which w j(i) =b 1 is established when k j(i) is the wildcard character and w j(i) =b 0 is established when k j(i) is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtain a concealed operation result [u′] in which operation results u′ N(i)+1 , . . . , u′ N are concealed, the operation results u′ N(i)+1 , . . . , u′ N in which u′ j″(i) =c 1 is established when k j″(i) is a null character and u′ j″(i) =c 0 is established when k j″(i) is not a null character, c 0 and c 1 are elements of a set {c 0 , c 1 }, and c 0 ≠c 1 , by secure computation using at least a part of the concealed search word [k];

obtain a concealed operation result [e′ i ] in which an operation result e′ i =(e′ i,1 , . . . , e′ i,N(i) ) is concealed, the operation result e′ i in which e′ i,j(i) =d 1 is established when at least one of e i,j(i) =a 1 and w j(i) =b 1 is satisfied and e′ i,j(i) =d 0 is established when both of e i,j(i) =a 0 and w j(i) =b 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [w];

obtain a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N )=(e′ i,1 , . . . , e′ i,N(i) , u′ N(i)+1 , . . . , u′ N ) is concealed, by secure computation using the concealed operation result [u′] and the concealed operation result [e′ i ];

obtain a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,Nmax =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,Nmax =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]; and

output the concealed match determination result [z i ] to the request device via the network,

wherein

N max =N(i) is established when N≤N(i), and N max =N is established when N>N(i), and

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

6. A retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs exact match search by secure computation in which

m, n, t(i), N, and N(i) are positive integers, N<N(i), i=1, . . . , m, j=1, . . . , N, j(i)=1, . . . , N(i), n≤N, t(i)≤N(i), and j″(i)=N+1, . . . , N(i), the retrieval device comprising:

a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,1(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ]; and

processing circuitry configured to

receive an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtain a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtain a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtain a concealed operation result [e′ i ] in which an operation result e′ i =(e′ i,1 , . . . , e′ i,N ) is concealed, the operation result e′ i in which e′ i,j =d 1 is established when at least one of e i,j =a 1 and w j =b 1 is satisfied and e′ i,j =d 0 is established when both of e i,j =a 0 and w j =b 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [w];

obtain a concealed operation result [μ′ i ] in which an operation result μ′ i =(μ′ i,N+1 , . . . , μ′ i,N(i) ) is concealed, the operation result μ′ i in which μ′ i,j″(i) =d 1 is established when x i,j″(i) is a null character and μ′ i,j″(i) =d 0 is established when x i,j″(i) is not a null character, by secure computation using at least a part of the concealed search target word [x i ];

obtain a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N(i) )=(e′ i,1 , . . . , e′ i,N , μ′ i,N+1 , . . . , μ′ i,N(i) ) is concealed, by secure computation using the concealed operation result [e′ i ] and the concealed operation result [μ′ i ];

obtain a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,Nmax =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,Nmax =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]; and

output the concealed match determination result [z i ] to the request device via the network,

wherein

N max =N(i) is established when N≤N(i), and N max =N is established when N>N(i), and

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

7. A retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs prefix search by secure computation in which

m, n, t(i), N, and N(i) are positive integers, N≤N(i), i=1, . . . , m, j=1, . . . , N, j(i)=1, . . . , N(i), n≤N, and t(i)≤N(i), the retrieval device comprising:

a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ]; and

processing circuitry configured to

receive an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtain a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtains a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtain a concealed operation result [u″] in which an operation result u″=(u″ 1 , . . . , u″ N ) is concealed, the operation result u″ in which u″ j =c 1 is established when k j is a null character and u″ j =c 0 is established when k j is not a null character, c 0 and c 1 are elements of a set {c 0 , c 1 }, and c 0 ≠c 1 , by secure computation using the concealed search word [k];

obtain a concealed operation result [w′] in which an operation result w′=(w′ 1 , . . . , w′ N ) is concealed, the operation result w′ in which w′ j =b′ 1 is established when at least one of u″ j =c 1 and w j =b 1 is satisfied and w′ j =b′ 0 is established when both of u″ j =c 0 and w j =b 0 are satisfied, b′ 0 and b′ 1 are elements of a set {b′ 0 , b′ 1 }, and b′ 0 ≠b′ 1 , by secure computation using the concealed operation result [w] and the concealed operation result [u″]; a second OR operation unit that obtains a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j =d 1 is established when at least one of e i,j =a 1 and w′ j =b′ 1 is satisfied and y i,j =d 0 is established when both of e i,j =a 0 and w′ j =b′ 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [w′]; and

obtain a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,Nmax =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,Nmax =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]; and

output the concealed match determination result [z i ] to the request device via the network,

wherein

N max =N(i) is established when N≤N(i), and N max =N is established when N>N(i), and

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

8. A retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs prefix search by secure computation in which

m, n, t(i), N, and N(i) are positive integers, N>N(i), i=1, . . . , m, j=1, . . . , N, j(i)=1, . . . , N(i), j″(i)=N(i)+1, . . . , N, n≤N, and t(i)≤N(i), the retrieval device comprising:

a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,1(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ]; and

processing circuitry configured to

receive an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtain a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N(i) ) is concealed, the operation result e i in which e i,j(i) =a 1 is established when x i,j(i) is k j(i) and e i,j(i) =a 0 is established when x i,j(i) is not k j(i) , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtain a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N(i) ) is concealed, the operation result w in which w j(i) =b 1 is established when k j(i) is the wildcard character and w j(i) =b 0 is established when k j(i) is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtain a concealed operation result [u″] in which an operation result u″=(u″ 1 , . . . , u″ N ) is concealed, the operation result u″ in which u″ j =c 1 is established when k j is a null character and u″ j =c 0 is established when k j is not a null character, c 0 and c 1 are elements of a set {c 0 , c 1 }, and c 0 ≠c 1 , by secure computation using the concealed search word [k];

obtain a concealed operation result [w′] in which an operation result w′=(w′ 1 , . . . , w′ N(i) ) is concealed, the operation result w′ in which w′ j(i) =b′ 1 is established when at least one of u″ j(i) =c 1 and w j(i) =b 1 is satisfied and w′ j(i) =b′ 0 is established when both of u″ j(i) =c 0 and w j(i) =b 0 are satisfied, b′ 0 and b′ 1 are elements of a set {b′ 0 , b′ 1 } and b′ 0 ≠b′ 1 , by secure computation using at least a part of the concealed operation result [w] and the concealed operation result [u″];

obtain a concealed operation result [e′ i ] in which an operation result e′ i =(e′ i,1 , . . . , e′ i,N(i) ) is concealed, the operation result e′ i in which e′ i,j(i) =d 1 is established when at least one of e i,j(i) =a 1 and w′ j(i) =b′ 1 is satisfied and e′ i,j(i) =d 0 is established when both of e i,j(i) =a 0 and w′ j(i) =b′ 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [w′];

obtain a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N )=(e′ i,1 , . . . , e′ i,N(i) , u″ N(i)+1 , . . . , u″ N ) is concealed, by secure computation using at least a part of the concealed operation result [e′ i ] and the concealed operation result [u″];

obtain a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,Nmax =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,Nmax =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]; and

output the concealed match determination result [z i ] to the request device via the network,

wherein

N max =N(i) is established when N≤N(i), and N max =N is established when N>N(i), and

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

9. A retrieval method of a retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs exact match search by secure computation in which m, n, t(i), and N are positive integers, i=1, . . . , m, j=1, . . . , N, n≤N, and t(i)≤N, the retrieval device comprises a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i (x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ] wherein

the retrieval method, performed by processing circuitry of the retrieval device comprises:

receiving an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtaining a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtaining a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j =d 1 is established when at least one of e i,j =a 1 and w j =b 1 is satisfied and y i,j =d 0 is established when both of e i,j =a 0 and w j =b 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [w]; and

obtaining a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,N =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,N =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]]; and

outputting the concealed match determination result [z i ] to the request device via the network,

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

10. A retrieval method of a retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs exact match search by secure computation in which

m, n, t(i), and N are positive integers, i=1, . . . , m, j=1, . . . , N, n≤N, and t(i)≤N, the retrieval device comprises a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ], wherein

the retrieval method, performed by processing circuitry of the retrieval device comprises:

receiving an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtaining a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtaining a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [μ i ] in which an operation result μ i =(μ i,1 , . . . , μ i,N ) is concealed, the operation result μ i in which μ i,j =θ 0 is established when x i,j is a null character and μ i,j =θ 1 is established when x i,j is not a null character, θ 0 and θ 1 are elements of a set {θ 0 , θ 1 }, and θ 0 ≠θ 1 , by secure computation using the concealed search target word [x i ];

obtaining a concealed operation result [v i ] in which an operation result v i =(v i,1 , . . . , v i,N ) is concealed, the operation result v i in which v i,j =ρ 1 is established when both of w j =b 1 and μ i,j =θ 1 are satisfied and v i,j =ρ 0 is established when at least one of w j =b 0 and μ i,j =θ 0 is satisfied, ρ 0 and ρ 1 are elements of a set {ρ 0 , ρ 1 }, and ρ 0 ≠ρ 1 , by secure computation using the concealed operation result [w] and the concealed operation result [μ i ];

obtaining a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j =d 1 is established when at least one of e i,j =a 1 and v i,j =ρ 1 is satisfied and y i,j =d 0 is established when both of e i,j =a 0 and v i,j =ρ 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [v i ]; and

obtaining a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,N =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,N =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]; and

outputting the concealed match determination result [z i ] to the request device via the network,

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

11. A retrieval method of a retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs prefix search by secure computation in which

m, n, t(i), and N are positive integers, i=1, . . . , m, j=1, . . . , N, n≤N, and t(i)≤N, the retrieval device comprises a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ], wherein

the retrieval method, performed by processing circuitry of the retrieval device comprises:

receiving an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtaining a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtaining a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [u] in which an operation result u=(u 1 , . . . , u N ) is concealed, the operation result u in which u j =c 1 is established when k j is a null character and u j =c 0 is established when k j is not a null character, c 0 and c 1 are elements of a set {c 0 , c 1 }, and c 0 ≠c 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j =d 1 is established when at least any one of e i,j =a 1 , w j =b 1 , and u j =c 1 is satisfied and y i,j =d 0 is established when all of e i,j =a 0 , w j =b 0 , and u j =c 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ], the concealed operation result [w], and the concealed operation result [u]; and

obtaining a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,N =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,N =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]]; and

outputting the concealed match determination result [z i ] to the request device via the network,

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

12. A retrieval method of a retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs prefix search by secure computation in which

m, n, t(i), and N are positive integers, i=1, . . . , m, j=1, . . . , N, n≤N, and t(i)≤N, the retrieval device comprises a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ], wherein

the retrieval method, performed by processing circuitry of the retrieval device comprises:

receiving an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtaining a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtaining a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [u] in which an operation result u=(u 1 , . . . , u N ) is concealed, the operation result u in which u j =c 1 is established when k j is a null character and u j =c 0 is established when k j is not a null character, c 0 and c 1 are elements of a set {c 0 , c 1 }, and c 0 ≠c 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [μ i ] in which an operation result μ i =(μ i,1 , . . . , μ i,N ) is concealed, the operation result μ i in which μ i,j =θ 0 is established when x i,j is a null character and μ i,j =θ 1 is established when x i,j is not a null character, θ 0 and θ 1 are elements of a set {θ 0 , θ 1 }, and θ 0 ≠θ 1 , by secure computation using the concealed search target word [x i ];

obtaining a concealed operation result [v i ] in which an operation result v i =(v i,1 , . . . , v i,N ) is concealed, the operation result v i in which v i,j =ρ 1 is established when both of w j =b 1 and μ i,j =θ 1 , are satisfied and v i,j =ρ 0 is established when at least one of w j =b 0 and μ i,j =θ 0 is satisfied, ρ 0 and ρ 1 are elements of a set {ρ 0 , ρ 1 }, and ρ 0 ≠ρ 1 , by secure computation using the concealed operation result [w] and the concealed operation result [μ i ];

obtaining a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j =d 1 is established when at least any one of e i,j =a 1 , v i,j =ρ 1 , and u j =c 1 is satisfied and y i,j =d 0 is established when all of e i,j =a 0 , v i,j =ρ 0 , and u j =c 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ], the concealed operation result [u], and the concealed operation result [v i ];

obtaining a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,N =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,N =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]]; and

outputting the concealed match determination result [z i ] to the request device via the network,

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

13. A retrieval method of a retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs exact match search by secure computation in which

m, n, t(i), N, and N(i) are positive integers, N>N(i), i=1, . . . , m, j=1, . . . , N, j(i)=1, . . . , N(i), j″(i)=N(i)+1, . . . , N, n≤N, and t(i)≤N(i), the retrieval device comprises a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i (x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ], wherein

the retrieval method, performed by processing circuitry of the retrieval device comprises:

receiving an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtaining a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N(i) ) is concealed, the operation result e i in which e i,j(i) =a 1 is established when x i,j(i) is k j(i) and e i,j(i) =a 0 is established when x i,j(i) is not k j(i) , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtaining a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N(i) ) is concealed, the operation result w in which w j(i) =b 1 is established when k j(i) is the wildcard character and w j(i) =b 0 is established when k j(i) is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [u′] in which operation results u′ N(i)+1 , . . . , u′ N are concealed, the operation results u′ N(i)+1 , . . . , u′ N in which u′ j″(i) =c 1 is established when k j″(i) is a null character and u′ j″(i) =c 0 is established when k j″(i) is not a null character, c 0 and c 1 are elements of a set {c 0 , c 1 }, and c 0 ≠c 1 , by secure computation using at least a part of the concealed search word [k];

obtaining a concealed operation result [e′ i ] in which an operation result e′ i =(e′ i,1 , . . . , e′ i,N(i) ) is concealed, the operation result e′ i in which e′ i,j(i) =d 1 is established when at least one of e i,j(i) =a 1 and w j(i) =b 1 is satisfied and e′ i,j(i) =d 0 is established when both of e i,j(i) =a 0 and w j(i) =b 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [w];

obtaining a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N )=(e′ i,1 , . . . , e′ i,N(i) , u′ N(i)+1 , . . . , u′ N ) is concealed, by secure computation using the concealed operation result [u′] and the concealed operation result [e′ i ];

obtaining a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,Nmax =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,Nmax =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]; and

outputting the concealed match determination result [z i ] to the request device via the network,

wherein

N max =N(i) is established when N≤N(i), and N max =N is established when N>N(i), and

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

14. A retrieval method of a retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs exact match search by secure computation in which

m, n, t(i), N, and N(i) are positive integers, N<N(i), i=1, . . . , m, j=1, . . . , N, j(i)=1, . . . , N(i), n≤N, t(i)≤N(i), and j″(i)=N+1, . . . , N(i), the retrieval device comprises a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ], wherein

the retrieval method, performed by processing circuitry of the retrieval device comprises:

receiving an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtaining a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtaining a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [e′ i ] in which an operation result e′ i =(e′ i,1 , . . . , e′ i,N ) is concealed, the operation result e′ i in which e′ i,j =d 1 is established when at least one of e i,j =a 1 and w j =b 1 is satisfied and e′ i,j =d 0 is established when both of e i,j =a 0 and w j =b 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [w];

obtaining a concealed operation result [μ′ i ] in which an operation result μ′ i =(μ′ i,N+1 , . . . , μ′ i,N(i) ) is concealed, the operation result μ′ i in which μ′ i,j(i) =d 1 is established when x i,j″(i) is a null character and μ′ i,j″(i) =d 0 is established when x i,j″(i) is not a null character, by secure computation using at least a part of the concealed search target word [x i ];

obtaining a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N(i) )=(e′ i,1 , . . . , e′ i,N , μ′ i,N+1 , . . . , μ′ i,N(i) ) is concealed, by secure computation using the concealed operation result [e′ i ] and the concealed operation result [μ′ i ];

obtaining a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,Nmax =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,Nmax =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]; and

outputting the concealed match determination result [z i ] to the request device via the network,

wherein

N max =N(i) is established when N≤N(i), and N max =N is established when N>N(i), and

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

15. A retrieval method of a retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs prefix search by secure computation in which

m, n, t(i), N, and N(i) am positive integers, N≤N(i), i=1, . . . , m, j=1, . . . , N, j(i)=1, . . . , N(i), n≤N, and t(i)≤N(i), the retrieval device comprises a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ] wherein

the retrieval method, performed by processing circuitry of the retrieval device comprises:

receiving an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtaining a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtaining a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [u″] in which an operation result u″=(u″ 1 , . . . , u″ N ) is concealed, the operation result u″ in which u″ j =c 1 is established when k j is a null character and u″ j =c 0 is established when k j is not a null character, c 0 and c 1 are elements of a set {c 0 , c 1 }, and c 0 ≠c 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [w′] in which an operation result w′=(w′ 1 , . . . , w′ N ) is concealed, the operation result w′ in which w′ j =b′ 1 is established when at least one of u″ j =c 1 and w j =b 1 is satisfied and w′ j =b′ 0 is established when both of u″ j =c 0 and w j =b 0 are satisfied, b′ 0 and b′ 1 are elements of a set {b′ 0 , b′ 1 }, and b′ 0 ≠b′ 1 , by secure computation using the concealed operation result [w] and the concealed operation result [u″];

obtaining a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j =d 1 is established when at least one of e i,j =a 1 and w′ j =b′ 1 is satisfied and y i,j =d 0 is established when both of e i,j =a 0 and w′ j =b 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [w′];

obtaining a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,Nmax =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,Nmax =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]; and

outputting the concealed match determination result [z i ] to the request device via the network,

wherein

N max =N(i) is established when N≤N(i), and N max =N is established when N>N(i), and

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

16. A retrieval method of a retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs prefix search by secure computation in which

m, n, t(i), N, and N(i) are positive integers, N>N(i), i=1, . . . , m, j=1, . . . , N, j(i)=1, . . . , N(i), j″(i)=N(i)+1, . . . , N, n≤N, and t(i)≤N(i), the retrieval device comprises a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ], wherein

the retrieval method, performed by processing circuitry of the retrieval device comprises:

receiving an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtaining a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N(i) ) is concealed, the operation result e i in which e i,j(i) =a 1 is established when x i,j(i) is k j(i) and e i,j(i) =a 0 is established when x i,j(i) is not k j(i) , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtaining a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N(i) ) is concealed, the operation result w in which w j(i) =b 1 is established when k j(i) is the wildcard character and w j(i) =b 0 is established when k j(i) is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [u″] in which an operation result u″=(u″ 1 , . . . , u″ N ) is concealed, the operation result u″ in which u″ j =c 1 is established when k j is a null character and u″ j =c 0 is established when k j is not a null character, c 0 and c 1 are elements of a set {c 0 , c 1 }, and c 0 ≠c 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [w′] in which an operation result w′=(w′ 1 , . . . , w′ N(i) ) is concealed, the operation result w′ in which w′ j(i) =b′ 1 is established when at least one of u″ j(i) =c 1 and w j(i) =b 1 is satisfied and w′ j(i) =b′ 0 is established when both of u″ j(i) =c 0 and w j(i) =b 0 are satisfied, b′ 0 and b′ 1 are elements of a set {b′ 0 , b′ 1 }, and b′ 0 ≠b′ 1 , by secure computation using at least a part of the concealed operation result [w] and the concealed operation result [u″];

obtaining a concealed operation result [e′ i ] in which an operation result e′ i =(e′ i,1 , . . . , e′ i,N(i) ) is concealed, the operation result e′ i in which e′ i,j(i) =d 1 is established when at least one of e i,j(i) =a 1 and w′ j(i) =b′ 1 is satisfied and e′ i,j(i) =d 0 is established when both of e i,j(i) =a 0 and w′ j(i) =b′ 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [w′];

obtaining a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N )=(e′ i,1 , . . . , e′ i,N(i) , u″ N(i)+1 , . . . , u″ N ) is concealed, by secure computation using at least a part of the concealed operation result [e′ i ] and the concealed operation result [u″]:

obtaining a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,Nmax =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,Nmax =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]; and

outputting the concealed match determination result [z i ] to the request device via the network,

wherein

N max =N(i) is established when N≤N(i), and N max =N is established when N>N(i), and

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

17. A non-transitory computer-readable recording medium that stores a program for making a computer function of a retrieval method of a retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs exact match search by secure computation in which

m, n, t(i), and N are positive integers, i=1, . . . , m, j=1, . . . , N, n≤N, and t(i)≤N, the retrieval device compress a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ], wherein

the retrieval method comprises:

receiving an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtaining a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtaining a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j =d 1 is established when at least one of e i,j =a 1 and w j =b 1 is satisfied and y i,j =d 0 is established when both of e i,j =a 0 and w j =b 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [w];

obtaining a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . y i,N =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,N =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]]; and

outputting the concealed match determination result [z i ] to the request device via the network,

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

18. A non-transitory computer-readable recording medium that stores a program for making a computer function of a retrieval method of a retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs exact match search by secure computation in which

m, n, t(i), and N are positive integers, i=1, . . . , m, j=1, . . . , N, n≤N, and t(i)≤N, the retrieval device comprises a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ], wherein

the retrieval method comprises:

receiving an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtaining a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtaining a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [μ i ] in which an operation result μ i =(μ i,1 , . . . , μ i,N ) is concealed, the operation result μ i in which μ i,j =θ 0 is established when x i,j is a null character and μ i,j =θ 1 is established when x i,j is not a null character, θ 0 and θ 1 are elements of a set {θ 0 , θ 1 }, and θ 0 ≠θ 1 , by secure computation using the concealed search target word [x i ];

obtaining a concealed operation result [v i ] in which an operation result v i =(v i,1 , . . . , v i,N ) is concealed, the operation result v i in which v i,j =ρ 1 is established when both of w j =b 1 and μ i,j =θ 1 are satisfied and v i,j ρ 0 is established when at least one of w j =b 0 and μ i,j =θ 0 is satisfied, ρ 0 and ρ 1 are elements of a set {ρ 0 , ρ 1 }, and ρ 0 ≠ρ 1 , by secure computation using the concealed operation result [w] and the concealed operation result [μ i ];

obtaining a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j d 1 is established when at least one of e i,j =a 1 and v i,j =ρ 1 is satisfied and y i,j =d 0 is established when both of e i,j =a 0 and v i,j =ρ 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [v i ];

obtaining a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,N =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,N =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]]; and

outputting the concealed match determination result [z i ] to the request device via the network,

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

19. A non-transitory computer-readable recording medium that stores a program for making a computer function of a retrieval method of a retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs prefix search by secure computation in which

m, n, t(i), and N are positive integers, i=1, . . . , m, j=1, . . . , N, n≤N, and t(i)≤N, the retrieval device comprises a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ], wherein

the retrieval method comprises:

receiving an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtaining a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtaining a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [u] in which an operation result u=(u 1 , . . . , u N ) is concealed, the operation result u in which u j =c 1 is established when k j is a null character and u j =c 0 is established when k j is not a null character, c 0 and c 1 are elements of a set {c 0 , c 1 }, and c 0 ≠c 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j =d 1 is established when at least any one of e i,j =a 1 , w j =b 1 , and u j =c 1 is satisfied and y i,j =d 0 is established when all of e i,j =a 0 , w j =b 0 , and u j =c 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ], the concealed operation result [w], and the concealed operation result [u]; and

obtaining a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . y i,N =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,N =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]]; and

outputting the concealed match determination result [z i ] to the request device via the network,

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

20. A non-transitory computer-readable recording medium that stores a program for making a computer function of a retrieval method of a retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs prefix search by secure computation in which

m, n, t(i), and N are positive integers, i=1, . . . , m, j=1, . . . , N, n≤N, and t(i)≤N, the retrieval device comprises a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ], wherein

the retrieval method comprises:

receiving an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtaining a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtaining a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [u] in which an operation result u=(u 1 , . . . , u N ) is concealed, the operation result u in which u j =c 1 is established when k j is a null character and u j =c 0 is established when k j is not a null character, c 0 and c 1 are elements of a set {c 0 , c 1 }, and c 0 ≠c 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [μ i ] in which an operation result μ i =(μ i,1 , . . . , μ i,N ) is concealed, the operation result μ i in which μ i,j =θ 0 is established when x i,j is a null character and μ i,j =θ 1 is established when x i,j is not a null character, θ 0 and θ 1 are elements of a set {θ 0 , θ 1 }, and θ 0 ≠θ 1 , by secure computation using the concealed search target word [x i ];

obtaining a concealed operation result [v i ] in which an operation result v i =(v i,1 , . . . , v i,N ) is concealed, the operation result v i in which v i,j =ρ 1 is established when both of w j =b 1 and μ i,j =θ 1 are satisfied and v i,j =ρ 0 is established when at least one of w j =b 0 and μ i,j =θ 0 is satisfied, ρ 0 and ρ 1 are elements of a set {ρ 0 , ρ 1 }, and ρ 0 ≠ρ 1 , by secure computation using the concealed operation result [w] and the concealed operation result [μ i ];

obtaining a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j =d 1 is established when at least any one of e i,j =a 1 , v i,j =ρ 1 , and u j =c 1 is satisfied and y i,j =d 0 is established when all of e i,j =a 0 , v i,j =ρ 0 , and u j =c 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ], the concealed operation result [u], and the concealed operation result [v i ];

obtaining a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . y i,N =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,N =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]]; and

outputting the concealed match determination result [z i ] to the request device via the network,

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

21. A non-transitory computer-readable recording medium that stores a program for making a computer function of a retrieval method of a retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs exact match search by secure computation in which

m, n, t(i), N, and N(i) are positive integers, N>N(i), i=1, . . . , m, j=1, . . . , N, j(i)=1, . . . , N(i), j″(i)=N(i)+1, . . . , N, n≤N, and t(i)≤N(i), the retrieval device comprises a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ], wherein

the retrieval method comprises:

receiving an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtaining a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N(i) ) is concealed, the operation result e i in which e i,j(i) =a 1 is established when x i,j(i) is k j(i) and e i,j(i) =a 0 is established when x i,j(i) is not k j(i) , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtaining a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N(i) ) is concealed, the operation result w in which w j(i) =b 1 is established when k j(i) is the wildcard character and w j(i) =b 0 is established when k j(i) is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [u′] in which operation results u′ N(i)+1 , . . . , u′ N are concealed, the operation results u′ N(i)+1 , . . . , u′ N in which u′ j″(i) =c 1 is established when k j″(i) is a null character and u′ j″(i) =c 0 is established when k j″(i) is not a null character, c 0 and c 1 are elements of a set {c 0 , c 1 }, and c 0 ≠c 1 , by secure computation using at least a part of the concealed search word [k];

obtaining a concealed operation result [e′ i ] in which an operation result e′ i (e′ i,1 , . . . , e′ i,N(i) ) is concealed, the operation result e′ i in which e′ i,j(i) =d 1 is established when at least one of e i,j(i) =a 1 and w j(i) =b 1 is satisfied and e′ i,j(i) =d 0 is established when both of e i,j(i) =a 0 and w j(i) =b 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [w];

obtaining a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N )=(e′ i,1 , . . . , e′ i,N(i) , u′ N(i)+1 , . . . , u′ N ) is concealed, by secure computation using the concealed operation result [u′] and the concealed operation result [e′ i ];

obtaining a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,Nmax =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,Nmax =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]; and

outputting the concealed match determination result [z i ] to the request device via the network,

wherein

N max =N(i) is established when N≤N(i), and N max =N is established when N>N(i), and

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

22. A non-transitory computer-readable recording medium that stores a program for making a computer function of a retrieval method of a retrieval device that performs exact match search by secure computation in which

m, n, t(i), N, and N(i) are positive integers, N<N(i), i=1, . . . , m, j=1, . . . , N, j(i)=1, . . . , N(i), n≤N, t(i)≤N(i), and j″(i)=N+1 . . . , N(i), the retrieval device comprises a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i an each of the plurality of retrieval devices stores the different concealed search target word [x i ], wherein

the retrieval method comprises:

receiving an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtaining a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtaining a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [e′ i ] in which an operation result e′ i =(e′ i,1 , . . . , e′ i,N ) is concealed, the operation result e′ i in which e′ i,j =d 1 is established when at least one of e i,j =a 1 and w j =b 1 is satisfied and e′ i,j =d 0 is established when both of e i,j =a 0 and w j =b 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [w];

obtaining a concealed operation result [μ′ i ] in which an operation result μ′ i =(μ′ i,N+1 , . . . , μ′ i,N(i) ) is concealed, the operation result μ′ i in which μ′ i,j″(i) =d 1 is established when x i,j″(i) is a null character and μ′ i,j″(i) =d 0 is established when x i,j″(i) is not a null character, by secure computation using at least a part of the concealed search target word [x i ];

obtaining a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N(i) )=(e′ i,1 , . . . , e′ i,N , μ′ i,N+1 , . . . , μ′ i,N(i) ) is concealed, by secure computation using the concealed operation result [e′ i ] and the concealed operation result [μ′ i ];

obtaining a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,Nmax =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,Nmax =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]; and

outputting the concealed match determination result [z i ] to the request device via the network,

wherein

N max =N(i) is established when N≤N(i), and N max =N is established when N>N(i), and

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

23. A non-transitory computer-readable recording medium that stores a program for making a computer function of a retrieval method of a retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs prefix search by secure computation in which

m, n, t(i), N, and N(i) am positive integers, N≤N(i), i=1, . . . , m, j=1, . . . , N, j(i)=1, . . . , N(i), n≤N, and t(i)≤N(i), the retrieval device comprises a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ], wherein

the retrieval method, performed by processing circuitry of the retrieval device comprises:

receiving an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtaining a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtaining a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [u″] in which an operation result u″=(u″ 1 , . . . , u″ N ) is concealed, the operation result u″ in which u″ j =c 1 is established when k j is a null character and u″ j =c 0 is established when k j is not a null character, c 0 and c 1 are elements of a set {c 0 , c 1 }, and c 0 ≠c 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [w′] in which an operation result w′=(w′ 1 , . . . , w′ N ) is concealed, the operation result w′ in which w′ j =b′ 1 is established when at least one of u″ j =c 1 and w j =b 1 is satisfied and w′ j =b′ 0 is established when both of u″ j =c 0 and w j =b 0 are satisfied, b′ 0 and b′ 1 are elements of a set {b′ 0 , b′ 1 }, and b′ 0 ≠b′ 1 , by secure computation using the concealed operation result [w] and the concealed operation result [u″];

obtaining a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j =d 1 is established when at least one of e i,j =a 1 and w′ j =b′ 1 is satisfied and y i,j =d 0 is established when both of e i,j =a 0 and w′ j =b′ 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [w′];

obtaining a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . =y i,Nmax =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,Nmax =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]; and

outputting the concealed match determination result [z i ] to the request device via the network,

wherein

N max =N(i) is established when N≤N(i), and N max =N is established when N>N(i), and

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.

24. A non-transitory computer-readable recording medium that stores a program for making a computer function of a retrieval method of a retrieval device among a plurality of retrieval devices of a system that further includes a request device, wherein the plurality of retrieval devices are configured to communicate with the request device over a network, wherein each of the plurality of retrieval devices performs prefix search by secure computation in which

m, n, t(i), N, and N(i) are positive integers, N>N(i), i=1, . . . , m, j=1, . . . , N, j(i)=1, . . . , N(i), j″(i)=N(i)+1, . . . , N, n≤N, and t(i)≤N(i), the retrieval device comprises a storage that stores a concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed from each of the plurality of retrieval devices, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) , wherein the concealed search target word [x i ] is a secret sharing value of the search target word x i and each of the plurality of retrieval devices stores the different concealed search target word [x i ], wherein

the retrieval method comprises:

receiving an input of a concealed search word [k] from the request device via the network, such that the concealed search word [k] is a secret sharing value of a search word k=(k 1 , . . . , k n , . . . , k N ) and each of the plurality of retrieval devices receives the different concealed search word [k] from the request device over the network, and in which the search word k=(k 1 , . . . , k n , . . . , k N ) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character;

obtaining a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N(i) ) is concealed, the operation result e i in which e i,j(i) =a 1 is established when x i,j(i) is k j(i) and e i,j(i) =a 0 is established when x i,j(i) is not k j(i) , a 0 and a 1 are elements of a set {a 0 , a 1 }, and a 0 ≠a 1 , by secure computation using the concealed search target word [x i ] and the concealed search word [k];

obtaining a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N(i) ) is concealed, the operation result w in which w j(i) =b 1 is established when k j(i) is the wildcard character and w j(i) =b 0 is established when k j(i) is not the wildcard character, b 0 and b 1 are elements of a set {b 0 , b 1 }, and b 0 ≠b 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [u″] in which an operation result u″=(u″ 1 , . . . , u″ N ) is concealed, the operation result u″ in which u″ j =c 1 is established when k j is a null character and u″ j =c 0 is established when k j is not a null character, c 0 and c 1 are elements of a set {c 0 , c 1 }, and c 0 ≠c 1 , by secure computation using the concealed search word [k];

obtaining a concealed operation result [w′] in which an operation result w′=(w′ 1 , . . . , w′ N(i) ) is concealed, the operation result w′ in which w′ j(i) =b′ 1 is established when at least one of u″ j(i) =c 1 and w j(i) =b 1 is satisfied and w′ j(i) =b′ 0 is established when both of u″ j(i) =c 0 and w j(i) =b 0 are satisfied, b′ 0 and b′ 1 are elements of a set {b′ 0 , b′ 1 }, and b′ 0 ≠b′ 1 , by secure computation using at least a part of the concealed operation result [w] and the concealed operation result [u″];

obtaining a concealed operation result [e′ i ] in which an operation result e′ i (e′ i,1 , . . . , e′ i,N(i) ) is concealed, the operation result e′ i in which e′ i,j(i) =d 1 is established when at least one of e i,j(i) =a 1 and w′ j(i) =b′ 1 is satisfied and e′ i,j(i) =d 0 is established when both of e i,j(i) =a 0 and w′ j(i) =b′ 0 are satisfied, d 0 and d 1 are elements of a set {d 0 , d 1 }, and d 0 ≠d 1 , by secure computation using the concealed operation result [e i ] and the concealed operation result [w′];

obtaining a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N )=(e′ i,1 , . . . , e′ i,N(i) , u″ N(i)+1 , . . . , u″ N ) is concealed, by secure computation using at least a part of the concealed operation result [e′ i ] and the concealed operation result [u″];

obtaining a concealed match determination result [z i ] in which a match determination result z i is concealed from the retrieval device, the match determination result z i in which z i =g 1 is established when y i,1 = . . . y i,Nmax =d 1 is satisfied and z i =g 0 is established when y i,1 = . . . =y i,Nmax =d 1 is not satisfied, g 0 and g 1 are elements of a set {g 0 , g 1 }, and g 0 ≠g 1 , by secure computation using the concealed operation result [y i ]; and

outputting the concealed match determination result [z i ] to the request device via the network,

wherein

N max =N(i) is established when N≤N(i), and N max =N is established when N>N(i), and

wherein the request device is configured to receive [z i ] transmitted from at least a predetermined number of the retrieval devices.