Retrieval device, retrieval method, program, and recording medium

Abstract

An equality determination unit obtains [e.sub.i] in which e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, by secure computation using a concealed search target word [x.sub.i] and a concealed search word [k]. A wildcard determination unit obtains [w] in which w=(w.sub.1, . . . , w.sub.N) is concealed, w in which w.sub.j=b.sub.1 is established when k.sub.j is a wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not a wildcard character, by secure computation using [k]. An OR operation unit obtains [y.sub.i] in which y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, y.sub.i in which y.sub.i,j=d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and w.sub.j=b.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when at least one of e.sub.i,j=a.sub.1 and w.sub.j=b.sub.1 is not satisfied, by secure computation using [e.sub.i] and [w].

Claims

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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtain a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.j] and the concealed search word [k]; obtain a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtain a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, the operation result y.sub.i in which y.sub.i,j=d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and w.sub.j=b.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when both of e.sub.i,j=a.sub.0 and w.sub.j=b.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w]; obtain a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]; and output the concealed match determination result [z.sub.i] to the request device via the network, wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtain a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtain a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtain a concealed operation result [μ.sub.i] in which an operation result μ.sub.i=(μ.sub.i,1, . . . , μ.sub.i,N) is concealed, the operation result μ.sub.i in which μ.sub.i,j=θ.sub.0 is established when x.sub.i,j is a null character and μ.sub.i,j=θ.sub.1 is established when x.sub.i,j is not a null character, θ.sub.0 and θ.sub.1 are elements of a set {θ.sub.0, θ.sub.1}, and θ.sub.0≠θ.sub.1, by secure computation using the concealed search target word [x.sub.i]; obtain a concealed operation result [v.sub.i] in which an operation result v.sub.i (v.sub.i,1, . . . , v.sub.i,N) is concealed, the operation result v.sub.i in which v.sub.i,j=ρ.sub.1 is established when both of w.sub.j=b.sub.j and μ.sub.i,j=θ.sub.1 are satisfied and v.sub.i,j=ρ.sub.0 is established when at least one of w.sub.j=b.sub.0 and μ.sub.i,j=θ.sub.0 is satisfied, ρ.sub.0 and ρ.sub.1 are elements of a set {ρ.sub.0, ρ.sub.1}, and ρ.sub.0≠ρ.sub.1, by secure computation using the concealed operation result [w] and the concealed operation result [μ.sub.i]; obtain a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, the operation result y.sub.i in which y.sub.i,j=d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and v.sub.i,j=ρ.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when both of e.sub.i,j=a.sub.0 and v.sub.i,j=ρ.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [v.sub.i]; obtain a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]; and output the concealed match determination result [z.sub.i] to the request device via the network, wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtain a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtain a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0 b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtain a concealed operation result [u] in which an operation result u=(u.sub.1, . . . , u.sub.N) is concealed, the operation result u in which u.sub.j=c.sub.1 is established when k.sub.j is a null character and u.sub.j=c.sub.0 is established when k.sub.j is not a null character, c.sub.0 and c.sub.1 are elements of a set {c.sub.0, c.sub.1}, and c.sub.0≠c.sub.1, by secure computation using the concealed search word [k]; obtain a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, the operation result y.sub.i in which y.sub.i,j=d.sub.1 is established when at least any one of e.sub.i,j=a.sub.1, w.sub.j=b.sub.1, and u.sub.j=c.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when all of e.sub.i,j=a.sub.0, w.sub.j=b.sub.0, and u.sub.j=c.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i], the concealed operation result [w], and the concealed operation result [u]; obtain a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]; and output the concealed match determination result [z.sub.i] to the request device via the network, wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtain a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtain a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtain a concealed operation result [u] in which an operation result u=(u.sub.1, . . . , u.sub.N) is concealed, the operation result u in which u.sub.j=c.sub.1 is established when k.sub.j is a null character and u.sub.j=c.sub.0 is established when k.sub.j is not a null character, c.sub.0 and c.sub.1 are elements of a set {c.sub.0, c.sub.1}, and c.sub.0≠c.sub.1, by secure computation using the concealed search word [k]; obtain a concealed operation result [μ.sub.i] in which an operation result μ.sub.i=(μ.sub.i,1, . . . , μ.sub.i,N) is concealed, the operation result μ.sub.i in which μ.sub.i,j=θ.sub.0 is established when x.sub.i,j is a null character and μ.sub.i,j=θ.sub.1 is established when x.sub.i,j is not a null character, θ.sub.0 and θ.sub.1 are elements of a set {θ.sub.0, θ.sub.1}, and θ.sub.0≠θ.sub.1, by secure computation using the concealed search target word [x.sub.i]; obtain a concealed operation result [v.sub.i] in which an operation result v.sub.i=(v.sub.i,1, . . . , v.sub.i,N) is concealed, the operation result v.sub.i in which v.sub.i,j=ρ.sub.1 is established when both of w.sub.j=b.sub.1 and μ.sub.i,j=θ.sub.1 are satisfied and v.sub.i,j=ρ.sub.0 is established when at least one of w.sub.j=b.sub.0 and μ.sub.i,j=θ.sub.0 is satisfied, ρ.sub.0 and ρ.sub.1 are elements of a set {ρ.sub.0, ρ.sub.1}, and ρ.sub.0≠ρ.sub.1, by secure computation using the concealed operation result [w] and the concealed operation result [μ.sub.i]; obtain a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, the operation result y.sub.i in which y.sub.i,j=d.sub.1 is established when at least any one of e.sub.i,j=a.sub.1, v.sub.i,j=ρ.sub.1, and u.sub.j=c.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when all of e.sub.i,j=a.sub.0, v.sub.i,j=ρ.sub.0, and u.sub.j=c.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i], the concealed operation result [u], and the concealed operation result [v.sub.i]; obtain a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]; and output the concealed match determination result [z.sub.i] to the request device via the network, wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtain a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N(i)) is concealed, the operation result e.sub.i in which e.sub.i,j(i)=a.sub.1 is established when x.sub.i,j(i) is k.sub.j(i) and e.sub.i,j(i)=a.sub.0 is established when x.sub.i,j(i) is not k.sub.j(i), a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtain a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N(i)) is concealed, the operation result w in which w.sub.j(i)=b.sub.1 is established when k.sub.j(i) is the wildcard character and w.sub.j(i)=b.sub.0 is established when k.sub.j(i) is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtain a concealed operation result [u′] in which operation results u′.sub.N(i)+1, . . . , u′.sub.N are concealed, the operation results u′.sub.N(i)+1, . . . , u′.sub.N in which u′.sub.j″(i)=c.sub.1 is established when k.sub.j″(i) is a null character and u′.sub.j″(i)=c.sub.0 is established when k.sub.j″(i) is not a null character, c.sub.0 and c.sub.1 are elements of a set {c.sub.0, c.sub.1}, and c.sub.0≠c.sub.1, by secure computation using at least a part of the concealed search word [k]; obtain a concealed operation result [e′.sub.i] in which an operation result e′.sub.i=(e′.sub.i,1, . . . , e′.sub.i,N(i)) is concealed, the operation result e′.sub.i in which e′.sub.i,j(i)=d.sub.1 is established when at least one of e.sub.i,j(i)=a.sub.1 and w.sub.j(i)=b.sub.1 is satisfied and e′.sub.i,j(i)=d.sub.0 is established when both of e.sub.i,j(i)=a.sub.0 and w.sub.j(i)=b.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w]; obtain a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N)=(e′.sub.i,1, . . . , e′.sub.i,N(i), u′.sub.N(i)+1, . . . , u′.sub.N) is concealed, by secure computation using the concealed operation result [u′] and the concealed operation result [e′.sub.i]; obtain a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]; and output the concealed match determination result [z.sub.i] to the request device via the network, wherein N.sub.max=N(i) is established when N≤N(i), and N.sub.max=N is established when N>N(i), and wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,1(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtain a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtain a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtain a concealed operation result [e′.sub.i] in which an operation result e′.sub.i=(e′.sub.i,1, . . . , e′.sub.i,N) is concealed, the operation result e′.sub.i in which e′.sub.i,j=d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and w.sub.j=b.sub.1 is satisfied and e′.sub.i,j=d.sub.0 is established when both of e.sub.i,j=a.sub.0 and w.sub.j=b.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w]; obtain a concealed operation result [μ′.sub.i] in which an operation result μ′.sub.i=(μ′.sub.i,N+1, . . . , μ′.sub.i,N(i)) is concealed, the operation result μ′.sub.i in which μ′.sub.i,j″(i)=d.sub.1 is established when x.sub.i,j″(i) is a null character and μ′.sub.i,j″(i)=d.sub.0 is established when x.sub.i,j″(i) is not a null character, by secure computation using at least a part of the concealed search target word [x.sub.i]; obtain a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N(i))=(e′.sub.i,1, . . . , e′.sub.i,N, μ′.sub.i,N+1, . . . , μ′.sub.i,N(i)) is concealed, by secure computation using the concealed operation result [e′.sub.i] and the concealed operation result [μ′.sub.i]; obtain a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]; and output the concealed match determination result [z.sub.i] to the request device via the network, wherein N.sub.max=N(i) is established when N≤N(i), and N.sub.max=N is established when N>N(i), and wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtain a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtains a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtain a concealed operation result [u″] in which an operation result u″=(u″.sub.1, . . . , u″.sub.N) is concealed, the operation result u″ in which u″.sub.j=c.sub.1 is established when k.sub.j is a null character and u″.sub.j=c.sub.0 is established when k.sub.j is not a null character, c.sub.0 and c.sub.1 are elements of a set {c.sub.0, c.sub.1}, and c.sub.0≠c.sub.1, by secure computation using the concealed search word [k]; obtain a concealed operation result [w′] in which an operation result w′=(w′.sub.1, . . . , w′.sub.N) is concealed, the operation result w′ in which w′.sub.j=b′.sub.1 is established when at least one of u″.sub.j=c.sub.1 and w.sub.j=b.sub.1 is satisfied and w′.sub.j=b′.sub.0 is established when both of u″.sub.j=c.sub.0 and w.sub.j=b.sub.0 are satisfied, b′.sub.0 and b′.sub.1 are elements of a set {b′.sub.0, b′.sub.1}, and b′.sub.0≠b′.sub.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.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, the operation result y.sub.i in which y.sub.i,j=d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and w′.sub.j=b′.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when both of e.sub.i,j=a.sub.0 and w′.sub.j=b′.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w′]; and obtain a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]; and output the concealed match determination result [z.sub.i] to the request device via the network, wherein N.sub.max=N(i) is established when N≤N(i), and N.sub.max=N is established when N>N(i), and wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,1(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtain a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N(i)) is concealed, the operation result e.sub.i in which e.sub.i,j(i)=a.sub.1 is established when x.sub.i,j(i) is k.sub.j(i) and e.sub.i,j(i)=a.sub.0 is established when x.sub.i,j(i) is not k.sub.j(i), a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtain a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N(i)) is concealed, the operation result w in which w.sub.j(i)=b.sub.1 is established when k.sub.j(i) is the wildcard character and w.sub.j(i)=b.sub.0 is established when k.sub.j(i) is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtain a concealed operation result [u″] in which an operation result u″=(u″.sub.1, . . . , u″.sub.N) is concealed, the operation result u″ in which u″.sub.j=c.sub.1 is established when k.sub.j is a null character and u″.sub.j=c.sub.0 is established when k.sub.j is not a null character, c.sub.0 and c.sub.1 are elements of a set {c.sub.0, c.sub.1}, and c.sub.0≠c.sub.1, by secure computation using the concealed search word [k]; obtain a concealed operation result [w′] in which an operation result w′=(w′.sub.1, . . . , w′.sub.N(i)) is concealed, the operation result w′ in which w′.sub.j(i)=b′.sub.1 is established when at least one of u″.sub.j(i)=c.sub.1 and w.sub.j(i)=b.sub.1 is satisfied and w′.sub.j(i)=b′.sub.0 is established when both of u″.sub.j(i)=c.sub.0 and w.sub.j(i)=b.sub.0 are satisfied, b′.sub.0 and b′.sub.1 are elements of a set {b′.sub.0, b′.sub.1} and b′.sub.0≠b′.sub.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′.sub.i] in which an operation result e′.sub.i=(e′.sub.i,1, . . . , e′.sub.i,N(i)) is concealed, the operation result e′.sub.i in which e′.sub.i,j(i)=d.sub.1 is established when at least one of e.sub.i,j(i)=a.sub.1 and w′.sub.j(i)=b′.sub.1 is satisfied and e′.sub.i,j(i)=d.sub.0 is established when both of e.sub.i,j(i)=a.sub.0 and w′.sub.j(i)=b′.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w′]; obtain a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N)=(e′.sub.i,1, . . . , e′.sub.i,N(i), u″.sub.N(i)+1, . . . , u″.sub.N) is concealed, by secure computation using at least a part of the concealed operation result [e′.sub.i] and the concealed operation result [u″]; obtain a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]; and output the concealed match determination result [z.sub.i] to the request device via the network, wherein N.sub.max=N(i) is established when N≤N(i), and N.sub.max=N is established when N>N(i), and wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtaining a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtaining a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, the operation result y.sub.i in which y.sub.i,j=d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and w.sub.j=b.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when both of e.sub.i,j=a.sub.0 and w.sub.j=b.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w]; and obtaining a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]]; and outputting the concealed match determination result [z.sub.i] to the request device via the network, wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtaining a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtaining a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [μ.sub.i] in which an operation result μ.sub.i=(μ.sub.i,1, . . . , μ.sub.i,N) is concealed, the operation result μ.sub.i in which μ.sub.i,j=θ.sub.0 is established when x.sub.i,j is a null character and μ.sub.i,j=θ.sub.1 is established when x.sub.i,j is not a null character, θ.sub.0 and θ.sub.1 are elements of a set {θ.sub.0, θ.sub.1}, and θ.sub.0≠θ.sub.1, by secure computation using the concealed search target word [x.sub.i]; obtaining a concealed operation result [v.sub.i] in which an operation result v.sub.i=(v.sub.i,1, . . . , v.sub.i,N) is concealed, the operation result v.sub.i in which v.sub.i,j=ρ.sub.1 is established when both of w.sub.j=b.sub.1 and μ.sub.i,j=θ.sub.1 are satisfied and v.sub.i,j=ρ.sub.0 is established when at least one of w.sub.j=b.sub.0 and μ.sub.i,j=θ.sub.0 is satisfied, ρ.sub.0 and ρ.sub.1 are elements of a set {ρ.sub.0, ρ.sub.1}, and ρ.sub.0≠ρ.sub.1, by secure computation using the concealed operation result [w] and the concealed operation result [μ.sub.i]; obtaining a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, the operation result y.sub.i in which y.sub.i,j=d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and v.sub.i,j=ρ.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when both of e.sub.i,j=a.sub.0 and v.sub.i,j=ρ.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [v.sub.i]; and obtaining a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]; and outputting the concealed match determination result [z.sub.i] to the request device via the network, wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtaining a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtaining a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [u] in which an operation result u=(u.sub.1, . . . , u.sub.N) is concealed, the operation result u in which u.sub.j=c.sub.1 is established when k.sub.j is a null character and u.sub.j=c.sub.0 is established when k.sub.j is not a null character, c.sub.0 and c.sub.1 are elements of a set {c.sub.0, c.sub.1}, and c.sub.0≠c.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, the operation result y.sub.i in which y.sub.i,j=d.sub.1 is established when at least any one of e.sub.i,j=a.sub.1, w.sub.j=b.sub.1, and u.sub.j=c.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when all of e.sub.i,j=a.sub.0, w.sub.j=b.sub.0, and u.sub.j=c.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i], the concealed operation result [w], and the concealed operation result [u]; and obtaining a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]]; and outputting the concealed match determination result [z.sub.i] to the request device via the network, wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtaining a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtaining a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [u] in which an operation result u=(u.sub.1, . . . , u.sub.N) is concealed, the operation result u in which u.sub.j=c.sub.1 is established when k.sub.j is a null character and u.sub.j=c.sub.0 is established when k.sub.j is not a null character, c.sub.0 and c.sub.1 are elements of a set {c.sub.0, c.sub.1}, and c.sub.0≠c.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [μ.sub.i] in which an operation result μ.sub.i=(μ.sub.i,1, . . . , μ.sub.i,N) is concealed, the operation result μ.sub.i in which μ.sub.i,j=θ.sub.0 is established when x.sub.i,j is a null character and μ.sub.i,j=θ.sub.1 is established when x.sub.i,j is not a null character, θ.sub.0 and θ.sub.1 are elements of a set {θ.sub.0, θ.sub.1}, and θ.sub.0≠θ.sub.1, by secure computation using the concealed search target word [x.sub.i]; obtaining a concealed operation result [v.sub.i] in which an operation result v.sub.i=(v.sub.i,1, . . . , v.sub.i,N) is concealed, the operation result v.sub.i in which v.sub.i,j=ρ.sub.1 is established when both of w.sub.j=b.sub.1 and μ.sub.i,j=θ.sub.1, are satisfied and v.sub.i,j=ρ.sub.0 is established when at least one of w.sub.j=b.sub.0 and μ.sub.i,j=θ.sub.0 is satisfied, ρ.sub.0 and ρ.sub.1 are elements of a set {ρ.sub.0, ρ.sub.1}, and ρ.sub.0≠ρ.sub.1, by secure computation using the concealed operation result [w] and the concealed operation result [μ.sub.i]; obtaining a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, the operation result y.sub.i in which y.sub.i,j=d.sub.1 is established when at least any one of e.sub.i,j=a.sub.1, v.sub.i,j=ρ.sub.1, and u.sub.j=c.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when all of e.sub.i,j=a.sub.0, v.sub.i,j=ρ.sub.0, and u.sub.j=c.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i], the concealed operation result [u], and the concealed operation result [v.sub.i]; obtaining a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]]; and outputting the concealed match determination result [z.sub.i] to the request device via the network, wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtaining a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N(i)) is concealed, the operation result e.sub.i in which e.sub.i,j(i)=a.sub.1 is established when x.sub.i,j(i) is k.sub.j(i) and e.sub.i,j(i)=a.sub.0 is established when x.sub.i,j(i) is not k.sub.j(i), a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtaining a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N(i)) is concealed, the operation result w in which w.sub.j(i)=b.sub.1 is established when k.sub.j(i) is the wildcard character and w.sub.j(i)=b.sub.0 is established when k.sub.j(i) is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [u′] in which operation results u′.sub.N(i)+1, . . . , u′.sub.N are concealed, the operation results u′.sub.N(i)+1, . . . , u′.sub.N in which u′.sub.j″(i)=c.sub.1 is established when k.sub.j″(i) is a null character and u′.sub.j″(i)=c.sub.0 is established when k.sub.j″(i) is not a null character, c.sub.0 and c.sub.1 are elements of a set {c.sub.0, c.sub.1}, and c.sub.0≠c.sub.1, by secure computation using at least a part of the concealed search word [k]; obtaining a concealed operation result [e′.sub.i] in which an operation result e′.sub.i=(e′.sub.i,1, . . . , e′.sub.i,N(i)) is concealed, the operation result e′.sub.i in which e′.sub.i,j(i)=d.sub.1 is established when at least one of e.sub.i,j(i)=a.sub.1 and w.sub.j(i)=b.sub.1 is satisfied and e′.sub.i,j(i)=d.sub.0 is established when both of e.sub.i,j(i)=a.sub.0 and w.sub.j(i)=b.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w]; obtaining a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N)=(e′.sub.i,1, . . . , e′.sub.i,N(i), u′.sub.N(i)+1, . . . , u′.sub.N) is concealed, by secure computation using the concealed operation result [u′] and the concealed operation result [e′.sub.i]; obtaining a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]; and outputting the concealed match determination result [z.sub.i] to the request device via the network, wherein N.sub.max=N(i) is established when N≤N(i), and N.sub.max=N is established when N>N(i), and wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtaining a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtaining a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [e′.sub.i] in which an operation result e′.sub.i=(e′.sub.i,1, . . . , e′.sub.i,N) is concealed, the operation result e′.sub.i in which e′.sub.i,j=d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and w.sub.j=b.sub.1 is satisfied and e′.sub.i,j=d.sub.0 is established when both of e.sub.i,j=a.sub.0 and w.sub.j=b.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w]; obtaining a concealed operation result [μ′.sub.i] in which an operation result μ′.sub.i=(μ′.sub.i,N+1, . . . , μ′.sub.i,N(i)) is concealed, the operation result μ′.sub.i in which μ′.sub.i,j(i)=d.sub.1 is established when x.sub.i,j″(i) is a null character and μ′.sub.i,j″(i)=d.sub.0 is established when x.sub.i,j″(i) is not a null character, by secure computation using at least a part of the concealed search target word [x.sub.i]; obtaining a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N(i))=(e′.sub.i,1, . . . , e′.sub.i,N, μ′.sub.i,N+1, . . . , μ′.sub.i,N(i)) is concealed, by secure computation using the concealed operation result [e′.sub.i] and the concealed operation result [μ′.sub.i]; obtaining a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]; and outputting the concealed match determination result [z.sub.i] to the request device via the network, wherein N.sub.max=N(i) is established when N≤N(i), and N.sub.max=N is established when N>N(i), and wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtaining a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtaining a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [u″] in which an operation result u″=(u″.sub.1, . . . , u″.sub.N) is concealed, the operation result u″ in which u″.sub.j=c.sub.1 is established when k.sub.j is a null character and u″.sub.j=c.sub.0 is established when k.sub.j is not a null character, c.sub.0 and c.sub.1 are elements of a set {c.sub.0, c.sub.1}, and c.sub.0≠c.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [w′] in which an operation result w′=(w′.sub.1, . . . , w′.sub.N) is concealed, the operation result w′ in which w′.sub.j=b′.sub.1 is established when at least one of u″.sub.j=c.sub.1 and w.sub.j=b.sub.1 is satisfied and w′.sub.j=b′.sub.0 is established when both of u″.sub.j=c.sub.0 and w.sub.j=b.sub.0 are satisfied, b′.sub.0 and b′.sub.1 are elements of a set {b′.sub.0, b′.sub.1}, and b′.sub.0≠b′.sub.1, by secure computation using the concealed operation result [w] and the concealed operation result [u″]; obtaining a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, the operation result y.sub.i in which y.sub.i,j=d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and w′.sub.j=b′.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when both of e.sub.i,j=a.sub.0 and w′.sub.j=b.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w′]; obtaining a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]; and outputting the concealed match determination result [z.sub.i] to the request device via the network, wherein N.sub.max=N(i) is established when N≤N(i), and N.sub.max=N is established when N>N(i), and wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtaining a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N(i)) is concealed, the operation result e.sub.i in which e.sub.i,j(i)=a.sub.1 is established when x.sub.i,j(i) is k.sub.j(i) and e.sub.i,j(i)=a.sub.0 is established when x.sub.i,j(i) is not k.sub.j(i), a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtaining a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N(i)) is concealed, the operation result w in which w.sub.j(i)=b.sub.1 is established when k.sub.j(i) is the wildcard character and w.sub.j(i)=b.sub.0 is established when k.sub.j(i) is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [u″] in which an operation result u″=(u″.sub.1, . . . , u″.sub.N) is concealed, the operation result u″ in which u″.sub.j=c.sub.1 is established when k.sub.j is a null character and u″.sub.j=c.sub.0 is established when k.sub.j is not a null character, c.sub.0 and c.sub.1 are elements of a set {c.sub.0, c.sub.1}, and c.sub.0≠c.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [w′] in which an operation result w′=(w′.sub.1, . . . , w′.sub.N(i)) is concealed, the operation result w′ in which w′.sub.j(i)=b′.sub.1 is established when at least one of u″.sub.j(i)=c.sub.1 and w.sub.j(i)=b.sub.1 is satisfied and w′.sub.j(i)=b′.sub.0 is established when both of u″.sub.j(i)=c.sub.0 and w.sub.j(i)=b.sub.0 are satisfied, b′.sub.0 and b′.sub.1 are elements of a set {b′.sub.0, b′.sub.1}, and b′.sub.0≠b′.sub.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′.sub.i] in which an operation result e′.sub.i=(e′.sub.i,1, . . . , e′.sub.i,N(i)) is concealed, the operation result e′.sub.i in which e′.sub.i,j(i)=d.sub.1 is established when at least one of e.sub.i,j(i)=a.sub.1 and w′.sub.j(i)=b′.sub.1 is satisfied and e′.sub.i,j(i)=d.sub.0 is established when both of e.sub.i,j(i)=a.sub.0 and w′.sub.j(i)=b′.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w′]; obtaining a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N)=(e′.sub.i,1, . . . , e′.sub.i,N(i), u″.sub.N(i)+1, . . . , u″.sub.N) is concealed, by secure computation using at least a part of the concealed operation result [e′.sub.i] and the concealed operation result [u″]: obtaining a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]; and outputting the concealed match determination result [z.sub.i] to the request device via the network, wherein N.sub.max=N(i) is established when N≤N(i), and N.sub.max=N is established when N>N(i), and wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtaining a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtaining a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, the operation result y.sub.i in which y.sub.i,j=d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and w.sub.j=b.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when both of e.sub.i,j=a.sub.0 and w.sub.j=b.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w]; obtaining a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . y.sub.i,N=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]]; and outputting the concealed match determination result [z.sub.i] to the request device via the network, wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtaining a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtaining a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [μ.sub.i] in which an operation result μ.sub.i=(μ.sub.i,1, . . . , μ.sub.i,N) is concealed, the operation result μ.sub.i in which μ.sub.i,j=θ.sub.0 is established when x.sub.i,j is a null character and μ.sub.i,j=θ.sub.1 is established when x.sub.i,j is not a null character, θ.sub.0 and θ.sub.1 are elements of a set {θ.sub.0, θ.sub.1}, and θ.sub.0≠θ.sub.1, by secure computation using the concealed search target word [x.sub.i]; obtaining a concealed operation result [v.sub.i] in which an operation result v.sub.i=(v.sub.i,1, . . . , v.sub.i,N) is concealed, the operation result v.sub.i in which v.sub.i,j=ρ.sub.1 is established when both of w.sub.j=b.sub.1 and μ.sub.i,j=θ.sub.1 are satisfied and v.sub.i,jρ.sub.0 is established when at least one of w.sub.j=b.sub.0 and μ.sub.i,j=θ.sub.0 is satisfied, ρ.sub.0 and ρ.sub.1 are elements of a set {ρ.sub.0, ρ.sub.1}, and ρ.sub.0≠ρ.sub.1, by secure computation using the concealed operation result [w] and the concealed operation result [μ.sub.i]; obtaining a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, the operation result y.sub.i in which y.sub.i,j d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and v.sub.i,j=ρ.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when both of e.sub.i,j=a.sub.0 and v.sub.i,j=ρ.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [v.sub.i]; obtaining a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]]; and outputting the concealed match determination result [z.sub.i] to the request device via the network, wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtaining a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtaining a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [u] in which an operation result u=(u.sub.1, . . . , u.sub.N) is concealed, the operation result u in which u.sub.j=c.sub.1 is established when k.sub.j is a null character and u.sub.j=c.sub.0 is established when k.sub.j is not a null character, c.sub.0 and c.sub.1 are elements of a set {c.sub.0, c.sub.1}, and c.sub.0≠c.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, the operation result y.sub.i in which y.sub.i,j=d.sub.1 is established when at least any one of e.sub.i,j=a.sub.1, w.sub.j=b.sub.1, and u.sub.j=c.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when all of e.sub.i,j=a.sub.0, w.sub.j=b.sub.0, and u.sub.j=c.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i], the concealed operation result [w], and the concealed operation result [u]; and obtaining a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . y.sub.i,N=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]]; and outputting the concealed match determination result [z.sub.i] to the request device via the network, wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtaining a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtaining a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [u] in which an operation result u=(u.sub.1, . . . , u.sub.N) is concealed, the operation result u in which u.sub.j=c.sub.1 is established when k.sub.j is a null character and u.sub.j=c.sub.0 is established when k.sub.j is not a null character, c.sub.0 and c.sub.1 are elements of a set {c.sub.0, c.sub.1}, and c.sub.0≠c.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [μ.sub.i] in which an operation result μ.sub.i=(μ.sub.i,1, . . . , μ.sub.i,N) is concealed, the operation result μ.sub.i in which μ.sub.i,j=θ.sub.0 is established when x.sub.i,j is a null character and μ.sub.i,j=θ.sub.1 is established when x.sub.i,j is not a null character, θ.sub.0 and θ.sub.1 are elements of a set {θ.sub.0, θ.sub.1}, and θ.sub.0≠θ.sub.1, by secure computation using the concealed search target word [x.sub.i]; obtaining a concealed operation result [v.sub.i] in which an operation result v.sub.i=(v.sub.i,1, . . . , v.sub.i,N) is concealed, the operation result v.sub.i in which v.sub.i,j=ρ.sub.1 is established when both of w.sub.j=b.sub.1 and μ.sub.i,j=θ.sub.1 are satisfied and v.sub.i,j=ρ.sub.0 is established when at least one of w.sub.j=b.sub.0 and μ.sub.i,j=θ.sub.0 is satisfied, ρ.sub.0 and ρ.sub.1 are elements of a set {ρ.sub.0, ρ.sub.1}, and ρ.sub.0≠ρ.sub.1, by secure computation using the concealed operation result [w] and the concealed operation result [μ.sub.i]; obtaining a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, the operation result y.sub.i in which y.sub.i,j=d.sub.1 is established when at least any one of e.sub.i,j=a.sub.1, v.sub.i,j=ρ.sub.1, and u.sub.j=c.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when all of e.sub.i,j=a.sub.0, v.sub.i,j=ρ.sub.0, and u.sub.j=c.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i], the concealed operation result [u], and the concealed operation result [v.sub.i]; obtaining a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . y.sub.i,N=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]]; and outputting the concealed match determination result [z.sub.i] to the request device via the network, wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtaining a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N(i)) is concealed, the operation result e.sub.i in which e.sub.i,j(i)=a.sub.1 is established when x.sub.i,j(i) is k.sub.j(i) and e.sub.i,j(i)=a.sub.0 is established when x.sub.i,j(i) is not k.sub.j(i), a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtaining a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N(i)) is concealed, the operation result w in which w.sub.j(i)=b.sub.1 is established when k.sub.j(i) is the wildcard character and w.sub.j(i)=b.sub.0 is established when k.sub.j(i) is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [u′] in which operation results u′.sub.N(i)+1, . . . , u′.sub.N are concealed, the operation results u′.sub.N(i)+1, . . . , u′.sub.N in which u′.sub.j″(i)=c.sub.1 is established when k.sub.j″(i) is a null character and u′.sub.j″(i)=c.sub.0 is established when k.sub.j″(i) is not a null character, c.sub.0 and c.sub.1 are elements of a set {c.sub.0, c.sub.1}, and c.sub.0≠c.sub.1, by secure computation using at least a part of the concealed search word [k]; obtaining a concealed operation result [e′.sub.i] in which an operation result e′.sub.i(e′.sub.i,1, . . . , e′.sub.i,N(i)) is concealed, the operation result e′.sub.i in which e′.sub.i,j(i)=d.sub.1 is established when at least one of e.sub.i,j(i)=a.sub.1 and w.sub.j(i)=b.sub.1 is satisfied and e′.sub.i,j(i)=d.sub.0 is established when both of e.sub.i,j(i)=a.sub.0 and w.sub.j(i)=b.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w]; obtaining a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N)=(e′.sub.i,1, . . . , e′.sub.i,N(i), u′.sub.N(i)+1, . . . , u′.sub.N) is concealed, by secure computation using the concealed operation result [u′] and the concealed operation result [e′.sub.i]; obtaining a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]; and outputting the concealed match determination result [z.sub.i] to the request device via the network, wherein N.sub.max=N(i) is established when N≤N(i), and N.sub.max=N is established when N>N(i), and wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i an each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtaining a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtaining a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [e′.sub.i] in which an operation result e′.sub.i=(e′.sub.i,1, . . . , e′.sub.i,N) is concealed, the operation result e′.sub.i in which e′.sub.i,j=d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and w.sub.j=b.sub.1 is satisfied and e′.sub.i,j=d.sub.0 is established when both of e.sub.i,j=a.sub.0 and w.sub.j=b.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w]; obtaining a concealed operation result [μ′.sub.i] in which an operation result μ′.sub.i=(μ′.sub.i,N+1, . . . , μ′.sub.i,N(i)) is concealed, the operation result μ′.sub.i in which μ′.sub.i,j″(i)=d.sub.1 is established when x.sub.i,j″(i) is a null character and μ′.sub.i,j″(i)=d.sub.0 is established when x.sub.i,j″(i) is not a null character, by secure computation using at least a part of the concealed search target word [x.sub.i]; obtaining a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N(i))=(e′.sub.i,1, . . . , e′.sub.i,N, μ′.sub.i,N+1, . . . , μ′.sub.i,N(i)) is concealed, by secure computation using the concealed operation result [e′.sub.i] and the concealed operation result [μ′.sub.i]; obtaining a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]; and outputting the concealed match determination result [z.sub.i] to the request device via the network, wherein N.sub.max=N(i) is established when N≤N(i), and N.sub.max=N is established when N>N(i), and wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtaining a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtaining a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is the wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [u″] in which an operation result u″=(u″.sub.1, . . . , u″.sub.N) is concealed, the operation result u″ in which u″.sub.j=c.sub.1 is established when k.sub.j is a null character and u″.sub.j=c.sub.0 is established when k.sub.j is not a null character, c.sub.0 and c.sub.1 are elements of a set {c.sub.0, c.sub.1}, and c.sub.0≠c.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [w′] in which an operation result w′=(w′.sub.1, . . . , w′.sub.N) is concealed, the operation result w′ in which w′.sub.j=b′.sub.1 is established when at least one of u″.sub.j=c.sub.1 and w.sub.j=b.sub.1 is satisfied and w′.sub.j=b′.sub.0 is established when both of u″.sub.j=c.sub.0 and w.sub.j=b.sub.0 are satisfied, b′.sub.0 and b′.sub.1 are elements of a set {b′.sub.0, b′.sub.1}, and b′.sub.0≠b′.sub.1, by secure computation using the concealed operation result [w] and the concealed operation result [u″]; obtaining a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, the operation result y.sub.i in which y.sub.i,j=d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and w′.sub.j=b′.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when both of e.sub.i,j=a.sub.0 and w′.sub.j=b′.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w′]; obtaining a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]; and outputting the concealed match determination result [z.sub.i] to the request device via the network, wherein N.sub.max=N(i) is established when N≤N(i), and N.sub.max=N is established when N>N(i), and wherein the request device is configured to receive [z.sub.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.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) is concealed from each of the plurality of retrieval devices, the search target word x.sub.i including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), wherein the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i and each of the plurality of retrieval devices stores the different concealed search target word [x.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.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.sub.1, . . . , k.sub.n, . . . , k.sub.N) is concealed from each of the plurality of retrieval devices, the search word k including n pieces of characters k.sub.1, . . . , k.sub.n including a wildcard character; obtaining a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N(i)) is concealed, the operation result e.sub.i in which e.sub.i,j(i)=a.sub.1 is established when x.sub.i,j(i) is k.sub.j(i) and e.sub.i,j(i)=a.sub.0 is established when x.sub.i,j(i) is not k.sub.j(i), a.sub.0 and a.sub.1 are elements of a set {a.sub.0, a.sub.1}, and a.sub.0≠a.sub.1, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]; obtaining a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N(i)) is concealed, the operation result w in which w.sub.j(i)=b.sub.1 is established when k.sub.j(i) is the wildcard character and w.sub.j(i)=b.sub.0 is established when k.sub.j(i) is not the wildcard character, b.sub.0 and b.sub.1 are elements of a set {b.sub.0, b.sub.1}, and b.sub.0≠b.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [u″] in which an operation result u″=(u″.sub.1, . . . , u″.sub.N) is concealed, the operation result u″ in which u″.sub.j=c.sub.1 is established when k.sub.j is a null character and u″.sub.j=c.sub.0 is established when k.sub.j is not a null character, c.sub.0 and c.sub.1 are elements of a set {c.sub.0, c.sub.1}, and c.sub.0≠c.sub.1, by secure computation using the concealed search word [k]; obtaining a concealed operation result [w′] in which an operation result w′=(w′.sub.1, . . . , w′.sub.N(i)) is concealed, the operation result w′ in which w′.sub.j(i)=b′.sub.1 is established when at least one of u″.sub.j(i)=c.sub.1 and w.sub.j(i)=b.sub.1 is satisfied and w′.sub.j(i)=b′.sub.0 is established when both of u″.sub.j(i)=c.sub.0 and w.sub.j(i)=b.sub.0 are satisfied, b′.sub.0 and b′.sub.1 are elements of a set {b′.sub.0, b′.sub.1}, and b′.sub.0≠b′.sub.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′.sub.i] in which an operation result e′.sub.i(e′.sub.i,1, . . . , e′.sub.i,N(i)) is concealed, the operation result e′.sub.i in which e′.sub.i,j(i)=d.sub.1 is established when at least one of e.sub.i,j(i)=a.sub.1 and w′.sub.j(i)=b′.sub.1 is satisfied and e′.sub.i,j(i)=d.sub.0 is established when both of e.sub.i,j(i)=a.sub.0 and w′.sub.j(i)=b′.sub.0 are satisfied, d.sub.0 and d.sub.1 are elements of a set {d.sub.0, d.sub.1}, and d.sub.0≠d.sub.1, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w′]; obtaining a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N)=(e′.sub.i,1, . . . , e′.sub.i,N(i), u″.sub.N(i)+1, . . . , u″.sub.N) is concealed, by secure computation using at least a part of the concealed operation result [e′.sub.i] and the concealed operation result [u″]; obtaining a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed from the retrieval device, the match determination result z.sub.i in which z.sub.i=g.sub.1 is established when y.sub.i,1= . . . y.sub.i,Nmax=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is not satisfied, g.sub.0 and g.sub.1 are elements of a set {g.sub.0, g.sub.1}, and g.sub.0≠g.sub.1, by secure computation using the concealed operation result [y.sub.i]; and outputting the concealed match determination result [z.sub.i] to the request device via the network, wherein N.sub.max=N(i) is established when N≤N(i), and N.sub.max=N is established when N>N(i), and wherein the request device is configured to receive [z.sub.i] transmitted from at least a predetermined number of the retrieval devices.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a block diagram illustrating a retrieval system according to embodiments.

