Secret computation system and method
View Patent ↗A secret computation system is a secret computation system for performing computation while keeping data concealed, and comprises a cyphertext generation device that generates cyphertext by encrypting the data, a secret computation device that generates encrypted basic statistics by performing secret computation of predetermined basic statistics using the cyphertext while keeping the cyphertext concealed, and a computation device that generates decrypted basic statistics by decrypting the encrypted basic statistics and performs predetermined computation using the decrypted basic statistics.
1. A secret computation system for performing computation while keeping data concealed, comprising:
a cyphertext generation device that generates cyphertext by encrypting the data;
a secret computation device that generates encrypted basic statistics by performing secret computation of predetermined basic statistics using the cyphertext while keeping the cyphertext concealed from the secret computation device; and
a computation device that generates decrypted basic statistics by decrypting the encrypted basic statistics and performs predetermined computation using the decrypted basic statistics,
wherein the cyphertext generation device, the secret computation device, and the computation device communicate with each other over a network, and
wherein the predetermined computation is a computation for estimating parameters w 0 and w 1 for a following linear model
b=w 0 +w 1 a
between m data a and m data b held by a registered terminals T H ,
the cyphertext generation device is the registered terminals T H ,
the secret computation device is n secret computation servers M 1 , . . . , M n ,
the computation device is an analysis terminal T A ,
cyphertext of “x” is described as [x]=([x] 1 , . . . ,[x] n ),
provided that i=1, . . . ,n, the registered terminals T H generates [a] i , [b] i and [m] i as the cyphertext and transmit [a] i , [b] i and [m] i and plaintext m to the secret computation servers M i ,
such that each of the secure computation servers M i receives, over the network, an input of one or more respective shares of original data a and b, and the data a and b are concealed from each of the secure computation servers, provided that i=1, . . . ,n, a=(a 1 , . . . ,a m ), b=(b 1 , . . . ,b m ), s a =Σ j=1 m aj , s b =Σ j=1 m bj , s a∧2 =Σ j=1 m aj 2 and s ab =Σ j=1 m ajbj , the secret computation servers M i generates [s a ] i , [S b ] i , [s a∧2 ] i and [s ab ] i as the basic statistics and transmits [s a ] i ,[S b ] i , [s a∧2 ] i , [s ab ] i and [m] i to the analysis terminal T A , and
the analysis terminal T A generates s a , S b , s a∧2 , s ab and m as the decrypted basic statistics and calculates μ a =(1/m)s a ,μ b =(1/m)s b , σ a 2 =(1/m)s a∧2 −(1/m 2 )s a 2 , σ a,b =(1/m)s ab −(1/m 2 )s a s b
wherein the analysis terminal T A obtains parameters w 0 and w 1 for the linear model by calculating w 0 =μ b −w 1 μ a and W 1 =(σ a,b )/(σ a 2 ).
2. A secret computation method for performing computation while keeping data concealed, comprising:
a cyphertext generation step in which a cyphertext generation device generates cyphertext by encrypting the data;
a secret computation step in which a secret computation device generates encrypted basic statistics by performing secret computation of predetermined basic statistics using the cyphertext while keeping the cyphertext concealed from the secret computation device; and
a computation step in which a computation device generates decrypted basic statistics by decrypting the encrypted basic statistics and performs predetermined computation using the decrypted basic statistics,
wherein the cyphertext generation device, the secret computation device, and the computation device communicate with each other over a network, and
wherein the predetermined computation is a computation for estimating parameters w 0 and w 1 for a following linear model
b=w 0 +w 1 a
between m data a and m data b held by a registered terminals T H ,
the cyphertext generation device is the registered terminals T H ,
the secret computation device is n secret computation servers M 1 , . . . , M n ,
the computation device is an analysis terminal T A ,
cyphertext of “x” is described as [x]=([x] 1 , . . . ,[x] n ),
provided that i=1, . . . ,n, the registered terminals T H generates [a] i , [b] i and [m] i as the cyphertext and transmit [a] i , [b] i and [m] i and plaintext m to the secret computation servers M i ,
such that each of the secure computation servers M i receives, over the network, an input of one or more respective shares of original data a and b, and the data a and b are concealed from each of the secure computation servers, provided that i=1, . . . ,n, a=(a 1 , . . . ,a m ), b=(b 1 , . . . ,b m ), s a =Σ j=1 m aj , s b =Σ j=1 m bj , s a∧2 =Σ j=1 m aj 2 and s ab =Σ j=1 m ajbj , the secret computation servers M i generates [s a ] i , [S b ] i , [s a∧2 ] i and [s ab ] i as the basic statistics and transmits [s a ] i ,[S b ] i , [s a∧2 ] i , [s ab ] i and [m] i to the analysis terminal T A , and
the analysis terminal T A generates s a , S b , s a∧2 , s ab and m as the decrypted basic statistics and calculates μ a =(1/m)s a ,μ b =(1/m)s b , σ a 2 =(1/m)s a∧2 −(1/m 2 )s a 2 , σ a,b =(1/m)s ab −(1/m 2 )s a s b ,
wherein the analysis terminal TA obtains parameters w 0 and w 1 for the linear model by calculating w 0 =μ b −w 1 μ a and W 1 =(σ a,b )/(σ a 2 ).
3. A secret computation system for performing computation while keeping data concealed, comprising:
a cyphertext generation device that generates cyphertext by encrypting the data;
a secret computation device that generates encrypted basic statistics by performing secret computation of predetermined basic statistics using the cyphertext while keeping the cyphertext concealed from the secret computation device; and
a computation device that generates decrypted basic statistics by decrypting the encrypted basic statistics and performs predetermined computation using the decrypted basic statistics,
wherein the cyphertext generation device, the secret computation device, and the computation device communicate with each other over a network, and
wherein the predetermined computation is a computation for estimating a parameter w=(w 0 ,w 1 , . . . ,w L ) for the following linear model
b=w 0 +w 1a1 + . . . +w LaL ,
between a matrix A of a number of records m and a number of attributes L and a vector b of the number of records m held by a registered terminals T H ,
the cyphertext generation device is the registered terminals T H ,
the secret computation device is n secret computation servers M 1 , . . . , M n ,
the computation device is an analysis terminal T A ,
cyphertext of “x” is described as [x]=([x] 1 , . . . ,[x] n ),
provided that i=1, . . . ,n, the registered terminals T H generates [A] i , [b] i , [m] i , and [L] i as the cyphertext and transmit [A] i , [b] i , [m] i , [L] i , and plaintext m and L to the secret computation servers M i ,
such that each of the secure computation servers M i receives, over the network, an input of one or more respective shares of original data A and b, and the data A and b are concealed from each of the secure computation servers, provided that i=1, . . . ,n, A=(a j,k ) 1≤j≤m, 1≤k≤L , q=1, . . . , L, s aq =Σ j=1 m a j,q ,, s aqb =Σ r=1 m a r,q b r , b=(b 1 , . . . ,b m ), s b =Σ j=1 m bj and S ajak =Σ r=1 m a r,j a r,k the secret computation servers M i generates [S A ] i =([S a1 ] i ), [S b ] i , [S A ] i =([S ajak ] i ) 1≤j,k≤L and [S Ab ] i =([S alb ] i , . . . ,[S aLb ] i ) as the basic statistics and transmits [S A ] i , [S b ] i , [S A ] i , and [S Ab ] i , [m] i and [L] i to the analysis terminal T A , the analysis terminal TA solves Formula (1) to find W=(W 0 , . . . ,W L )
(
m
s
a
1
…
s
a
L
s
a
1
s
a
1
2
…
s
a
1
a
L
⋮
⋮
⋱
⋮
s
a
L
s
a
L
a
1
…
s
a
L
a
L
)
(
w
0
w
1
⋮
w
L
)
=
(
s
b
s
a
1
b
⋮
s
a
L
b
)
.
(
1
)
4. A secret computation system for performing computation while keeping data concealed, comprising:
a cyphertext generation device that generates cyphertext by encrypting the data;
a secret computation device that generates encrypted basic statistics by performing secret computation of predetermined basic statistics using the cyphertext while keeping the cyphertext concealed from the secret computation device; and
a computation device that generates decrypted basic statistics by decrypting the encrypted basic statistics and performs predetermined computation using the decrypted basic statistics,
wherein the cyphertext generation device, the secret computation device, and the computation device communicate with each other over a network, and
wherein the predetermined computation is a computation for performing principal component analysis for data A which is a matrix of a number of records m and a number of attributes L held by a registered terminals T H ,
the cyphertext generation device is the registered terminals T H ,
the secret computation device is n secret computation servers M 1 , . . . , M n ,
the computation device is an analysis terminal T A ,
cyphertext of “x” is described as [x]=([x] 1 , . . . ,[x] n ),
provided that i=1, . . . ,n, the registered terminals T H generates [A] i , [m] i , and [L] i as the cyphertext and transmit [A] i , [m] i and [L] i and plaintext m and L to the secret computation servers M i ,
such that each of the secure computation servers M i receives, over the network, an input of one or more respective shares of original data A, and the data A are concealed from each of the secure computation servers, provided that i=1, . . . ,n, A=(a j,k ) 1≤j≤m, 1≤k≤L , q=1, . . . ,L, S ai =Σ j=1 m a q,j and S ajak =Σ r=1 m ar,jar,k , the secret computation servers M i generates [s] i =([s a1 ] i , . . . , [S aL ] i ) and [S] i =([s ajak ] i ) 1≤j,k≤L as the basic statistics and transmits [s] i , [S] i , [m] i and [L] i to the analysis terminal T A , and
provided that σ aj 2 =(1/m)s aj∧2 −(1/m 2 )s aj 2 , σ ak 2 =(1/m)s ak∧2 −(1/m 2 )s ak 2 the analysis terminal T A generates s, S, m and L as the decrypted basic statistics, calculates V=(σ aj,ak ) 1≤j,k≤L =((1/m)s ajak −(1/m 2 )s aj s ak ) 1≤j,k≤L , C=((σ aj,ak )/(σ aj 2 σ ak 2 ) 1/2 ) 1≤j,k≤L and performs computation of eigenvalues and eigenvectors for C to find p=(p 1 , . . . ,p L ), which are the principal components for data A.
5. A secret computation method for performing computation while keeping data concealed, comprising:
a cyphertext generation step in which a cyphertext generation device generates cyphertext by encrypting the data;
a secret computation step in which a secret computation device generates encrypted basic statistics by performing secret computation of predetermined basic statistics using the cyphertext while keeping the cyphertext concealed from the secret computation device; and
a computation step in which a computation device generates decrypted basic statistics by decrypting the encrypted basic statistics and performs predetermined computation using the decrypted basic statistics,
wherein the cyphertext generation device, the secret computation device, and the computation device communicate with each other over a network, and
wherein the predetermined computation is a computation for estimating a parameter w=(w 0 ,w 1 , . . . ,w L ) for the following linear model
b=w 0 +w 1a1 + . . . +w LaL
between a matrix A of a number of records m and a number of attributes L and a vector b of the number of records m held by a registered terminals T H ,
the cyphertext generation device is the registered terminals T H ,
the secret computation device is n secret computation servers M 1 , . . . , M n ,
the computation device is an analysis terminal T A ,
cyphertext of “x” is described as [x]=([x] 1 , . . . ,[x] n ),
provided that i=1, . . . ,n, the registered terminals T H generates [A] i , [b] i , [m] i , and [L] i as the cyphertext and transmit [A] i , [m] i and [L] i and plaintext m and L to the secret computation servers M i ,
such that each of the secure computation servers M receives, over the network, an input of one or more respective shares of original data A and b, and the data A and b are concealed from each of the secure computation servers, provided that provided that i=1, . . . ,n, A=(a j,k ) 1≤j≤m, 1≤k≤L , q=1, . . . ,L, S aq =Σ j=1 m a j,q , S aqb =Σ r=1 m a r,q b r , b=(b 1 , . . . , b m ) S b =Σ j=1 m a bj and S ajak =Σ r=1 m ar,jar,k , the secret computation servers M i generates [s A ] i =([s a1 ] i , . . . , [S aL ] i ),[S b ] i , [SA] i =([s ajak ] i ) 1≤j,k≤L and [S Ab ] i =([S alb ] i , . . . ,[S aLb ] i ) as the basic statistics and transmits [s A ] i , [sb] i , [S A ] i , and [s Ab ] i , [m] i , and [L] i , to the analysis terminal T A ,
the analysis terminal TA solves Formula (1) to find w=(w 0 , . . . ,w L )
(
m
s
a
1
…
s
a
L
s
a
1
s
a
1
2
…
s
a
1
a
L
⋮
⋮
⋱
⋮
s
a
L
s
a
L
a
1
…
s
a
L
a
L
)
(
w
0
w
1
⋮
w
L
)
=
(
s
b
s
a
1
b
⋮
s
a
L
b
)
.
(
1
)
6. A secret computation method for performing computation while keeping data concealed, comprising:
a cyphertext generation step in which a cyphertext generation device generates cyphertext by encrypting the data;
a secret computation step in which a secret computation device generates encrypted basic statistics by performing secret computation of predetermined basic statistics using the cyphertext while keeping the cyphertext concealed from the secret computation device; and
a computation step in which a computation device generates decrypted basic statistics by decrypting the encrypted basic statistics and performs predetermined computation using the decrypted basic statistics,
wherein the cyphertext generation device, the secret computation device, and the computation device communicate with each other over a network, and
wherein the predetermined computation is a computation for performing principal component analysis for data A which is a matrix of a number of records m and a number of attributes L held by a registered terminals T H ,
the cyphertext generation device is the registered terminals T H ,
the secret computation device is n secret computation servers M 1 , M n ,
the computation device is an analysis terminal T A ,
cyphertext of “x” is described as [x]=([x] 1 , . . . ,[x] n ),
provided that i=1, . . . ,n, the registered terminals T H generates [A] i , [m] i , and [L] i as the cyphertext and transmit [A] i , [m] i and [L] i and plaintext m and L to the secret computation servers M i ,
such that each of the secure computation servers M i receives, over the network, an input of one or more respective shares of original data A, and the data A are concealed from each of the secure computation servers, provided that i=1, . . . ,n, A=(a j,k ) 1≤j≤m, 1≤k≤L , q=1, . . . ,L, S ai =Σ j=1 m a q,j and S ajak =Σ r=1 m ar,jar,k , the secret computation servers M i generates [s] i =([s a1 ] i , . . . , [S aL ] i ) and [S] i =([s ajak ] i ) 1≤j,k≤L as the basic statistics and transmits [s] i , [S] i , [m] i and [L] i to the analysis terminal T A , and
provided that σ aj 2 =(1/m)s aj∧2 −(1/m 2 )s aj 2 , σ ak 2 =(1/m)s ak∧2 −(1/m 2 )s ak 2 the analysis terminal T A generates s, S, m and L as the decrypted basic statistics, calculates V=(σ aj,ak ) 1≤j,k≤L =((1/m)s ajak −(1/m 2 )s aj s ak ) 1≤j,k≤L , C=((σ aj,ak )/(σ aj 2 ak 2 ) 1/2 ) 1≤j,k≤L and performs computation of eigenvalues and eigenvectors for C to find p=(p 1 , . . . ,p L ), which are the principal components for data A.