Secret joining system, method, secret calculation apparatus and program

1. A secure joining system comprising:

a plurality of secure computation apparatuses, wherein

F is an arbitrary ring, [α] represents shares obtained by α being secret-shared while maintaining confidentiality when α is an arbitrary vector, {{β}} represents shares obtained by β being secret-shared while maintaining confidentiality when β is an arbitrary permutation, m 0 , m 1 , L 0 and L 1 are integers equal to or larger than 1, k 0 ∈F m0 is a vector of keys of a first table, k 1 ∈F m1 is a vector of keys of a second table, v 0,p ∈F m0 is a vector of attribute values of attributes p of the first table when p=0, . . . , L 0 −1 is assumed, v 1,q ∈F m1 is a vector of attribute values of attributes q of the second table when q=0, . . . , L 1 −1 is assumed, and π 0 and π 1 are predetermined permutations of lengths m 0 and m 1 , respectively; and

the plurality of secure computation apparatuses comprise:

processing circuitry configured to

generate shares [k′] of a vector k′∈[F] m0+m1 obtained by joining the vector k 0 and the vector k 1 , using shares [k 0 ] of the vector k 0 and shares [k 1 ] of the vector k 1 ;

generate shares {{σ}} of a permutation σ that performs stable sorting of the vector k′ in ascending order, using the shares [k′];

generate shares [σ(k′)] of a vector σ(k′) obtained by applying the permutation σ to the vector k′, using the shares [k′] and the shares {{σ}};

generate shares [e] of a vector e that has 1 as an element corresponding to a certain element of the vector σ(k′) if the certain element and an element next to the certain element are the same and has 0 as the element corresponding to the certain element if the certain element and the element next to the certain element are different, using the shares [σ(k′)];

generate shares [e′] of a vector e′ that has 1 as an element corresponding to a certain element of the vector e if one of the certain element and an element before the certain element is 1 and, otherwise, has 0 as the element corresponding to the certain element, using the shares [e];

generate shares [e″] of a vector e″ obtained by bit-flipping each element of the vector e′, using the shares [e′];

generate shares {{σ′}} of a permutation σ′ that performs stable sorting of the vector e″ in ascending order, using the shares [e″];

generate shares [σ′(e″)] of a vector σ′(e″) obtained by applying the permutation σ′ to the vector e″, using the shares [e″] and the shares {{σ′}};

generate shares [x] of a vector x that has └ i/2 ┘ as an element corresponding to a certain element i of the vector σ′(e″) if the certain element i is 0 and has 0 as the element corresponding to the certain element i if the certain element i is not 0, using the shares [σ′(e″)];

generate shares [σ −1 (σ′ −1 (x))] of a vector σ −1 (σ′ −1 (x)) obtained by applying an inverse permutation σ′ −1 of the permutation σ′ and an inverse permutation σ −1 of the permutation σ to the vector x, using the shares [x], the shares {{σ}} and the shares {{σ′}};

generate shares [s 0 ] of a vector s 0 composed of m 0 elements from the top of the vector σ −1 (σ′ −1 (x)) and shares [s 1 ] of a vector s 1 composed of remaining m 1 elements of the vector σ −1 (σ′ −1 (x)), using the shares [σ −1 (σ′ −1 (x))];

generate shares [π 0 (s 0 )] of a vector τ 0 :=π 0 (s 0 ) obtained by applying a permutation π 0 to the vector s 0 and shares [π 1 (s 1 )] of a vector τ 1 :=π 1 (s 1 ) obtained by applying a permutation π 1 to the vector s 1 , using the shares [s 0 ], the shares [s 1 ] and the permutations π 0 and π 1 , and publishing τ 0 :=π 0 (s 0 ) and τ 1 :=π 1 (s 1 );

generate shares [v′ 0,p ] of a vector v′ 0,p obtained by permutating a vector v 0,p of attribute values of the attributes p of the first table by the permutation π 0 and shares [v′ 1,q ] of a vector v′ 1,q obtained by permutating a vector v 1,q of attribute values of the attributes q of the second table by the permutation π 1 , using the shares {{π 0 }} of the permutation π 0 , the shares {{π 1 }} of the permutation π 1 , the shares [v 0,p ] of the vector v 0,p and the shares [v 1,q ] of the vector v 1,q ; and

generate shares [v″ 0,p ] of a vector v″ 0,p that has the i′-th element of the vector v′ 0,p as the (i′−1)th element if the i′-th element of the vector τ 0 is not 0, and shares [v″ 1,q ] of a vector v″ 1,q that has the i′-th element of the vector v′ 1,q as the (i′−1)th element if the i′-th element of the vector τ 1 is not 0, using the vector τ 0 , the vector τ 1 , the shares [v′ 0,p ] and the shares [v′ 1,q ].

2. A secure joining method, wherein

