Back to results
US 12,744,666 B2Granted
Secure inverse computation system, secure normalization system, methods therefor, secure computation apparatus, and program
AssigneeNTT, Inc.
InventorDai Ikarashi
Life of this patent
Estimating the term…
Abstract
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 a0, . . . , aλ−1 of a. The flag sequence generation unit (12) generates {x0}, . . . , {xλ−1} indicating a most significant bit of {a0}, . . . , {aλ−1}. A bit sequence generation unit (13) generates {y0}, . . . , {yλ−1} in which {y0}, {y1}: ={0}, {yi}: ={(¬ai−2∧xi−1) XOR xi} (2≤i<λ), {yλ}: ={¬aλ−2∧xλ−1}. The normalization multiplier generation unit (14) generates [c] obtained by bit-connecting {yλ−1}, . . . , {y0}. The normalization unit (15) calculates [b]: =[a][c].
Claims6
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 secure computation apparatus of the plurality of secure computation apparatuses comprises processing circuitry configured to:
- generate, in cooperation with others of the plurality of secure computation apparatuses via communications including transmitting and receiving data over a network, a first sequence of share values {a0}, . . . , {aλ−1} of a bit representation a0, . . . , aλ−1 of the value a from the share value [a];
- generate, in cooperation with others of the plurality of secure computation apparatuses via communications including transmitting and receiving data over the network, a second sequence of share values {x0}, . . . , {xλ−1} of a flag sequence x0, . . . , xλ−1 indicating a most significant bit of the first sequence of share values {a0}, . . . , {aλ−1};
- generate, in cooperation with others of the plurality of secure computation apparatuses via communications including transmitting and receiving data over the network, a third sequence of share values {y0}, . . . , {yλ−1} of a bit sequence y0, . . . , yλ−1, {y0} and {y1} being share values of 0, {y2}, . . . , {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 {ai−2} of the first sequence of share values and share values {xi−1} of the second sequence of share values, and share values {xi} 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, in cooperation with others of the plurality of 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 third sequence of share values {y0}, . . . , {yλ−1} in reverse order;
- calculate, in cooperation with others of the plurality of 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];
- obtain a share value [w] by calculating [1/b], in cooperation with others of the plurality of secure computation apparatuses via communications including transmitting and receiving data over the network, using the share value [b];
- and
- calculate, in cooperation with others of the plurality of secure computation apparatuses via communications including transmitting and receiving data over the network, the share value [1/a] obtained by multiplying the share value [w] by the share value [c].
8 more elements
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 secure computation apparatus of the plurality of secure computation apparatuses comprises processing circuitry configured to:
- generate, in cooperation with others of the plurality of secure computation apparatuses via communications including transmitting and receiving data over a network, a first sequence of share values {a0}, . . . , {aλ−1} of a bit representation a0, . . . , aλ−1 of the value a from the share value [a];
- generate, in cooperation with others of the plurality of secure computation apparatuses via communications including transmitting and receiving data over the network, a second sequence of share values {x0}, . . . , {xλ−1} of a flag sequence x0, . . . , xλ−1 indicating a most significant bit of the first sequence of share values {a0}, . . . , {aλ−1};
- generate, in cooperation with others of the plurality of secure computation apparatuses via communications including transmitting and receiving data over the network, a third sequence of share values {y0}, . . . , {yλ−1} of a bit sequence y0, . . . , yλ−1, {y0} and {y1} being share values of 0, {y2}, . . . , {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 {ai−2} of the first sequence of share values and share value {xi−1} of the second sequence of share values, and share values {xi} 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, in cooperation with others of the plurality of 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 third sequence of share values {y0}, . . . , {yλ−1} in reverse order;
- and
- calculate, in cooperation with others of the plurality of 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].
6 more elements
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 secure computation apparatus of the plurality of secure computation apparatuses in cooperation with others of the plurality of secure computation apparatuses via communications including transmitting and receiving data over a network, a first sequence of share values {a0}, . . . , {aλ−1} of a bit representation a0, . . . , aλ−1 of the value a from the share value [a];
- generating, by the processing circuitry of each secure computation apparatus of the plurality of secure computation apparatuses in cooperation with others of the plurality of secure computation apparatuses via communications including transmitting and receiving data over the network, a second sequence of share values {x0}, . . . , {xλ−1} of a flag sequence x0, . . . , xλ−1 indicating a most significant bit of the first sequence of share values {a0}, . . . , {aλ−1};
- generating, by the processing circuitry of each secure computation apparatus of the plurality of secure computation apparatuses in cooperation with others of the plurality of secure computation apparatuses via communications including transmitting and receiving data over the network, a third sequence of share values {y0}, . . . , {yλ−1} of a bit sequence y0, . . . , yλ−1, {y0} and {y1} being share values of 0, {y2}, . . . , {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 {ai−2} of the first sequence of share values and share values {xi−1} of the second sequence of share values, and share values {xi} of the second sequence of share values where i as 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;
- generating, by the processing circuitry of each secure computation apparatus of the plurality of secure computation apparatuses in cooperation with others of the plurality of 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 third sequence of share values {y0}, . . . , {yλ−1} in reverse order;
- calculating, by the processing circuitry of each secure computation apparatus of the plurality of secure computation apparatuses in cooperation with others of the plurality of 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];
- obtaining a share value [w] by calculating [1/b], by the processing circuitry of each secure computation apparatus of the plurality of secure computation apparatuses in cooperation with others of the plurality of secure computation apparatuses via communications including transmitting and receiving data over the network, using the share value [b];
- and
- calculating, by the processing circuitry of each secure computation apparatus of the plurality of secure computation apparatuses in cooperation with others of the plurality of secure computation apparatuses via communications including transmitting and receiving data over the network, 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.
6 more elements
Dependencies are inferred from the claim text.