(2) FIG. 2 is a block diagram illustrating a retrieval device according to the embodiments.

(3) FIG. 3 is a flow diagram for explaining a retrieval method according to a first embodiment.

(4) FIG. 4 is a conceptual diagram for explaining the retrieval method according to the first embodiment.

(5) FIG. 5 is a conceptual diagram for explaining the retrieval method according to the first embodiment.

(6) FIG. 6 is a conceptual diagram for explaining the retrieval method according to the first embodiment.

(7) FIG. 7 is a conceptual diagram for explaining the retrieval method according to the first embodiment.

(8) FIG. 8 is a conceptual diagram for explaining the retrieval method according to the first embodiment.

(9) FIG. 9 is a conceptual diagram for explaining the retrieval method according to the first embodiment.

(10) FIG. 10 is a flow diagram for explaining a retrieval method according to a second embodiment.

(11) FIG. 11 is a conceptual diagram for explaining the retrieval method according to the second embodiment.

(12) FIG. 12 is a conceptual diagram for explaining the retrieval method according to the second embodiment.

(13) FIG. 13 is a conceptual diagram for explaining the retrieval method according to the second embodiment.

(14) FIG. 14 is a flow diagram for explaining a retrieval method according to a third embodiment.

(15) FIG. 15 is a conceptual diagram for explaining the retrieval method according to the third embodiment.

