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 {x0}, . . . , {λ−1} of a flag sequence x0, . . . , 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 {x2i} and share values {x2i+1} of the first sequence of share values to obtain share values {yi} of a bit yi to generate a second sequence of share values {y0}, . . . , {yλ′−1} of a bit sequence y0, . . . , 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 {x2i} 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 {y0}, . . . , {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 {x0}, . . . , {λ−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.