Secure computation apparatus, secure computation method, and program

A secure computation method for performing arithmetic operations while keeping a database including a key column k→ which is an attribute column and a data column v→ which is a value column concealed, wherein

• a group flag column g→ represents a vector in which a value becomes 1 at a position where a value of the key column changes, and a value becomes 0 at other positions,
• a share of a value x according to replicated secret sharing is represented as {x},
• a share of the value x according to Shamir secret sharing is represented as ((x)),
• a current row number is represented by i, a window frame start position is represented by s, and a window frame end position is represented by t,
• the number of rows of the key column and the data column is set to 1, and the current row number i is incremented by one each time all flag column generation processing ends in a range of 0 or more and less than 1, the secure computation method comprising:
• generating, with respect to a vector subVector ({g→}, s+1, i} obtained by extracting elements from an (s+1)-th element to an i-th element of {g→}, a bit column obtained by an OR operation performed on all bits from the i-th element of the vector sub Vector ({→}, s+1, i) to each position as a first half window frame flag column {wf→};
• generating, with respect to a vector subVector ({g→}, i+1, t}) obtained by extracting elements from an (i+1)-th element to a t-th element of {g→}, a bit column obtained by an OR operation performed on all bits from i+1th element of the vector subVector ({g→}, t+1, i) to each position as a second half window frame flag column {wl→};
• generating a window frame flag column {w→} by combining the first half window frame flag column {wf→} from the front side and the second half window frame flag column {wl→} from the rear side having {0} interposed between the first half window frame flag column {wf→} and the second half window frame flag column {wl→};
• generating an inverted window frame flag column {w′→} by performing a NOT operation on the window frame flag column {w→};
• converting the inverted window frame flag column {w′→} into an inverted window frame flag column ((w′→));
• and
• executing a product-sum operation on sub Vector ((v′→, s, t) obtained by extracting elements from s to t of a data column ((v′→)) obtained by sorting a data column ((v→)) in ascending order and the inverted window frame flag column (([w′→])).

A computer-readable non-transitory recording medium storing a computer-executable program instructions that when executed by a processor cause a computer to function as the secure computation apparatus for performing arithmetic operations while keeping a database including a key column k→ which is an attribute column and a data column v→ which is a value column concealed, wherein

• a group flag column g→ represents a vector in which a value becomes 1 at a position where a value of the key column changes, and a value becomes 0 at other positions,
• a share of a value x according to replicated secret sharing is represented as {x},
• a share of the value x according to Shamir secret sharing is represented as ((x)),
• a current row number is represented by i, a window frame start position is represented by s, and a window frame end position is represented by t,
• the number of rows of the key column and the data column is set to 1, and the current row number i is incremented by one each time all flag column generation processing ends in a range of 0 or more and less than 1, the secure computation apparatus comprising:
• processing circuitry configured to
• generate, with respect to a vector subVector ({g→}, s+1, i) obtained by extracting elements from an (s+1)-th element to an i-th element of {g→}, a bit column obtained by an OR operation performed on all bits from the i-th element of the vector subVector ({g→}, s+1, i) to each position as a first half window frame flag column {wf→};
• generate, with respect to a vector sub Vector ({g→}, i+1, t) obtained by extracting elements from an (i+1)-th element to a t-th element of {g→}, a bit column obtained by an OR operation performed on all bits from i+1th element of the vector subVector ({g→}, t+1, i) to each position as a second half window frame flag column {wl→};
• generate a window frame flag column {w→} by combining the first half window, frame flag column {wf→} from a front side and the second half window frame flag column {wl→} from a rear side having {0} interposed between the first half window frame flag column {wf→} and the second half window frame flag column {wl→};
• generate an inverted window frame flag column {w′→} by performing a NOT operation on the window frame flag column {w→};
• convert the inverted window frame flag column {w′→} into an inverted window frame flag column ((w′→));
• and
• execute a product-sum operation on sub Vector ((v′→)), s, t) obtained by extracting elements from s to t of a data column ((v′→)) obtained by sorting a data column ((v→)) in ascending order and the inverted window frame flag column ((w′→)).