(16) FIG. 16 is a conceptual diagram for explaining the retrieval method according to the third embodiment.

(17) FIG. 17 is a flow diagram for explaining a retrieval method according to a fourth embodiment.

(18) FIG. 18 is a conceptual diagram for explaining the retrieval method according to the fourth embodiment.

(19) FIG. 19 is a conceptual diagram for explaining the retrieval method according to the fourth embodiment.

(20) FIG. 20 is a flow diagram for explaining a retrieval method according to a fifth embodiment.

(21) FIG. 21 is a conceptual diagram for explaining the retrieval method according to the fifth embodiment.

(22) FIG. 22 is a conceptual diagram for explaining the retrieval method according to the fifth embodiment.

(23) FIG. 23 is a conceptual diagram for explaining the retrieval method according to the fifth embodiment.

(24) FIG. 24 is a conceptual diagram for explaining the retrieval method according to the fifth embodiment.

(25) FIG. 25 is a flow diagram for explaining a retrieval method according to a sixth embodiment.

(26) FIG. 26 is a conceptual diagram for explaining the retrieval method according to the sixth embodiment.

(27) FIG. 27 is a conceptual diagram for explaining the retrieval method according to the sixth embodiment.

(28) FIG. 28 is a conceptual diagram for explaining the retrieval method according to the sixth embodiment.

DETAILED DESCRIPTION OF THE EMBODIMENTS

(29) Embodiments according to the present invention are described below with reference to the accompanying drawings.

First Embodiment

(30) A first embodiment is described. In the present embodiment, exact match search for concealed database is performed while concealing a search word including a wildcard character.

(31) <Configuration>

(32) As illustrated in FIG. 1, a retrieval system 1 according to the present embodiment includes a request device 11 which requests retrieval and retrieval devices 12-h which perform retrieval, and the retrieval system 1 performs retrieval processing based on secure computation. Here, h=1, . . . , H and H is an integer which is 1 or greater. H≥2 is established when secure computation based on a secret sharing scheme is performed and H=1 is established when secure computation based on a homomorphic cryptosystem is performed.

(33) As illustrated in FIG. 2, the retrieval device 12-h of the present embodiment includes a control unit 120-h, an equality determination unit 121-h, a wildcard determination unit 122-h, an OR operation unit 123-h, an AND operation unit 127-h, a storage 128-h, an input unit 1291-h, and an output unit 1292-h. The retrieval device 12-h executes each processing under the control of the control unit 120-h. Further, data obtained in respective units are stored in the storage 128-h one by one and read out as needed to be used for other processing.

(34) <Preprocessing>

(35) The storage 128-h stores concealed database [x.sub.1], . . . , [x.sub.m] including a concealed search target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N) (see DB in FIG. 4 and FIG. 6, for example) including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i) is concealed. Here, m, t(i), and N are positive integers, i=1, . . . , m, j=1, . . . , N, and t(i)≤N. t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i) included in the search target word x.sub.i are normal characters which are retrieval targets. On the other hand, the remaining N−t(i) pieces of characters x.sub.i,t(i)+1, . . . , x.sub.i,N included in the search target word x.sub.i are special characters (null characters) representing null values. Null characters are predetermined (“0”, for example) and are not used as normal characters. When t(i)=N, the search target word x.sub.i does not include any null characters. Each character is expressed as an element of a finite field, for example. When secure computation based on the secret sharing scheme is performed, the concealed search target word [x.sub.i] is a secret sharing value of the search target word x.sub.i. When secure computation based on the homomorphic cryptosystem is performed, the concealed search target word [x.sub.i] is a cipher text of the search target word x.sub.i. A set of concealed values [x.sub.i,1], . . . , [x.sub.i,t(i)], . . . , [x.sub.i,N] obtained by separately concealing respective characters x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N may be defined as the concealed search target word [x.sub.i] or N pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N may be collectively concealed to be defined as the concealed search target word [x.sub.i]. Further, each concealed search target word [x.sub.i] may be associated with a concealed value of content information representing a content or a position of the content on a network.

(36) <Retrieval Processing>

(37) Retrieval processing of the present embodiment is described with reference to FIG. 3.

(38) The request device 11 conceals a search word k=(k.sub.1, . . . , k.sub.n, . . . , k.sub.N) (see FIG. 4 and FIG. 6, for example) including n pieces of characters k.sub.1, . . . , k.sub.n so as to obtain a concealed search word [k]. Here, n is a positive integer and n≤N. The characters k.sub.1, . . . , k.sub.n may include one or more wildcard characters. Characters other than a wildcard character among the characters k.sub.1, . . . , k.sub.n are normal characters. Wildcard characters are predetermined (“*”, for example) and are not used as normal characters. Further, one wildcard character corresponds to one normal character or one null character (the same goes for each of the following embodiments). When the above-described search target word x.sub.i (here, i=1, . . . , m) does not include any null characters, any character among the characters k.sub.1, . . . , k.sub.n may be a wildcard character. On the other hand, it is assumed that, when the search target word x.sub.i includes null characters x.sub.i,t(i)+1, . . . , x.sub.i,N, k.sub.t(i)+1, . . . , k.sub.N do not include any wildcard characters in the present embodiment. N−n pieces of characters k.sub.n+1, . . . , k.sub.N included in the search word k are null characters. However, when n=N, the search word k does not include any null characters (see FIG. 4, for example). A null character included in the search word k is the same as the above-described null character included in the search target word x.sub.i. When secure computation based on the secret sharing scheme is performed in the retrieval device 12-h, the concealed search word [k] is a secret sharing value of the search word k. On the other hand, when secure computation based on the homomorphic cryptosystem is performed in the retrieval device 12-h, the concealed search word [k] is a cipher text of the search word k. A set of concealed values [k.sub.1], . . . , [k.sub.n], . . . , [k.sub.N] obtained by separately concealing respective characters k.sub.1, . . . , k.sub.n, . . . , k.sub.N may be defined as the concealed search word [k] or N pieces of characters k.sub.1, . . . , k.sub.n, . . . , k.sub.N may be collectively concealed to be defined as the concealed search word [k].

(39) The request device 11 outputs the concealed search word [k]. The outputted concealed search word [k] is transmitted to the retrieval device 12-h via a network or the like. The concealed search word [k] is inputted into the input unit 1291-h of the retrieval device 12-h to be stored in the storage 128-h (step S1291-h). Subsequently, the following processing is executed for each i=1, . . . , m.

(40) First, the equality determination unit 121-h obtains a concealed operation result [e.sub.i], in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k], which are read from the storage 128-h, and outputs the concealed operation result [e.sub.i]. Here, e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j (when x.sub.i,j=k.sub.j) and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j (when x.sub.i,j≠k.sub.j). e.sub.i,j∈{a.sub.0, a.sub.1}, in which a.sub.0=0 and a.sub.1=1, for example. Since a wildcard character is different from a normal character, e.sub.i,j=a.sub.0 is always established when k.sub.j is a wildcard character. In a similar manner, since a null character is different from a normal character, e.sub.i,j=a.sub.0 is always established when k.sub.j is a null character and x.sub.i,j is a normal character and when k.sub.j is a normal character and x.sub.i,j is a null character. Further, when both of k.sub.j and x.sub.i,j are null characters, e.sub.i,j=a.sub.1 is established. For example, the equality determination unit 121-h performs equality determination (match determination) between [k.sub.j] and [x.sub.i,j] for j=1, . . . , N by secure computation, obtains [e.sub.i,j] in which e.sub.i,j is concealed, and obtains a set of [e.sub.i,1], . . . , [e.sub.i,N] as the concealed operation result [e.sub.i]. Alternatively, the equality determination unit 121-h may obtain the concealed operation result [e.sub.i] in which e.sub.i,1, . . . , e.sub.i,N are collectively concealed, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]. The concealed operation result [e.sub.i] is stored in the storage 128-h (step S121-h).

