Secure aggregate maximum system, secure aggregate minimum system, secure computation apparatus, secure aggregate maximum method, secure aggregate minimum method, and program

A secure aggregate minimum system comprising a plurality of secure computation apparatuses,

• m being an integer equal to or greater than 2, [v]:=[v0], . . . , [vm−1] being a share obtained by secret sharing a desired value attribute v:=v0, . . . , vm−1 when a table including a key attribute and a value attribute is stably sorted based on a value of the value attribute and a value of the key attribute, [e]:=[e0], . . . , [em−1] being a share obtained by secret sharing a flag e:=e0, . . . , em−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:
• generate a share [e′] which becomes a flag e′:=e′0, . . . , e′m−1, when reconstructed, by setting [ei−1] at [e′i] and setting true at [e′0] for each integer i equal to or greater than 1 and equal to or less than m−1 using the share [e];
• generate a share [f′] which becomes a vector f′:=f′0, . . . , f′m−1, when reconstructed, by setting [vi] at [f′i] if [e′i] is true, and setting a predetermined fixed value at [f′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 [σ(f′)] which becomes a sorted vector σ(f′) obtained by sorting the vector f′ with the permutation σ, when reconstructed, using the share [f′] and the share {{σ}};
• and
• generate a share [x′] which becomes a vector x′:=σ(f′)0, . . . , σ(f′)min(g, m)−1 representing a minimum of each group, when reconstructed, using the share [σ(f′)].

A secure computation apparatus,

• m being an integer equal to or greater than 2, [v]:=[v0], . . . , [vm−1] being a share obtained by secret sharing a desired value attribute v:=v0, . . . , when a table including a key attribute and a value attribute is stably sorted based on a value of the value attribute and a value of the key attribute, [e]:=[e0], . . . , [em−1] being a share obtained by secret sharing a flag e:=e0, . . . , em−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:
• generate a share [f] which becomes a vector f:=f0, . . . , fm−1, when reconstructed, by setting [vi] at [fi] if [ei] is true, and setting a predetermined fixed value at [fi] if [ei] 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 [σ(f)] which becomes a sorted vector σ(f) obtained by sorting the vector f with the permutation σ, when reconstructed, using the share [f] and the share {{σ}}, and
• generate a share [x] which becomes a vector x:=σ(f)0, . . . , σ(f)min(g,m)−1 representing a maximum of each group, when reconstructed, using the share [σ(f)].

A secure computation apparatus,

• m being an integer equal to or greater than 2, [v]:=[v0], . . . , [vm−1] being a share obtained by secret sharing a desired value attribute v:=v0, . . . , vm−1 when a table including a key attribute and a value attribute is stably sorted based on a value of the value attribute and a value of the key attribute, [e]:=[e0], . . . , [em−1] being a share obtained by secret sharing a flag e:=e0, . . . , em−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:
• generate a share [e′] which becomes a flag e′:=e′0, . . . , e′m−1, when reconstructed, by setting [ei−1] at [e′i] for each integer i equal to or greater than 1 and equal to or less than m−1 and setting true at [e′0] using the share [e];
• generate a share [f′] which becomes a vector f′:=f′0, . . . , f′m−1, when reconstructed, by setting [vi] at [f′i] if [e′i] is true, and setting a predetermined fixed value at [f′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 [σ(f′)] which becomes a sorted vector σ(f′) obtained by sorting the vector f′ with the permutation σ, when reconstructed, using the share [f′] and the share {{σ}};
• and
• generate a share [x′] which becomes a vector x′:=σ(f′)0, . . . , σ(f′)min(g,m)−1 representing a minimum of each group, when reconstructed, using the share [σ(f′)].

A secure aggregate maximum method to be executed by a secure aggregate maximum system comprising a plurality of secure computation apparatuses,

• m being an integer equal to or greater than 2, [v]:=[v0], . . . , [vm−1] being a share obtained by secret sharing a desired value attribute v:=v0, . . . , vm−1 when a table including a key attribute and a value attribute is stably sorted based on a value of the value attribute and a value of the key attribute, [e]:=[e0], . . . , [em−1] being a share obtained by secret sharing a flag e:=e0, . . . , em−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 a 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 maximum method comprising:
• generating, by processing circuitry of each of the secure computation apparatuses, a share [f] which becomes a vector f:=f0, . . . , fm−1, when reconstructed, by setting [vi] at [fi] if [ei] is true, and setting a predetermined fixed value at [fi] if [ei] 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 [σ(f)] which becomes a sorted vector σ(f) obtained by sorting the vector f with the permutation σ, when reconstructed, using the share [f] and the share {{σ}}, and
• generating, by the processing circuitry of each of the secure computation apparatuses, a share [x] which becomes a vector x:=σ(f)0, . . . , σ(f)min(g,m)−1 representing a maximum of each group, when reconstructed, using the share [σ(f)].

A secure aggregate minimum method to be executed by a secure aggregate minimum system comprising a plurality of secure computation apparatuses,

• m being an integer equal to or greater than 2, [v]:=[v0], . . . , [vm−1] being a share obtained by secret sharing a desired value attribute v:=v0, . . . , vm−1 when a table including a key attribute and a value attribute is stably sorted based on a value of the value attribute and a value of the key attribute, [e]:=[e0], . . . , [em−1] being a share obtained by secret sharing a flag e:=e0, . . . , em−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 of the group,
• the secure aggregate minimum method comprising:
• generating, by processing circuitry of each of the secure computation apparatuses, a share [e′] which becomes a flag e′:=e′0, . . . , e′m−1, when reconstructed, by setting [ei−1] at [e′i] for each integer i equal to or greater than 1 and equal to or less than m−1 and setting true at [e′0] using the share [e];
• generating, by the processing circuitry of each of the secure computation apparatuses, a share [f′] which becomes a vector f′:=f′0, . . . , f′m−1, when reconstructed, by setting [vi] at [f′i] if [e′i] is true, and setting a predetermined fixed value at [f′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 [σ(f′)] which becomes a sorted vector σ(f′) obtained by sorting the vector f′ with the permutation σ, when reconstructed, using the share [f′] and the share {{σ}};
• and
• generating, by the processing circuitry of each of the secure computation apparatuses, a share [x′] which becomes a vector x′:=σ(f′)0, . . . , σ(f′)min(g, m)−1 representing a minimum of each group, when reconstructed, using the share [σ(f′)].