Patent ID: 11888973
Assignee: NIPPON TELEGRAPH AND TELEPHONE CORPORATION
Field: Computer technology (Electrical engineering)
Classification: CPC H  G | IPC G  H

Claim 5:
6. 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.