Secure aggregate sum system, secure computation apparatus, secure aggregate sum method, and program

1. A secure aggregate sum system comprising a plurality of secure computation apparatuses,

m being an integer equal to or greater than 2, [v]: =[v 0 ], . . . , [v m−1 ] being a share obtained by secret sharing a desired value attribute v: =v 0 , . . . , v m−1 when a table including a key attribute and a value attribute is sorted based on a value of the key attribute, [e]: =[e 0 ], . . . , [e m−1 ] being a share obtained by secret sharing a flag e: =e 0 , . . . , e m−1 indicating that a last element of each group is true and other elements are false when the table is grouped based on the value of the key attribute, {{σ}} being a share obtained by secret sharing a permutation σ which moves elements so that the last elements of each group are sequentially arranged from beginning when the table is grouped based on the value of the key attribute, and g being a maximum number of the groups,

each of the secure computation apparatuses comprising processing circuitry configured to securely:

generate a share [v′] which becomes a vector v′: =v′ 0 , . . . , v′ m−1 , when reconstructed, by setting a sum from v 0 to v i at for each integer i equal to or greater than 0 and equal to or less than m−1 using the share [v];

generate a share [t] which becomes a vector t: =t 0 , . . . , t m−1 , when reconstructed, by setting [v′ i ] at [t i ] if [e i ] is true, and setting [v′ m−1 ] at [t i ] if [e i ] is false for each integer i equal to or greater than 0 and equal to or less than m−1 using the share [v′] and the share [e];

generate a share [σ(t)] which becomes a sorted vector σ(t) obtained by sorting the vector t with the permutation σ, when reconstructed, using the share [t] and the share {{σ}}; and

generate a share [s] which becomes a vector s: =s 0 , . . . , s min(g, m)−1 representing a sum of a value attribute v for each group, when reconstructed, by setting [s i ]: =[σ(t) i −σ(t) i−1 ] for each integer i equal to or greater than 1 and equal to or less than min(g, m)−1, and setting [s 0 ]:=[σ(t) 0 ] using the share [σ(t)],

wherein the processing circuitry of said each of the plurality of secure computation apparatuses is configured to:

receive [v], [e] and {{σ}} through secret sharing, and

output the share [s].

2. The secure aggregate sum system according to claim 1 ,

wherein F is an arbitrary ring, nk is an integer equal to or greater than 1, [k 0 ], . . . , [k nk−1 ] are shares obtained by secret sharing key attributes k 0 , . . . , k nk−1 ∈F m , and [v″] is a share obtained by secret sharing a desired value attribute v″∈F m before the table is sorted based on the value of the key attribute, and

the processing circuitry is further configured to:

generate a share {{σ 0 }} which becomes a permutation σ 0 which stably sorts a bit string b in ascending order, when reconstructed, from a share {b} which becomes the bit string b: =b 0 , . . . , b m−1 , obtained by bit-decomposing and concatenating the key attributes k 0 , . . . , k nk−1 , when reconstructed, using the shares [k 0 ], . . . , [k nk−1 ];

generate a share {b′} which becomes a sorted bit string b′: =b′ 0 , . . . , b′ m−1 obtained by sorting the bit string b with the permutation σ 0 , when reconstructed, using the share {σ} and the share {{σ 0 }};

generate the share {e} which becomes the flag e: =e 0 , . . . , e m−1 , when reconstructed, by setting {e i }: ={b′ i ≠b′ i+1 } for each integer i equal to or greater than 0 and equal to or less than m−2, and setting {e m−1 }: ={1}, using the share {b′};

generate the share {{σ}} which becomes the permutation σ which stably sorts a negation e of the flag e in ascending order, when reconstructed, using the share {e}; and

generate a share [v] which becomes the value attribute v obtained by sorting the value attribute v″ with the permutation σ 0 , when reconstructed, using the share [v″] and the share {{σ 0 }}.

3. A secure computation apparatus,