(41) The wildcard determination unit 122-h obtains a concealed operation result [w], in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, by secure computation using the concealed search word [k] read from the storage 128-h and outputs the concealed operation result [w]. Here, w.sub.j=b.sub.1 is established when k.sub.j is a wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not a wildcard character. w.sub.j∈{b.sub.0, b.sub.1}, in which b.sub.0=0 and b.sub.1=1, for example. The wildcard determination unit 122-h obtains the concealed operation result [w] by secure computation by using the concealed search word [k] and a concealed wildcard character which is obtained by concealing a wildcard character, for instance. As an example, the wildcard determination unit 122-h performs equality determination between [k.sub.j] and the concealed wildcard character for j=1, . . . , N by secure computation, obtains [w.sub.j] in which w.sub.j is concealed, and obtains a set of [w.sub.1], . . . , [w.sub.N] as the concealed operation result [w]. Alternatively, the wildcard determination unit 122-h may obtain the concealed operation result [w] in which w.sub.1, . . . , w.sub.N are collectively concealed, by secure computation using the concealed search word [k] and the concealed wildcard character. The concealed operation result [w] is stored in the storage 128-h (step S122-h).

(42) The OR operation unit 123-h obtains a concealed operation result [y.sub.i], in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w], which are read from the storage 128-h, and outputs the concealed operation result [y.sub.i]. Here, y.sub.i,j=d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and w.sub.j=b.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when both of e.sub.i,j=a.sub.0 and w.sub.j=b.sub.0 are satisfied. y.sub.i,j∈{d.sub.0, d.sub.1}, in which d.sub.0=0 and d.sub.1=1, for example. When a.sub.0=0, a.sub.1=1, b.sub.0=0, b.sub.1=1, d.sub.0=0, and d.sub.1=1, y.sub.i,j=e.sub.i,j∨w.sub.j is established, for example. Here, “∨” denotes a logical sum (OR). For example, the OR operation unit 123-h performs an OR operation between [e.sub.i,j] and [w.sub.j] for j=1, . . . , N by secure computation, obtains [y.sub.i,j] in which y.sub.i,j=e.sub.i,j∨w.sub.j is concealed, and obtains a set of [y.sub.i,1], . . . , [y.sub.i,N] as the concealed operation result [y.sub.i]. Alternatively, the OR operation unit 123-h may obtain the concealed operation result [y.sub.i] in which y.sub.i,1 . . . , y.sub.i,N are collectively concealed, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w]. The concealed operation result [y.sub.i] is stored in the storage 128-h (step S123-h).

(43) The AND operation unit 127-h obtains a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed, by secure computation using the concealed operation result [y.sub.i] read from the storage 128-h and outputs the concealed match determination result [z.sub.i]. Here, z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,N=d.sub.1 is not satisfied. z.sub.i∈{g.sub.0, g.sub.1}, in which g.sub.0=0 and g.sub.1=1, for example. When d.sub.0=0, d.sub.1=1, g.sub.0=0, and g.sub.1=1, z.sub.i=y.sub.i,1∧ . . . ∧y.sub.i,N is established, for example. Here, “∧” denotes a logical product (AND). z.sub.i=g.sub.1 represents that the search target word x.sub.i is matched with the search word k and z.sub.i=g.sub.0 represents that the search target word x.sub.i is not matched with the search word k. The concealed match determination result [z.sub.i] is stored in the storage 128-h (step S127-h).

(44) The output unit 1292-h outputs the concealed match determination result [z.sub.i] for each i=1, . . . , m (step S1292-h). The concealed match determination result [z.sub.i] is transmitted to the request device 11 via a network or the like. The request device 11 reconstructs the concealed match determination result [z.sub.i] for each i=1, . . . , m so as to obtain z.sub.i. For example, when secure computation based on the secret sharing scheme is performed, the request device 11 reconstructs z.sub.i based on [z.sub.i] transmitted from a predetermined number or more of the retrieval devices 12-h. On the other hand, when secure computation based on the homomorphic cryptosystem is performed, the transmitted [z.sub.i] is decrypted to obtain z.sub.i. Thus, retrieval results for respective i are obtained. After that, processing using these retrieval results (request for concealed values of content information corresponding to the matched concealed search target word [x.sub.i], for example) is executed.

Specific Example

(45) A specific example for the case where a.sub.0=0, a.sub.1=1, b.sub.0=0, b.sub.1=1, d.sub.0=0, d.sub.1=1, g.sub.0=0, and g.sub.1=1 is described below.

(46) As illustrated in FIG. 4, e.sub.1=(1, . . . , 1, 0, 1, . . . , 1), w=(0, . . . , 0, 1, 0, . . . , 0), and y.sub.1=(1, . . . , 1, 1, 1, . . . , 1) when N=n=t(i), k.sub.r is a wildcard character “*”, 1≤r≤n, and x.sub.1,j=k.sub.j is satisfied for j=1, . . . , n other than r. Therefore, z.sub.1=1 is established.

(47) As illustrated in FIG. 5, d.sub.2=(0, 1, 1, 0, 1, . . . , 1), w=(0, 0, . . . , 0, 1, 0, . . . , 0), and y.sub.2=(0, 1, . . . , 1, 1, 1, . . . , 1) when N=n=t(i) and x.sub.2,j=k.sub.j is satisfied only for j=2, . . . , n other than 1 and r. Therefore, z.sub.2=0 is established.

(48) FIG. 6 to FIG. 9 illustrate examples of n<N and t(i)<N. As illustrated in FIG. 6, k.sub.n+1, . . . , k.sub.N and x.sub.i,t(i)+1, . . . , x.sub.i,N are null characters.

(49) As illustrated in FIG. 7, e.sub.1=(1, 1, . . . , 0, . . . , 1, . . . , 1), w=(0, 0, . . . , 1, . . . , 0, . . . , 0), and y.sub.1=(1, 1, . . . , 1, . . . , 1, . . . , 1) when t(1)=n, k.sub.r is a wildcard character “*”, 1≤r≤n, and x.sub.1,j=k.sub.j is satisfied for j=1, . . . , n other than r. Therefore, z.sub.1=1 is established.

(50) As illustrated in FIG. 8, e.sub.2=(1, 1, . . . , 0, . . . , 1, 0, 1, . . . , 1), w=(0, 0, . . . , 1, . . . , 0, 0, 0, . . . , 0) and y.sub.2=(1, 1, . . . , 1, . . . , 1, 0, 1, . . . , 1) when t(2)=n+1, k.sub.r is a wildcard character “*”, 1≤r≤n, and x.sub.2,j=k.sub.j is satisfied for j=1, . . . , n other than r. Therefore, z.sub.2=0 is established.

(51) As illustrated in FIG. 9, e.sub.3=(1, 1, . . . , 0, . . . , 0, 1, 1, . . . , 1), w=(0, 0, . . . , 1, . . . , 0, 0, 0, . . . , 0), and y.sub.3=(1, 1, . . . , 1, . . . , 0, 1, 1, . . . , 1) when t(3)=n−1, k.sub.r is a wildcard character “*”, 1≤r≤n−1, and x.sub.3,j=k.sub.j is satisfied only for j=1, . . . , n−1 other than r. Therefore, z.sub.3=0 is established.

Characteristics of Present Embodiment

(52) As described above, exact match search of concealed database can be performed while concealing a search word including a wildcard character, in the present embodiment. Further, match retrieval of concealed database can be performed with less communication volume (communication volume of O(N), for example) than that of related art.

Second Embodiment

(53) When characters x.sub.i,t(i)+1, . . . , x.sub.i,N of the search target word x.sub.i are null characters and characters k.sub.t(i)+1, . . . , k.sub.N of the search word k may include a wildcard character, exact match search may not be able to be correctly performed by the method of the first embodiment. For instance, in the case of the example of FIG. 11, characters x.sub.3,n, . . . , x.sub.i,N of a search target word x.sub.3 are null characters and a character k.sub.n of the search word k is a wildcard character. Though a wildcard character has to be determined to match with any normal characters, the wildcard character has to be determined not to match with null characters. However, when x.sub.3,j=k.sub.j is satisfied for j=1, . . . , n−1, y.sub.3=(1, 1, . . . , 1, . . . , 1, 1, 1, . . . , 1) is obtained and z.sub.3=1 is established in the method of the first embodiment. The present embodiment describes a method for correctly performing exact match search in such a case. Note that differences from the above-described matters are mainly described and description of common matters is simplified by referring to the same reference characters below.

(54) <Configuration>

(55) As illustrated in FIG. 1, a retrieval system 2 according to the present embodiment includes a request device 11 which requests retrieval and retrieval devices 22-h which perform retrieval, and the retrieval system 2 performs retrieval processing based on secure computation. Here, h=1, . . . , H and H is an integer which is 1 or greater.

(56) As illustrated in FIG. 2, the retrieval device 22-h of the present embodiment includes a control unit 120-h, an equality determination unit 121-h, a wildcard determination unit 122-h, an OR operation unit 223-h, a null determination unit 224-h, AND operation units 127-h and 226-h, a storage 128-h, an input unit 1291-h, and an output unit 1292-h. The retrieval device 22-h executes each processing under the control of the control unit 120-h. Further, data obtained in respective units are stored in the storage 128-h one by one and read out as needed to be used for other processing.

(57) <Preprocessing>

(58) Same as the first embodiment.

(59) <Retrieval Processing>

(60) Retrieval processing of the present embodiment is described with reference to FIG. 10. The request device 11 conceals a search word k=(k.sub.1, . . . , k.sub.n, . . . , k.sub.N) including n pieces of characters k.sub.1, . . . , k.sub.n so as to obtain a concealed search word [k]. Here, n is a positive integer and n≤N. The characters k.sub.1, . . . , k.sub.n may include a wildcard character. Different from the first embodiment, when the search target word x.sub.i includes null characters x.sub.i,t(i)+1, . . . , x.sub.i,N, k.sub.t(i)+1, . . . , k.sub.N can include a wildcard character.

(61) The request device 11 outputs the concealed search word [k]. The outputted concealed search word [k] is transmitted to the retrieval device 22-h via a network or the like. The concealed search word [k] is inputted into the input unit 1291-h of the retrieval device 22-h to be stored in the storage 128-h (step S1291-h). Subsequently, the following processing is executed for each i=1, . . . , m.

(62) First, the equality determination unit 121-h obtains a concealed operation result [e.sub.i], in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k], which are read from the storage 128-h, and outputs the first concealed operation result [e.sub.i]. Here, e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j (when x.sub.i,j=k.sub.j) and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j (when x.sub.i,j≠k.sub.j). The concealed operation result [e.sub.i] is stored in the storage 128-h (step S121-h).

(63) The wildcard determination unit 122-h obtains a concealed operation result [w], in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, by secure computation using the concealed search word [k] read from the storage 128-h and outputs the concealed operation result [w]. Here, w.sub.j=b.sub.1 is established when k.sub.j is a wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not a wildcard character. The concealed operation result [w] is stored in the storage 128-h (step S122-h).

(64) The null determination unit 224-h obtains a concealed operation result [μ.sub.i], in which an operation result μ.sub.i=(μ.sub.i,1, . . . , μ.sub.i,N) is concealed, by secure computation using the concealed search target word [x.sub.i], which is read from the storage 128-h, and outputs the concealed operation result [μ.sub.i]. Here, μ.sub.i,j=θ.sub.0 is established when x.sub.i,j is a null character and μ.sub.i,j=θ.sub.1 is established when x.sub.i,j is not a null character. μ.sub.i,j∈{θ.sub.0, θ.sub.1}, in which θ.sub.0=0 and θ.sub.1=1, for example. The null determination unit 224-h obtains the concealed operation result [μ.sub.i] by secure computation by using the concealed search target word [x.sub.i] and a concealed null character which is obtained by concealing a null character, for instance. As an example, the null determination unit 224-h performs equality determination between [x.sub.i,j] and the concealed null character for j=1, . . . , N by secure computation, obtains [μ.sub.i,j] in which μ.sub.i,j is concealed, and obtains a set of [μ.sub.i,1], . . . , [μ.sub.i,N] as the concealed operation result [μ.sub.i]. Alternatively, the null determination unit 224-h may obtain the concealed operation result [μ.sub.i] in which μ.sub.i,1, . . . , μ.sub.i,N are collectively concealed, by secure computation using the concealed search target word [x.sub.i] and the concealed null character. The concealed operation result [μ.sub.i] is stored in the storage 128-h (step S224-h).

(65) The AND operation unit 226-h obtains a concealed operation result [v.sub.i], in which an operation result v.sub.i=(v.sub.i,1, . . . , v.sub.i,N) is concealed, by secure computation using the concealed operation result [w] and the concealed operation result [μ.sub.i], which are read from the storage 128-h, and outputs the concealed operation result [v.sub.i]. Here, v.sub.i,j=ρ.sub.1 is established when both of w.sub.j=b.sub.1 and μ.sub.i,j=θ.sub.1 are satisfied, and v.sub.i,j=ρ.sub.0 is established when at least one of w.sub.j=b.sub.0 and μ.sub.i,j=θ.sub.0 is satisfied. v.sub.i,j∈{ρ.sub.0, ρ.sub.1}, in which ρ.sub.0=0 and ρ.sub.1=1, for example. When b.sub.0=0, b.sub.1=1, ρ.sub.0=0, and ρ.sub.1=1, v.sub.i,j=w.sub.j∧μ.sub.i,j is established, for example. For instance, the AND operation unit 226-h performs an AND operation between [w.sub.j] and [μ.sub.i,j] for j=1, . . . , N by secure computation, obtains [v.sub.i,j] in which v.sub.i,j=w.sub.j∧μ.sub.i,j is concealed, and obtains a set of [v.sub.i,1], . . . , [v.sub.i,N] as the concealed operation result [v.sub.i]. Alternatively, the AND operation unit 226-h may obtain the concealed operation result [v.sub.i] in which v.sub.i,1, . . . , v.sub.i,N are collectively concealed, by secure computation using the concealed operation result [w] and the concealed operation result [μ.sub.i]. The concealed operation result [v.sub.i] is stored in the storage 128-h (step S226-h).

(66) The OR operation unit 223-h obtains a concealed operation result [y.sub.i], in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [v.sub.i], which are read from the storage 128-h, and outputs the concealed operation result [y.sub.i]. Here, y.sub.i,j=d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and v.sub.i,j=ρ.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when both of e.sub.i,j=a.sub.0 and v.sub.i,j=ρ.sub.0 are satisfied. y.sub.i,j∈{d.sub.0, d.sub.1}, in which d.sub.0=0 and d.sub.1=1, for example. When a.sub.0=0, a.sub.1=1, ρ.sub.0=0, ρ.sub.1=1, d.sub.0=0, and d.sub.1=1, y.sub.i,j=e.sub.i,j∨v.sub.i,j is established, for example. For example, the OR operation unit 223-h performs an OR operation between [e.sub.i,j] and [v.sub.i,j] for j=1, . . . , N by secure computation, obtains [y.sub.i,j] in which y.sub.i,j=e.sub.i,j∨w.sub.i,j is concealed, and obtains a set of [y.sub.i,1], . . . , [y.sub.i,N] as the concealed operation result [y.sub.i]. Alternatively, the OR operation unit 223-h may obtain the concealed operation result [y.sub.i] in which y.sub.i,1 . . . . , y.sub.i,N are collectively concealed, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [v.sub.i]. The concealed operation result [y.sub.i] is stored in the storage 128-h (step S223-h).

