Secure aggregate function computation system, secure computation apparatus, secure aggregate function computation method, and program
View Patent ↗To efficiently determine intermediate data for use with an aggregate function while keeping confidentiality, a bit decomposition unit generates a share of a bit string by bit decomposition and concatenation of key attributes. A group sort generation unit generates a share of a first permutation, which performs a stable sort of the bit string in ascending order. A bit string sorting unit generates a share of a sorted bit string obtained by sorting the bit string with the first permutation. A flag generation unit generates a share of a flag indicating a boundary between groups. A key aggregate sort generation unit generates a share of a second permutation, which performs a stable sort of the negation of the flag in ascending order. A de-duplication unit generates shares of de-duplicated key attributes. A key sorting unit generates shares of sorted key attributes by sorting the de-duplicated key attributes.
1. A secure aggregate function computation system comprising:
a plurality of secure computation apparatuses, wherein
F is an arbitrary ring; m is an integer greater than or equal to 2; n k is an integer greater than or equal to 1; and [k 0 ], . . . , [k nk−1 ] are shares obtained by secret sharing of key attributes k 0 , . . . , k nk−1 ∈F m , and
each of the secure computation apparatuses comprising processing circuitry configured to:
generate, from a share {b} which becomes a bit string b:=b 0 , . . . , b m−1 obtained by bit decomposition and concatenation of the key attributes k 0 , . . . , k nk−1 when reconstructed, a share {{σ 0 }} that becomes a permutation σ 0 for performing a stable sort of the bit string b in ascending order when reconstructed, using the shares [k 0 ], . . . , [k nk−1 ],
generate a share {b′} that becomes a sorted bit string b′:=b′ 0 , . . . , b′ m−1 which is the bit string b as sorted by the permutation σ 0 when reconstructed, using the share {b} and the share {{σ 0 }},
generate a share {e} that becomes a flag e:=e 0 , . . . , e m−1 when reconstructed, using the share {b′}, by setting {e i }:={b′ i ≠b′ i+1 } for each integer i greater than or equal to 0 and smaller than or equal to m−2 and also setting {e m−1 }:={1},
generate a share {{σ}} that becomes a permutation σ for performing a stable sort of negation ¬e of the flag e in ascending order when reconstructed, using the share {e}, and
output at least one of share {e} and the share {{σ}} as intermediate data which is required for one or more group-by operations that are subsequently calculated.
2. The secure aggregate function computation system according to claim 1 , wherein
n a is an integer greater than or equal to 1; and [v 0 ], . . . , [v na−1 ] are shares obtained by secret sharing of value attributes v 0 , . . . , v na−1 ∈F m , and
the processing circuitry is further configured to:
generate shares [k″ 0 ], . . . , [k″ nk−1 ] that become de-duplicated key attributes k″ 0 , . . . , k″ nk−1 when reconstructed, using the share {e}, by setting [k j,i ] into [k″ j,i ] when {e i }={1} and setting a predetermined constant into [k″ j,i ] when {e i }≠{1} for each integer i greater than or equal to 0 and smaller than or equal to m−1 and for each integer j greater than or equal to 0 and smaller than or equal to n k −1,
generate shares [k′ 0 ], . . . , [k′ nk−1 ] that become sorted key attributes k′ 0 , . . . , k′ nk−1 which are the de-duplicated key attributes k″ 0 , . . . , k″ nk−1 as sorted by the permutation σ 0 and the permutation σ in sequence when reconstructed, using the shares [k″ 0 ], . . . , [k″ nk−1 ], the share {{σ 0 }}, and the share {{σ}},
generate shares [v′ 0 ], . . . , [v′ na−1 ] that become sorted value attributes v′ 0 , . . . , v′ na−1 which are the value attributes v 0 , . . . , v na−1 as sorted by the permutation σ 0 when reconstructed, using the shares [v 0 ], . . . , [v na−1 ] and the share {{σ 0 }}, and
output at least one of share {e}, the share {{σ}}, shares [k′ 0 ], . . . , [k′ nk−1 ] and shares [v′ 0 ], . . . , [v′ na−1 ] as intermediate data which is required for one or more group-by operations that are subsequently calculated.
3. A secure computation apparatus,
where F is an arbitrary ring; m is an integer greater than or equal to 2; n k is an integer greater than or equal to 1; and [k 0 ], . . . , [k nk−1 ] are shares obtained by secret sharing of key attributes k 0 , . . . , k nk−1 ∈F m ,
the secure computation apparatus comprising processing circuitry configured to:
generate, from a share {b} which becomes a bit string b:=b 0 , . . . , b m−1 obtained by bit decomposition and concatenation of the key attributes k 0 , . . . , k nk−1 when reconstructed, a share {{σ 0 }} that becomes a permutation σ 0 for performing a stable sort of the bit string b in ascending order when reconstructed, using the shares [k 0 ], . . . , [k nk−1 ];
generate a share {b′} that becomes a sorted bit string b′:=b′ 0 , . . . , b′ m−1 which is the bit string b as sorted by the permutation σ 0 when reconstructed, using the share {b} and the share {{σ 0 }};
generate a share {e} that becomes a flag e:=e 0 , . . . , e m−1 when reconstructed, using the share {b′}, by setting {e i }:={b′ i ≠b′ i+1 } for each integer i greater than or equal to 0 and smaller than or equal to m−2 and also setting {e m−1 }:={1};
generate a share {{σ}} that becomes a permutation σ for performing a stable sort of negation ¬e of the flag e in ascending order when reconstructed, using the share {e}, and
output at least one of share {e} and the share {{σ}} as intermediate data which is required for one or more group-by operations that are subsequently calculated.
4. A non-transitory computer-readable recording medium on which a program is recorded that, when executed on a computer, controls the computer to function as the secure computation apparatus according to claim 3 .
5. A secure aggregate function computation method for execution by a secure aggregate function computation system including a plurality of secure computation apparatuses, wherein
F is an arbitrary ring; m is an integer greater than or equal to 2; n k is an integer greater than or equal to 1; and [k 0 ], . . . , [k nk−1 ] are shares obtained by secret sharing of key attributes k 0 , . . . , k nk−1 ∈F m ,
the secure aggregate function computation method comprising:
generating, by processing circuitry of each of the secure computation apparatuses, from a share {b} which becomes a bit string b:=b 0 , . . . , b m−1 obtained by bit decomposition and concatenation of the key attributes k 0 , . . . , k nk−1 when reconstructed, a share {{σ 0 }} that becomes a permutation σ 0 for performing a stable sort of the bit string b in ascending order when reconstructed, using the shares [k 0 ], . . . , [k nk−1 ],
generating, by the processing circuitry of each of the secure computation apparatus, a share {b′} that becomes a sorted bit string b′:=b′ 0 , . . . , b′ m−1 which is the bit string b as sorted by the permutation σ 0 when reconstructed, using the share {b} and the share {{σ 0 }},
generating, by the processing circuitry of each of the secure computation apparatus, a share {e} that becomes a flag e:=e 0 , . . . , e m−1 when reconstructed, using the share {b′}, by setting {e i }:={b′ i ≠b′ i+1 } for each integer i greater than or equal to 0 and smaller than or equal to m−2 and also setting {e m−1 }:={1},
generating, by the processing circuitry of each of the secure computation apparatus generates a share {{σ}} that becomes a permutation σ for performing a stable sort of negation ¬e of the flag e in ascending order when reconstructed, using the share {e}, and
output at least one of share {e} and the share {{σ}} as intermediate data which is required for one or more group-by operations that are subsequently calculated.