Secure division system, secure computation apparatus, secure division method, and program

A secure computation apparatus for use in a secure division system that obtains a secret value representing a result of dividing N by D using a secret value [N] of N and a secret value [D] of D, where R is an integer not less than 3, L0 and L1 are non-negative integers, N is a real number not less than 0 and less than RL1, N is expressed in radix R, D is a natural number, N−L0, . . . , NL1−1 are values of respective digits from an L0th digit after the decimal point to an L1th digit of an integer part in R notation of N, j is each integer from L1−1 to −L0, and L1 is related to the integer part of N and −L0 to L1−1 is related to the fractional part of N, the secure computation apparatus comprising processing circuitry that, in cooperative computation with other secure computation apparatuses:

• sets a secret value [PL1] of a partial remainder PL1 to 0;
• computes secret values [E1], . . . , [ER−1] of comparison results E1, . . . , ER−1 of comparing a secret value [n] of a partial divisor n=Pj+1R+Nj with [D]×g for each integer g not less than 1 and less than R in parallel;
• computes a secret value [Qj] of a quotient Qj and a secret value [Pj] of a partial remainder Pj that satisfy n=DQj+Pj using the secret values [E1], . . . , [ER−1] of the comparison results E1, . . . , ER−1;
• and
• outputs a corresponding one of the secret values [Q−L0] to [QL1−1] of the quotients Q−L0 to QL1−1.

A secure division method for execution by a secure division system comprising a plurality of secure computation apparatuses, the secure division system being used to obtain a secret value representing a result of dividing N by D using a secret value [N] of N and a secret value [D] of D by cooperation of the secure computation apparatuses, where R is an integer not less than 3, L0 and L1 are non-negative integers, N is a real number not less than 0 and less than RL1, N is expressed in radix R, D is a natural number, N−L0, . . . , NL1−1 are values of respective digits from an L0th digit after the decimal point to an L1th digit of an integer part in R notation of N, j is each integer from L1−1 to −L0, and L1 is related to the integer part of N and −L0 to L1−1 is related to the fractional part of N, the secure division method comprising:

• setting a secret value [PL1] of a partial remainder PL1 to 0 with processing circuitry of each secure computation apparatus;
• computing secret values [E1], . . . , [ER−1] of comparison results E1, . . . , ER−1 of comparing a secret value [n] of a partial divisor n=Pj+1R+Nj with [D]×g for each integer g not less than 1 and less than R in parallel with the processing circuitry of each secure computation apparatus;
• computing a secret value [Qj] of a quotient Qj and a secret value [Pj] of a partial remainder Pj that satisfy n=DQj+Pj using the secret values [E1], . . . , [ER−1] of the comparison results E1, . . . , ER−1 with the processing circuitry of each secure computation apparatus;
• and
• outputting the secret values [Q−L0] to [QL1−1] of the quotients Q−L0 to QL1−1 with the processing circuitry of each secure computation apparatus.