Secure joining system, method, secure computing apparatus and program
A secure joining system is a secure joining system including a plurality of secure computing apparatuses. The plurality of secure computing apparatuses include a first vector joining unit, a first permutation calculation unit, a first vector generation unit, a second vector joining unit, a first permutation application unit, a second vector generation unit, a first inverse permutation application unit, a first vector extraction unit, a second permutation application unit, a third vector generation unit, a second inverse permutation application unit, a second vector extraction unit, a modified second table generation unit, a third permutation application unit, a fourth vector generation unit, a shifting unit, a third inverse permutation application unit, a bit inversion unit, a third vector extraction unit, a modified first table generation unit, a first table joining unit, and a first table formatting unit.
1. A secure joining system comprising:
a plurality of secure computing apparatuses, wherein
F, F k , and F v 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∈F k m is a vector of a key of a first table; d∈F v m is a vector of an attribute of the first table; there is no overlap of keys in the first table; and x∈F k n 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 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,
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 [f 1 ′] of a vector f 1 ′ which is generated by extracting m+1th to m+nth elements of the vector g′,
use the share [f 1 ′] and the share [y] to generate a modified second table by joining the vector f 1 ′, a table having the ith element of the attribute of the second table as u v2 if f 1 ′ i =0 with i=1, . . . , n, and the vector y, where u v2 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 u k and having the ith element of the attribute of the first table as u v1 if f′ i =0 with i=1, . . . , m, and a vector with elements being u v2 as a vector corresponding to the attribute of the second table, where f′ i is the ith element of the vector f′, r i is the ith element of the vector r, and u k , u v1 , and u v2 are predetermined values,
generate a joined table by joining the modified second table and the modified first table, and
use the joined table and the shares [f 1 ′] and [f′] to generate a formatted joined table by extracting, from the joined table, records for which elements of the vector f 1 ′ and the vector f′ are 1.
2. A secure joining system comprising:
a plurality of secure computing apparatuses, wherein
F, F k , and F v 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∈F k m is a vector of a key of a first table; d∈F v m is a vector of an attribute of the first table; there is no overlap of keys in the first table; and x∈F k n 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 [f 1 ′] of a vector f 1 ′ which is generated by extracting m+1th to m+nth elements of the vector g′,
use the share [f 1 ′] and the share [y] to generate a modified second table by joining the vector f 1 ′, a table having the ith element of the attribute of the second table as u v2 if f 1 ′ i =0 with i=1, . . . , n, and the vector y, where u v2 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 u k and having the ith element of the attribute of the first table as u v1 if f′ i =0 with i=1, . . . , m, and a vector with elements being u v2 as a vector corresponding to the attribute of the second table, where f′ i is the ith element of the vector f′, r i is the ith element of the vector r, and u k , u v1 , and u v2 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 f 1 ′ and the vector f′ in the joined table.
3. A secure joining system comprising:
a plurality of secure computing apparatuses, wherein
F k and F v 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∈F k m is a vector of a key of a first table; d∈F v m is a vector of an attribute of the first table; there is no overlap of keys in the first table; and x∈F k n 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.
4. A secure joining system comprising:
a plurality of secure computing apparatuses, wherein
F, F k , and F v 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∈F k m is a vector of a key of a first table; d∈F v m is a vector of an attribute of the first table; there is no overlap of keys in the first table; and x∈F k n 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 u k and having the ith element of the attribute of the first table as u v1 if f′ i =0 with i=1, . . . , m, and a vector with elements being u v2 as a vector corresponding to the attribute of the second table, where f′ i is the ith element of the vector f′, r i is the ith element of the vector r, and u k , u v1 , and u v2 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.
5. A secure joining system comprising:
a plurality of secure computing apparatuses, wherein
F, F k , and F v 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∈F k m is a vector of a key of a first table; d∈F v m is a vector of an attribute of the first table; there is no overlap of keys in the first table; and x∈F k n 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 u k and having the ith element of the attribute of the first table as u v1 if f′ i =0 with i=1, . . . , m, and a vector with elements being u v2 as a vector corresponding to the attribute of the second table, where f′ i is the ith element of the vector f′, r i is the ith element of the vector r, and u k , u v1 , and u v2 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.
6. A secure joining method,
where F, F k , and F v 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∈F k m is a vector of a key of a first table; d∈F v m is a vector of an attribute of the first table; there is no overlap of keys in the first table; and x∈F k n 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 [f 1 ′] of a vector f 1 ′ 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 [f 1 ′] and the share [y] to generate a modified second table by joining the vector f 1 ′, a table having the ith element of the attribute of the second table as u v2 if f 1 ′ i =0 with i=1, . . . , n, and the vector y, where u v2 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 u k and having the ith element of the attribute of the first table as u v1 if f′ i =0 with i=1, . . . , m, and a vector with elements being u v2 as a vector corresponding to the attribute of the second table, where f′ i is the ith element of the vector f′, r i is the ith element of the vector r, and u k , u v1 and u v2 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 [f 1 ′] and [f′] to generate a formatted joined table by extracting, from the joined table, records for which elements of the vector f 1 ′ and the vector f′ are 1.
7. A secure joining method,
where F, F k , and F v 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∈F k m is a vector of a key of a first table; d∈F v m is a vector of an attribute of the first table; there is no overlap of keys in the first table; and x∈F k n 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 [f 1 ′] of a vector f 1 ′ 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 [f 1 ′] and the share [y] to generate a modified second table by joining the vector f 1 ′, a table having the ith element of the attribute of the second table as u v2 if f 1 ′ i =0 with i==1, . . . , n, and the vector y, where u v2 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 u k and having the ith element of the attribute of the first table as u v1 if f′ i =0 with i=1, . . . , m, and a vector with elements being u v2 as a vector corresponding to the attribute of the second table, where f′ i is the ith element of the vector f′, r i is the ith element of the vector r, and u k , u v1 , and u v2 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 f 1 ′ and the vector f′ in the joined table.
8. A secure joining method,
where F k and F v 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∈F k m is a vector of a key of a first table; d∈F v m is a vector of an attribute of the first table; there is no overlap of keys in the first table; and x∈F k n 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.
9. A secure joining method,
where F, F k , and F v 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∈F k m is a vector of a key of a first table; d∈F v m is a vector of an attribute of the first table; there is no overlap of keys in the first table; and x∈F k n 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 u k and having the ith element of the attribute of the first table as u v1 if f′ i =0 with i=1, . . . , m, and a vector with elements being u v2 as a vector corresponding to the attribute of the second table, where f′ i is the ith element of the vector f′, r i is the ith element of the vector r, and u k , u v1 , and u v2 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.
10. A secure joining method,
where F, F k , and F v 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∈F k m is a vector of a key of a first table; d∈F v m is a vector of an attribute of the first table; there is no overlap of keys in the first table; and x∈F k n 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 u k and having the ith element of the attribute of the first table as u v1 if f′ i =0 with i=1, . . . , m, and a vector with elements being u v2 as a vector corresponding to the attribute of the second table, where f′ i is the ith element of the vector f′, r i is the ith element of the vector r, and u k , u v1 , and u v2 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.
11. A secure computing apparatus of the secure joining system according to any one of claims 1 to 5 .
12. One or more non-transitory computer readable media that store a program for causing one or more computers to perform the method according to any one of claims 6 - 10 .