Retrieval device, retrieval method, program, and recording medium

Patent metadata

Field	Value
Publication number	US-2021011953-A1
Application number	US-201816954247-A
Country	US
Kind code	A1
Filing date	Dec 10, 2018
Priority date	Dec 19, 2017
Publication date	Jan 14, 2021
Grant date	—

Abstract

An equality determination unit obtains [ei] in which ei=(ei,1, . . . , ei,N) is concealed, ei in which ei,j=a1 is established when xi,j is kj and ei,j=a0 is established when xi,j is not kj, by secure computation using a concealed search target word [xi] and a concealed search word [k]. A wildcard determination unit obtains [w] in which w=(w1, . . . , wN) is concealed, w in which wj=b1 is established when kj is a wildcard character and wj=b0 is established when kj is not a wildcard character, by secure computation using [k]. An OR operation unit obtains [yi] in which yi=(yi,1, . . . , yi,N) is concealed, yi in which yi,j=d1 is established when at least one of ei,j=a1 and wj=b1 is satisfied and yi,j=d0 is established when at least one of ei,j=a1 and wj=b1 is not satisfied, by secure computation using [ei] and [w].

First claim

1 : A retrieval device that 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 concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) ; an input unit that receives an input of a concealed search word [k] in which a search word k=(k 1 , . . . , k n , . . . , k N ) is concealed, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character; an equality determination unit that obtains a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , by secure computation using the concealed search target word [x i ] and the concealed search word [k]; a wildcard determination unit that obtains a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, by secure computation using the concealed search word [k]; and an OR operation unit that obtains a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j =d 1 is established when at least one of e i,j =a 1 and w j =b 1 is satisfied and y i,j =d 0 is established when both of e i,j =a 0 and w j =b 0 are satisfied, by secure computation using the concealed operation result [e i ] and the concealed operation result [w].

2 : A retrieval device that 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 concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x 1 =(x i,1 , . . . , x i,t(i) , . . . , x i,N )is concealed, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) ; an input unit that receives an input of a concealed search word [k] in which a search word k=(k 1 , . . . , k n , . . . , k N ) is concealed, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character; an equality determination unit that obtains a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , by secure computation using the concealed search target word [x i ] and the concealed search word [k]; a wildcard determination unit that obtains a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, by secure computation using the concealed search word [k]; a null determination unit that obtains a concealed operation result [μ i ] in which an operation result μ i =(μ i,1 , . . . , μ i,N ) is concealed, the operation result μ i in which μ i,j =θ 0 is established when x i,j is a null character and μ i,j =θ 1 is established when x i,j is not a null character, by secure computation using the concealed search target word [x i ]; an AND operation unit that obtains a concealed operation result [v i ] in which an operation result v i =(v i,1 , . . . , v i,N ) is concealed, the operation result v i in which w i,j =ρ 1 is established when both of w j =b 1 and μ i,j =θ 1 are satisfied and v i,j =ρ 0 is established when at least one of w j =b 0 and μ i,j =θ 0 is satisfied, by secure computation using the concealed operation result [w] and the concealed operation result [μ i ]; and an OR operation unit that obtains a concealed operation result [y i ] in which an operation result y i =( i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j =d 1 is established when at least one of e i,j =a 1 and v i,j =ρ 1 is satisfied and y i,j =d 0 is established when both of e i,j =a 0 and v i,j =ρ 0 are satisfied, by secure computation using the concealed operation result [e i ] and the concealed operation result [v i ].

3 : A retrieval device that 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 concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , w i,t(i) , . . . , x i,N ) is concealed, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) ; in input unit that receives an input of a concealed search word [k] in which a search word k=(k 1 , . . . , k n , . . . , k N ) is concealed, the search word k including n pieces of characters k 1 , . . . , k n including a wildcard character; an equality determination unit that obtains a concealed operation result [e i ] in which an operation result e i =(e i,1 , . . . , e i,N ) is concealed, the operation result e i in which e i,j =a 1 is established when x i,j is k j and e i,j =a 0 is established when x i,j is not k j , by secure computation using the concealed search target word [x i ] and the concealed search word [k]; a wildcard determination unit that obtains a concealed operation result [w] in which an operation result w=(w 1 , . . . , w N ) is concealed, the operation result w in which w j =b 1 is established when k j is the wildcard character and w j =b 0 is established when k j is not the wildcard character, by secure computation using the concealed search word [k]; a first null determination unit that obtains a concealed operation result [u] in which air operation result uu=(u 1 , . . . , u N ) is concealed, the operation result u in which u j =c 1 is established when k j is a null character and u j =c 0 is established when k j is not a null character, by secure computation using the concealed search word [k]; and an OR operation unit that obtains a concealed operation result [y i ] in which an operation result y i =(y i,1 , . . . , y i,N ) is concealed, the operation result y i in which y i,j =d 1 is established when at least any one of e i,j =a 1 , w j =b 1 , and u j =c 1 is satisfied and y i,j =d 0 is established hwen all of e i,j =a 0 , w j =b 0 , and u j =c 0 are satisfied, by secure computation using the concealed operation result [e i ], the concealed operation result [w], and the concealed operation result [u].

4 : A retrieval device that 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 concealed database [x 1 ], . . . , [x m ] including a concealed search target word [x i ] in which a search target word x i =(x i,1 , . . . , x i,t(i) , . . . , x i,N ) is concealed, the search target word x i including t(i) pieces of characters x i,1 , . . . , x i,t(i) ; an input unit that receives an input of a concealed search word [k] in which a search word k=(k 1 , . . . , k n , . . . , k N ) is concealed, the search word k including n pieces of characters k 1 , . . . , k n including a w

Assignees

• Nippon Telegraph & Telephone

Inventors

• Ikarashi Dai

Classifications

• H04L9/008 Primary

  involving homomorphic encryption · CPC title

• H04L9/085

  Secret sharing or secret splitting, e.g. threshold schemes · CPC title

• H04L2209/46

  Secure multiparty computation, e.g. millionaire problem · CPC title

• G06F16/90335 Primary

  Query processing · CPC title

• Y02D10/00

  Energy efficient computing, e.g. low power processors, power management or thermal management · CPC title