(67) After that, the processing, which is described in the first embodiment, after step S127-h is executed.

Specific Example

(68) A specific example for the case where a.sub.0=0, a.sub.1=1, b.sub.0=0, b.sub.1=1, ρ.sub.0=0, ρ.sub.1=1, d.sub.0=0, d.sub.1=1, g.sub.0=0 and g.sub.1=1 is described below.

(69) FIG. 11 to FIG. 13 illustrate examples of n<N and t(i)<N. As illustrated in FIG. 11, k.sub.n is a wildcard character “*”, and k.sub.n+1, . . . , k.sub.N and x.sub.i,t(i)+1, . . . , x.sub.i,N are null characters.

(70) As illustrated in FIG. 12, e.sub.1=(1, 1, . . . , 1, 0, 1, 1, . . . , 1), w=(0, 0, . . . , 0, 1, 0, 0, . . . , 0), μ.sub.1=(1, 1, . . . , 1, 1, 0, 0, . . . , 0), v.sub.1=(0, 0, . . . , 0, 1, 0, 0, . . . , 0), and y.sub.1=(1, 1, . . . , 1, 1, 1, 1, . . . , 1) when t(1)=n and x.sub.1,j=k.sub.j is satisfied for j=1, . . . , n−1. Therefore, z.sub.1=1 is established.

(71) As illustrated in FIG. 13, e.sub.3=(1, 1, . . . , 1, 0, 1, 1, . . . , 1), w=(0, 0, . . . , 0, 1, 0, 0, . . . , 0), μ.sub.3=(1, 1, . . . , 1, 0, 0, 0, . . . , 0), v.sub.3=(0, 0, . . . , 0, 0, 0, 0, . . . , 0), and y.sub.3=(1, 1, . . . , 1, 0, 1, 1, . . . 1) when t(3)=n−1 and x.sub.i,j=k.sub.j is satisfied for j=1, . . . , n−1. Therefore, z.sub.3=0 is established.

Characteristics of Present Embodiment

(72) As described above, even when characters x.sub.i,t(i)+1, . . . , x.sub.i,N of the search target word x.sub.i are null characters and characters k.sub.t(i)+1, . . . , k.sub.N of the search word k may include a wildcard character, exact match search of concealed database can be performed while concealing the search word including the wildcard character, in the present embodiment. Further, match retrieval of concealed database can be performed with less communication volume than that of related art.

Third Embodiment

(73) A third embodiment is a modification of the first embodiment. In the present embodiment, prefix search of concealed database is performed while concealing a search word including a wildcard character.

(74) <Configuration>

(75) As illustrated in FIG. 1, a retrieval system 3 according to the present embodiment includes a request device 11 which requests retrieval and retrieval devices 32-h which perform retrieval, and the retrieval system 3 performs retrieval processing based on secure computation. Here, h=1, . . . , H and H is an integer which is 1 or greater. H≥2 is established when secure computation based on a secret sharing scheme is performed and H=1 is established when secure computation based on a homomorphic cryptosystem is performed.

(76) As illustrated in FIG. 2, the retrieval device 32-h of the present embodiment includes a control unit 120-h, an equality determination unit 121-h, a wildcard determination unit 122-h, an OR operation unit 323-h, a null determination unit 325-h, an AND operation unit 127-n, a storage 128-h, an input unit 1291-h, and an output unit 1292-h. The retrieval device 32-h executes each processing under the control of the control unit 120-h. Further, data obtained in respective units are stored in the storage 128-h one by one and read out as needed to be used for other processing.

(77) <Preprocessing>

(78) Same as the first embodiment.

(79) <Retrieval Processing>

(80) Retrieval processing of the present embodiment is described with reference to FIG. 14. The request device 11 conceals a search word k=(k.sub.1, . . . , k.sub.n, . . . , k.sub.N) including n pieces of characters k.sub.1, . . . , k.sub.n so as to obtain a concealed search word [k]. Here, n is a positive integer and n≤N. The characters k.sub.1, . . . , k.sub.n may include a wildcard character. When the search target word x.sub.i (here, i=1, . . . , m) does not include any null characters, any character among the characters k.sub.1, . . . , k.sub.n may be a wildcard character. On the other hand, it is assumed that, when the search target word x.sub.i includes null characters x.sub.i,t(i)+1, . . . , x.sub.i,N, k.sub.t(i)+1, . . . , k.sub.N do not include any wildcard characters in the present embodiment.

(81) The request device 11 outputs the concealed search word [k]. The outputted concealed search word [k] is transmitted to the retrieval device 32-h via a network or the like. The concealed search word [k] is inputted into the input unit 1291-h of the retrieval device 32-h to be stored in the storage 128-h (step S1291-h). Subsequently, the following processing is executed for each i=1, . . . , m.

(82) First, the equality determination unit 121-h obtains a concealed operation result [e.sub.i], in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k], which are read from the storage 128-h, and outputs the concealed operation result [e.sub.i]. Here, e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j (when x.sub.i,j=k.sub.j) and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j (when x.sub.i,j≠k.sub.j). The concealed operation result [e.sub.i] is stored in the storage 128-h (step S121-h).

(83) The wildcard determination unit 122-h obtains a concealed operation result [w], in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, by secure computation using the concealed search word [k] read from the storage 128-h and outputs the concealed operation result [w]. Here, w.sub.j=b.sub.1 is established when k.sub.j is a wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not a wildcard character. The concealed operation result [w] is stored in the storage 128-h (step S122-h).

(84) The null determination unit 325-h obtains a concealed operation result [u], in which an operation result u=(u.sub.1, . . . , u.sub.N) is concealed, by secure computation using the concealed search word [k], which is read from the storage 128-h, and outputs the concealed operation result [u]. Here, u.sub.j=c.sub.1 is established when k.sub.j is a null value and u.sub.j=c.sub.0 is established when k.sub.j is not a null value. u.sub.j∈{c.sub.0, c.sub.1}, in which c.sub.0=0 and c.sub.1=1, for example. The null determination unit 325-h obtains the concealed operation result [u] by secure computation by using the concealed search word [k] and a concealed null character which is obtained by concealing a null character, for instance. As an example, the null determination unit 325-h performs equality determination between [k.sub.j] and the concealed null character for j=1, . . . , N by secure computation, obtains [u.sub.j] in which u.sub.j is concealed, and obtains a set of [u.sub.1], . . . , [u.sub.N] as the concealed operation result [u]. Alternatively, the null determination unit 325-h may obtain the concealed operation result [u], in which u.sub.1, . . . , u.sub.N are collectively concealed, by secure computation using the concealed search word [k] and the concealed null character. The concealed operation result [u] is stored in the storage 128-h (step S325-h).

(85) The OR operation unit 323-h obtains a concealed operation result [y.sub.i], in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, by secure computation using the concealed operation result [e.sub.i], the concealed operation result [w], and the concealed operation result [u], which are read from the storage 128-h, and outputs the concealed operation result [y.sub.i]. Here, y.sub.i,j=d.sub.1 is established when at least any one of e.sub.i,j=a.sub.1, w.sub.j=b.sub.1, and u.sub.j=c.sub.1 is satisfied, and y.sub.i,j=d.sub.0 is established when all of e.sub.i,j=a.sub.0, w.sub.j=b.sub.0, and u.sub.j=c.sub.0 are satisfied. y.sub.i,j∈{d.sub.0, d.sub.1}, in which d.sub.0=0 and d.sub.1=1, for example. When a.sub.0=0, a.sub.1=1, b.sub.0=0, b.sub.1=1, c.sub.0=0, c.sub.1=1, d.sub.0=0, and d.sub.1=1, y.sub.i,j=e.sub.i,j∨w.sub.j∨u.sub.j is established, for example. For example, the OR operation unit 323-h performs an OR operation among [e.sub.i,j], [w.sub.j], and [u.sub.j] for j=1, . . . , N by secure computation, obtains which [y.sub.i,j] in which y.sub.i,j=e.sub.i,j∨w.sub.j∨u.sub.j is concealed, and obtains a set of [y.sub.i,1], . . . , [y.sub.i,N] as the concealed operation result [y.sub.i]. Alternatively, the OR operation unit 323-h may obtain the concealed operation result [y.sub.i] in which y.sub.i,1 . . . , y.sub.i,N are collectively concealed, by secure computation using the concealed operation result [e.sub.i], the concealed operation result [w], and the concealed operation result [u]. The concealed operation result [y.sub.i] is stored in the storage 128-h (step S323-h).

(86) After that, the processing, which is described in the first embodiment, after step S127-h is executed.

Specific Example

(87) A specific example for the case where a.sub.0=0, a.sub.1=1, b.sub.0=0, b.sub.1=1, c.sub.0=0, c.sub.1=1, d.sub.0=0, d.sub.1=1, g.sub.0=0, and g.sub.1=1 is described below.

(88) As illustrated in FIG. 15, e.sub.2=(1, 1, . . . , 0, . . . , 1, 0, 1, . . . , 1), w=(0, 0, . . . , 1, . . . , 0, 0, 0, . . . , 0) u=(0, 0, . . . , 0, . . . , 0, 1, 1, . . . , 1) and y.sub.2=(1, 1, . . . , 1, . . . , 1, 1, 1, . . . , 1) when t(2)≤n+1 and x.sub.1,j=k.sub.j is satisfied for j=1, . . . , n. Therefore, z.sub.2=1 is established.

(89) As illustrated in FIG. 16, e.sub.3=(1, 1, . . . , 0, . . . , 0, 1, 1, . . . , 1), w=(0, 0, . . . , 1, . . . , 0, 0, 0, . . . , 0), u=(0, 0, . . . , 0, . . . , 0, 1, 1, . . . , 1), and y.sub.3=(1, 1, . . . , 1, . . . , 0, 1, 1, . . . , 1) when t(3)=n−1 and x.sub.1,j=k.sub.j is satisfied for j=1, . . . , n−1. Therefore, z.sub.3=0 is established.

Characteristics of Present Embodiment

(90) As described above, prefix search of concealed database can be performed while concealing a search word including a wildcard character, in the present embodiment. Further, match retrieval of concealed database can be performed with less communication volume than that of related art.

Fourth Embodiment

(91) A fourth embodiment is a modification of the second and third embodiments. In the present embodiment, prefix search of concealed database is performed while concealing a search word including a wildcard character. When characters x.sub.i,t(i)+1, . . . , x.sub.i,N of the search target word x.sub.i are null characters and characters k.sub.t(i)+1, . . . , k.sub.N of the search word k may include a wildcard character, prefix search may not be able to be correctly performed by the method of the third embodiment, as is the case with the exact match search. The present embodiment describes a method for correctly performing prefix search in such a case.

(92) <Configuration>

(93) As illustrated in FIG. 1, a retrieval system 4 according to the present embodiment includes a request device 11 which requests retrieval and retrieval devices 42-h which perform retrieval, and the retrieval system 4 performs retrieval processing based on secure computation. Here, h=1, . . . , H and H is an integer which is 1 or greater. H≥2 is established when secure computation based on a secret sharing scheme is performed and H=1 is established when secure computation based on a homomorphic cryptosystem is performed.

(94) As illustrated in FIG. 2, the retrieval device 42-h of the present embodiment includes a control unit 120-h, an equality determination unit 121-h, a wildcard determination unit 122-h, an OR operation unit 423-h, null determination units 224-h and 325-h, AND operation units 127-h and 226-h, a storage 128-h, an input unit 1291-h, and an output unit 1292-h. The retrieval device 42-h executes each processing under the control of the control unit 120-h. Further, data obtained in respective units are stored in the storage 128-h one by one and read out as needed to be used for other processing.

(95) <Preprocessing>

(96) Same as the first embodiment.

(97) <Retrieval Processing>

(98) Retrieval processing of the present embodiment is described with reference to FIG. 17. The request device 11 conceals a search word k=(k.sub.1, . . . , k.sub.n, . . . , k.sub.N) including n pieces of characters k.sub.1, . . . , k.sub.n so as to obtain a concealed search word [k]. Here, n is a positive integer and n≥N. The characters k.sub.1, . . . , k.sub.n may include a wildcard character. Different from the third embodiment, when the search target word x.sub.i includes null characters x.sub.i,t(i)+1, . . . , x.sub.i,N, k.sub.t(i)+1, . . . , k.sub.N can include a wildcard character.

(99) The request device 11 outputs the concealed search word [k]. The outputted concealed search word [k] is transmitted to the retrieval device 42-h via a network or the like. The concealed search word [k] is inputted into the input unit 1291-h of the retrieval device 42-h to be stored in the storage 128-h (step S1291-h). Subsequently, the following processing is executed for each i=1, . . . , m.

(100) First, the equality determination unit 121-h obtains a concealed operation result [e.sub.i], in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k], which are read from the storage 128-h, and outputs the concealed operation result [e.sub.i]. Here, e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j (when x.sub.i,j=k.sub.j) and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j (when x.sub.i,j≠k.sub.j). The concealed operation result [e.sub.i] is stored in the storage 128-h (step S121-h).

(101) The wildcard determination unit 122-h obtains a concealed operation result [w], in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, by secure computation using the concealed search word [k] read from the storage 128-h and outputs the concealed operation result [w]. Here, w.sub.j=b.sub.1 is established when k.sub.j is a wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not a wildcard character. The concealed operation result [w] s stored in the storage 128-h (step S122-h).

(102) The null determination unit 325-h obtains a concealed operation result [u], in which an operation result u=(u.sub.1, . . . , u.sub.N) is concealed, by secure computation using the concealed search word [k], which is read from the storage 128-h, and outputs the concealed operation result [u]. Here, u.sub.j=c.sub.1 is established when k.sub.j is a null value and u.sub.j=c.sub.0 is established when k.sub.j is not a null value. The null determination unit 325-h obtains the concealed operation result [u] by secure computation by using the concealed search word [k] and a concealed null character which is obtained by concealing a null character, for instance. The concealed operation result [u] is stored in the storage 128-h (step S325-h).

(103) The null determination unit 224-h obtains a concealed operation result [μ.sub.i], in which an operation result μ.sub.i=(μ.sub.i,1, . . . , μ.sub.i,N) is concealed, by secure computation using the concealed search target word [x.sub.i], which is read from the storage 128-h, and outputs the concealed operation result [μ.sub.i]. Here, μ.sub.i,j=θ.sub.0 is established when x.sub.i,j is a null character and μ.sub.i,j=θ.sub.1 is established when x.sub.i,j is not a null character. The concealed operation result [μ.sub.i] is stored in the storage 128-h (step S224-h).

(104) The AND operation unit 226-h obtains a concealed operation result [v.sub.i], in which an operation result v.sub.i=(v.sub.i,1, . . . , v.sub.i,N) is concealed, by secure computation using the concealed operation result [w] and the concealed operation result [μ.sub.i], which are read from the storage 128-h, and outputs the concealed operation result [v.sub.i]. Here, v.sub.i,j=ρ.sub.1 is established when both of w.sub.j=b.sub.1 and μ.sub.i,j=θ.sub.1 are satisfied, and v.sub.i,j=ρ.sub.0 is established when at least one of w.sub.j=b.sub.0 and μ.sub.i,j=θ.sub.0 is satisfied. The concealed operation result [v.sub.i] is stored in the storage 128-h (step S226-h).

