Secure joining system, method, secure computing apparatus and program

A secure joining system comprising:

• a plurality of secure computing apparatuses, wherein
• F, Fk, and Fv are arbitrary rings;
• [α] is a share generated by secret sharing of α, with α being an arbitrary vector or permutation;
• m and n are predetermined integers greater than or equal to 1;
• u is a predetermined value;
• r∈Fkm is a vector of a key of a first table;
• d∈Fvm is a vector of an attribute of the first table;
• there is no overlap of keys in the first table;
• and x∈Fkn is a vector of a key of a second table;
• and
• the plurality of secure computing apparatuses include processing circuitry configured to, in cooperation with each other and without reconstructing shares,
• use a share [r] of a vector r, a share [x] of a vector x, a share [d] of a vector d, and the u to calculate a share [y] of a vector y which is output when strong mapping that maps a value of each element of the vector r to a value of a corresponding element of the vector d and maps a value that does not exist in the elements of the vector r to the u is applied to the vector x, where the elements of the vector r are a domain of definition and the elements of the vector d are a range,
• use a share [g] of a vector g∈[F]2m+n which is generated by joining m elements each being 1, n elements each being 0, and m elements each being −1 and use a share [σ] of a permutation σ for stable swing of a vector k which is generated by joining the vector r, the vector x and a same vector as the vector r to generate a share [σ(g)] of a vector σ(g) which is generated by application of the permutation σ to the vector g,
• use the share [σ(g)] to generate a share [σ(g′)] of a vector σ(g′), each element of which is a sum of elements of the vector σ(g) up to an element corresponding to that element, the elements including the element corresponding to that element,
• use the share [σ(g′)] to generate a share [g′] of a vector g′ which is generated by application of an inverse permutation σ−1 of the permutation σ to the vector σ(g′),
• use the share [g′] to generate a share [f1′] of a vector f1′ which is generated by extracting m+1th to m+nth elements of the vector g′,
• use the share [f1′] and the share [y] to generate a modified second table by joining the vector f1′, a table having the ith element of the attribute of the second table as uv2 if f1′i=0 with i=1, . . . , n, and the vector y, where uv2 is a predetermined value,
• use the share [σ] and a share [e] of a vector e∈[F]2m+n which is generated by joining m elements each being 1, n elements each being 0, and m elements each being −1 to generate a share [σ(e)] of a vector σ(e) which is generated by application of the permutation σ to the vector e,
• use the share [σ(e)] to generate a share [σ(e′)] of a vector σ(e′), each element of which is a sum of elements of the vector σ(e) up to an element corresponding to that element, the elements including the element corresponding to that element,
• use the share [σ(e′)] to generate a share [σ(e″)] of a vector σ(e″) which is generated by shifting elements of the vector σ(e) each by one,
• use the share [σ(e″)] and the share [σ] to generate a share [e″] of a vector e″ which is generated by application of the inverse permutation σ−1 of the permutation σ to the vector σ(e″),
• use the share [e″] to generate a share [f] of a vector f which is generated by inverting 0 and 1 of elements of the vector e″,
• use the share [f] to generate a share [f′] of a vector f′ which is generated by extracting m elements of the vector f from the left,
• use the share [f′], the share [r], and the share [d] to generate a modified first table by joining the vector f′, a table having the ith element of the key of the first table as uk and having the ith element of the attribute of the first table as uv1 if f′i=0 with i=1, . . . , m, and a vector with elements being uv2 as a vector corresponding to the attribute of the second table, where f′i is the ith element of the vector f′, ri is the ith element of the vector r, and uk, uv1, and uv2 are predetermined values, and
• generate a joined table by joining the modified second table and the modified first table, and output a table formed from a portion other than the vector f1′ and the vector f′ in the joined table.

A secure joining system comprising:

