Secure equijoin system, secure equijoin device, secure equijoin method, and program

Abstract

A secure equijoin technique of generating one table from two tables while curbing the volume of communications traffic is provided. The technique includes: a first permutation generating meansthat generates a permutation <σ> from an element sequence which is generated from the first column of a table L and the first column of a table R; a first column generating meansthat generates, for j=2, . . . , a, by using the permutation <σ>, a prefix sum, and an inverse permutation <σ>, the j-th column of a table J from an element sequence which is generated from the to j-th column of the table L; a join-result element sequence generating meansthat generates a join-result element sequence from an element sequence ([[1]], . . . , [[1]], [[0]], . . . , [[0]], [[−1]], . . . , [[−1]]) by using the permutation <σ>, the prefix sum, and the inverse permutation <σ>; a second column generating meansthat generates, for j=a+1, . . . , a+b−1, the j-th column of the table J by using the join-result element sequence and the j−a+1-th column of the table R; and a third column generating meansthat generates the first column of the table J by using the join-result element sequence and the first column of the table R.