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

Claim 1:
2. 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.