SECRET EQUI-JOIN SYSTEM, SECRET EQUI-JOIN DEVICE, SECRET EQUI-JOIN METHOD, AND PROGRAM

摘要

The present invention provides a secret equi-join technique for creating one table from two tables while minimizing the amount of communication. A secret equi-join device includes: a first substitutiongeneration means (110) for generating a substitution σ from an element string generated from a first row of a table L and a first row of a table R; a first row generation means 120 for generating a jth row of a table J for j = 2, …,a from an element string generated from a jth row of the table L using the substitution σ, a prefix sum, and a reverse substitution σ^-1; a join-result element string generation means 130 for generating a join-result element string from an element string ([[1]],..,[[1]],[[0]],..,[[0]],[[−1]],..,[[−1]]) using the substitution σ, the prefix sum, and the reverse substitution σ^-1; a second row generation means 140 for generating a jth row of a table J for j = a + 1, …, a + b − 1 using the join-result element string and the (j − a + 1)th row of the table R; and a third row generation means 150 for generating a first row of the table J using the join-result element string and the first row of the table R.