(105) The OR operation unit 423-h obtains a concealed operation result [y.sub.i], in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, by secure computation using the concealed operation result [e.sub.i], the concealed operation result [u], and the concealed operation result [v.sub.i], which are read from the storage 128-h, and outputs the concealed operation result [y.sub.i]. Here, y.sub.i,j=d.sub.1 is established when at least any one of e.sub.i,j=a.sub.1, v.sub.i,j=ρ.sub.1, and u.sub.j=c.sub.1 is satisfied, and y.sub.i,j=d.sub.0 is established when all of e.sub.i,j=a.sub.0, v.sub.i,j=ρ.sub.0, and u.sub.j=c.sub.0 are satisfied. y.sub.i,j∈{d.sub.0, d.sub.1}, in which d.sub.0=0 and d.sub.1=1, for example. When a.sub.0=0, a.sub.1=1, ρ.sub.0=0, ρ.sub.1=1, c.sub.0=0, c.sub.1=1, d.sub.0=0, and d.sub.1=1, y.sub.i,j=e.sub.i,j∨v.sub.i,j∨u.sub.j is established, for example. For example, the OR operation unit 423-h performs an OR operation among [e.sub.i,j], [v.sub.i,j], and [u.sub.j] for j=1, . . . , N by secure computation, obtains [y.sub.i,j] in which y.sub.i,j=e.sub.i,j∨v.sub.i,j∨u.sub.j is concealed, and obtains a set of [y.sub.i,1], . . . , [y.sub.i,N] as the concealed operation result [y.sub.i]. Alternatively, the OR operation unit 423-h may obtain the concealed operation result [y.sub.i] in which y.sub.i,1 . . . , y.sub.i,N are collectively concealed, by secure computation using the concealed operation result [e.sub.i], the concealed operation result [v.sub.i], and the concealed operation result [u]. The concealed operation result [y.sub.i] is stored in the storage 128-h (step S423-h).

(106) After that, the processing, which is described in the first embodiment, after step S127-h is executed.

Specific Example

(107) A specific example for the case where a.sub.0=0, a.sub.1=1, b.sub.0=0, b.sub.1=1, c.sub.0=0, c.sub.1=1, d.sub.0=0, d.sub.1=1, ρ.sub.0=0, ρ.sub.1=1, g.sub.0=0, and g.sub.1=1 is described below. FIG. 18 and FIG. 19 illustrate examples of n<N and t(i)≤N. k.sub.n is a wildcard character “*”, and k.sub.n+1, . . . , k.sub.N and x.sub.i,t(i)+1, . . . , x.sub.i,N are null characters.

(108) As illustrated in FIG. 18, e.sub.1=(1, 1, . . . , 1, 0, 1, 1, . . . , 1), w=0, . . . , 0, 1, 0, 0, . . . , 0), u=(0, 0, . . . , 0, 1, 1, . . . , 1), μ.sub.1=(1, 1, . . . , 1, 1, 0, 0, . . . , 0), v.sub.1=(0, 0, . . . , 0, 1, 0, 0, . . . , 0), and y.sub.1=(1, 1, . . . , 1, 1, 1, 1, . . . , 1) when t(1)=n and x.sub.1,j=k.sub.j is satisfied for j=1, . . . , n−1. Therefore, z.sub.1=1 is established.

(109) As illustrated in FIG. 19, e.sub.3=(1, 1, . . . , 1, 0, 1, 1, . . . , 1), w=(0, 0, . . . , 0, 1, 0, 0, . . . , 0), u=(0, 0, . . . , 0, 0, 1, 1, . . . , 1), μ.sub.3=(1, 1, . . . , 1, 0, 0, 0, . . . , 0), v.sub.3=(0, 0, . . . , 0, 0, 0, 0, . . . , 0), and y.sub.3=(1, 1, . . . , 1, 0, 1, 1, . . . , 1) when t(3)=n−1 and x.sub.1,j=k.sub.j is satisfied for j=1, . . . , n−1. Therefore, z.sub.3=0 is established.

Characteristics of Present Embodiment

(110) As described above, even when characters x.sub.i,t(i)+1, . . . , x.sub.i,N of the search target word x.sub.i are null characters and characters k.sub.t(i)+1, . . . , k.sub.N of the search word k may include a wildcard character, prefix search of concealed database can be performed while concealing the search word including the wildcard character, in the present embodiment. Further, match retrieval of concealed database can be performed with less communication volume than that of related art.

Fifth Embodiment

(111) A fifth embodiment is a modification of the first and second embodiments. It is assumed that the length of a concealed search target word and the length of a concealed search word are the same as each other, in the first and second embodiments. On the other hand, exact match search can be performed irrespective of whether or not the length of a concealed and the length of a concealed retrieval word are the same as each other, in the present embodiment.

(112) <Configuration>

(113) As illustrated in FIG. 1, a retrieval system 5 according to the present embodiment includes a request device 11 which requests retrieval and retrieval devices 52-h which perform retrieval, and the retrieval system 5 performs retrieval processing based on secure computation. Here, h=1, . . . , H and H is an integer which is 1 or greater. H≥2 is established when secure computation based on a secret sharing scheme is performed and H=1 is established when secure computation based on a homomorphic cryptosystem is performed.

(114) As illustrated in FIG. 2, the retrieval device 52-h of the present embodiment includes a control unit 120-h, an equality determination unit 521-h, a wildcard determination unit 522-h, an OR operation unit 523-h, null determination units 524-h and 525-h, an AND operation unit 527h, a concatenation unit 528-h, a storage 128-h, an input unit 1291-h, and an output unit 1292-h. The retrieval device 52-h executes each processing under the control of the control unit 120-h. Further, data obtained in respective units are stored in the storage 128-h one by one and read out as needed to be used for other processing.

(115) <Preprocessing>

(116) The storage 128-h stores concealed database [x.sub.1], . . . , [x.sub.m] including a concealed retrieval target word [x.sub.i] in which a search target word x.sub.i=(x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N(i)) (See DB in FIG. 21, for example) including t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i) is concealed. Here, m, t(i), and N(i) are positive integers, i=1, . . . , m, j(i)=1, . . . , N(i), and t(i)≤N(i). t(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i) included in the search target word x.sub.i are normal characters which are retrieval targets. On the other hand, the remaining N(i)−t(i) pieces of characters x.sub.i,t(i)+1, . . . , x.sub.i,N(i) included in the search target word x.sub.i are null characters. A set of concealed values [x.sub.i,1], . . . , [x.sub.i,t(i)], . . . , [x.sub.i,N(i)] obtained by separately concealing respective characters x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N(i) may be defined as the concealed search target word [x.sub.i] or N(i) pieces of characters x.sub.i,1, . . . , x.sub.i,t(i), . . . , x.sub.i,N(i) may be collectively concealed to be defined as the concealed search target word [x.sub.i]. Other matters are the same as those described in the first embodiment.

(117) <Retrieval Processing>

(118) Retrieval processing of the present embodiment is described with reference to FIG. 20. The request device 11 conceals a search word k=(k.sub.1, . . . , k.sub.n, . . . , k.sub.N) including n pieces of characters k.sub.1, . . . , k.sub.n so as to obtain a concealed search word [k]. Here, j=1, . . . , N, n is a positive integer, and n≤N. The characters k.sub.1, . . . , k.sub.n may include a wildcard character. When the search target word x.sub.i includes null characters x.sub.i,t(i)+1, . . . , x.sub.i,N(i), k.sub.t(i)+1, . . . , k.sub.N can include a wildcard character. n and N are positive integers and n≤N. M.sub.min=N is established when N≤N(i), and M.sub.min=N(i) is established when N>N(i). Such M.sub.min is expressed as M.sub.min=min(N(i), N). Further, N.sub.max=N(i) is established when N≤N(i), and N.sub.max=N is established when N>N(i). Such M.sub.max is expressed as M.sub.max=max(N(i), N). Due to the limit of notation, N.sub.min is sometimes written as “Nmin”, and N.sub.max is sometimes written as “Nmax”. j″=M.sub.min+1, . . . , N and j″(i)=M.sub.min+1, . . . , N(i). However, j″ is nil when M.sub.min+1≥N and j″(i) is nil when M.sub.min+1≥N(i). As described above, a set of concealed values [k.sub.1], . . . , [k.sub.n], . . . , [k.sub.N] Obtained by separately concealing respective characters k.sub.1, . . . , k.sub.n, . . . , k.sub.N may be defined as the concealed search word [k] or N pieces of characters k.sub.1, . . . , k.sub.n, . . . , k.sub.N may be collectively concealed to be defined as the concealed search word [k].

(119) The request device 11 outputs the concealed search word [k]. The outputted concealed search word [k] is transmitted to the retrieval device 52-h via a network or the like. The concealed search word [k] is inputted into the input unit 1291-h of the retrieval device 52-h to be stored in the storage 128-h (step S1291-h). Subsequently, the following processing is executed for each i=1, . . . , m.

(120) First, the equality determination unit 521-h obtains a concealed operation result [e.sub.i], in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,Nmin) is concealed, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k], which are read from the storage 128-h, and outputs the concealed operation result [e.sub.i]. Here, e.sub.i,j′=a.sub.1 is established when x.sub.i,j′ is k.sub.j′ and e.sub.i,j′=a.sub.0 is established when x.sub.i,j′ is not k.sub.j′ for j′=1, . . . , N.sub.min. e.sub.i,j′∈{a.sub.0, a.sub.1}, in which a.sub.0=0 and a.sub.1=1, for example. For example, the equality determination unit 521-h performs equality determination between [k.sub.j′] and [x.sub.i,j′] for j′=1, . . . , N.sub.min by secure computation, obtains [e.sub.i,j′] in which e.sub.i,j′ is concealed, and obtains a set of [e.sub.i,1], . . . , [e.sub.i,Nmin] as the concealed operation result [e.sub.i]. Alternatively, the equality determination unit 521-h may obtain the concealed operation result [e.sub.i] in which e.sub.i,1, . . . , e.sub.i,Nmin are collectively concealed, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k]. The concealed operation result [e.sub.i] is stored in the storage 128-h (step S521-h).

(121) The wildcard determination unit 522-h obtains a concealed operation result [w], in which an operation result w=(w.sub.1, . . . , w.sub.Nmin) is concealed, by secure computation using the concealed search word [k] read from the storage 128-h and outputs the concealed operation result [w]. Here, w.sub.j′=b.sub.1 is established when k.sub.j′ is a wildcard character and w.sub.j′=b.sub.0 is established when k.sub.j′ is not a wildcard character for j′=1, . . . , N.sub.min. The wildcard determination unit 522-h obtains the concealed operation result [w] by secure computation by using the concealed search word [k] and a concealed wildcard character which is obtained by concealing a wildcard character, for instance. As an example, the wildcard determination unit 522-h performs equality determination between [k.sub.j′] and the concealed wildcard character for j′=1, . . . , N.sub.min by secure computation, obtains [w.sub.j′] in which w.sub.j′ is concealed, and obtains a set of [w.sub.1], . . . , [w.sub.Nmin] as the concealed operation result [w]. Alternatively, the wildcard determination unit 522-h may obtain the concealed operation result [w] in which w.sub.1, . . . , w.sub.Nmin are collectively concealed, by secure computation using the concealed search word [k] and the concealed wildcard character. The concealed operation result [w] is stored in the storage 128-h (step S522-h).

(122) The null determination unit 525-h obtains a concealed operation result [u′], in which operation results u′.sub.Mmin+1, . . . , u′.sub.N are concealed, by secure computation computation using at least a part of the concealed search word [k], which is read from the storage 128-h, and outputs the concealed operation result [u′]. Here, u′.sub.j″=c.sub.1 is established when k.sub.j″ is a null character and u′.sub.j″=c.sub.0 is established when k.sub.j″ is not a null character for j″=M.sub.min+1, . . . , N. μ′.sub.j″∈{c.sub.0, c.sub.1}, in which c.sub.0=0 and c.sub.1=1, for example. The null determination unit 525-h obtains the concealed operation result [u′] by secure computation by using at least a part of the concealed search word [k] and a concealed null character which is obtained by concealing a null character, for instance. As an example, the null determination unit 525-h performs equality determination between [k.sub.j″] and the concealed null character for j″=M.sub.min+1, . . . , N by secure computation, obtains [u′.sub.j″] in which u′.sub.j″ is concealed, and obtains a set of [u′.sub.Mmin+1], . . . , [u′.sub.N] as the concealed operation result [u′]. Alternatively, the null determination unit 525-h may obtain the concealed operation result [u′] in which u′.sub.Mmin+1, . . . , u′.sub.N are collectively concealed, by secure computation using the concealed search word [k] and the concealed null character. The concealed operation result [u′] is stored in the storage 128-h (step S525-h). Here, the processing of step S525-h is not executed when M.sub.min+1≥N.

(123) The OR operation unit 523-h obtains a concealed operation result [e′.sub.i], in which an operation result e′.sub.i=(e′.sub.i,1, . . . , e′.sub.i,Nmin) is concealed, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w], which are read from the storage 128-h, and outputs the concealed operation result [e′.sub.i]. Here, e′.sub.i,j′=d.sub.1 is established when at least one of e.sub.i,j′=a.sub.1 and w.sub.j′=b.sub.1 is satisfied and e′.sub.i,j′=d.sub.0 is established when both of e.sub.i,j′=a.sub.0 and w.sub.j′=b.sub.0 are satisfied for j′1, . . . , N.sub.min. e′.sub.i,j′∈{d.sub.0, d.sub.1}, in which d.sub.0=0 and d.sub.1=1, for example. When a.sub.0=0, a.sub.1=1, b.sub.0=0, b.sub.1=1, d.sub.0=0, and d.sub.1=1, e′.sub.i,j=e.sub.i,j′∨w.sub.j′ is established, for example. For example, the OR operation unit 523-h performs an OR operation between [e.sub.i,j′] and [w.sub.j′] for j′=1, . . . , N.sub.min by secure computation, obtains [e′.sub.i,j′] in which e′.sub.i,j′=e.sub.i,j′∨w.sub.j′ is concealed, and obtains a set of [e′.sub.i,1], . . . , [e′.sub.i,Nmin] as the concealed operation result [e′.sub.i]. Alternatively, the OR operation unit 523-h may obtain the concealed operation result [e′.sub.i] in which e′.sub.i,1, . . . , e′.sub.i,Nmin are collectively concealed, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w]. The concealed operation result [e′.sub.i] is stored in the storage 128-h (step S5231-h).

(124) The null determination unit 524-h obtains a concealed operation result [μ′.sub.i], in which an operation result μ′.sub.i=(μ′.sub.i,Mmin+1, . . . , μ′.sub.i,N(i)) is concealed, by secure computation using at least a part of the concealed search target word [x.sub.i], which is read from the storage 128-h, and outputs the concealed operation result [μ′.sub.i]. Here, μ′.sub.i,j″(i)=d.sub.1 is established when x.sub.i,j″(i) is a null character and μ′.sub.i,j″(i)=d.sub.0 is established when x.sub.i,j″(i) is not a null character for j″(i)=M.sub.min+1, . . . , N(i). μ′.sub.i,j″(i)∈{d.sub.0, d.sub.1}, in which d.sub.0=0 and d.sub.1=1, for example. The null determination unit 524-h obtains the concealed operation result [μ′.sub.i] by secure computation by using at least a part of the concealed search target word [x.sub.i] and a concealed null character which is obtained by concealing a null character. As an example, the null determination unit 524-h performs equality determination between [x.sub.i,j″(i)] and the concealed null character for j″(i)=M.sub.min+1, . . . , N(i) by secure computation, obtains [μ′.sub.i,j″(i)] in which μ′.sub.i,j″(i) is concealed, and obtains a set of [μ′.sub.i,Mmin+1], . . . , [μ′.sub.i,N(i)] as the concealed operation result [μ′.sub.i]. Alternatively, the null determination unit 524-h may obtain the concealed operation result in which [μ′.sub.i] in which μ′.sub.i,Mmin+1, . . . , μ′.sub.i,N(i) are collectively concealed, by secure computation using the concealed search target word [x.sub.i] and the concealed null character. The concealed operation result [μ′.sub.i] is stored in the storage 128-h (step S524-h). Here, the processing of step S524-h is not executed when M.sub.min+1≥N(i).