• a plurality of secure computing apparatuses, wherein
• Fk and Fv are arbitrary rings;
• [α] is a share generated by secret sharing of α, with α being an arbitrary vector or permutation;
• m and n are predetermined integers greater than or equal to 1;
• u is a predetermined value;
• r∈Fkm is a vector of a key of a first table;
• d∈Fvm is a vector of an attribute of the first table;
• there is no overlap of keys in the first table;
• and x∈Fkn is a vector of a key of a second table, and
• the plurality of secure computing apparatuses include processing circuitry configured to in cooperation with each other and without reconstructing shares,
• use a share [r] of a vector r, a share [x] of a vector x, a share [d] of a vector d, and the u to calculate a share [y] of a vector y which is output when strong mapping that maps a value of each element of the vector r to a value of a corresponding element of the vector d and maps a value that does not exist in the elements of the vector r to the u is applied to the vector x, where the elements of the vector r are a domain of definition and the elements of the vector d are a range, and
• use the share [y] to generate a modified second table by joining the second table and the vector y.

A secure joining system comprising:

• a plurality of secure computing apparatuses, wherein
• F, Fk, and Fv are arbitrary rings;
• [α] is a share generated by secret sharing of α, with α being an arbitrary vector or permutation;
• m and n are predetermined integers greater than or equal to 1;
• u is a predetermined value;
• r∈Fkm is a vector of a key of a first table;
• d∈Fvm is a vector of an attribute of the first table;
• there is no overlap of keys in the first table;
• and x∈Fkn is a vector of a key of a second table, and
• the plurality of secure computing apparatuses include processing circuitry configured to, in cooperation with each other and without reconstructing shares,
• use a share [r] of a vector r, a share [x] of a vector x, a share [d] of a vector d, and the u to calculate a share [y] of a vector y which is output when strong mapping that maps a value of each element of the vector r to a value of a corresponding element of the vector d and maps a value that does not exist in the elements of the vector r to the u is applied to the vector x, where the elements of the vector r are a domain of definition and the elements of the vector d are a range,
• use the share [y] to generate a modified second table by joining the second table and the vector y,
• use a share [e] of a vector e∈[F]2m+n which is generated by joining m elements each being 1, n elements each being 0, and m elements each being −1 and use a share [σ] of a permutation σ for stable sorting of a vector k which is generated by joining the vector r, the vector x and a same vector as the vector r to generate a share [σ(e)] of a vector σ(e) which is generated by application of the permutation σ to the vector e,
• use the share [σ(e)] to generate a share [σ(e)] of a vector σ(e′), each element of which is a sum of elements of the vector σ(e) up to an element corresponding to that element, the elements including the element corresponding to that element,
• use the share [σ(e)] to generate a share [σ(e″)] of a vector σ(e″) which is generated by shifting elements of the vector σ(e) each by one,
• use the share [σ(e″)] and the share [σ] to generate a share [e″] of a vector e″ which is generated by application of an inverse permutation σ−1 of the permutation σ to the vector σ(e″),
• use the share [e″] to generate a share [f] of a vector f which is generated by inverting 0 and 1 of elements of the vector e″,
• use the share [f] to generate a share [f′] of a vector f′ which is generated by extracting m elements of the vector f from the left,
• use the share [f′], the share [r], and the share [d] to generate a modified first table by joining the vector f′, a table having the ith element of the key of the first table as uk and having the ith element of the attribute of the first table as uv1 if f′i=0 with i=1, . . . , m, and a vector with elements being uv2 as a vector corresponding to the attribute of the second table, where f′i is the ith element of the vector f′, ri is the ith element of the vector r, and uk, uv1, and uv2 are predetermined values,
• use the modified first table and the share [f′] to generate a formatted modified first table by extracting, from the modified first table, records for which elements of the vector f′ are 1, and
• generate a joined table by joining the modified second table and the formatted modified first table.

A secure joining system comprising:

• a plurality of secure computing apparatuses, wherein
• F, Fk, and Fv are arbitrary rings;
• [α] is a share generated by secret sharing of α, with α being an arbitrary vector or permutation;
• m and n are predetermined integers greater than or equal to 1;
• u is a predetermined value;
• r∈Fkm is a vector of a key of a first table;
• d∈Fvm is a vector of an attribute of the first table;
• there is no overlap of keys in the first table;
• and x∈Fkn is a vector of a key of a second table, and
• the plurality of secure computing apparatuses include processing circuitry configured to, in cooperation with each other and without reconstructing shares,
• use a share [r] of a vector r, a share [x] of a vector x, a share [d] of a vector d, and the u to calculate a share [y] of a vector y which is output when strong mapping that maps a value of each element of the vector r to a value of a corresponding element of the vector d and maps a value that does not exist in the elements of the vector r to the u is applied to the vector x, where the elements of the vector r are a domain of definition and the elements of the vector d are a range,
• use the share [y] to generate a modified second table by joining the second table and the vector y,
• use a share [e] of a vector e∈[F]2m+n which is generated by joining m elements each being 1, n elements each being 0, and m elements each being −1 and use a share [σ] of a permutation σ for stable sorting of a vector k which is generated by joining the vector r, the vector x and a same vector as the vector r to generate a share [σ(e)] of a vector σ(e) which is generated by application of the permutation σ to the vector e,
• use the share [σ(e)] to generate a share [σ(e′)] of a vector σ(e′), each element of which is a sum of elements of the vector σ(e) up to an element corresponding to that element, the elements including the element corresponding to that element,
• use the share [σ(e′)] to generate a share [σ(e″)] of a vector σ(e″) which is generated by shifting elements of the vector σ(e) each by one,
• use the share [σ(e″)] and the share [σ] to generate a share [e″] of a vector e″ which is generated by application of an inverse permutation σ−1 of the permutation σ to the vector σ(e″),
• use the share [e″] to generate a share [f] of a vector f which is generated by inverting 0 and 1 of elements of the vector e″,
• use the share [f′] to generate a share [f′], of a vector f′ which is generated by extracting m elements of the vector f from the left,
• use the share [f′], the share [r], and the share [d] to generate a modified first table by joining the vector f′, a table having the ith element of the key of the first table as uk and having the ith element of the attribute of the first table as uv1 if f′i=0 with i=1, . . . , m, and a vector with elements being uv2 as a vector corresponding to the attribute of the second table, where f′i is the ith element of the vector f′, ri is the ith element of the vector r, and uk, uv1, and uv2 are predetermined values, and
• generate a table that joins the modified second table and a table excluding the vector f′ portion in the modified first table.

A secure joining method,

• where F, Fk, and Fv are arbitrary rings;
• [α] is a share generated by secret sharing of α, with α being an arbitrary vector or permutation;
• m and n are predetermined integers greater than or equal to 1;
• u is a predetermined value;
• r∈Fkm is a vector of a key of a first table;
• d∈Fvm is a vector of an attribute of the first table;
• there is no overlap of keys in the first table;
• and x∈Fkn is a vector of a key of a second table;
• the secure joining method comprising:
• without reconstructing shares:
• using, by a plurality of secure computing apparatuses cooperating with each other, a share [r] of a vector r, a share [x] of a vector x, a share [d] of a vector d, and the u to calculate a share [y] of a vector y which is output when strong mapping that maps a value of each element of the vector r to a value of a corresponding element of the vector d and maps a value that does not exist in the elements of the vector r to the u is applied to the vector x, where the elements of the vector r are a domain of definition and the elements of the vector d are a range;
• using by the plurality of secure computing apparatuses cooperating with each other, a share [g] of a vector g∈[F]2m+n which is generated by joining m elements each being 1, n elements each being 0, and m elements each being −1 and use a share [σ] of a permutation σ for stable sorting of a vector k which is generated by joining the vector r, the vector x and a same vector as the vector r to generate a share [σ(g)] of a vector σ(g) which is generated by application of the permutation σ to the vector g;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [σ(g)] to generate a share [σ(g′)] of a vector σ(g′), each element of which is a sum of elements of the vector σ(g) up to an element corresponding to that element, the elements including the element corresponding to that element;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [σ(g′)] to generate a share [g′] of a vector g′ which is generated by application of an inverse permutation σ−1 of the permutation σ to the vector σ(g′);
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [g′] to generate a share [f1′] of a vector f1′ which is generated by extracting m+1th to m+nth elements of the vector g′;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [f1′] and the share [y] to generate a modified second table by joining the vector f1′, a table having the ith element of the attribute of the second table as uv2 if f1′i=0 with i=1, . . . , n, and the vector y, where uv2 is a predetermined value;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [σ] and a share [e] of a vector e∈[F]2m+n which is generated by joining in elements each being 1, n elements each being 0, and m elements each being −1 to generate a share [σ(e)] of a vector σ(e) which is generated by application of the permutation σ to the vector e;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [σ(e)] to generate a share [σ(e′)] of a vector σ(e′), each element of which is a sum of elements of the vector σ(e) up to an element corresponding to that element, the elements including the element corresponding to that element;
• using, by the plurality of secure crating with each other, the share [σ(e′)] to generate a share [σ(e″)] of a vector σ(e″) which is generated by shifting elements of the vector σ(e) each by one;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [σ(e″)] and the share [σ] to generate a share [e″] of a vector e″ which is generated by application of the inverse permutation σ−1 of the permutation σ to the vector σ(e″);
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [e″] to generate a share [f] of a vector f which is generated by inverting 0 and 1 of elements of the vector e″;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [f] to generate a share [f′] of a vector f′ which is generated by extracting m elements of the vector f from the left;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [f′], the share [r], and the share [d] to generate a modified first table by joining the vector f′, a table having the ith element of the hey of the first table as uk and having the ith element of the attribute of the first table as uv1 if f′i=0 with i=1, . . . , m, and a vector with elements being uv2 as a vector corresponding to the attribute of the second table, where f′i is the ith element of the vector f′, ri is the ith element of the vector r, and uk, uv1 and uv2 are predetermined values;
• generating, by the plurality of secure computing apparatuses cooperating with each other, a joined table by joining the modified second table and the modified first table;
• and
• using, by the plurality of secure computing apparatuses cooperating with each other, the joined table and the shares [f1′] and [f′] to generate a formatted joined table by extracting, from the joined table, records for which elements of the vector f1′ and the vector f′ are 1.

