SECURE CONJUGATE GRADIENT METHOD COMPUTATION METHOD, SECURE CONJUGATE GRADIENT METHOD COMPUTATION SYSTEM, SECURE COMPUTATION APPARATUS, AND PROGRAM
A method and circuitry to calculate a simultaneous linear equation with a plurality of symmetric positive definite matrices as coefficients. N symmetric positive definite matrices A ˜ and N vectors B are input to input circuitry. Initialization circuitry initializes secret values of matrices X, R, and P and a vector γ → . First calculation circuitry collectively calculates N matrix calculations to generate a secret value of a vector α → . Second calculation circuitry updates the secret value of the matrix X. Third calculation circuitry collectively calculates N matrix calculations to update the secret value of the matrix R. Fourth calculation circuitry collectively calculates an inner product of N vectors to generate a secret value of the vector β → . Fifth calculation circuitry updates the secret value of the matrix P, and sixth calculation circuitry collectively calculates the inner product of the N vectors and updates the secret value of the vector γ → .
1 . A secure conjugate gradient method computation method for receiving a secret value of a multi-dimensional matrix A˜ consisting of N symmetric positive definite matrices A 1 , A 2 , . . . , A N and a secret value of a matrix B consisting of N vectors b → 1 , . . . , b → N and outputting a secret value of a matrix X consisting of A 1 −1 b → 1 , . . . , A N −1 b → N , the secure conjugate gradient method computation method being executed by a secure conjugate gradient method computation system including a plurality of secure computation apparatuses, wherein ⋅ T represents a transpose of a matrix ⋅, diag (⋅) represents a function for outputting diagonal elements of the matrix ⋅, n represents a predetermined natural number, and 0 n represents a vector having a length of n with all elements being 0,
an initialization circuitry of each secure computation apparatus securely computes the following formulas to generate a secret value of the matrix X, a secret value of a matrix R=(r → 1 , . . . , r → N ), a secret value of a matrix P=(p → 1 , . . . , p → N )), and a secret value of a vector γ → .
X
←
(
0
n
,
0
n
,
…
,
0
n
)
[
Math
.
18
]
R
,
P
←
B
γ
→
"\[Rule]"
←
diag
(
R
T
R
)
a first calculation circuitry of each secure computation apparatus securely computes the following formula so that communication required for matrix calculation is collectively performed once for integer i equal to or greater than 1 or equal to or smaller than N, to generate a secret value of a vector α → =(α 1 , . . . , α N )
α
i
←
r
→
i
T
p
→
i
p
→
i
T
A
i
p
→
i
,
[
Math
.
19
]
a second calculation circuitry of each secure computation apparatus securely computes the following formula to update the secret value of the matrix X
X
←
X
+
α
→
T
P
,
[
Math
.
20
]
a third calculation circuitry of each secure computation apparatus securely computes the following formula so that the communication required for the matrix calculation is collectively performed once for integer i equal to or greater than 1 or equal to or smaller than N, to update a secret value of the matrix R
r
→
i
←
r
→
i
-
α
i
A
i
p
→
i
,
[
Math
.
21
]
a fourth calculation circuitry of each secure computation apparatus securely computes the following formula while converting multiplication of N values into element-wise multiplication of one vector to generate a secret value of the vector β →
β
→
←
diag
(
R
T
R
)
/
γ
→
,
[
Math
.
22
]
a fifth calculation circuitry of each secure computation apparatus securely computes the following formula to update the secret value of the matrix P,
P
←
R
+
β
→
T
P
,
[
Math
.
23
]
and a sixth calculation circuitry of each secure computation apparatus securely computes the following formula while converting multiplication of N values into element-wise multiplication of one vector, to update the secret value of the vector γ →
γ
→
←
diag
(
R
T
R
)
[
Math
.
24
]
2 . The secure conjugate gradient method computation method according to claim 1 ,
wherein the initialization circuitry, the fourth calculation circuitry, and the sixth calculation circuitry
generate a concatenated vector r → obtained by concatenating vectors r → 1 , . . . , r → N included in the matrix R, generate an element product vector g → obtained by multiplying two concatenated vectors r → element by element, divide elements of the element product vector g → into n pieces, sum each n pieces of elements, and obtain a resultant vector e to calculate R T R.
3 . The secure conjugate gradient method computation method according to claim 1 ,
wherein the first calculation circuitry and the third calculation circuitry collectively perform N local operations required for matrix calculation by secure computation when a vector p i included in the matrix P and a symmetric positive definite matrix A i included in the multi-dimensional matrix A˜ are subjected to the matrix calculation, for integer i equal to or greater than 1 or equal to or smaller than N, and collectively perform communication required for the matrix calculation as one communication.
4 . A secure conjugate gradient method computation system including a plurality of secure computation apparatuses, receiving a secret value of a multi-dimensional matrix A˜ consisting of N symmetric positive definite matrices A 1 , . . . , A N and a secret value of a matrix B consisting of N vectors b → 1 , . . . , b → N , and outputting a secret value of a matrix X consisting of A 1 −1 b → 1 , . . . , A N −1 b → N ,
wherein ⋅ T represents a transpose of a matrix ⋅, diag (⋅) represents a function for outputting diagonal elements of the matrix ⋅, n represents a predetermined natural number, and 0 n represents a vector having a length of n with all elements being 0, and
each secure computation apparatus includes
an initialization circuitry configured to securely compute the following formulas to generate a secret value of the matrix X, a secret value of a matrix R=(r → 1 , . . . , r → N ), a secret value of a matrix P=(p → 1 , . . . , p → N )), and a secret value of a vector γ → ,
X
←
(
0
n
,
0
n
,
…
,
0
n
)
R
,
P
←
B
γ
→
←
diag
(
R
T
R
)
[
Math
.
25
]
a first calculation circuitry configured to securely compute the following formula so that communication required for matrix calculation is collectively performed once for integer i equal to or greater than 1 or equal to or smaller than N, to generate a secret value of a vector α → =(α 1 , . . . , α N )
α
i
←
r
→
i
T
p
→
i
p
→
i
T
A
i
p
→
i
;
[
Math
.
26
]
a second calculation circuitry configured to securely compute the following formula to update the secret value of the matrix X,
X
←
X
+
α
→
T
P
;
[
Math
.
27
]
a third calculation circuitry configured to securely compute the following formula so that the communication required for the matrix calculation is collectively performed once for integer i equal to or greater than 1 or equal to or smaller than N, to update a secret value of the matrix R
r
→
i
←
r
→
i
-
α
i
A
i
p
→
i
;
[
Math
.
28
]
a fourth calculation circuitry configured to securely compute the following formula while converting multiplication of N values into element-wise multiplication of one vector to generate a secret value of the vector β→
β
→
←
diag
(
R
T
R
)
/
γ
→
;
[
Math
.
29
]
a fifth calculation circuitry configured to securely compute the following formula to update the secret value of the matrix P
P
←
R
+
β
→
T
P
;
[
Math
.
30
]
and a sixth calculation circuitry configured to securely compute the following formula while converting multiplication of N values into element-wise multiplication of one vector, to update the secret value of the vector γ→
γ
→
←
diag
(
R
T
R
)
[
Math
.
31
]
5 . A secure computation apparatus used in the secure conjugate gradient method computation system according to claim 4 .
6 . A non-transitory computer-readable recording medium which stores a program for causing a computer to execute each step of the secure conjugate gradient method computation method according to claim 1 .