SECURE INVERSE SQUARE ROOT COMPUTATION SYSTEM, SECURE NORMALIZATION SYSTEM, METHODS THEREFOR, SECURE COMPUTATION APPARATUS, AND PROGRAM

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

a plurality of secure computation apparatuses,

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

each of the plurality of secure computation apparatus comprises

processing circuitry configured to:

generate a first sequence of share values {a 0 }, . . . , {a λ−1 } of a bit representation a 0 , . . . , a λ−1 of the value a from the share value [a];

obtain share values {a′ i } of a bit a′ i by calculating a logical sum of share values {a i } and share values {a i+1 } of the first sequence of share values to generate a second sequence of share values {a′ 0 }, . . . , {a′ λ′−1 } of a bit sequence a′ 0 , . . . , a′ λ′−1 where i is an integer equal to or greater than 0 and smaller than λ″;

generate a third sequence of share values {x 0 }, . . . , {x λ′−1 } of a flag sequence x 0 , . . . , x λ′−1 indicating the most significant bit of the second sequence of share values {a′ 0 }, . . . , {a′ λ′−1 };

generate a share value [c′] of a normalization multiplier c′ obtained by bit-connecting the third sequence of share values {x 0 }, . . . , {x λ′−1 } in reverse order;

set share values {a 2i } of the first sequence of share values as share values {a″ i } of bits a″ i to generate a fourth sequence of share values {a″ 0 }, . . . , {a″ λ′−1 } of a bit sequence a″ 0 , . . . , a″ λ′−1 where i is an integer equal to or greater than 0 and smaller than λ″;

sum products of share values {x j } of the third sequence of share values and share values {a″ j } of the fourth sequence of share values to calculate a share value {r} of a multiplication flag r where j is an integer equal to or greater than 0 and smaller than λ′;

use the share value [a], the share value [c′], and the share value {r} to calculate [c′][c′][2a] when r=1 and [c′][c′][a] when r=0 to calculate a share value [b];

use the share value [b] and the share value [r] to calculate [1/√b]*√2 when r=1 and [1/√b] when r=0 to calculate a share value [w]; and

calculate the share value [1/√a] by multiplying the share value [w] by the share value [c′].

2 . The secure inverse 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,

the processing circuitry further configured to:

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

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

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

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

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

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

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

3 . A secure normalization system for normalizing a share value [a] of a value a in order to calculate a share value [ 1 /√a] of the inverse of the square root of the value a, the secure normalization system comprising:

a plurality of secure computation apparatuses

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

each of the secure computation apparatuses comprises

processing circuitry configured to:

generate a first sequence of share values {a 0 }, . . . , {a λ−1 } of a bit representation a 0 , . . . , {a λ−1 } of the value a from the share value [a];

obtain share values {a′ i } of bits a′ i by calculating a logical sum of share values {a i } and share values {a i+1 } of the first sequence of share values to generate a second sequence of share values {a′ 0 }, . . . , {a′ λ−1 } of a bit sequence a′ 0 , . . . , a′ λ′−1 where i is an integer equal to or greater than 0 and smaller than λ″;

generate a third sequence of share values {x 0 }, . . . , {x λ′−1 } of a flag sequence x 0 , . . . , x λ′−1 indicating the most significant bit of the second sequence of share values {a′ 0 }, . . . , {a′ λ′−1 };

generate a share value [c′] of a normalization multiplier c′ obtained by bit-connecting the third sequence of share values {x 0 }, . . . , {x λ′−1 } in reverse order;

set share values {a 2i } of the first sequence of share values u share values {a″ i } of bits a″ i to generate a fourth sequence of share values {a″ 0 }, . . . , {a″ λ′−1 } of a bit sequence a″ 0 , . . . , a″ λ′−1 where i is an integer equal to or greater than 0 and smaller than λ″;

sum products of share values {x j } of the third sequence of share values and share values {a″ j } of the fourth sequence of share values to calculate a share value {r} of a multiplication flag r where j is an integer equal to or greater than 0 and smaller than λ′; and

use the share value [a], the share value [c′], and the share value {r} to calculate [c′][c′][2a] when r=1 and [c′][c′][a] when r=0 to calculate a share value [b].

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

generating, by processing circuitry of each of the plurality of secure computation apparatuses, a first sequence of share values {a 0 }, . . . , {a λ−1 } of a bit representation a 0 , . . . , a λ−1 of the value a from the share value [a];

obtaining, by the processing circuitry of the secure computation apparatus, share values {a i } of bits a′ i by calculating a logical sum of share values {a i } and share values {a i+1 } of the first sequence of share values to generate a second sequence of share values {a′ 0 }, . . . , {a′ λ′− } of a bit sequence a′ 0 , . . . , a′ λ′-1 where i is an integer equal to or greater than 0 and smaller than λ″;

generating, by the processing circuitry of the secure computation apparatus, a third sequence of share values {x 0 }, . . . , {x λ′−1 } of a flag sequence x 0 , . . . , x λ′−1 indicating the most significant bit of the second sequence of share values {a′ 0 }, . . . , {a′ λ′−1 };

generating, by the processing circuitry of the secure computation apparatus, a share value [c′] of a normalization multiplier c′ obtained by bit-connecting the third sequence of share values {x 0 }, . . . , {x λ′−1 } in reverse order;

setting, by the processing circuitry of the secure computation apparatus, share values {a 2i } of the first sequence of share values as share values {a″ i } of bits a″ i to generate a fourth sequence of share values {a″ 0 }, . . . , (a″ λ′−1 ) of a bit sequence a″ 0 , . . . , a″ λ′−1 where i is an integer equal to or greater than 0 and smaller than λ″;

summing, by the processing circuitry of the secure computation apparatus, products of share values {x j } of the third sequence of share values and share values {a″ j } of the fourth sequence of share values to calculate a share value {r} of a multiplication flag r where j is an integer equal to or greater 0 and smaller than λ′;

using, by the processing circuitry of the secure computation apparatus, the share value [a], the share value [c′], and the share value {r} to calculate [c′][c′][2a] when r=1 and [c′][c′][a] when r=0 to calculate a share value [b];

using, by the processing circuitry of the secure computation apparatus, the share value [b] and the share value [r] to calculate [1/√b]*√2 when r=1 and [1/√b] when r=0 to calculate a share value [w]; and

calculating, by the processing circuitry of the secure computation apparatus, the share value [1/√a] by multiplying the share value [w] by the share value [c′]

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

5 . (canceled)

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

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

8 . The secure computation apparatus used in the secure normalization system according to claim 3 .