SECURE SEARCH SYSTEM, SECURE SEARCH APPARATUS, SECURE SEARCH METHOD, AND PROGRAM

1 . A secure search system including three or more secure search devices and computing a share of a vector (hereinafter referred to as a search result vector) including K first elements satisfying search conditions regarding a query q among elements of a vector → v from a share (( → v)) of the aligned vector → v having a length N and a share ((q)) of the query q, wherein

N is an integer of 1 or more and K is an integer of 2 or more, the secret search system comprising:

a vector decomposition circuitry for computing a share (( → v)) of a vector → v i (i=1, . . . , α) having a length β (where → v 1 → v 2 . . . → v α = → v → X ( → X is a vector having a length αβ-N in which all elements are dummy data X)) from the share (( → v)), wherein

α and β are integers of 1 or more (where α and β satisfy αβ≥N);

a first detection circuitry for generating a share (( → u)) of a vector → u=( → v 1 (β), . . . , → v α (β)) having the length α from the share (( → v i )) (i=1, . . . , α) and computing a share (( → f)) of a vector → f having the length α (where S is a number of a first element satisfying the search conditions regarding the query q among elements of the vector → u, and → f is a vector in which the S-th element is 1 and the other elements are 0) from the share (( → u));

a partial vector computation circuitry for computing a share (( → a)) of a vector → a (where → a= → v S → v S+1 . . . → v S+γ−1 ) having a length βγ using the share (( → v i )) (i=1, . . . , α) and the share ((( → f)), wherein

γ is an integer of 1 or more (where γ satisfies 1+(y → 1) β≥K);

a second detection circuitry for computing a share (( → b)) of a vector → b (where T is a number of a first element satisfying the search conditions regarding the query q among elements of the vector → a, and → b is a vector in which the T-th element is 1 and the other elements are 0) having the length β from the share ((( → a)); and

an output computation circuitry for computing a share (( → c)) of a vector → c (where → v(j)=X(j>N), and → c=( → v((S → 1)β+T+1), → v((S → 1)β+T+1), . . . , → v((S → 1)β+T+K → 1))) having the length K from the share (( → a) using the share (( → b)), and setting the share H (( → c)) as a share of the search result vector.

2 . The secure search system according to claim 1 , wherein

the partial vector computation circuitry computes a share (( → y i )) (i=1, . . . , γ) of a vector → y i having the length β by setting (( → y i (j)))=(( → v i (j), . . . , → v i+α−1 (j))* → f)) (j=1, . . . , β) from a share (( → v i (j), . . . , → v i+α−1 (j))) of a vector ( → v i (j), . . . , → v i+α−1 (j)) (j=1, . . . , β) and the share (( → f)), and

computes the share (( → a)) by setting → a= → y i (j) → y 2 . . . → y γ from the share (( → y i )) (i=1, . . . , γ).

3 . The secure search system according to claim 1 , wherein

the output computation circuitry computes the share (( → c)) by setting (( → c j))=((( → d j (1), . . . , → d j (β)* → b)) (i=1, . . . , K) from a share (((( → d j (1), . . . , → d j (β)))) of a vector including elements from a first element to a β-th element of a vector → d j =( → a(j), . . . , → a(βγ), X, . . . , X) (j=1, . . . , K) having a length βγ and the share (( → b)).

4 . The secure search system according to claim 1 , wherein

the search conditions regarding the query q are search conditions of q or more or search conditions of greater than q in a case in which the vector → v is aligned in ascending order, and search conditions of q or less or search conditions of smaller than q in a case in which the vector → v is aligned in descending order.

5 . A secure search device in a secure search system including three or more secure search devices and computing a share of a vector (hereinafter referred to as a search result vector) including K first elements satisfying search conditions regarding a query q among elements of a vector → v from a share ((( → )) of the aligned vector → v having a length N and a share (((q)) of the query q, wherein

N is an integer of 1 or more and K is an integer of 2 or more, the secret search device comprising:

a vector decomposition circuitry that computes a share (( → v i )) of a vector → v i (i=1, . . . , α) having a length β (where → v 1 → v 2 . . . → v α = → v → X ( → X is a vector having a length αβ-N in which all elements are dummy data X)) from the share (( → v)), wherein

α and β are integers of 1 or more (where α and β satisfy αβ≥N);

a first detection circuitry that generates a share (( → u)) of a vector → u=( → v 1 (β), . . . , → v α (β)) having the length α from the share (( → v i )) (i=1, . . . , α) and computes a share (( → f)) of a vector → f having the length α (where S is a number of a first element satisfying the search conditions regarding the query q among elements of the vector → u, and → f is a vector in which the S-th element is 1 and the other elements are 0) from the share (( → u));

a partial vector computation circuitry that computes a share (( → a)) of a vector → a (where → a= → v S → v S+1 . . . → v S+γ−1 ) having a length βγ using the share (( → v i )) (i=1, . . . , α) and the share ( → f)), wherein

γ is an integer of 1 or more (where γ satisfies 1+(γ → 1) β≥K);

a second detection circuitry that computes a share (( → b)) of a vector → b (where T is a number of a first element satisfying the search conditions regarding the query q among elements of the vector → a, and → b is a vector in which the T-th element is 1 and the other elements are 0) having the length β from the share (( → a)); and

an output computation circuitry that computes a share (( → c)) of a vector → c (where → v(j)=X(j>N), and → c=( → v((S → 1)β+T), → v((S → 1)β+T+1), . . . , → v((S → 1)β+T+K → 1))) having the length K from the share (( → a)) using the share (( → b)), and sets the share (( → c)) as a share of the search result vector.

6 . A secure search method by which a secure search system including three or more secure search devices computes a share of a vector (hereinafter referred to as a search result vector) including K first elements satisfying search conditions regarding a query q among elements of a vector → v from a share ((( → v)) of the aligned vector → v having a length N and a share ((q)) of the query q, wherein

N is an integer of 1 or more and K is an integer of 2 or more, the secret search method comprising:

a vector decomposition step in which the secure search system computes a share (( → v i )) of a vector → v i (i=1, . . . , α) having a length β (where → v 1 → v 2 . . . → v α = → v → X ( → X is a vector having a length αβ-N in which all elements are dummy data X)) from the share (( → v)), wherein

α and β are integers of 1 or more (where a and β satisfy αβ≥N);

a first detection step in which the secure search system generates a share (( → u)) of a vector → u=( → v 1 (β), . . . , → v α (β)) having the length α from the share (( → v i )) (i=1, . . . , α) and computes a share (( → f)) of a vector → f having the length α (where S is a number of a first element satisfying the search conditions regarding the query q among elements of the vector → u, and → f is a vector in which the S-th element is 1 and the other elements are 0) from the share (( → u));

a partial vector computation step in which the secure search system computes a share (( → a)) of a vector → a (where → a= → v S → v S+1 . . . → v S+γ−1 ) having a length βγ using the share (( → v)) (i=1, . . . , α) and the share (( → f)), wherein

γ is an integer of 1 or more (where γ satisfies 1+(γ → 1) β≥K);

a second detection step in which the secure search system computes a share (( → b)) of a vector → b (where T is a number of a first element satisfying the search conditions regarding the query q among elements of the vector → a, and → b is a vector in which the T-th element is 1 and the other elements are 0) having the length β from the share (( → a)); and

an output computation step in which the secure search system computes a share (( → c)) of a vector → c (where → v(j)=X(j>N), and → c=( → v((S → 1)β+T), → v((S → 1)β+T+1), . . . , → v((S → 1)β+T+K → 1))) having the length K from the share (( → a)) using the share)), and sets the share (( → c)) as a share of the search result vector.

7 . A non-transitory computer-readable storage medium which stores a program for causing a computer to function as the secure search device according to claim 5 .