(125) The concatenation unit 528-h obtains a concealed operation result [y.sub.i], in which an operation result y.sub.i is concealed, by secure computation using at least the concealed operation result [e′.sub.i] and outputs the concealed operation result [y.sub.i]. When N=N(i), the concatenation unit 528-h outputs the concealed operation result [e′.sub.i] as the concealed operation result [y.sub.i]. When N>N(i), the concatenation unit 528-h obtains the concealed operation result [y.sub.i], in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N)=(e′.sub.i,1, . . . , e′.sub.i,N(i), u′.sub.N(i)+1, . . . , u′.sub.N) is concealed, by secure computation using the concealed operation result [u′] and the concealed operation result [e′.sub.i] and outputs the concealed operation result [y.sub.i]. When N<N(i), the concatenation unit 528-h obtains the concealed operation result [y.sub.i], in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N(i))=(e′.sub.i,1, . . . , e′.sub.i,N, μ′.sub.i,N+1, . . . , μ′.sub.i,N(i)) is concealed, by secure computation using the concealed operation result [e′.sub.i] and the concealed operation result [μ′.sub.i] and outputs the concealed operation result [y.sub.i]. [y.sub.i] may be a set of concealed results obtained by concealing respective elements of y.sub.i or may be obtained by collectively concealing all elements of y.sub.i. The concealed operation result [y.sub.i] is stored in the storage 128-h (step S528-h).

(126) The AND operation unit 527-h obtains a concealed match determination result [z.sub.i] in which a match determination result z.sub.i is concealed, by secure computation using the concealed operation result [y.sub.i] read from the storage 128-h, and outputs the concealed match determination result [z.sub.i]. Here, z.sub.i=g.sub.1 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is satisfied and z.sub.i=g.sub.0 is established when y.sub.i,1= . . . =y.sub.i,Nmax=d.sub.1 is not satisfied. z.sub.i∈{g.sub.0, g.sub.1}, in which g.sub.0=0 and g.sub.1=1, for example. When d.sub.0=0, d.sub.1=1, g.sub.0=0, and g.sub.1=1, z.sub.i=y.sub.i,1∨ . . . ∨y.sub.i,Nmax is established, for example. The concealed match determination result [z.sub.i] is stored in the storage 128-h (step S527-h).

(127) After that, the processing of step S1292-h, which is described in the first embodiment, is executed.

Specific Example

(128) The followings are obtained when processing of the present embodiment is described in a separate manner to the case of N=N(i), the case of N>N(i), and the case of N<N(i).

(129) <<Case of N=N(i)>>

(130) m, n, t(i), N, and N(i) are positive integers, i=1, . . . , m, j=1, . . . , N, j(i)=1, . . . , N(i), n≤N, and t(i)≤N(i). The equality determination unit 521-h obtains a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k] and outputs the concealed operation result [e.sub.i]. The wildcard determination unit 522-h obtains a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is a wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not a wildcard character, by secure computation using the concealed search word [k] and outputs the concealed operation result [w]. The OR operation unit 523-h obtains a concealed operation result [y.sub.i]=[e′.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, the operation result y.sub.i in which y.sub.i,j=d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and w.sub.j=b.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when both of e.sub.i,j=a.sub.0 and w.sub.j=b.sub.0 are satisfied, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w] and outputs the concealed operation result [y.sub.i]=[e′.sub.i]. For example, as illustrated in FIG. 23, when a.sub.0=0, a.sub.1=1, b.sub.0=0, b.sub.1=1, d.sub.0=0, d.sub.1=1, g.sub.0=0, g.sub.1=1, k.sub.n−1 is a wildcard character “*”, and x.sub.2,j=k.sub.j is satisfied for j=1, . . . , n−2, n, e.sub.2=(1, 1, . . . , 1, 0, 1, 0, 1, . . . , 1), w=(0, 0, . . . , 0, 1, 0, 0, 0, . . . , 0), and y.sub.2=e′.sub.2=(1, 1, . . . , 1, 1, 1, 0, 1, . . . , 1). Therefore, z.sub.2=0 is established.

(131) <<Case of N>N(i)>>

(132) m, n, t(i), N, and N(i) are positive integers, 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 equality determination unit 521-h obtains a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N(i)) is concealed, the operation result e.sub.i in which e.sub.i,j(i)=a.sub.1 is established when x.sub.i,j(i) is k.sub.j(i) and e.sub.i,j(i)=a.sub.0 is established when x.sub.i,j(i) is not k.sub.j(i), by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k] and outputs the concealed operation result [e.sub.i]. The wildcard determination unit 522-h obtains a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N(i)) is concealed, the operation result w in which w.sub.j(i)=b.sub.1 is established when k.sub.j(i) is a wildcard character and w.sub.j(i)=b.sub.0 is established when k.sub.j(i) is not a wildcard character, by secure computation using the concealed search word [k] and outputs the concealed operation result [w]. The null determination unit 525-h (first null determination unit) obtains a concealed operation result [u′] in which operation results u′.sub.N(i)+1, . . . , u′.sub.N are concealed, the operation results u′.sub.N(i)+1, . . . , u′.sub.N in which u′.sub.j″(i)=c.sub.1 is established when k.sub.j″(i) is a null character and u′.sub.j″(i)=c.sub.0 is established when k.sub.j″(i) is not a null character, by secure computation using at least a part of the concealed search word [k] and outputs the concealed operation result [u′]. The OR operation unit 523-h obtains a concealed operation result [e′.sub.i] in which an operation result e′.sub.i=(e′.sub.i,1, . . . , e′.sub.i,N(i)) is concealed, the operation result e′.sub.i in which e′.sub.i,j(i)=d.sub.1 is established when at least one of e.sub.i,j(i)=a.sub.1 and w.sub.j(i)=b.sub.1 is satisfied and e′.sub.i,j(i)=d.sub.0 is established when both of e.sub.i,j(i)=a.sub.0 and w.sub.j(i)=b.sub.0 are satisfied, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w] and outputs the concealed operation result [e′.sub.i]. The concatenation unit 528-h obtains a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N)=(e′.sub.i,1, . . . , e′.sub.i,N(i), u′.sub.N(i)+1, . . . , u′.sub.N) is concealed, by secure computation using the concealed operation result [u′] and the concealed operation result [e′.sub.i] and outputs the concealed operation result [y.sub.i]. For example, as illustrated in FIG. 22, when a.sub.0=0, a.sub.1=1, b.sub.0=0, b.sub.1=1, d.sub.0=0, d.sub.1=1, g.sub.0=0, g.sub.1=1, k.sub.n−1 is a wildcard character “*”, and x.sub.1,j=k.sub.j is satisfied for j=1, . . . , n−2, n, e.sub.1=(1, 1, . . . , 0, 1, 1, 1, . . . , 1), w=(0, 0, . . . , 0, 1, 0, 0, 0, . . . , 0), e′.sub.1=(1, 1, . . . , 1, 1, 1, 1, 1, . . . , 1), and y.sub.1=(1, 1, . . . , 1, 1, 1, 1, 1, . . . , 1, 1). Therefore, z.sub.1=1 is established.

(133) <<Case of N<N(i)>>

(134) 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 equality determination unit 521-h obtains a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k] and outputs the concealed operation result [e.sub.i]. The wildcard determination unit 522-h obtains a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is a wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not a wildcard character, by secure computation using the concealed search word [k] and outputs the concealed operation result [w]. The OR operation unit 523-h obtains a concealed operation result [e′.sub.i] in which an operation result e′.sub.i=(e′.sub.i,1, . . . , e′.sub.i,N) is concealed, the operation result e′.sub.i in which e′.sub.i,j=d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and w.sub.j=b.sub.1 is satisfied and e′.sub.i,j=d.sub.0 is established when both of e.sub.i,j=a.sub.0 and w.sub.j=b.sub.0 are satisfied, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w] and outputs the concealed operation result [e′.sub.i]. The null determination unit 524-h (second null determination unit) obtains a concealed operation result [μ′.sub.i] in which an operation result μ′.sub.i=(μ′.sub.i,N+1, . . . , μ′.sub.i,N(i)) is concealed, the operation result μ′.sub.i in which μ′.sub.i,j″(i)=d.sub.1 is established when x.sub.i,j″(i) is a null character and μ′.sub.i,j″(i)=d.sub.0 is established when x.sub.i,j″(i) is not a null character, by secure computation using at least a part of the concealed search target word [x.sub.i] and outputs the concealed operation result [μ′.sub.i]. The concatenation unit 528-h obtains a concealed operation result [y.sub.i] in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N(i))=(e′.sub.i,1, . . . , e′.sub.iN, u′.sub.i,N+1, . . . , μ′.sub.i,N(i)) is concealed, by secure computation using the concealed operation result [e′.sub.i] and the concealed operation result [μ′.sub.i] and outputs the concealed operation result [y.sub.i]. For example, as illustrated in FIG. 24, when a.sub.0=0, a.sub.1=1, b.sub.0=0, b.sub.1=1, d.sub.0=0, d.sub.1=1, g.sub.0=0, g.sub.1=1, k.sub.n−1 is a wildcard character “*”, and x.sub.3,j=k.sub.j is satisfied for j=1, . . . , n−2, n, e.sub.3=(1, 1, . . . , 1, 0, 0, 1, 1, . . . , 1), w=(0, 0, . . . , 0, 1, 0, 0, 0, . . . , 0), e′.sub.3=(1, 1, . . . , 1, 1, 0, 1, 1, . . . , 1), and y.sub.3=(1, 1, . . . , 1, 1, 0, 1, 1, . . . , 1, 1). Therefore, z.sub.3=0 is established.

Characteristics of Present Embodiment

(135) As described above, even when the search word k may include a wildcard character or even when at least one of the search word k and the search target word x.sub.i may include a null character, exact match search of concealed database can be performed while concealing the search word including the wildcard character, in the present embodiment. Further, exact match search can be performed irrespective of whether or not the length of the concealed search target word and the length of the concealed search word are the same as each other, in the present embodiment. Furthermore, match retrieval of concealed database can be performed with less communication volume than that of related art.

Sixth Embodiment

(136) A sixth embodiment is a modification of the third and fourth embodiments. It is assumed that the length of a concealed search target word and the length of a concealed search word are the same as each other, in the third and fourth embodiments. On the other hand, prefix search can be performed irrespective of whether or not the length of a concealed search target word and the length of a concealed search word are the same as each other, in the present embodiment.

(137) <Configuration>

(138) As illustrated in FIG. 1, a retrieval system 6 according to the present embodiment includes a request device 11 which requests retrieval and retrieval devices 62-h which perform retrieval, and the retrieval system 6 performs retrieval processing based on secure computation. Here, h=1, . . . , H and H is an integer which is 1 or greater. H≥2 is established when secure computation based on a secret sharing scheme is performed and H=1 is established when secure computation based on a homomorphic cryptosystem is performed.

(139) As illustrated in FIG. 2, the retrieval device 62-h of the present embodiment includes a control unit 120-h, an equality determination unit 521-h, a wildcard determination unit 522-h, an OR operation unit 623-h, a null determination unit 625-h, an AND operation unit 527-h, a concatenation unit 628-h, a storage 128-h, an input unit 1291-h, and an output unit 1292-h. The retrieval device 62-h executes each processing under the control of the control unit 120-h. Further, data obtained in respective units are stored in the storage 128-h one by one and read out as needed to be used for other processing.

(140) <Preprocessing>

(141) Same as the fifth embodiment.

(142) <Retrieval Processing>

(143) Retrieval processing of the present embodiment is described with reference to FIG. 25. The request device 11 conceals a search word k=(k.sub.1, . . . , k.sub.n, . . . , k.sub.N) including n pieces of characters k.sub.1, . . . , k.sub.n so as to obtain a concealed search word [k]. The request device 11 outputs the concealed search word [k]. The outputted concealed search word [k] is transmitted to the retrieval device 62-h via a network or the like. The concealed search word [k] is inputted into the input unit 1291-h of the retrieval device 62-h to be stored in the storage 128-h (step S1291-h). Subsequently, the following processing is executed for each i=1, . . . , m.

(144) First, the equality determination unit 521-h obtains a concealed operation result [e.sub.i], in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,Nmin) is concealed, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k], which are read from the storage 128-h, and outputs the concealed operation result [e.sub.i]. Here, e.sub.i,j′=a.sub.1 is established when x.sub.i,j′ is k.sub.j′ and e.sub.i,j′=a.sub.0 is established when x.sub.i,j′ is not k.sub.j′ for j′=1, . . . , N.sub.min. The concealed operation result [e.sub.i] is stored in the storage 128-h (step S521-h).

(145) The wildcard determination unit 522-h obtains a concealed operation result [w], in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, by secure computation using the concealed search word [k] read from the storage 128-h and outputs the concealed operation result [w]. Here, w.sub.j′=b.sub.1 is established when k.sub.j′ is a wildcard character and w.sub.j′=b.sub.0 is established when is not a wildcard character for j′=1, . . . , N.sub.min. The concealed operation result [w] is stored in the storage 128-h (step S522-h).

(146) The null determination unit 625-h obtains a concealed operation result [u″], in which operation results u″=(u″.sub.1, . . . , u″.sub.N) are concealed, by secure computation using the concealed search word [k], which is read from the storage 128-h, and outputs the concealed operation result [u″]. Here, u″.sub.j=c.sub.1 is established when k.sub.j is a null character and u″.sub.j=c.sub.0 is established when k.sub.j is not a null character for j=1, . . . , N. μ″.sub.j∈{c.sub.0, c.sub.1}, in which c.sub.0=0 and c.sub.1=1, for example. The null determination unit 625-h obtains the concealed operation result [u″] by secure computation by using at least a part of the concealed search word [k] and a concealed null character which is obtained by concealing a null character, for instance. As an example, the null determination unit 625-h performs equality determination between [k.sub.j] and the concealed null character for j=1, . . . , N by secure computation, obtains [u″.sub.j] in which u″.sub.j is concealed, and obtains a set of [u″.sub.1], . . . , [u″.sub.N] as the concealed operation result [u″]. Alternatively, the null determination unit 625-h may obtain the concealed operation result [u″] in which u″.sub.1, . . . , u″.sub.N are collectively concealed, by secure computation using the concealed search word [k] and the concealed null character. The concealed operation result [u″] is stored in the storage 128-h (step S6251-h).

(147) The OR operation unit 623-h (first OR operation unit) obtains a concealed operation result [w′], in which an operation result w′=(w′.sub.1, . . . , w′.sub.Nmin) is concealed, by secure computation using at least a part of the concealed operation result [w] and the concealed operation result [u″], which are read from the storage 128-h, and outputs the concealed operation result [w′]. Here, w′.sub.j′=b′.sub.1 is established when at least one of u″j.sub.j′=c.sub.1 and w.sub.j′=b.sub.1 is satisfied, and w′.sub.j′=b′.sub.0 is established when both of u″.sub.j′=c.sub.0 and w.sub.j′=b.sub.0 are satisfied for j′1, . . . , N.sub.min. w′.sub.j∈{b′.sub.0, b′.sub.1}, in which b′.sub.0=0 and b′.sub.1=1, for example. When b.sub.0=0, b.sub.1=1, c.sub.0=0, c.sub.1=1, b′.sub.0=0, and b′.sub.1=1, w′.sub.j′=u″.sub.j′∨w.sub.j′ is established, for example. For example, the OR operation unit 623-h performs an OR operation between and [u″.sub.j′] and [w.sub.j′] for j′=1, . . . , N.sub.min by secure computation, obtains [w′.sub.j′] in which w′.sub.j′=u″.sub.j′∨w.sub.j′ is concealed, and obtains a set of [w′.sub.1], . . . , [w′.sub.Nmin] as the concealed operation result [w′]. Alternatively, the OR operation unit 623-h may obtain the concealed operation result [w′] in which w′.sub.1, . . . , w′.sub.Nmin are collectively concealed, by secure computation using the concealed operation result [w] and the concealed operation result [u″]. The concealed operation result [w′] is stored in the storage 128-h (step S6231-h).