A secure joining method,

• where F, Fk, and Fv are arbitrary rings;
• [α] is a share generated by secret sharing of α, with α being an arbitrary vector or permutation;
• m and n are predetermined integers greater than or equal to 1;
• u is a predetermined value;
• r∈Fkm is a vector of a key of a first table;
• d∈Fvm is a vector of an attribute of the first table;
• there is no overlap of keys in the first table;
• and x∈Fkn is a vector of a key of a second table,
• the secure joining method comprising:
• without reconstructing shares:
• using, by a plurality of secure computing apparatuses cooperating with each other, a share [r] of a vector r, a share [x] of a vector x, a share [d] of a vector d, and the u to calculate a share [y] of a vector y which is output when strong mapping that maps a value of each element of the vector r to a value of a corresponding element of the vector d and maps a value that does not exist in the elements of the vector r to the u is applied to the vector x, where the elements of the vector r are a domain of definition and the elements of the vector d are a range;
• using, by the plurality of secure computing apparatuses cooperating with each other, a share [g] of a vector g∈[F]2m+n which is generated by joining m elements each being 1, n elements each being 0, and in elements each being −1 and use a share [σ] of a permutation σ for stable sorting of a vector k which is generated by joining the vector r, the vector x and a same vector as the vector r to generate a share [σ(g)] of a vector σ(g) which is generated by application of the permutation σ to the vector g;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [σ(g)] to generate a share [σ(g′)] of a vector σ(g′), each element of which is a sum of elements of the vector σ(g) up to an element corresponding to that element, the elements including the element corresponding to that element;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [σ(g′)] to generate a share [g′] of a vector g′ which is generated by application of an inverse permutation σ−1 of the permutation σ to the vector σ(g′);
• using by the plurality of secure computing apparatuses cooperating with each other, the share [g′] to generate a share [f1′] of a vector f1′ which is generated by extracting m+1th to m+nth elements of the vector g′;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [f1′] and the share [y] to generate a modified second table by joining the vector f1′, a table having the ith element of the attribute of the second table as uv2 if f1′i=0 with i==1, . . . , n, and the vector y, where uv2 is a predetermined value;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [σ] and a share [e] of a vector e∈[F]2m+n which is generated by joining m elements each being 1, n elements each being 0, and m elements each being −1 to generate a share [σ(e)] of a vector σ(e) which is generated by application of the permutation σ to the vector e;
• using by the plurality of secure computing apparatuses cooperating with each other, the share [σ(e)] to generate a share [σ(e′)] of a vector σ(e′), each element of which is a SUM of elements of the vector σ(e) up to an element corresponding to that element, the elements including the element corresponding to that element;
• using by the plurality of secure computing apparatuses cooperating with each other, the share [σ(e′)] to generate a share [σ(e″)] of a vector σ(e″) which is generated by shifting elements of the vector σ(e) each by one;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [σ(e″)] and the share [σ] to generate a share [e″] of a vector e″ which is generated by application of the inverse permutation σ−1 of the permutation σ to the vector σ(e″);
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [e″] to generate a share [f] of a vector f which is generated by inverting 0 and 1 of elements of the vector e″;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [f] to generate a share [f′] of a vector f′ which is generated by extracting m elements of the vector f from the left;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [f′], the share [r], and the share [d] to generate a modified first table by joining the vector f′, a table having the ith element of the hey of the first table as uk and having the ith element of the attribute of the first table as uv1 if f′i=0 with i=1, . . . , m, and a vector with elements being uv2 as a vector corresponding to the attribute of the second table, where f′i is the ith element of the vector f′, ri is the ith element of the vector r, and uk, uv1, and uv2 are predetermined values;
• and
• generating, by the plurality of secure computing apparatuses cooperating with each other, a joined table by joining the modified second table and the modified first table, and output a table formed from a portion other than the vector f1′ and the vector f′ in the joined table.

