Secret batch approximation system, secure computation device, secret batch approximation method, and program
View Patent ↗Calculation time is reduced without degrading approximation accuracy in calculation of a complicated function through secure computation. A secret batch approximation system calculates a concealed text [z] of an approximate value z for a function value y satisfying yj=f(xj) by using a concealed text [x] of a value x as input. g is defined as a polynomial for approximating each section of m sections into which the function f is divided. A parameter acquisition unit acquires a concealed text [a] of a parameter a corresponding to the value x for each integer j that is not less than 1 and not more than n, where aj is defined as a parameter pi corresponding to a section Ri including a value xj. A polynomial calculation unit calculates a polynomial g([x], [a]) by using the concealed text [x] of the value x as input based on the concealed text [a].
1. A secret batch approximation system including three or more secure computation apparatuses for calculating a concealed text [z] :=([z 1 ], . . . , [z n ]) of an approximate value z :=(z 1 , . . . , z n ) for a function value y :=(y 1 , . . . , y n ) satisfying y j =f(x j ) for each integer j, the integer j being greater than or equal to 1 and less than or equal to n, the three or more secure computation apparatuses cooperatively calculating the concealed text [z] using a concealed text [x] :=([x 1 ], . . . , [x n ]) of n pieces of values x :=(x 1 , . . . , x n ) as input when n is defined as an integer greater than or equal to 1, wherein
m is defined as an integer greater than or equal to 2, g is defined as a polynomial for approximating each section of m sections into which a function f is divided, i is defined as each integer and is greater than or equal to 1 and less than or equal to m, R i is defined as one of the m sections, and p i is defined as a parameter of the polynomial g corresponding to the section R i ,
each of the three or more secure computation apparatuses comprises processing circuitry configured to:
receive the concealed text [x] :=([x 1 ], . . . , [x n ]) as input;
acquire a concealed text [a] :=([a 1 ], . . . , [a n ]) of a parameter a :=(a 1 , . . . , a n ) corresponding to a value x :=(x 1 , . . . , x n ) for each integer j, where a j is defined as a parameter p i corresponding to the section R i including the value x j ;
calculate the polynomial g([x], [a]) by using the concealed text [x] of the value x as input based on the concealed text [a] of the parameter a so as to obtain the concealed text [z] of the approximate value z for the function value y; and
set the concealed text [z] as output of each of the three or more secure computation apparatuses,
wherein
the processing circuitry acquires the concealed text [a] :=([a 1 ], . . . m [a n ]) of the parameter a :=(a 1 , . . . , a n ) based on a formula:
([ a 1 ], . . . ,[a n ])←BatchMap([ x ],( u 1 , . . . ,u m ),( p 1 , . . . ,p m ))
where BatchMap is defined as a secure computation batch mapping algorithm, u i is defined as a value indicating a boundary of the section R i , and u i <u +1 .
2. The secret batch approximation system according to claim 1 , wherein the function f is a sigmoid function with a domain of definition expressed as X :=[0, 1000), m≤5000 holds.
3. The secret batch approximation system according to claim 1 , wherein the polynomial g is a quadratic polynomial.
4. A secure computation apparatus that is included in a secret batch approximation system, the secret batch approximation system including three or more secure computation apparatuses that cooperatively calculate a concealed text [z] :=([z 1 ], . . . , [z n ]) of an approximate value z :=(z 1 , . . . , z n ) for a function value y :=(y 1 , . . . , y n ) satisfying y j =f(x j ) for each integer j, the integer j being greater than or equal to 1 and less than or equal to n, by using a concealed text [x] :=([x 1 ], . . . , [x n ]) of n pieces of values x :=(x 1 , . . . , x n ) as input when n is defined as an integer greater than or equal to 1, wherein
m is defined as an integer greater than or equal to 2, g is defined as a polynomial for approximating each section of m sections into which a function f is divided, i is defined as each integer greater than or equal to 1 and less than or equal to m, R i is defined as one of the m sections, and p i is defined as a parameter of the polynomial g corresponding to the section R i ,
the secure computation apparatus comprises processing circuitry configured to:
receive the concealed text [x] :=([x 1 ], . . . ,[x n ]) as input;
acquire a concealed text [a] :=([a 1 ], . . . , [a n ]) of a parameter a :=(a 1 , . . . , a n ) corresponding to a value x :=(x 1 , . . . , x n ) for each integer j, where a j is defined as a parameter p i corresponding to the section R i including the value x j ;
calculate the polynomial g([x], [a]) by using the concealed text [x] of the value x as input based on the concealed text [a] of the parameter a so as to obtain the concealed text [z] of the approximate value z for the function value y; and
set the concealed text IzI as output of each of the three or more secure computation apparatuses,
wherein
the processing circuitry acquires the concealed text [a] :=([a 1 ], . . . , [a n ]) of the parameter a :=(a 1 , . . . , a n ) based on a formula:
([ a 1 ], . . . ,[a n ])←BatchMap([ x ],( u 1 , . . . ,u m ),( p 1 , . . . ,p m ))
where BatchMap is defined as a secure computation batch mapping algorithm, u i is defined as a value indicating a boundary of the section R i , and u i <u i+1 .
5. A non-transitory computer readable medium having a program recorded thereon for making a computer function as the secure computation apparatus according to claim 4 .
6. The secret batch approximation system according to claim 4 , wherein the polynomial g is a cubic polynomial.
7. A secret batch approximation method that is executed by a secret batch approximation system, the secret batch approximation system including three or more secure computation apparatuses that cooperatively calculate a concealed text [z] :=([z 1 ], . . . , [z n ]) of an approximate value z :=(z 1 , . . . , z n ) for a function value y :=(y 1 , . . . , y n ) satisfying y j =f(x j ) for each integer j, the integer j being greater than or equal to 1 and less than or equal to n, by using a concealed text [x] :=([x 1 ], . . . , [x n ]) of n pieces of values x :=(x 1 , . . . , x n ) as input when n is defined as an integer greater than or equal to 1, wherein
m is defined as an integer greater than or equal to 2, g is defined as a polynomial for approximating each section of m sections into which a function f is divided, i is defined as each integer greater than or equal to 1 and less than or equal to m, R i is defined as one of the m sections, and p i is defined as a parameter of the polynomial g corresponding to the section R i ,
the secure computation apparatus comprises processing circuitry configured to:
receiving, by processing circuitry of each of the three or more secure computation apparatuses, the concealed text [x] :=([x 1 ], . . . ,[x n ]) as input,
acquiring, by processing circuitry of each of the three or more secure computation apparatuses, a concealed text [a] :=([a 1 ], . . . , [a n ]) of a parameter a :=(a 1 , . . . , a n ) corresponding to a value x :=(x 1 , . . . , x n ) for each integer j, where a j is defined as a parameter p i corresponding to the section R i including the value x j ,
calculating, by the processing circuitry of each of the three or more secure computation apparatuses, the polynomial g([x], [a]) by using the concealed text [x] of the value x as input based on the concealed text [a] of the parameter a so as to obtain the concealed text [z] of the approximate value z for the function value y, and
setting, by the processing circuitry of each of the three or more secure computation apparatuses, the concealed text [z] as output of each of the three or more secure computation apparatuses,
wherein the method further comprises:
acquiring the concealed text [a] :=([a 1 ], . . . , [a n ]) of the parameter a :=(a 1 , . . . , a n ) based on a formula:
([ a 1 ], . . . ,[a n ])←BatchMap([ x ],( u 1 , . . . ,u m ),( p 1 , . . . ,p m ))
where BatchMap is defined as a secure computation batch mapping algorithm, u i is defined as a value indicating a boundary of the section R i , and u i <u i+1 .