SECURE CONJUGATE GRADIENT METHOD COMPUTATION SYSTEM, SECURE COMPUTATION APPARATUS, CONJUGATE GRADIENT METHOD COMPUTATION APPARATUS, SECURE CONJUGATE GRADIENT METHOD COMPUTATION METHOD, CONJUGATE GRADIENT METHOD COMPUTATION METHOD, AND PROGRAM

1 . A secure conjugate gradient method computation system comprising a plurality of secure computation apparatuses, the secure conjugate gradient method computation system being configured to obtain, letting X be a set of values for computing a product of a d-dimensional real symmetric positive definite matrix A and a d-dimensional vector, b{right arrow over ( )} be a d-dimensional vector, f be a function for computing Ax{right arrow over ( )} based on a matrix X and a d-dimensional vector x{right arrow over ( )}, k be an integer of d or less, i be each of integers from 1 to k, x{right arrow over ( )} 0 be a d-dimensional vector for which a suitable value is set, and D be a value whose absolute value is less than 1 and other than 0, an approximate solution x{right arrow over ( )} k of a solution x{right arrow over ( )}* of Ax{right arrow over ( )}=b{right arrow over ( )} with secret values of the set X and a secret value of the vector b{right arrow over ( )} used as inputs,

wherein each of the secure computation apparatuses includes:

initialization circuitry configured to compute the following expression using secure computation, and generate secret values of vectors p{right arrow over ( )} 0 and r{right arrow over ( )} 0 and a value ρ 0 ;

{right arrow over (p)} 0 ={right arrow over (r)} 0 ={right arrow over (b)}−ƒ ( X,{right arrow over (x)} 0 ), ρ 0 ={right arrow over (r)} 0 T {right arrow over (r)} 0

first computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a vector a{right arrow over ( )} i−1 ;

{right arrow over (a)} i−1 =D× (ƒ( X,{right arrow over (p)} i−1 ))

second computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a value γ i−1 ;

γ i−1 =D× ( {right arrow over (p)} i T {right arrow over (a)} i−1 )

third computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a value α i−1 ;

α

i

-

1

=

ρ

i

-

1

γ

i

-

1

fourth computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a vector d{right arrow over ( )} i ;

{right arrow over (d)} i =D× (α i−1 {right arrow over (p)} i−1 )

fifth computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a vector x{right arrow over ( )} i ;

{right arrow over (x)} i ={right arrow over (x)} i−1 +{right arrow over (d)} i

sixth computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a vector r{right arrow over ( )} i ;

{right arrow over (r)} i ={right arrow over (r)} i−1 −α i−1 {right arrow over (a)} i−1

seventh computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a value ρ i ;

ρ i =D× ( {right arrow over (r)} i T {right arrow over (r)} i )

eighth computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a value β i ;

β

i

=

ρ

i

ρ

i

-

1

ninth computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a vector p{right arrow over ( )} i .

{right arrow over (p)} i ={right arrow over (r)} i −β i {right arrow over (p)} i−1

2 . A secure computation apparatus used in a secure conjugate gradient method computation system configured to obtain, letting X be a set of values for computing a product of a d-dimensional real symmetric positive definite matrix A and a d-dimensional vector, b{right arrow over ( )} be a d-dimensional vector, f be a function for computing Ax{right arrow over ( )} based on a matrix X and a d-dimensional vector x{right arrow over ( )}, k be an integer of d or less, i be each of integers from 1 to k, x{right arrow over ( )} 0 be a d-dimensional vector for which a suitable value is set, and D be a value whose absolute value is less than 1 and other than 0, an approximate solution x{right arrow over ( )} k of a solution x{right arrow over ( )}* of Ax{right arrow over ( )}=b{right arrow over ( )} with secret values of the set X and a secret value of the vector b{right arrow over ( )} used as inputs,

the secure computation apparatus comprising:

initialization circuitry configured to compute the following expression using secure computation, and generate secret values of vectors p{right arrow over ( )} 0 and r{right arrow over ( )} 0 and a value ρ 0 ;

{right arrow over (p)} 0 ={right arrow over (r)} 0 ={right arrow over (b)}−ƒ ( X,{right arrow over (x)} 0 ), ρ 0 ={right arrow over (r)} 0 T {right arrow over (r)} 0

first computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a vector a{right arrow over ( )} i−1 ;

{right arrow over (a)} i−1 =D× (ƒ( X,{right arrow over (p)} i−1 ))

second computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a value γ i−1 ;

γ i−1 =D× ( {right arrow over (p)} i T {right arrow over (a)} i−1 )

third computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a value α i−1 ;

α