A secure joining method,

• where Fk and Fv are arbitrary rings;
• [α] is a share generated by secret sharing of α, with α being an arbitrary vector or permutation;
• m and n are predetermined integers greater than or equal to 1;
• u is a predetermined value;
• r∈Fkm is a vector of a key of a first table;
• d∈Fvm is a vector of an attribute of the first table;
• there is no overlap of keys in the first table;
• and x∈Fkn is a vector of a key of a second table,
• the secure joining method comprising:
• without reconstructing shares:
• using, by a plurality of secure computing apparatuses cooperating with each other, a share [r] of a vector r, a share [x] of a vector x, a share [d] of a vector d, and the u to calculate a share [y] of a vector y which is output when strong mapping that maps a value of each element of the vector r to a value of a corresponding element of the vector d and maps a value that does not exist in the elements of the vector r to the u is applied to the vector x, where the elements of the vector r are a domain of definition and the elements of the vector d are a range;
• and
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [y] to generate a modified second table by joining the second table and the vector y.

A secure joining method,

• where F, Fk, and Fv are arbitrary rings;
• [α] is a share generated by secret sharing of α, with α being an arbitrary vector or permutation;
• m and n are predetermined integers greater than or equal to 1;
• u is a predetermined value;
• r∈Fkm is a vector of a key of a first table;
• d∈Fvm is a vector of an attribute of the first table;
• there is no overlap of keys in the first table;
• and x∈Fkn is a vector of a key of a second table,
• the secure joining method comprising:
• without reconstructing shares:
• using, by a plurality of secure computing apparatuses cooperating with each other, a share [r] of a vector r, a share [x] of a vector x, a share [d] of a vector d, and the u to calculate a share [y] of a vector y which is output when strong mapping that maps a value of each element of the vector r to a value of a corresponding element of the vector d and maps a value that does not exist in the elements of the vector r to the u is applied to the vector x, where the elements of the vector r are a domain of definition and the elements of the vector d are a range;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [y] to generate a modified second table by joining the second table and the vector y;
• using, by the plurality of secure computing apparatuses cooperating with each other, a share [e] of a vector e∈[F]2m+n which is generated by joining m elements each being 1, n elements each being 0, and m elements each being −1 and use a share [σ] of a permutation σ for stable sorting of a vector k which is generated by joining the vector r, the vector x and a same vector as the vector r to generate a share [σ(e)] of a vector σ(e) which is generated by application of the permutation σ to the vector e;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [σ(e)] to generate a share [σ(e′)] of a vector σ(e′), each element of which is a sum of elements of the vector σ(e) up to an element corresponding to that element, the elements including the element corresponding to that element;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [σ(e′)] to generate a share [σ(e″)] of a vector (σ(e″) which is generated by shifting elements of the vector σ(e) each by one;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [σ(e″)] and the share [σ] to generate a share [e″] of a vector e″ which is generated by application of an inverse permutation σ−1 of the permutation σ to the vector σ(e″);
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [e″] to generate a share [f] of a vector f which is generated by inverting 0 and 1 of elements of the vector e″;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [f] to generate a share [f′] of a vector f′ which is generated by extracting in elements of the vector f from the left;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [f′], the share [r], and the share [d] to generate a modified first table by joining the vector f′, a table having the ith element of the key of the first table as uk and having the ith element of the attribute of the first table as uv1 if f′i=0 with i=1, . . . , m, and a vector with elements being uv2 as a vector corresponding to the attribute of the second table, where f′i is the ith element of the vector f′, ri is the ith element of the vector r, and uk, uv1, and uv2 are predetermined values;
• using, the plurality of secure computing apparatuses cooperating with each other, the modified first table and the share [f′] to generate a formatted modified first table by extracting, from the modified first table, records for which elements of the vector f′ are 1;
• and
• generating, by the plurality of secure computing apparatuses cooperating with each other, a joined table by joining the modified second table and the formatted modified first table.

A secure joining method,

• where F, Fk, and Fv are arbitrary rings;
• [α] is a share generated by secret sharing of α, with α being an arbitrary vector or permutation;
• m and n are predetermined integers greater than or equal to 1;
• u is a predetermined value;
• r∈Fkm is a vector of a key of a first table;
• d∈Fvm is a vector of an attribute of the first table;
• there is no overlap of keys in the first table;
• and x∈Fkn is a vector of a key of a second table,
• the secure joining method comprising:
• without reconstructing shares:
• using, by a plurality of secure computing apparatuses cooperating with each other, a share [r] of a vector r, a share [x] of a vector x, a share [d] of a vector d, and the u to calculate a share [y] of a vector y which is output when strong mapping that maps a value of each element of the vector r to a value of a corresponding element of the vector d and maps a value that does not exist in the elements of the vector r to the u is applied to the vector x, where the elements of the vector r are a domain of definition and the elements of the vector d are a range;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [y] to generate a modified second table by joining the second table and the vector y;
• using, by the plurality of secure computing apparatuses cooperating with each other, a share [e] of a vector e∈[F]2m+n which is generated by joining m elements each being 1, n elements each being 0, and m elements each being −1 and use a share [σ] of a permutation σ for stable sorting of a vector k which is generated by joining the vector r, the vector x and a same vector as the vector r to generate a share [σ(e)] of a vector σ(e) which is generated by application of the permutation σ to the vector e;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [σ(e)] to generate a share [σ(e′)] of a vector σ(e′), each element of which is a sum of elements of the vector σ(e) up to an element corresponding to that element, the elements including the element corresponding to that element;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [σ(e′)] to generate a share [σ(e″)] of a vector σ(e″) which is generated by shifting elements of the vector σ(e) each by one;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [σ(e″)] and the share [σ] to generate a share [e″] of a vector e″ which is generated by application of an inverse permutation σ−1 of the permutation to the vector σ(e″);
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [e″] to generate a share [f] of a vector f which is generated by inverting 0 and 1 of elements of the vector e″;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [f] to generate a share [f′] of a vector f′ which is generated by extracting m elements of the vector f from the left;
• using, by the plurality of secure computing apparatuses cooperating with each other, the share [f′], the share [r], and the share [d] to generate a modified first table by joining the vector f′, a table having the ith element of the hey of the first table as uk and having the ith element of the attribute of the first table as uv1 if f′i=0 with i=1, . . . , m, and a vector with elements being uv2 as a vector corresponding to the attribute of the second table, where f′i is the ith element of the vector f′, ri is the ith element of the vector r, and uk, uv1, and uv2 are predetermined values;
• and
• generating, by the plurality of secure computing apparatuses cooperating with each other, a table that joins the modified second table and a table excluding the vector f′ portion in the modified first table.