Back to results
US 11,537,726 B2Granted
Secret computation system and method
AssigneeNippon Telegraph and Telephone Corporation
InventorsSatoshi Tanaka, Ryo Kikuchi, Koji Chida
Life of this patent
Estimating the term…
Abstract
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.
Claims6
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 w0 and w1 for a following linear model
- b=w0+w1a
- between m data a and m data b held by a registered terminals TH,
- the cyphertext generation device is the registered terminals TH,
- the secret computation device is n secret computation servers M1, . . . , Mn,
- the computation device is an analysis terminal TA,
- cyphertext of “x” is described as [x]=([x]1, . . . ,[x]n),
- provided that i=1, . . . ,n, the registered terminals TH 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 Mi,
- such that each of the secure computation servers Mi 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=(a1, . . . ,am), b=(b1, . . . ,bm), sa=Σj=1maj, sb=Σj=1mbj, sa∧2=Σj=1maj2 and sab=Σj=1majbj, the secret computation servers Mi generates [sa]i, [Sb]i, [sa∧2]i and [sab]i as the basic statistics and transmits [sa]i,[Sb]i, [sa∧2]i, [sab]i and [m]i to the analysis terminal TA, and
- the analysis terminal TA generates sa, Sb, sa∧2, sab and m as the decrypted basic statistics and calculates μa=(1/m)sa,μb=(1/m)sb, σa2=(1/m)sa∧2−(1/m2)sa2, σa,b=(1/m)sab−(1/m2)sasb
- wherein the analysis terminal TA obtains parameters w0 and w1 for the linear model by calculating w0=μb−w1μa and W1=(σa,b)/(σa2).
13 more elements
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 w0 and w1 for a following linear model
- b=w0+w1a
- between m data a and m data b held by a registered terminals TH,
- the cyphertext generation device is the registered terminals TH,
- the secret computation device is n secret computation servers M1, . . . , Mn,
- the computation device is an analysis terminal TA,
- cyphertext of “x” is described as [x]=([x]1, . . . ,[x]n),
- provided that i=1, . . . ,n, the registered terminals TH 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 Mi,
- such that each of the secure computation servers Mi 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=(a1, . . . ,am), b=(b1, . . . ,bm), sa=Σj=1maj, sb=Σj=1mbj, sa∧2=Σj=1maj2 and sab=Σj=1majbj, the secret computation servers Mi generates [sa]i, [Sb]i, [sa∧2]i and [sab]i as the basic statistics and transmits [sa]i,[Sb]i, [sa∧2]i, [sab]i and [m]i to the analysis terminal TA, and
- the analysis terminal TA generates sa, Sb, sa∧2, sab and m as the decrypted basic statistics and calculates μa=(1/m)sa,μb=(1/m)sb, σa2=(1/m)sa∧2−(1/m2)sa2, σa,b=(1/m)sab−(1/m2)sasb,
- wherein the analysis terminal TA obtains parameters w0 and w1 for the linear model by calculating w0=μb−w1μa and W1=(σa,b)/(σa2).
13 more elements
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=(w0,w1, . . . ,wL) for the following linear model
- b=w0+w1a1+ . . . +wLaL,
- 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 TH,
- the cyphertext generation device is the registered terminals TH,
- the secret computation device is n secret computation servers M1, . . . , Mn,
- the computation device is an analysis terminal TA,
- cyphertext of “x” is described as [x]=([x]1, . . . ,[x]n),
- provided that i=1, . . . ,n, the registered terminals TH 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 Mi,
- such that each of the secure computation servers Mi 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=(aj,k)1≤j≤m, 1≤k≤L, q=1, . . . , L, saq=Σj=1maj,q,, saqb=Σr=1mar,qbr, b=(b1, . . . ,bm), sb=Σj=1mbj and Sajak=Σr=1mar,jar,k the secret computation servers Mi generates [SA]i=([Sa1]i), [Sb]i, [SA]i=([Sajak]i)1≤j,k≤L and [SAb]i=([Salb]i, . . . ,[SaLb]i) as the basic statistics and transmits [SA]i, [Sb]i, [SA]i, and [SAb]i, [m]i and [L]i to the analysis terminal TA, the analysis terminal TA solves Formula (1) to find W=(W0, . . . ,WL)
- (
- 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
- )
85 more elements
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 TH,
- the cyphertext generation device is the registered terminals TH,
- the secret computation device is n secret computation servers M1, . . . , Mn,
- the computation device is an analysis terminal TA,
- cyphertext of “x” is described as [x]=([x]1, . . . ,[x]n),
- provided that i=1, . . . ,n, the registered terminals TH 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 Mi,
- such that each of the secure computation servers Mi 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=(aj,k)1≤j≤m, 1≤k≤L, q=1, . . . ,L, Sai=Σj=1maq,j and Sajak=Σr=1mar,jar,k, the secret computation servers Mi generates [s]i=([sa1]i, . . . , [SaL]i) and [S]i=([sajak]i)1≤j,k≤L as the basic statistics and transmits [s]i, [S]i, [m]i and [L]i to the analysis terminal TA, and
- provided that σaj2=(1/m)saj∧2−(1/m2)saj2, σak2=(1/m)sak∧2−(1/m2)sak2 the analysis terminal TA generates s, S, m and L as the decrypted basic statistics, calculates V=(σaj,ak)1≤j,k≤L=((1/m)sajak−(1/m2)sajsak)1≤j,k≤L, C=((σaj,ak)/(σaj2σak2)1/2)1≤j,k≤L and performs computation of eigenvalues and eigenvectors for C to find p=(p1, . . . ,pL), which are the principal components for data A.
10 more elements
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=(w0,w1, . . . ,wL) for the following linear model
- b=w0+w1a1+ . . . +wLaL
- 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 TH,
- the cyphertext generation device is the registered terminals TH,
- the secret computation device is n secret computation servers M1, . . . , Mn,
- the computation device is an analysis terminal TA,
- cyphertext of “x” is described as [x]=([x]1, . . . ,[x]n),
- provided that i=1, . . . ,n, the registered terminals TH 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 Mi,
- 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=(aj,k)1≤j≤m, 1≤k≤L, q=1, . . . ,L, Saq=Σj=1maj,q, Saqb=Σr=1mar,q br, b=(b1, . . . , bm) Sb=Σj=1mabj and Sajak=Σr=1mar,jar,k, the secret computation servers Mi generates [sA]i=([sa1]i, . . . , [SaL]i),[Sb]i, [SA]i=([sajak]i)1≤j,k≤L and [SAb]i=([Salb]i, . . . ,[SaLb]i) as the basic statistics and transmits [sA]i, [sb]i, [SA]i, and [sAb]i, [m]i, and [L]i, to the analysis terminal TA,
- the analysis terminal TA solves Formula (1) to find w=(w0, . . . ,wL)
- (
- 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
- )
86 more elements
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 TH,
- the cyphertext generation device is the registered terminals TH,
- the secret computation device is n secret computation servers M1, Mn,
- the computation device is an analysis terminal TA,
- cyphertext of “x” is described as [x]=([x]1, . . . ,[x]n),
- provided that i=1, . . . ,n, the registered terminals TH 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 Mi,
- such that each of the secure computation servers Mi 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=(aj,k)1≤j≤m, 1≤k≤L, q=1, . . . ,L, Sai=Σj=1maq,j and Sajak=Σr=1mar,jar,k, the secret computation servers Mi generates [s]i=([sa1]i, . . . , [SaL]i) and [S]i=([sajak]i)1≤j,k≤L as the basic statistics and transmits [s]i, [S]i, [m]i and [L]i to the analysis terminal TA, and
- provided that σaj2=(1/m)saj∧2−(1/m2)saj2, σak2=(1/m)sak∧2−(1/m2)sak2 the analysis terminal TA generates s, S, m and L as the decrypted basic statistics, calculates V=(σaj,ak)1≤j,k≤L=((1/m)sajak−(1/m2)sajsak)1≤j,k≤L, C=((σaj,ak)/(σaj2ak2)1/2)1≤j,k≤L and performs computation of eigenvalues and eigenvectors for C to find p=(p1, . . . ,pL), which are the principal components for data A.
10 more elements
Dependencies are inferred from the claim text.