(148) The OR operation unit 623-h (second OR operation unit) obtains a concealed operation result [e′.sub.i], in which an operation result e′.sub.1=(e′.sub.i,1, . . . , e′.sub.i,Nmin) is concealed, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w′], which are read from the storage 128-h, and outputs the concealed operation result [e′.sub.i]. Here, e′.sub.i,j′=d.sub.1 is established when at least one of e.sub.i,j′=a.sub.1 and w′.sub.j′=b′.sub.1 is satisfied and e′.sub.i,j′=d.sub.0 is established when both of e.sub.i,j′=a.sub.0 and w′.sub.j′=b′.sub.0 are satisfied for j′1, . . . , N.sub.min. e′.sub.i,j′∈{d.sub.0, d.sub.1}, in which d.sub.0=0 and d.sub.1=1, for example. When a.sub.0=0, a.sub.1=1, b′.sub.0=0, b′.sub.1=1, d.sub.0=0, and d.sub.1=1, e′.sub.i,j′=e.sub.i,j′∨w′.sub.j′ is established, for example. For example, the OR operation unit 623-h performs an OR operation between [e.sub.i,j′] and [w′.sub.j′] for j′1, . . . , N.sub.min by secure computation, obtains [e′.sub.i,j′] in which e′.sub.i,j′=e.sub.i,j′∨w′.sub.j′ is concealed, and obtains a set of [e′.sub.i,1], . . . , [e′.sub.i,Nmin] as the concealed operation result [e′.sub.i]. Alternatively, the OR operation unit 623-h may obtain the concealed operation result [e′.sub.1] in which e′.sub.i,1, . . . , e′.sub.i,Nmin are collectively concealed, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w′]. The concealed operation result [e′.sub.i] is stored in the storage 128-h (step S6232-h).

(149) The concatenation unit 628-h obtains a concealed operation result [y.sub.i], in which an operation result y.sub.i is concealed, by secure computation using at least the concealed operation result [e′.sub.i] and outputs the concealed operation result [y.sub.i]. When N≤N(i), the concatenation unit 628-h outputs the concealed operation result [e′.sub.i] as the concealed operation result [y.sub.i]. When N>N(i), the concatenation unit 628-h obtains the concealed operation result [y.sub.i], in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N)=(e′.sub.i,1, . . . , e′.sub.i,N(i), u″.sub.N(i)+1, . . . , u″.sub.N) is concealed, by secure computation using at least a part of the concealed operation result [e′.sub.i] and the concealed operation result [u″] and outputs the concealed operation result [y.sub.i]. [y.sub.i] may be a set of concealed results obtained by concealing respective elements of y.sub.i or may be obtained by collectively concealing all elements of y.sub.i. The concealed operation result [y.sub.i] is stored in the storage 128-h (step S628-h).

(150) After that, the processing of step S527-h and the processing of step S1292-h, which is described in the first embodiment, are executed.

Specific Example

(151) The followings are obtained when processing of the present embodiment is described in a separate manner to the case of N>N(i) and the case of N≤N(i).

(152) <<Case of N>N(i)>>

(153) m, n, t(i), N, and N(i) are positive integers, i=1, . . . , m, j=1, . . . , N, j(i)=1, . . . , N(i), j″(i)=N(i)+1, . . . , N, n≤N, and t(i)≤(i). The equality determination unit 521-h obtains a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N(i)) is concealed, the operation result e.sub.i in which e.sub.i,j(i)=a.sub.1 is established when x.sub.i,j(i) is k.sub.j(i) and e.sub.i,j(i)=a.sub.0 is established when x.sub.i,j(i) is not k.sub.j(i), by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k] and outputs the concealed operation result [e.sub.i]. The wildcard determination unit 522-h obtains a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N(i)) is concealed, the operation result w in which w.sub.j(i)=b.sub.1 is established when k.sub.j(i) is a wildcard character and w.sub.j(i)=b.sub.0 is established when k.sub.j(i) is not a wildcard character, by secure computation using the concealed search word [k] and outputs the concealed operation result [w]. The null determination unit 625-h obtains a concealed operation result [u″] in which an operation result u″=(u″.sub.1, . . . , u″.sub.N) is concealed, the operation result u″ in which u″.sub.j=c.sub.1 s established when k.sub.j is a null character and u″.sub.j=c.sub.0 is established when k.sub.j is not a null character, by secure computatioi using the concealed search word [k] and outputs the concealed operation result [u″]. The OR operation unit 623-h obtains a concealed operation result [w′] which an operation result w′=(w′.sub.1, . . . , w′.sub.N(i)) is concealed, the operation result w′ in which w′.sub.j(i)=b′.sub.1 is established when at least one of u″.sub.j(i)=c.sub.1 and w.sub.j(i)=b.sub.1 is satisfied and w′.sub.j(i)=b′.sub.0 is established when both of u″.sub.j(i)=c.sub.0 and w.sub.j(i)=b.sub.0 are satisfied, by secure computation using at least a part of the concealed operation result [w] and the concealed operation result [u″] and outputs the concealed operation result [w′]. The OR operation unit 623-h obtains a concealed operation result [e′.sub.i] in which an operation result e′.sub.i=(e′.sub.i,1, . . . , e′.sub.i,N(i)) is concealed, the operation result e′.sub.1 in which e′.sub.i,j(i)=d.sub.1 is established when at least one of e.sub.i,j(i)=a.sub.1 and w′.sub.j(i)=b′.sub.1 is satisfied and e′.sub.i,j(i)=d.sub.0 is established when both of e.sub.i,j(i)=a.sub.0 and w′.sub.j(i)=b′.sub.0 are satisfied, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w′] and outputs the concealed operation result [e′.sub.i]. The concatenation unit 628-h obtains a concealed operation result [y.sub.i], in which an operation result y.sub.i=(y.sub.i,1, . . . , y.sub.i,N)=(e′.sub.i,1, . . . , e′.sub.i,N(i), u″.sub.N(i)+1, . . . , u″.sub.N) is concealed, by secure computation using at least a part of the concealed operation result [e′.sub.i] and the concealed operation result [u″] and outputs the concealed operation result [y.sub.i]. For example, as illustrated in FIG. 26, when a.sub.0=0, a.sub.1=1, b.sub.0=0, b.sub.1=1, b′.sub.0=0, b′.sub.1=1, c.sub.0=0, c.sub.1=1, d.sub.0=0, d.sub.1=1, g.sub.0=0, g.sub.1=1, k.sub.n−1 is a wildcard character “*”, and x.sub.1,j=k.sub.j is satisfied for j=1, . . . , n−2, n, e.sub.1=(1, 1, . . . , 1, 0, 1, 1, 1, . . . , 1), w=(0, 0, . . . , 0, 1, 0, 0, 0, . . . , 0), u″=(0, 0, . . . , 0, 0, 0, 1, 1, . . . , 1, 1), w′=(0, 0, . . . , 1, 0, 1, 1, . . . , 1), e′.sub.1=(1, 1, . . . , 1, 1, 1, 1, 1, . . . , 1), and y.sub.1=(1, 1, . . . , 1, 1, 1, 1, . . . , 1, 1). Therefore, z.sub.1=1 is established.

(154) <<Case of N≤N(i)>>

(155) m, n, t(i), N, and N(i) are positive integers, i=1, . . . , m, j=1, . . . , N, j(i)=1, . . . , N(i), n≤N, and t(i)≤N(i). The equality determination unit 521-h obtains a concealed operation result [e.sub.i] in which an operation result e.sub.i=(e.sub.i,1, . . . , e.sub.i,N) is concealed, the operation result e.sub.i in which e.sub.i,j=a.sub.1 is established when x.sub.i,j is k.sub.j and e.sub.i,j=a.sub.0 is established when x.sub.i,j is not k.sub.j, by secure computation using the concealed search target word [x.sub.i] and the concealed search word [k] and outputs the concealed operation result [e.sub.i]. The wildcard determination unit 522-h obtains a concealed operation result [w] in which an operation result w=(w.sub.1, . . . , w.sub.N) is concealed, the operation result w in which w.sub.j=b.sub.1 is established when k.sub.j is a wildcard character and w.sub.j=b.sub.0 is established when k.sub.j is not a wildcard character, by secure computation using the concealed search word [k] and outputs the concealed operation result [w]. The null determination unit 625-h obtains a concealed operation result [u″] in which an operation result u″=(u″.sub.1, . . . , u″.sub.N) is concealed, the operation result u″ in which u′.sub.j=c.sub.1 is established when k.sub.j is a null character and u″.sub.j=c.sub.0 is established when k.sub.j is not a null character, by secure computation using the concealed search word [k] and outputs the concealed operation result [u″]. The OR operation unit 623-h obtains a concealed operation result [w] in which an operation result w′=(w′.sub.1, . . . , w′.sub.N) is concealed, the operation result w′ in which w′.sub.j=b′.sub.1 is established when at least one of u″.sub.j=c.sub.1 and w.sub.j=b.sub.1 is satisfied and w′.sub.j=b′.sub.0 is established when both of u″.sub.j=c.sub.0 and w.sub.j=b.sub.0 are satisfied, by secure computation using the concealed operation result [w] and the concealed operation result [e″] and outputs the concealed operation result [w′]. The OR operation unit 623-h obtains a concealed operation result [y.sub.i] in which an operation result e′.sub.i=y.sub.i=(y.sub.i,1, . . . , y.sub.i,N) is concealed, the operation result e′.sub.i in which y.sub.i,j=d.sub.1 is established when at least one of e.sub.i,j=a.sub.1 and w′.sub.j=b′.sub.1 is satisfied and y.sub.i,j=d.sub.0 is established when both of e.sub.i,j=a.sub.0 and w′.sub.j=b′.sub.0 are satisfied, by secure computation using the concealed operation result [e.sub.i] and the concealed operation result [w′] and outputs the concealed operation result [y.sub.i]. For example, as illustrated in FIG. 27, when a.sub.0=0, a.sub.1=1, b.sub.0=0, b.sub.1=1, b′.sub.0=0, b′.sub.1=1, c.sub.0=0, c.sub.1=1, d.sub.0=0, d.sub.1=1, g.sub.0=0, g.sub.1=1, k.sub.n−1 is a wildcard character “*”, x.sub.1,j=k.sub.j is satisfied for j=1, . . . , n−2, n, and N=N(2), e.sub.2=(1, 1, . . . , 1, 0, 1, 1, 1, . . . , 1), w=(0, 0, . . . , 0, 1, 0, 0, 0, . . . , 0), u″=(0, 0, . . . , 0, 0, 0, 1, 1, . . . , 1), w′=(0, 0, . . . , 0, 1, 0, 1, 1, . . . , 1), e′.sub.2=(1, 1, . . . , 1, 1, 1, 1, 1, . . . , 1), and y.sub.2=(1, 1, . . . , 1, 1, 1, 1, 1, . . . , 1). Therefore, z.sub.1=1 is established. For example, as illustrated in FIG. 28, when N<N(3), e.sub.3=(1, 1, . . . , 1, 0, 0, 1, 1, . . . , 1), w=(0, 0, . . . , 0, 1, 0, 0, 0, . . . , 0), u″=(0, 0, . . . , 0, 0, 0, 1, 1, . . . , 1), w′=(0, 0, . . . , 0, 1, 0, 1, 1, . . . , 1), e′.sub.3=(1, 1, . . . , 1, 1, 0, 1, 1, . . . , 1), and y.sub.3=(1, 1, . . . , 1, 1, 0, 1, 1, . . . , 1). Therefore, z.sub.3=0 is established.

Characteristics of Present Embodiment

(156) As described above, even when the search word k may include a wildcard character or even when at least one of the search word k and the search target word x.sub.i may include a null character, prefix search of concealed database can be performed while concealing the search word including the wildcard character, in the present embodiment. Further, prefix search can be performed irrespective of whether or not the length of the concealed search target word and the length of the concealed search word are the same as each other, in the present embodiment. Furthermore, match retrieval of concealed database can be performed with less communication volume than that of related art.

(157) [Modification Etc.]

(158) Note that the present invention is not limited to the above-described embodiments. For example, the retrieval device may directly output the concealed operation result [y.sub.i], or may execute secure computation which is different from that of step S127-h with respect to the concealed operation result [y.sub.i] and output the obtained result.

(159) The secure computation system is not limited as described above. As long as equality determination and logical operations (OR operation, AND operation) based on secure computation are possible, secure computation based on the secret sharing scheme may be used or secure computation based on the homomorphic cryptosystem may be used. For example, a secure computation system described below may be employed. Reference Literature 1: Ivan Damgard, Matthias Fitzi, Eike Kiltz, Jesper Buus Nielsen, Tomas Toft, “Unconditionally Secure Constant-Rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation”, TCC 2006, pp. 285-304. Reference Literature 2: Koji Chida, Koki Hamada, Dai Ikarashi, Katsumi Takahashi, “A Three-party Secure Function Evaluation with Lightweight Verifiability Revisited”, In CSS, 2010. Reference Literature 3: Takashi Nishide, Kazuo Ohta, “Multiparty computation for interval, equality, and comparison without bit-decomposition protocol”, PKC, pp. 343-360, 2007.

(160) The above-described various kinds of processing may be executed, in addition to being executed in chronological order in accordance with the descriptions, in parallel or individually depending on the processing power of a device that executes the processing or when necessary. In addition, it goes without saying that changes may be made as appropriate without departing from the spirit of the present invention.

(161) The above-described each device is embodied by execution of a predetermined program by a general- or special-purpose computer having a processor (hardware processor) such as a central processing unit (CPU), memories such as random-access memory (RAM) and read-only memory (ROM), and the like, for example. The computer may have one processor and one memory or have multiple processors and memories. The program may be installed on the computer or pre-recorded on the ROM and the like. Also, some or all of the processing units may be embodied using an electronic circuit that implements processing functions without using programs, rather than an electronic circuit (circuitry) that implements functional components by loading of programs like a CPU. An electronic circuit constituting a single device may include multiple CPUs.

(162) When the above-described configurations are implemented by a computer, the processing details of the functions supposed to be provided in each device are described by a program. As a result of this program being executed by the computer, the above-described processing functions are implemented on the computer. The program describing the processing details can be recorded on a computer-readable recording medium. An example of the computer-readable recording medium is a non-transitory recording medium. Examples of such a recording medium include a magnetic recording device, an optical disk, a magneto-optical recording medium, and semiconductor memory.

(163) The distribution of this program is performed by, for example, selling, transferring, or lending a portable recording medium such as a DVD or a CD-ROM on which the program is recorded. Furthermore, a configuration may be adopted in which this program is distributed by storing the program in a storage device of a server computer and transferring the program to other computers from the server computer via a network.

(164) The computer that executes such a program first, for example, temporarily stores the program recorded on the portable recording medium or the program transferred from the server computer in a storage device thereof. At the time of execution of processing, the computer reads the program stored in the storage device thereof and executes the processing in accordance with the read program. As another mode of execution of this program, the computer may read the program directly from the portable recording medium and execute the processing in accordance with the program and, furthermore, every time the program is transferred to the computer from the server computer, the computer may sequentially execute the processing in accordance with the received program. A configuration may be adopted in which the transfer of a program to the computer from the server computer is not performed and the above-described processing is executed by so-called application service provider (ASP)-type service by which the processing functions are implemented only by an instruction for execution thereof and result acquisition.

(165) Instead of executing a predetermined program on the computer to implement the processing functions of the present devices, at least some of the processing functions may be implemented by hardware.

DESCRIPTION OF REFERENCE NUMERALS

(166) 1-4 retrieval system 12-1 to 12-H, 22-1 to 22-H, 32-1 to 32-H, 42-1 to 42-H retrieval device