Secure joining information generation system, secure joining system, methods therefor, secure computing apparatus and program

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 arbitrary permutation;
• m0 and m1 are integers greater than or equal to 1;
• k0 ∈ Fkm0 is a vector of a key of a first table;
• v0 ∈ Fvm0 is a vector of an attribute value of the first table;
• k1 ∈ Fkm1 is a vector of a key of a second table;
• v1 ∈ Fvm1 is a vector of an attribute value of the second table;
• and π0 and π1 are predetermined permutations with lengths of m0 and m1, respectively, and
• the plurality of secure computing apparatuses include
• processing circuitry configured to
• use a share [k0] of the vector k0, a share [k1] of the vector k1, a share [π0] of the permutation π0, and a share [π1] of the permutation π1 to generate:
• a share [π0(σ0−1)] of a vector π0(σ0−1) which is generated by application of the permutation π0 to an inverse permutation σ0−1 of a permutation σ0, where permutation of each vector of the first table with the permutation σ0 causes records for keys common to the first table and the second table to move to a head side;
• a share [π1(σ1−1)] of a vector π1(σ1−1) which is generated by application of the permutation π1 to an inverse permutation σ1−1 of a permutation σ1, where permutation of each vector of the second table with the permutation σ1 causes records for keys common to the first table and the second table to move to the head side;
• a share [g0] of a vector g0 which is formed from a value g0,i indicating whether the ith record of the first table is a record for a key that is common to the first table and the second table;
• and a share [g1] of a vector g1 which is formed from a value g1,i indicating whether the ith record of the second table is a record for a key that is common to the first table and the second table,
• use the share [g1], the share [k1] of the vector k1, and the share [V1] of the vector v1 to generate a modified second table in which if g1,i=1, the ith element of the key of the second table is set to a predefined value u1,k indicating null and the ith element of the attribute of the second table is set to a predefined value u1,v indicating null, where g1,i is the ith element of the vector g1,
• use the share [k0] of the vector k0, a share [V0] of the vector v0, a share [k1′] of k1′, which is a vector of the key of the modified second table, a share [V1′] of v1′, which is a vector of the attribute value of the modified second table, the share [π0] of the permutation π0, the share [π1] of the permutation π1, the share [π0(σ0−1)], and the share [π1(σ1−1)] to calculate a share [k0′] of a vector k0′=(π0(σ0−1))−1(π0(k0))), a share [V0′] of a vector V0′=(π0(σ0−1))−1(π0(V0)), a share [k1″] of a vector k1″=(π1(σ1−1))−1(π1(k1′)), and a share [V1″] of a vector v1″=(π1(σ1−1))−1(π1(V1′)), and
• use the share [k0′], the share [V0′], the share [k1″], and the share [V1″] to generate, when m0<m1, a joined table which joins the vector k0′, the vector V0′, a vector generated by extracting first m0 elements of the vector k1″, and a vector generated by extracting first m0 elements of the vector v1″, and to generate, when m0>m1, a joined table which joins the vector k0′, the vector V0′, a vector generated by adding m0<m1 elements being a predefined value uk indicating null to the vector k1″, and a vector generated by adding m0-m1 elements being a predefined value uv indicating null to the vector v1″.

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 arbitrary permutation;
• m0 and m1 are integers greater than or equal to 1;
• k0 ∈ Fkm0 is a vector of a key of a first table;
• v0 ∈ Fvm0 is a vector of an attribute value of the first table;
• k1 ∈ Fkm1 is a vector of a key of a second table;
• V1 ∈ Fvm1 is a vector of an attribute value of the second table;
• and π0 and π1 are predetermined permutations with lengths of m0 and m1, respectively, and
• the plurality of secure computing apparatuses include
• processing circuitry configured to
• use a share [k0] of the vector k0, a share [k1] of the vector k1, a share [π0] of the permutation π0, and a share [π1] of the permutation π1 to generate:
• a share [π0(σ0−1)] of a vector π0(σ0−1) which is generated by application of the permutation π0 to an inverse permutation σ0−1 of a permutation σ0, where permutation of each vector of the first table with the permutation σ0 causes records for keys common to the first table and the second table to move to a head side;
• a share [π1(σ1−1)] of a vector π1(σ1−1) which is generated by application of the permutation π1 to an inverse permutation σ1−1 of a permutation σ1, where permutation of each vector of the second table with the permutation σ1 causes records for keys common to the first table and the second table to move to the head side;
• a share [g0] of a vector g0 which is formed from a value g0,i indicating whether the ith record of the first table is a record for a key that is common to the first table and the second table;
• and a share [g1] of a vector g1 which is formed from a value g1,i indicating whether the ith record of the second table is a record for a key that is common to the first table and the second table,
• use the share [k0] of the vector k0, a share [V0] of the vector v0, the share [k1] of the vector k1, and a share [V1] of the vector v1 to calculate a share [k0′] of a vector k0′=(π0(σ0−1)−1(π0(k0))), a share [V0′] of a vector V0′=(π0(σ0−1)−1(π0(V0)), a share [k1′] of a vector k1′=(π1(σ1−1))−1(π1(k1′)), and a share [V1′] of a vector v1′=(π1(σ1−1))−1(π1(V1′)), and
• use the share [k0′], the share [V0′], the share [k1′], and the share [V1′] to generate a joined table which joins a table (1) which joins a vector generated by extracting first c elements of the vector k0′, a vector generated by extracting first c elements of the vector V0′, a vector generated by extracting first c elements of the vector k1′, and a vector generated by extracting first c elements of the vector v1′, a table (2) which joins a vector generated by extracting remaining m0-c elements of the vector k0′, a vector generated by extracting remaining m0-c elements of the vector V0′, and a vector having a value corresponding to the attribute value of the second table set to a predefined value u′1,v indicating null, and a table (3) which joins a vector generated by extracting remaining m0-c elements of the vector V0′a vector generated by extracting remaining m1-c elements of the vector V1′, and a vector having a value corresponding to the attribute value of the first table set to a predefined value u′0,v indicating null, where c is the number of 0 elements in the vector g0 or the vector g1.

A secure joining information generation method,

• where Fk and Fv are arbitrary rings;
• [α] is a share generated by secret sharing of α, with α being an arbitrary vector or arbitrary permutation;
• m0 and m1 are integers greater than or equal to 1;
• k0 ∈ Fkm0 is a vector of a key of a first table;
• v0 ∈ Fvm0 is a vector of an attribute value of the first table;
• k1 ∈ Fkm1 is a vector of a key of a second table;
• V1 ∈ Fvm1 is a vector of an attribute value of the second table;
• and π0 and π1 are predetermined permutations with lengths of m0 and m1, respectively,
• the secure joining information generation method comprising:
• a vector joining step in which a plurality of vector joining circuitries use a share [k0] of the vector k0 and a share [k1] of the vector k1 to generate a share [k] of a vector k ∈ [Fk]m0+m1 which is generated by joining the vector k0 and the vector k1;
• a first vector generation step in which a plurality of first vector generation circuitries generate a share [f] of a vector f which is generated by joining m0 0's and m1 1's;
• a first permutation calculation step in which a plurality of first permutation calculation circuitries use the share [k] to generate a share [σ] of a permutation σ for stable sorting of the vector k;
• a first permutation application step in which a plurality of first permutation application circuitries use the share [k], the share [σ], and the share [f] to generate a share [σ(k)] of a vector σ(k) which is generated by application of the permutation σ to the vector k and a share [σ(f)] of a vector σ(f) which is generated by application of the permutation σ to the vector f;
• a second vector generation step in which a plurality of second vector generation circuitries use the share [σ(k)] to generate a share [e] of a vector e which has 1 when a certain element of the vector σ(k) and an element following that element are the same and has 0 when they are different as an element corresponding to that element;
• a third vector generation step in which a plurality of third vector generation circuitries use the share [e] to generate a share [e′] of a vector e′, which is generated by bit inversion of each element of a vector which has 1 when one of a certain element of the vector e and an element preceding that element is 1 and has 0 otherwise as an element corresponding to that element:
• a second permutation calculation step in which a plurality of second permutation calculation circuitries use the share [e′] to generate a share [σ′] of a permutation σ′ for stable sorting of the vector e′;
• a second permutation application step in which a plurality of second permutation application circuitries use the share [σ(f)] and the share [σ′] to generate a share [f′] of a vector f=σ′(σ(f)) which is generated by application of the permutation σ′ to the vector σ(f):
• a fourth vector generation step in which a plurality of fourth vector generation circuitries use the share [f′] to generate a share [s] of a vector s, each element of which is a sum of elements of the vector f′ up to an element corresponding to that element, the elements including the element corresponding to that element, and a share [s′] of a vector s′, each element of which is a sum of elements of a bit-inverted vector up to an element corresponding to that element, the elements including the element corresponding to that element, where the bit-inverted vector is a vector generated by bit inversion of each element of the vector f;
• a fifth vector generation step in which a plurality of fifth vector generation circuitries use the share [f′], the share [s], and the share [s′] to calculate a share [σ″] of a vector σ″=fs+(1−f)s′−1;
• a first inverse permutation application step in which a plurality of first inverse permutation application circuitries use the share [e′] and the share [σ] to generate a share [e″] of a vector e″=σ−1(e′) which is generated by application of an inverse permutation a-1 of the permutation σ to the vector e′:
• a first vector separation step in which a plurality of first vector separation circuitries use the share [e″] to generate a share [g0] of a vector g0 which is formed from first m0 elements of the vector e″ and a share [g1] of a vector g1 which is formed from remaining m1 elements of the vector e″;
• a second inverse permutation application step in which a plurality of second inverse permutation application circuitries use the share [σ″], the share [σ], and the share [σ′] to generate a share [σ′″−1] of a vector σ′″−1=σ−1(σ′−1(σ″)) which is generated by application of an inverse permutation σ′−1 of the permutation σ′ and the inverse permutation σ−1 of the permutation σ to the vector x;
• a second vector separation step in which a plurality of second vector separation circuitries use the share [σ′″−1] to generate a share [σ0−1] of a vector σ0−1 which is formed from first m0 elements of the vector σ′″−1 and a share [σ1−1] of a vector σ1−1 which is formed from remaining m1 elements of the vector σ′″−1;
• and
• a third permutation application step in which a plurality of third permutation application circuitries use the share [σ0−1], the share [σ1−1], a share [π0] of the permutation π0, and a share [π1] of the permutation π1 to generate a share [π0(σ0−1)] of a vector π0(σ0−1) which is generated by application of the permutation π0 to the vector σ0−1 and a share [π1(σ1−1)] of a vector π1(σ1−1) which is generated by application of the permutation π1 to the vector σ1−1, and release the π0(σ0−1) and the π1(σ1−1).

A secure joining method,

• where Fk and FR are arbitrary rings;
• [α] is a share generated by secret sharing of α, with α being an arbitrary vector or arbitrary permutation;
• m0 and m1 are integers greater than or equal to 1;
• k0 ∈ Fkm0 is a vector of a key of a first table;
• v0 ∈ Fvm0 is a vector of an attribute value of the first table;
• k1 ∈ Fkm1 is a vector of a key of a second table;
• V1 ∈ Fvm1 is a vector of an attribute value of the second table;
• and π0 and π1 are predetermined permutations with lengths of m0 and m1, respectively,
• the secure joining method comprising:
• a secure joining information generation step in which a plurality of secure joining information generation circuitries use a share [k0] of the vector k0, a share [k1] of the vector k1, a share [π0] of the permutation π0, and a share [π1] of the permutation π1 to generate:
• a share [π0(σ0−1)] of a vector π0(σ0−1) which is generated by application of the permutation π0 to an inverse permutation σ0−1 of a permutation σ0, where permutation of each vector of the first table with the permutation σ0 causes records for keys common to the first table and the second table to move to a head side;
• a share [π1(σ1−1)] of a vector π1(σ1−1) which is generated by application of the permutation π1 to an inverse permutation σ1−1 of a permutation σ1, where permutation of each vector of the second table with the permutation σ1 causes records for keys common to the first table and the second table to move to the head side;
• a share [g0] of a vector g0 which is formed from a value g0,i indicating whether the ith record of the first table is a record for a key that is common to the first table and the second table;
• and a share [g1] of a vector g1 which is formed from a value g1,i indicating whether the ith record of the second table is a record for a key that is common to the first table and the second table;
• a filtering step in which a plurality of filtering circuitries use the share [g1], the share [k1] of the vector k1, and the share [V1] of the vector v1 to generate a modified second table in which if g1,i=1, the ith element of the key of the second table is set to a predefined value u1,k indicating null and the ith element of the attribute of the second table is set to a predefined value u1,v indicating null, where g1,i is the ith element of the vector g1;
• a fifth permutation application step in which a plurality of fifth permutation application circuitries use the share [k0] of the vector k0, a share [V0] of the vector v0, a share [k1′] of k1′, which is a vector of the key of the modified second table, a share [V1′] of v1′, which is a vector of the attribute value of the modified second table, the share [π0] of the permutation π0, the share [π1] of the permutation π1, the share [π0(σ0−1)], and the share [π1(σ1−1)] to calculate a share [k0′] of a vector k0′=(π0(σ0−1))−1(π0(k0))), a share [v0′] of a vector V0′=(π0(σ0−1))−1(π0(V0)), a share [k1″] of a vector k1″=(π1(σ1−1))−1(π1(k1′)), and a share [V1″] of a vector v1″=(π1(σ1−1))−1(π1(V1′));
• and
• a second joined table generation step in which a plurality of second joined table generation circuitries use the share [k0′], the share [V0′], the share [k1″], and the share [V1″] to generate, when m0<m1, a joined table which joins the vector k0′, the vector V0′, a vector generated by extracting first m0 elements of the vector k1″, and a vector generated by extracting first m0 elements of the vector v1″, and to generate, when m0>m1, a joined table which joins the vector k0′, the vector V0′, a vector generated by adding m0>m1 elements being a predefined value uk indicating null to the vector k1″, and a vector generated by adding m0-m1 elements being a predefined value uv indicating null to the vector v1″.

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 arbitrary permutation;
• m0 and m1 are integers greater than or equal to 1;
• k0 ∈ Fkm0 is a vector of a key of a first table;
• v0 ∈ Fv m0 is a vector of an attribute value of the first table:
• k1 ∈ Fkm1 is a vector of a key of a second table:
• v1 ∈ Fvm1 is a vector of an attribute value of the second table;
• and π0 and π1 are predetermined permutations with lengths of m0 and m1, respectively,
• the secure joining method comprising:
• a secure joining information generation step in which a plurality of secure joining information generation circuitries use a share [k0] of the vector k0, a share [k1] of the vector k1, a share [π0] of the permutation π0, and a share [π1] of the permutation π1 to generate:
• a share [π0(σ0−1)] of a vector π0(σ0−1) which is generated by application of the permutation π0 to an inverse permutation σ0−1 of a permutation σ0, where permutation of each vector of the first table with the permutation σ0 causes records for keys common to the first table and the second table to move to a head side;
• a share [π1(σ1−1)] of a vector π1(σ1−1) which is generated by application of the permutation π1 to an inverse permutation σ1−1 of a permutation σ1, where permutation of each vector of the second table with the permutation σ1 causes records for keys common to the first table and the second table to move to the head side:
• a share [g0] of a vector g0 which is formed from a value g0,i indicating whether the ith record of the first table is a record for a key that is common to the first table and the second table;
• and a share [g1] of a vector g1 which is formed from a value g1,i indicating whether the ith record of the second table is a record for a key that is common to the first table and the second table;
• a fourth permutation application step in which a plurality of fourth permutation application circuitries use the share [k0] of the vector k0, a share [V0] of the vector v0, the share [k1] of the vector k1, and a share [V1] of the vector v1 to calculate a share [k0′] of a vector k0′=(π0(σ0−1))−1(π0(k0))), a share [V0′] of a vector V0′=(π0(σ0−1))−1(π0(V0)), a share [k1′] of a vector k1′=(π1(σ1−1))−1(π1(k1′)), and a share [V1′] of a vector v1′=(π1(σ1−1))−1(π1(V1′));
• and
• a third joined table generation step in which a plurality of third joined table generation circuitries use the share [k0′], the share [V0′], the share [k1′], and the share [V1′] to generate a joined table which joins a table (1) which joins a vector generated by extracting first c elements of the vector k0′, a vector generated by extracting first c elements of the vector V0′, a vector generated by extracting first c elements of the vector k1′, and a vector generated by extracting first c elements of the vector v1′, a table (2) which joins a vector generated by extracting remaining m0-c elements of the vector k0′, a vector generated by extracting remaining m0-c elements of the vector V0′, and a vector having a value corresponding to the attribute value of the second table set to a predefined value u′1,v indicating null, and a table (3) which joins a vector generated by extracting remaining m0-c elements of the vector v0′, a vector generated by extracting remaining m1-c elements of the vector v1′, and a vector having a value corresponding to the attribute value of the first table set to a predefined value u′0,v indicating null, where c is the number of 0 elements in the vector g0 or the vector g1.