F is an arbitrary ring, [α] represents shares obtained by α being secret-shared while maintaining confidentiality when α is an arbitrary vector, {{β}} represents shares obtained by β being secret-shared while maintaining confidentiality when β is an arbitrary permutation, m 0 , m 1 , L 0 and L 1 are integers equal to or larger than 1, k 0 ∈F m0 is a vector of keys of a first table, k 1 ∈F m1 is a vector of keys of a second table, v 0,p ∈F m0 is a vector of attribute values of attributes p of the first table when p=0, . . . , L 0 −1 is assumed, v 1,q ∈F m1 is a vector of attribute values of attributes q of the second table when q=0, . . . , L 1 −1 is assumed, and π 0 and π 1 are predetermined permutations of lengths m 0 and m 1 , respectively; and

the secure joining method comprises:

a vector joining step of a plurality of vector joining parts generating shares [k′] of a vector k′∈[F] m0+m1 obtained by joining the vector k 0 and the vector k 1 , using shares [k 0 ] of the vector k 0 and shares [k 1 ] of the vector k 1 ;

a first permutation calculating step of a plurality of first permutation calculating parts generating shares {{σ}} of a permutation a that performs stable sorting of the vector k′ in ascending order, using the shares [k′];

a first permutation applying step of a plurality of first permutation applying parts generating shares [σ(k′)] of a vector σ(k′) obtained by applying the permutation σ to the vector k′, using the shares [k′] and the shares {{σ}};

a first vector generating step of a plurality of first vector generating parts generating shares [e] of a vector e that has 1 as an element corresponding to a certain element of the vector σ(k′) if the certain element and an element next to the certain element are the same and has 0 as the element corresponding to the certain element if the certain element and the element next to the certain element are different, using the shares [σ(k′)];

a second vector generating step of a plurality of second vector generating parts generating shares [e′] of a vector e′ that has 1 as an element corresponding to a certain element of the vector e if one of the certain element and an element before the certain element is 1 and, otherwise, has 0 as the element corresponding to the certain element, using the shares [e];

a bit-flipping step of a plurality of bit-flipping parts generating shares [e″] of a vector e″ obtained by bit-flipping each element of the vector e′, using the shares [e′];

a second permutation calculating step of a plurality of second permutation calculating parts generating shares {{σ′}} of a permutation σ′ that performs stable sorting of the vector e″ in ascending order, using the shares [e″];

a second permutation applying step of a plurality of second permutation applying parts generating shares [σ′(e″)] of a vector σ′(e″) obtained by applying the permutation σ′ to the vector e″, using the shares [e″] and the shares {{σ′}};

a third vector generating step of a plurality of third vector generating parts generating shares [x] of a vector x that has └i/ 2 ┘ as an element corresponding to a certain element i of the vector σ′(e″) if the certain element i is 0 and has 0 as the element corresponding to the certain element i if the certain element i is not 0, using the shares [σ′(e″)];

an inverse permutation applying step of a plurality of inverse permutation applying parts generating shares [σ −1 (σ′ −1 (x))] of a vector σ −1 (σ′ −1 (x)) obtained by applying an inverse permutation σ′ −1 of the permutation σ′ and an inverse permutation σ −1 of the permutation σ to the vector x, using the shares [x], the shares {{σ}} and the shares {{σ′}};

a vector separating step of a plurality of vector separating parts generating shares [s 0 ] of a vector s 0 composed of m 0 elements from the top of the vector σ −1 (σ′ −1 (x)) and shares [s 1 ] of a vector s 1 composed of remaining m 1 elements of the vector σ −1 (σ′ −1 (x)), using the shares [σ −1 (σ′ −1 (x))];

a third permutation applying step of a plurality of third permutation applying parts generating shares [π 0 (s 0 )] of a vector τ 0 :=π 0 (s 0 ) obtained by applying a permutation π 0 to the vector s 0 and shares [π 1 (s 1 )] of a vector τi:=π 1 (s 1 ) obtained by applying a permutation π 1 to the vector s 1 , using the shares [s 0 ], the shares [s 1 ] and the permutations π 0 and π 1 , and publishing τ 0 :=π 0 (s 0 ) and τ 1 :=π 1 (s 1 );

an attribute value permutating step of a plurality of attribute value permutating parts generating shares [v′ 0,p ] of a vector v′ 0,p obtained by permutating a vector v 0,p of attribute values of the attributes p of the first table by the permutation π 0 and shares [v′ 1,q ] of a vector v′ 1,q obtained by permutating a vector v 1,q of attribute values of the attributes q of the second table by the permutation π 1 , using the shares {{π 0 }} of the permutation π 0 , the shares {{π 1 }} of the permutation π 1 , the shares [v 0,p] of the vector v 0,p and the shares [v 1,q ] of the vector v 1,q ; and

a fourth vector generating step of a plurality of fourth vector generating parts generating shares [v″ 0,p ] of a vector v″ 0,p that has the i′-th element of the vector v′ 0,p as the (i′−1)th element if the i′-th element of the vector τ 0 is not 0, and shares [v″ 1,q ] of a vector v″ 1,q that has the i′-th element of the vector v′ 1,q as the (i′−1)th element if the i′-th element of the vector τ 1 is not 0, using the vector τ 0 , the vector τ 1 , the shares [v′ 0,p ] and the shares [v′ 1,q ].

3. One or more non-transitory computer readable medium that store a program for causing one or more computers to perform the method of claim 2 .