m being an integer equal to or greater than 2, [v]: [v 0 ], . . . , [v m−1 ] being a share obtained by secret sharing a desired value attribute v: =v 0 , . . . , v m−1 when a table including a key attribute and a value attribute is sorted based on a value of the key attribute, [e]: =[e 0 ], . . . , [e m−1 ] being a share obtained by secret sharing a flag e: =e 0 , . . . , e m−1 indicating that a last element of each group is true and other elements are false when the table is grouped based on the value of the key attribute, {{σ}} being a share obtained by secret sharing a permutation σ which moves elements so that the last elements of each group are sequentially arranged from beginning when the table is grouped based on the value of the key attribute, and g being a maximum number of the groups,

the secure computation apparatus comprising processing circuitry configured to securely:

generate a share [V′] which becomes a vector v′: =v′ 0 , . . . , v′ m−1 , when reconstructed, by setting a sum from v 0 to v i at v′ i for each integer i equal to or greater than 0 and equal to or less than m−1 using the share [v];

generate a share [t] which becomes a vector t: =t 0 , . . . , t m−1 , when reconstructed, by setting [v′] at [t i ] if [e i ] is true, and setting [v′ m−1 at [t i ] if [e i ] is false for each integer i equal to or greater than 0 and equal to or less than m−1 using the share [V′] and the share [e];

generate a share [σ(t)] which becomes a sorted vector σ(t) obtained by sorting the vector t with the permutation σ, when reconstructed, using the share [t] and the share {{σ}}; and

generate a share [s] which becomes a vector s: =s 0 , . . . , s min(g, m)−1 representing a sum of value attributes v for each group, when reconstructed, by setting [s i ]: [σ(t) i −σ(t) i−1 ] for each integer i equal to or greater than 1 and equal to or less than min(g, m)−1 and setting [s 0 ]: =[σ(t) 0 ] using the share [σ(t)],

wherein the processing circuitry of said each of the plurality of secure computation apparatuses is configured to

receive [v], [e], and {{σ}} through secret sharing, and

output the share [s].

4. Secure aggregate sum method to be executed by a secure aggregate sum system comprising a plurality of secure computation apparatuses,

m being an integer equal to or greater than 2, [v]: =[v 0 ], . . . , [v m−1 ] being a share obtained by secret sharing a desired value attribute v: v 0 , . . . , v m−1 when a table including a key attribute and a value attribute is sorted based on a value of the key attribute, [e]: =[e 0 ], . . . , [e m−1 ] being a share obtained by secret sharing a flag e: =e 0 , . . . , e m−1 indicating that a last element of each group is true and other elements are false when the table is grouped based on the value of the key attribute, {{σ}} being a share obtained by secret sharing a permutation σ which moves elements so that the last elements of each group are sequentially arranged from beginning when the table is grouped based on the value of the key attribute, and g being a maximum number of the groups,

the secure aggregate sum method comprising securely:

generating, by processing circuitry of each of the secure computation apparatuses, a share [V′] which becomes a vector v′: =v′ 0 , . . . , v′ m−1 , when reconstructed, by setting a sum from v 0 to v i at v′ i for each integer i equal to or greater than 0 and equal to or less than m−1 using the share [v];

generating, by the processing circuitry of each of the secure computation apparatuses, a share [t] which becomes a vector t: =t 0 , . . . , t m−1 , when reconstructed, by setting [v′ i ] at [t i ] if [e i ] is true, and setting [v′ m−1 ] at [t i ] if [e i ] is false for each integer i equal to or greater than 0 and equal to or less than m−1 using the share [v′] and the share [e];

generating, by the processing circuitry of each of the secure computation apparatuses, a share [σ(t)] which becomes a sorted vector σ(t) obtained by sorting the vector t with the permutation σ, when reconstructed, using the share [t] and the share {{σ}}; and

generating, by the processing circuitry of each of the secure computation apparatuses, a share [s] which becomes a vector s: =s 0 , . . . , s min(g, m)−1 representing a sum of value attributes v for each group, when reconstructed, by setting [S i ]: =[σ(t) i −σ(t) i−1 ] for each integer i equal to or greater than 1 and equal to or less than min(g, m)−1, and setting [s 0 ]: =[σ(t) 0 ] using the share [σ(t)],

wherein the method further comprises:

receiving [v], [e], and {{σ}} through secret sharing, and

outputting the share [s].

5. A non-transitory computer-readable recording medium on which a program recorded thereon for causing a computer to function as the secure computation apparatus according to claim 3 .