Secret computation system and method

Patent metadata

Field	Value
Publication number	US-11537726-B2
Application number	US-201816772543-A
Country	US
Kind code	B2
Filing date	Dec 14, 2018
Priority date	Dec 18, 2017
Publication date	Dec 27, 2022
Grant date	Dec 27, 2022

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.

First claim

What is claimed is:

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

Assignees

• Nippon Telegraph & Telephone

Inventors

• Tanaka Satoshi
• Kikuchi Ryo
• Chida Koji

Classifications

• G06F21/6254 Primary

  by anonymising data, e.g. decorrelating personal data from the owner's identification · CPC title

• H04L9/0894

  Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage · CPC title

• G06F21/602 Primary

  Providing cryptographic facilities or services · CPC title

• G06F2221/2107

  File encryption · CPC title

• H04L2209/46

  Secure multiparty computation, e.g. millionaire problem · CPC title