SECURE INVERSE COMPUTATION SYSTEM, SECURE NORMALIZATION SYSTEM, METHODS THEREFOR, SECURE COMPUTATION APPARATUS, AND PROGRAM
Normalization is performed with high precision in secure computation. A secure inverse computation system ( 100 ) receives [a] as an input and calculates [1/a]. The bit decomposition unit ( 11 ) generates a bit representation a 0 , . . . , a λ−1 of a. The flag sequence generation unit ( 12 ) generates {x 0 }, . . . , {x λ−1 } indicating a most significant bit of {a 0 }, . . . , {a λ−1 }. A bit sequence generation unit ( 13 ) generates {y 0 }, . . . , {y λ−1 } in which {y 0 }, {y 1 }: ={0 }, {y i }: ={(¬a i−2 ∧x i−1 ) XOR x i } (2≤i<λ), {y λ }: ={¬a λ−2 ∧x λ−1 }. The normalization multiplier generation unit ( 14 ) generates [c] obtained by bit-connecting {y λ−1 }, . . . , {y 0 }. The normalization unit ( 15 ) calculates [b]: =[a][c].
1 . A secure inverse 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 value a, the secure inverse computation system comprising:
a plurality of secure computation apparatuses,
wherein λ is a decimal point position of the value a, and
each of the plurality of 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];
generate a second sequence of share values {x 0 }, . . . , {x λ−1 } of a flag sequence x 0 , . . . , x λ−1 indicating a most significant bit of the first sequence of share values {a 0 }, . . . , {a λ−1 };
generate a third sequence of share values {y 0 }, . . . , {y λ−1 } of a bit sequence y 0 , . . . , y λ−1 , {y 0 } and {y 1 } being share values of 0, {y 2 }, . . . , {y λ−1 } being share values of a value obtained by calculating an exclusive logical sum of a result of calculating a logical product of a logical negation of share values {a i−2 } of the first sequence of share values and share values {x i−1 } of the second sequence of share values, and share values {x i } of the second sequence of share values where i is an integer equal to or greater than 2 and smaller than λ, and {y λ } being a share value of a value obtained by calculating a logical product of a logical negation of a share value {a λ−2 } of the first sequence of share values and a share value {x λ−1 } of the second sequence of share values;
generate a share value [c] of a normalization multiplier c obtained by bit-connecting the third sequence of share values {y 0 }, . . . , {y λ−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] to obtain a share value [w] obtained by calculating [1/b]; and
calculate the share value [1/a] obtained by multiplying the share value [w] by the share value [c].
2 . The secure inverse 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 inverse 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−l)x−m];
calculate [z]: =[z′+(ky+lx+m)];
calculate [w′/γ: =[z(αz+d−n/γ)+(βx+f−o/γ)y+(g−p)x+(H−q/γ];
calculate [w′]: =[w′/γ]*γ; and
calculate [w]: =(w′+(nz+op+px+q)].
3 . A secure normalization system for normalizing a share value [a] of a value a,
the secure normalization system comprising:
a plurality of secure computation apparatuses,
wherein λ is a decimal point position of the value a, and
each of the plurality of 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];
generate a second sequence of share values {x 0 }, . . . , {x λ−1 } of a flag sequence x 0 , . . . , x λ−1 indicating a most significant bit of the first sequence of share values {a 0 }, . . . , {a λ−1 };
generate a third sequence of share values {y 0 }, . . . , {y λ−1 } of a bit sequence y 0 , . . . , y λ−1 , {y 0 } and {y 1 } being share values of 0, {y 2 }, . . . , {y λ−1 } being share values of a value obtained by calculating an exclusive logical sum of a result of calculating a logical product of a logical negation of share values {a i−2 } of the first sequence of share values and share value {x i−1 } of the second sequence of share values, and share values {x i } of the second sequence of share values where i is an integer equal to or greater than 2 and smaller than λ, and {y λ } being a share value of a value obtained by calculating a logical product of a logical negation of a share value {a λ−2 } of the first sequence of share values and a share value {x λ−1 } of the second sequence of share values;
generate a share value [c] of a normalization multiplier c obtained by bit-connecting the third sequence of share values {y 0 }, . . . , {y λ−1 } in reverse order; and
calculate a share value [b] obtained by multiplying the share value [a] by the share value [c].
4 . A secure inverse computation method executed by a secure inverse 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 value a, the secure inverse computation system including a plurality of secure computation apparatuses, the secure inverse 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];
generating, by the processing circuitry of the secure computation apparatus, a second sequence of share values {x 0 }, . . . , {x λ−1 } of a flag sequence x 0 , . . . , x λ−1 indicating a most significant bit of the first sequence of share values {a 0 }, . . . , {a λ−1 };
generating, by the processing circuitry of the secure computation apparatus, a third sequence of share values {y 0 }, . . . , {y λ−1 } of a bit sequence y 0 , . . . , y λ−1 , {y 0 } and {y 1 } being share values of 0, {y 2 }, . . . , {y λ−1 } being share values of a value obtained by calculating an exclusive logical sum of a result of calculating a logical product of a logical negation of share values {a i−2 } of the first sequence of share values and share values {x i−1 } of the second sequence of share values, and share values {x i } of the second sequence of share values where i as an integer equal to or greater than 2 and smaller than λ, and {y 2 } being a share value of a value obtained by calculating a logical product of a logical negation of a share value {a λ−2 } of the first sequence of share values and a share value {x λ−1 } of the second sequence of share values;
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 {y 0 }, . . . , {y λ−1 } in reverse order;
calculating, by the processing circuitry of the secure computation apparatus, a share value [b] obtained by multiplying the share value [a] by the share value [c],
using, by the processing circuitry of the secure computation apparatus, the share value [b] to obtain a share value [w] obtained by calculating [1/b]; and
calculating, by the processing circuitry of the secure computation apparatus, the share value [1/a] obtained by multiplying the share value [w] by the share value [c]
wherein λ is a decimal point position of the value a.
5 . (canceled)
6 . The secure computation apparatus used in the secure inverse 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 .