Loading patent…
AssigneeNippon Telegraph and Telephone Corporation
InventorKoki Hamada
Estimating the term…
A secure computation technique of calculating a polynomial in a shorter calculation time is provided. A secure computation system generates concealed text [[u]] of u, which is the result of magnitude comparison between a value x and a random number r, from concealed text [[x]] by using concealed text [[r]]; generates concealed text [[c]] of a mask c from the concealed text [[x]], [[r]], and [[u]]; reconstructs the mask c from the concealed text [[c]]; calculates, for i=0, . . . , n, a coefficient bi from an order n, coefficients a0, a1, . . . , an, and the mask c; generates, for i=1, . . . , n, concealed text [[si]] of a selected value si, which is determined in accordance with the result u of magnitude comparison, from the concealed text; [[u]]; and calculates a linear combination b0+b1[[s1]]+ . . . +bn[[sn]] of the coefficient bi and the concealed text [[si]] as concealed text [[a0+a1x1+ . . . +anxn]].
A secure computation system in which a0+a1x1+ . . . +anxn is an n-th order polynomial (n is an order of the polynomial and a0, a1, . . . , an are coefficients of the polynomial) in a variable x, x is a value which is substituted into the n-th order polynomial, k is an integer which satisfies k≤x<k+1, r is a random number which satisfies k≤r<k+1, and [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] are concealed text of a power of the random number r and a power of r−1, the secure computation system which includes two or more secure computation devices and calculates, from concealed text [[x]] of the value x, concealed text [[a0+a1x1+ . . . +anxn]] of values of the n-th order polynomial a0+a1x1+ . . . +anxn in which the value x is substituted, the secure computation system comprising:
A secure computation system in which a0+a1x1+ . . . +anxn is an n-th order polynomial (n is an order of the polynomial and a0, a1, . . . , an are coefficients of the polynomial) in a variable x, x is a value which is substituted into the n-th order polynomial, r is a random number which satisfies 1≤r<2, [[r]], [[r2]], . . . , [[rn]], [[(r−1)]], [[(r−1)2]], . . . , [[(r−1)n]] are concealed text of a power of the random number r and a power of r−1, and a reciprocal 1/x of the value x is expressed as 1/x=a0+a1x1+ . . . +anxn, the secure computation system which includes two or more secure computation devices and calculates concealed text [[1/x]] of the reciprocal 1/x from concealed text [[x]] of the value x, the secure computation system comprising:
A secure computation system in which a0+a1x1+ . . . +anxn is an n-th order polynomial (n is an order of the polynomial and a0, a1, . . . , an are coefficients of the polynomial) in a variable x, x is a value which is substituted into the n-th order polynomial, r is a random number which satisfies 1≤r<2, [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] are concealed text of a power of the random number r and a power of r−1, and a logarithm log x of the value x is expressed as log x=a0+a1x1+ . . . +anxn, the secure computation system which includes two or more secure computation devices and calculates concealed text [[log x]] of the logarithm log x from concealed text [[x]] of the value x, the secure computation system comprising:
A secure computation device in a secure computation system in which a0+a1x1+ . . . +anxn is an n-th order polynomial (n is an order of the polynomial and a0, a1, . . . , an are coefficients of the polynomial) in a variable x, x is a value which is substituted into the n-th order polynomial, k is an integer which satisfies k≤x<k+1, r is a random number which satisfies k≤r<k+1, and [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] are concealed text of a power of the random number r and a power of r−1, the secure computation system which includes two or more secure computation devices and calculates, from the concealed text [[x]] of the value x, concealed text [[a0+a1x1+ . . . +anxn]] of values of the n-th order polynomial a0+a1x1+ . . . +anxn in which the value x is substituted, the secure computation device comprising:
A secure computation device in a secure computation system in which a0+a1x1+ . . . +anxn is an n-th order polynomial (n is an order of the polynomial and a0, a1, . . . , an are coefficients of the polynomial) in a variable x, x is a value which is substituted into the n-th order polynomial, r is a random number which satisfies 1≤r<2, [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] are concealed text of a power of the random number r and a power of r−1, and a reciprocal 1/x of the value x is expressed as 1/x=a0+a1x1+ . . . +anxn, the secure computation system which includes two or more secure computation devices and calculates concealed text [[1/x]] of the reciprocal 1/x from concealed text [[x]] of the value x, the secure computation device comprising:
A secure computation device in a secure computation system in which a0+a1x1+ . . . +anxn is an n−th order polynomial (n is an order of the polynomial and a0, a1, . . . , an are coefficients of the polynomial) in a variable x, x is a value which is substituted into the n-th order polynomial, r is a random number which satisfies 1≤r<2, [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] are assumed text of a power of the random number r and a power of r−1, and a logarithm log x of the value x is expressed as log x=a0+a1x1+ . . . +anxn, the secure computation system which includes two or more secure computation devices and calculates concealed text [[log x]] of the logarithm log x from concealed text [[x]] of the value x, the secure computation device comprising:
A secure computation method in which a0+a1x1+ . . . +anxn is an n-th order polynomial (n is an order of the polynomial and a0, a1, . . . , an are coefficients of the polynomial) in a variable x, x is a value which is substituted into the n-th order polynomial, k is an integer which satisfies k≤x<k+1, r is a random number which satisfies k≤r<k+1, and [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] are concealed text of a power of the random number r and a power of r−1, the secure computation method by which concealed text [[a0+a1x1+ . . . +anxn]] of values of the n-th order polynomial a0+a1x1+ . . . +anxn in which the value x is substituted is calculated from concealed text of the value x by using a secure computation system which includes two or more secure computation devices, the secure computation method comprising:
A secure computation method in which a0+a1x1+ . . . +anxn is an n-th order polynomial (n is an order of the polynomial and a0, a1, . . . , an are coefficients of the polynomial) in a variable x, x is a value which is substituted into the n-th order polynomial, r is a random number which satisfies 1≤r<2, [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] are concealed text of a power of the random number r and a power of r−1, and a reciprocal 1/x of the value x is expressed as 1/x=a0+a1x1+ . . . +anxn, the secure computation method by which concealed text [[1/x]] of the reciprocal 1/x is calculated from concealed text [[x]] of the value x by using a secure computation system which includes two or more secure computation devices, the secure computation method comprising:
A secure computation method in which a0+a1x1+ . . . +anxn is an n-th order polynomial (n is an order of the polynomial and a0, a1, . . . , an are coefficients of the polynomial) in a variable x, x is a value which is substituted into the n-th order polynomial, r is a random number which satisfies 1≤r<2, [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] are concealed text of a power of the random number r and a power of r−1, and a logarithm log x of the value x is expressed as log x=a0+a1x1+ . . . +anxn, the secure computation method by which concealed text [[log x]] of the logarithm log x is calculated from concealed text [[x]] of the value x by using a secure computation system which includes two or more secure computation devices, the secure computation method comprising:
A non-transitory computer readable medium that stores a program for causing a computer to function as a secure computation device in a secure computation system in which a0+a1x1+ . . . +anxn is an n-th order polynomial (n is an order of the polynomial and a0, a1, . . . , an are coefficients of the polynomial) in a variable x, x is a value which is substituted into the n-th order polynomial, k is an integer which satisfies k≤x<k+1, r is a random number which satisfies k≤r<k+1, and [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] are concealed text of a power of the random number r and a power of r−1, the secure computation system which includes two or more secure computation devices and calculates, from the concealed text [[x]] of the value x, concealed text [[a0+a1x1+ . . . +anxn]] of values of the n-th order polynomial a0+a1x1+ . . . +anxn in which the value x is substituted, the secure computation device comprising:
Dependencies are inferred from the claim text.