i

-

1

=

ρ

i

-

1

γ

i

-

1

fourth computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a vector d{right arrow over ( )} i ;

{right arrow over (d)} i =D× (α i−1 {right arrow over (p)} i−1 )

fifth computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a vector x{right arrow over ( )} i ;

{right arrow over (x)} i ={right arrow over (x)} i−1 +{right arrow over (d)} i

sixth computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a vector r{right arrow over ( )} i ;

{right arrow over (r)} i ={right arrow over (r)} i−1 −α i−1 {right arrow over (a)} i−1

seventh computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a value ρ i ;

ρ i =D× ( {right arrow over (r)} i T {right arrow over (r)} i )

eighth computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a value β i ;

β

i

=

ρ

i

ρ

i

-

1

ninth computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a vector p{right arrow over ( )} i .

{right arrow over (p)} i ={right arrow over (r)} i −β i {right arrow over (p)} i−1

3 . A conjugate gradient method computation apparatus configured to obtain, letting X be a set of values for computing a product of a d-dimensional real symmetric positive definite matrix A and a d-dimensional vector, b{right arrow over ( )} be a d-dimensional vector, f be a function for computing Ax{right arrow over ( )} based on a matrix X and a d-dimensional vector x{right arrow over ( )}, k be an integer of d or less, i be each of integers from 1 to k, x{right arrow over ( )} 0 be a d-dimensional vector for which a suitable value is set, and D be a value whose absolute value is less than 1 and other than 0, an approximate solution x{right arrow over ( )} k of a solution x{right arrow over ( )}* of Ax{right arrow over ( )}=b{right arrow over ( )} with the set X and the vector b{right arrow over ( )} used as inputs, the conjugate gradient method computation apparatus comprising:

initialization circuitry configured to compute the following expression, and generate vectors p{right arrow over ( )} 0 and r{right arrow over ( )} 0 and a value ρ 0 ;

{right arrow over (p)} 0 ={right arrow over (r)} 0 ={right arrow over (b)}−ƒ ( X,{right arrow over (x)} 0 ), ρ 0 ={right arrow over (r)} 0 T {right arrow over (r)} 0

first computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a vector a{right arrow over ( )} i−1 ;

{right arrow over (a)} i−1 =D× (ƒ( X,{right arrow over (p)} i−1 ))

second computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a value γ i−1 ;

γ i−1 =D× ( {right arrow over (p)} i T {right arrow over (a)} i−1 )

third computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a value α i−1 ;

α

i

-

1

=

ρ

i

-

1

γ

i

-

1

fourth computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a vector d{right arrow over ( )} i ;

{right arrow over (d)} i =D× (α i−1 {right arrow over (p)} i−1 )

fifth computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a vector x{right arrow over ( )} i ;

{right arrow over (x)} i ={right arrow over (x)} i−1 +{right arrow over (d)} i

sixth computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a vector r{right arrow over ( )} i ;

{right arrow over (r)} i ={right arrow over (r)} i−1 −α i−1 {right arrow over (a)} i−1

seventh computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a value ρ i ;

ρ i =D× ( {right arrow over (r)} i T {right arrow over (r)} i )

eighth computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a value β i ;

β

i

=

ρ

i

ρ

i

-

1

ninth computation circuitry configured to compute the following expression using secure computation, and generate a secret value of a vector p{right arrow over ( )} i .

{right arrow over (p)} i ={right arrow over (r)} i −β i {right arrow over (p)} i−1

4 . A secure conjugate gradient method computation method executed by a secure conjugate gradient method computation system including a plurality of secure computation apparatuses, the secure conjugate gradient method computation system being configured to obtain, letting X be a set of values for computing a product of a d-dimensional real symmetric positive definite matrix A and a d-dimensional vector, b{right arrow over ( )} be a d-dimensional vector, f be a function for computing Ax{right arrow over ( )} based on a matrix X and a d-dimensional vector x{right arrow over ( )}, k be an integer of d or less, i be each of integers from 1 to k, x{right arrow over ( )} 0 be a d-dimensional vector for which a suitable value is set, and D be a value whose absolute value is less than 1 and other than 0, an approximate solution x{right arrow over ( )} k of a solution x{right arrow over ( )}* of Ax{right arrow over ( )}=b{right arrow over ( )} with secret values of the set X and a secret value of the vector b{right arrow over ( )} used as inputs,

the secure conjugate gradient method computation method comprising:

computing the following expression using secure computation, and generating secret values of vectors p{right arrow over ( )} 0 and r{right arrow over ( )} 0 and a value ρ 0 ;

