Secure square root computation system, secure normalization system, methods therefor, secure computation apparatus, and program

1 . A secure square root computation system for receiving a share value [a] of a value a as an input, and calculating a share value [√a] of a square root of the value a, the secure square root computation system comprising:

a plurality of secure computation apparatuses,

wherein λ is a decimal point position of the value a, and λ′ is the smallest integer equal to or greater than λ/2, and each of the plurality of secure computation apparatuses comprises:

processing circuitry configured to:

generate, in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over a network, a first sequence of share values {x 0 }, . . . , {x λ−1 } of a flag sequence x 0 , . . . , x λ−1 indicating a most significant bit of the value a;

calculate, in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, an exclusive logical sum of share values {x 2i } and share values {x 2i+1 } of the first sequence of share values to obtain share values {y i } of a bit y i to generate a second sequence of share values {y 0 }, . . . , {y λ′−1 } of a bit sequence y 0 , . . . , y λ′−1 where i is an integer equal to or greater than 0 and smaller than λ′;

calculate, in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, an exclusive logical sum of all share values {x j } of the first sequence of share values to obtain a share value {r} of a division flag r where j is an odd number equal to or greater than 0 and smaller than λ;

set, in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, a public value multiplier r′, the public value multiplier r′ being √2 when λ is an odd number and 1 when λ is an even number;

generate, in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, a share value [c′] of an inverse normalization multiplier c′ obtained by bit-connecting the second sequence of share values {y 0 }, . . . , {y λ′−1 } in order from the front;

generate, in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, a share value [c] of a normalization multiplier c obtained by bit-connecting the first sequence of share values {x 0 }, . . . , {x λ−1 } in reverse order;

calculate a share value [b] obtained by multiplying the share value [a] by the share value [c];

use the share value [b], the share value {r}, and the public value multiplier r′ and calculate [√b]*(r′/√2) when r=1 and [√b]*r′ when r=0 to obtain, in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, a share value [w]; and

calculate, in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, the share value [√a] obtained by shifting right a multiplication result of the share value [w] and the share value [c′] by λ′ bits.

2 . The secure square root computation system according to claim 1 ,

wherein a, b, c, d, f, g, H, i, j, k, l, m, n, o, p, q, α, β, γ, δ, and ζ are parameters for approximating a square root function with an eighth degree polynomial, and [x]:=[b] is assumed, and

the processing circuitry further configured to:

calculate [y′]:=[x(δx+a−i)−j];

calculate [y]:=[y′+(ix+j)];

calculate [z′]:=[y(ζy+b−k)+(c−1)x−m];

calculate [z]:=[z′+(ky+lx+m)];

calculate [w′/γ]:=[z(αz+d−n/γ)+(βx+f−o/γ)y+(g−p)x+(H−q)/γ];

use the share value {r} to calculate [w′/γ]*(r′/√2)γ when r=1 and [w′/γ]*r′γ when r=0 to obtain a calculation result [w′]; and

calculate [w]:=[w′+(nz+op+px+q)].

3 . The secure computation apparatus used in the secure square root computation system according to claim 1 .

4 . A non-transitory computer recording medium on which a program for causing a computer to operate as the secure computation apparatus according to claim 3 .

5 . A secret normalization system for normalizing a share value [a] of a value a to calculate a share value [√a] of a square root of the value a, the secret normalization system comprising:

a plurality of secure computation apparatuses

wherein λ is a decimal point position of the value a, and λ′ is the smallest integer equal to or greater than λ/2, and each of the plurality of secure computation apparatuses comprises:

processing circuitry configured to:

generate, in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over a network, a first sequence of share values {x 0 }, . . . , {x λ−1 } of a flag sequence x 0 , . . . , x λ−1 indicating a most significant bit of the value a;

calculate, in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, an exclusive logical sum of share values {x 2i } and share values {x 2i+1 } of the first sequence of share values to obtain share values {y i } of a bit y i to generate a second sequence of share values {y 0 }, . . . , {y λ′−1 } of a bit sequence y 0 , . . . , y λ′−1 where i is an integer equal to or greater than 0 and smaller than λ′;

calculate, in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, an exclusive logical sum of all share values {x j } of the first sequence of share values to obtain a share value {r} of a division flag r where j is an odd number equal to or greater than 0 and smaller than λ;

set, in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, a public value multiplier r′, the public value multiplier r′ being √2 when λ is an odd number and 1 when λ is an even number;

generate, in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, a share value [c′] of an inverse normalization multiplier c′ obtained by bit-connecting the second sequence of share values {y 0 }, . . . , {y λ′−1 } in order from the front;

generate, in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, a share value [c] of a normalization multiplier c obtained by bit-connecting the first sequence of share values {x 0 }, . . . , {x λ−1 } in reverse order; and

calculate, in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, the share value [b] obtained by multiplying the share value [a] by the share value [c′].

6 . The secure computation apparatus used in the secret normalization system according to claim 5 .

7 . A secure square root computation method executed by a secure square root computation system for receiving a share value [a] of a value a as an input, and calculating a share value [√a] of a square root of the value a, the secure square root computation system including a plurality of secure computation apparatuses,

the secure square root computation method comprising:

generating, by processing circuitry of each of the plurality of secure computation apparatuses and in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over a network, a first sequence of share values {x 0 }, . . . , { λ−1 } of a flag sequence x 0 , . . . , x λ−1 indicating a most significant bit of the value a;

calculating, by the processing circuitry of the secure computation apparatus and in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, an exclusive logical sum of share values {x 2i } and share values {x 2i+1 } of the first sequence of share values to obtain share values {y i } of a bit y i to generate a second sequence of share values {y 0 }, . . . , {y λ′−1 } of a bit sequence y 0 , . . . , y λ′−1 where i is an integer equal to or greater than 0 and smaller than λ′;

calculating, by the processing circuitry of the secure computation apparatus and in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, an exclusive logical sum of all share values {x 2i } of the first sequence of share values to obtain a share value {r} of a division flag r where j is an odd number equal to or greater than 0 and smaller than λ;

setting, by the processing circuitry of the secure computation apparatus and in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, a public value multiplier r′, the public value multiplier r′ being √2 when λ is an odd number and 1 when λ is an even number;

generating, by the processing circuitry of the secure computation apparatus and in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, a share value [c′] of an inverse normalization multiplier c′ obtained by bit-connecting the second sequence of share values {y 0 }, . . . , {y λ′−1 } in order from the front;

generating, by the processing circuitry of the secure computation apparatus and in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, a share value [c] of a normalization multiplier c obtained by bit-connecting the first sequence of share values {x 0 }, . . . , { λ−1 } in reverse order;

calculating, by the processing circuitry of the secure computation apparatus and in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, a share value [b] obtained by multiplying the share value [a] by the share value [c];

using, by the processing circuitry of each secure computation apparatus and in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, the share value [b], the share value {r}, and the public value multiplier r′ to calculate [√b]*(r′/√2) when r=1 and [√b]*r′ when r=0 to obtain a share value [w]; and

calculating, by the processing circuitry of the secure computation apparatus and in cooperation with others of the secure computation apparatuses via communications including transmitting and receiving data over the network, the share value [√a] obtained by shifting right a multiplication result of the share value [w] and the share value [c′] by λ′ bits,

wherein λ is a decimal point position of the value a, and λ′ is the smallest integer equal to or greater than λ/2.