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

A secure aggregate order 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 cross tabulation v:
• =v0, . . . , vm−1 in which the number of records of each group when a table including a key attribute and a value attribute is grouped based on a value of the key attribute is set at elements corresponding to the number of groups from the head, and {{σ}} being a share obtained by secret sharing a permutation a which moves elements so that last elements of each group are sequentially arranged from beginning when the table is grouped based on the value of the key attribute,
• each of the secure computation apparatuses comprising processing circuitry configured to:
• generate a share [v′] which becomes a shifted cross tabulation v′:
• =v′0, . . . , v′m−1, when reconstructed, by setting [v′]:
• =[vi+1] for each integer i equal to or greater than 0 and equal to or less than m−2 and setting [vm−1]:
• =[σ′] using the share [v];
• generate a share [u′]:
• =[σ−1(v)] which becomes an inversely permutated cross tabulation u′:
• =σ−1(V) obtained by inversely applying the permutation a to the shifted cross tabulation v′, when reconstructed, using the share [v′] and the share {{σ}};
• generate a share [s′] which becomes a vector s′:
• =s′0, . . . , s′m−1 ∈ F, when reconstructed, by setting a sum from [di] to [u′m−i] at [s′i] for each integer i equal to or greater than 0 and equal to or less than m−1 using the share [u′];
• and
• generate a share [x′] which becomes a vector x′:
• =x′0, . . . , x′m−1 representing descending order within a group, when reconstructed, by setting [x′i]:
• =[m−i−s′i−1] for each integer i equal to or greater than 1 and equal to or less than m−1 using the share [s′].

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 cross tabulation v:
• =v0, . . . , vm−1 in which the number of records of each group when a table including a key attribute and a value attribute is grouped based on a value of the key attribute is set at elements corresponding to the number of groups from the head, and {{σ}} being a share obtained by secret sharing a permutation a which moves elements so that last elements of each group are sequentially arranged from beginning when the table is grouped based on the value of the key attribute,
• the secure computation apparatus comprising processing circuitry configured to:
• generate a share [u]:
• =[σ−1(v)] which becomes an inversely permutated cross tabulation u:
• =σ−1(v) obtained by inversely applying the permutation σ to the cross tabulation v, when reconstructed, using the share [v] and the share {{σ}};
• generate a share [s] which becomes a vector s:
• =s0, . . . , sm−1 ∈ F, when reconstructed, by setting a sum from [u0] to [ui] at [si] for each integer i equal to or greater than 0 and equal to or less than m−1 using the share [u];
• and
• generate a share [x] which becomes a vector x:
• =x0, . . . , xm−1 representing ascending order within a group, when reconstructed, by setting [xi]:
• =[i−si−1] for each integer i equal to or greater than 1 and equal to or less than m−1 and setting [x0]:
• =[0] using the share [s].

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 cross tabulation v:
• =v0, . . . , vm−1 in which the number of records of each group when a table including a key attribute and a value attribute is grouped based on a value of the key attribute is set at elements corresponding to the number of groups from the head, and {{σ}} being a share obtained by secret sharing a permutation σ which moves elements so that last elements of each group are sequentially arranged from beginning when the table is grouped based on the value of the key attribute,
• the secure computation apparatus comprising processing circuitry configured to:
• generate a share [v′] which becomes a shifted cross tabulation v′:
• =v′0, . . . , v′m−1, when reconstructed, by setting [v′i]:
• =[vi+1] for each integer i equal to or greater than 0 and equal to or less than m−2 and setting [v′m−1]:
• =[0] using the share [v];
• generate a share [u′]:
• =[σ−1(v′)] which becomes an inversely permutated cross tabulation u′:
• =σ−1(v′) obtained by inversely applying the permutation σ to the shifted cross tabulation v′, when reconstructed, using the share [V′] and the share {{σ}};
• generate a share [s′] which becomes a vector s′:
• =s′0, . . . , s′m−1 ∈ F, when reconstructed, by setting a sum from [u′i] to [u′m−1] at [s′i] for each integer i equal to or greater than 0 and equal to or less than m−1 using the share [u′];
• and
• generate a share [x′] which becomes a vector x′:
• =x′0, . . . , x′m−1 representing descending order within a group, when reconstructed, by setting [x′i]:
• =[m−i−s′i−1] for each integer i equal to or greater than 1 and equal to or less than m−1 using the share [s′].

A secure aggregate order method to be executed by a secure aggregate order 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 cross tabulation v:
• =v0, . . . , vm−1 in which the number of records of each group when a table including a key attribute and a value attribute is grouped based on a value of the key attribute is set at elements corresponding to the number of groups from the head, and {{σ}} being a share obtained by secret sharing σ permutation a which moves elements so that last elements of each group are sequentially arranged from beginning when the table is grouped based on the value of the key attribute,
• the secure aggregate order method comprising:
• generating, by processing circuitry of each of the secure computation apparatuses, a share [u]:
• =[σ−1(v)] which becomes an inversely permutated cross tabulation u:
• =σ−1(v) obtained by inversely applying the permutation σ to the cross tabulation v, when reconstructed, using the share [v] and the share {{σ}};
• generating, by the processing circuitry of each of the secure computation apparatuses, a share [s] which becomes a vector s:
• =s0, . . . , sm−1 ∈ F, when reconstructed, by setting a sum from [u0] to [ui] at [si] for each integer i equal to or greater than 0 and equal to or less than m−1 using the share [u];
• and
• generating, by the processing circuitry of each of the secure computation apparatuses, a share [x] which becomes a vector x:
• =x0, . . . , xm−1 representing ascending order within a group, when reconstructed, by setting [xi]:
• =[i−si−1] for each integer i equal to or greater than 1 and equal to or less than m−1 and setting [x0]:
• =[0] using the share [s].

A secure aggregate order method to be executed by a secure aggregate order 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 cross tabulation v:
• =v0, . . . , vm−1 in which the number of records of each group when a table including a key attribute and a value attribute is grouped based on a value of the key attribute is set at elements corresponding to the number of groups from the head, and {{σ}} being a share obtained by secret sharing a permutation a which moves elements so that last elements of each group are sequentially arranged from beginning when the table is grouped based on the value of the key attribute,
• the secure aggregate order method comprising:
• generating, by processing circuitry of each of the secure computation apparatuses, a share [v′] which becomes a shifted cross tabulation v′:
• =v′0, . . . , v′m−1, when reconstructed, by setting [v′i:
• =[vi+] ] for each integer i equal to or greater than 0 and equal to or less than m−2 and setting [v′m−1]:
• =[0] using the share [v];
• generating, by the processing circuitry of each of the secure computation apparatuses, a share [u′]:
• =[σ−1(v′)] which becomes an inversely permutated cross tabulation u′:
• =σ−1(V) obtained by inversely applying the permutation a to the shifted cross tabulation v′, when reconstructed, using the share [V′] and the share {{σ}};
• generating, by the processing circuitry of each of the secure computation apparatuses, a share [s′] which becomes a vector s′:
• =s′0, . . . , s′m−1 ∈ F, when reconstructed, by setting a sum from [u′i] to [u′m−i ] at [s′i] for each integer i equal to or greater than 0 and equal to or less than m−1 using the share [u′];
• and
• generating, by the processing circuitry of each of the secure computation apparatuses, a share [x′] which becomes a vector x′:
• =x′0, . . . , x′m−1 representing descending order within a group, when reconstructed, by setting [x′i]:
• =[m−i−s′i−1] for each integer i equal to or greater than 1 and equal to or less than m−1 using the share [s′].