{right arrow over (p)} 0 ={right arrow over (r)} 0 ={right arrow over (b)}−ƒ ( X,{right arrow over (x)} 0 ), ρ 0 ={right arrow over (r)} 0 T {right arrow over (r)} 0

computing the following expression using secure computation, and generating a secret value of a vector a{right arrow over ( )} i−1 ;

{right arrow over (a)} i−1 =D× (ƒ( X,{right arrow over (p)} i−1 ))

computing the following expression using secure computation, and generating a secret value of a value γ i−1 ;

γ i−1 =D× ( {right arrow over (p)} i T {right arrow over (a)} i−1 )

computing the following expression using secure computation, and generating a secret value of a value α i−1 ;

α

i

-

1

=

ρ

i

-

1

γ

i

-

1

computing the following expression using secure computation, and generating a secret value of a vector d{right arrow over ( )} i ;

{right arrow over (d)} i =D× (α i−1 {right arrow over (p)} i−1 )

computing the following expression using secure computation, and generating a secret value of a vector x{right arrow over ( )} i ;

{right arrow over (x)} i ={right arrow over (x)} i−1 +{right arrow over (d)} i

computing the following expression using secure computation, and generating a secret value of a vector r{right arrow over ( )} i ;

{right arrow over (r)} i ={right arrow over (r)} i−1 −α i−1 {right arrow over (a)} i−1

computing the following expression using secure computation, and generating a secret value of a value ρ i ;

ρ i =D× ( {right arrow over (r)} i T {right arrow over (r)} i )

computing the following expression using secure computation, and generating a secret value of a value β i ;

β

i

=

ρ

i

ρ

i

-

1

computing the following expression using secure computation, and generating a secret value of a vector p{right arrow over ( )} i .

{right arrow over (p)} i ={right arrow over (r)} i −β i {right arrow over (p)} i−1

5 . A conjugate gradient method computation method executed by a conjugate gradient method computation apparatus configured to obtain, letting X be a set of values for computing a product of a d-dimensional real symmetric positive definite matrix A and a d-dimensional vector, b{right arrow over ( )} be a d-dimensional vector, f be a function for computing Ax{right arrow over ( )} based on a matrix X and a d-dimensional vector x{right arrow over ( )}, k be an integer of d or less, i be each of integers from 1 to k, x{right arrow over ( )} 0 be a d-dimensional vector for which a suitable value is set, and D be a value whose absolute value is less than 1 and other than 0, an approximate solution x{right arrow over ( )} k of a solution x{right arrow over ( )}* of Ax{right arrow over ( )}=b{right arrow over ( )} with the set X and the vector b{right arrow over ( )} used as inputs,

the conjugate gradient method computation method comprising:

computing the following expression, and generating vectors p{right arrow over ( )} 0 and r{right arrow over ( )} 0 and a value ρ 0 ;

{right arrow over (p)} 0 ={right arrow over (r)} 0 ={right arrow over (b)}−ƒ ( X,{right arrow over (x)} 0 ), ρ 0 ={right arrow over (r)} 0 T {right arrow over (r)} 0

computing the following expression, and generating a vector a{right arrow over ( )} i−1 ;

{right arrow over (a)} i−1 =D× (ƒ( X,{right arrow over (p)} i−1 ))

computing the following expression, and generating a value γ i−1 ;

γ i−1 =D× ( {right arrow over (p)} i T {right arrow over (a)} i−1 )

computing the following expression, and generating a value α i−1 ;

α

i

-

1

=

ρ

i

-

1

γ

i

-

1

computing the following expression, and generating a vector d{right arrow over ( )} i ;

{right arrow over (d)} i =D× (α i−1 {right arrow over (p)} i−1 )

computing the following expression, and generating a vector x{right arrow over ( )} i ;

{right arrow over (x)} i ={right arrow over (x)} i−1 +{right arrow over (d)} i

computing the following expression, and generating a vector r{right arrow over ( )} i ;

{right arrow over (r)} i ={right arrow over (r)} i−1 −α i−1 {right arrow over (a)} i−1

computing the following expression, and generating a value ρ i ;

ρ i =D× ( {right arrow over (r)} i T {right arrow over (r)} i )

computing the following expression, and generating a value β i ;

β

i

=

ρ

i

ρ

i

-

1

computing the following expression, and generating a vector p{right arrow over ( )} i .

{right arrow over (p)} i ={right arrow over (r)} i −β i {right arrow over (p)} i−1

6 . A non-transitory computer-readable recording medium on which a program is recorded for causing a computer to perform the method of claim 4 .

7 . A non-transitory computer-readable recording medium on which a program is recorded for causing a computer to perform the method of claim 5 .