(57)【特許請求の範囲】
【請求項１】
データを秘匿化したまま計算を行う秘密計算システムであって、
上記データを暗号化することにより暗号文を生成する暗号文生成装置と、
上記暗号文を秘匿化したまま上記暗号文を用いて所定の基礎統計量を秘密計算することにより暗号化された基礎統計量を生成する秘密計算装置と、
上記暗号化された基礎統計量を復号することにより復号された基礎統計量を生成し、上記復号された基礎統計量を用いて所定の計算を行う計算装置と、
を含む秘密計算システムであって、
前記所定の計算は、登録端末THが持つm個のデータaとデータb間の線形モデルb=w0+w1aについて、パラメータw0,w1の推定を行う計算であり、
前記暗号文生成装置は、登録端末THであり、
前記秘密計算装置は、n台の秘密計算サーバM1,…,Mnであり、
前記計算装置は、分析端末TAであり、
xの暗号文を[x]=([x]1,…,[x]n)のように記述するとして、
i=1,…,nであり、前記登録端末THは、前記暗号文として、[a]i, [b]i, [m]iを生成して、[a]i, [b]i, [m]i と平文mを、前記秘密計算サーバMiに送信し、
i=1,…,nであり、a=(a1,…,am), b=(b1,…,bm), sa=Σj=1maj, sb=Σj=1mbj, sa^2=Σj=1maj2, sab=Σj=1majbjであり、前記秘密計算サーバMiは、前記暗号化された基礎統計量として、[sa]i, [sb]i, [sa^2]iと[sab]iを生成して、[sa]i, [sb]i, [sa^2]i,[sab]iと[m]iを分析端末TAに送信し、
前記分析端末TAは、前記復号された基礎統計量として、sa, sb, sa^2, sab, mを生成し、μa=(1/m)sa, μb=(1/m)sb, σa2=(1/m)sa^2-(1/m2)sa2, σa,b=(1/m)sab-(1/m2)sasbを計算し、w0=μb-w1μa, w1=(σa,b)/(σa2)を計算する。
【請求項２】
データを秘匿化したまま計算を行う秘密計算システムであって、
上記データを暗号化することにより暗号文を生成する暗号文生成装置と、
上記暗号文を秘匿化したまま上記暗号文を用いて所定の基礎統計量を秘密計算することにより暗号化された基礎統計量を生成する秘密計算装置と、
上記暗号化された基礎統計量を復号することにより復号された基礎統計量を生成し、上記復号された基礎統計量を用いて所定の計算を行う計算装置と、
を含む秘密計算システムであって、
前記所定の計算は、登録端末THが持つレコード数m、属性数Lの行列A=(a1T,…,aLT)とレコード数mのベクトルb間の線形モデルb=w0+w1a1+…+wLaLについて、パラメータw=(w0,w1,…,wL)の推定を行う計算であり、
前記暗号文生成装置は、登録端末THであり、
前記秘密計算装置は、n台の秘密計算サーバM1,…,Mnであり、
前記計算装置は、分析端末TAであり、
xの暗号文を[x]=([x]1,…,[x]n)のように記述するとして、
i=1,…,nであり、前記登録端末THは、前記暗号文として、[A]i, [b]i, [m]i, [L]iを生成して、[A]i, [b]i, [m]i, [L]iと平文m,Lを、前記秘密計算サーバMiに送信し、
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であり、sajak=Σr=1mar,jar,kであり、前記秘密計算サーバMiは、前記暗号化された基礎統計量として、[sA]i=([sa1]i,…, [saL]i), [sb]i, [SA]i=([sajak]i)1≦j,k≦L=と[sAb]i= ([sa1b]i,…, [saLb]i)を生成して、[sA]i, [sb]i, [SA]i, [sAb]iと[m]i, [L]iを分析端末TAに送信し、
前記分析端末TAは、前記復号された基礎統計量として、sA, sb, SA, sAb, m, Lを生成し、
【数２】
0006988918.tif 000004
式（１）の線形方程式を解き、w=(w0,…,wL)を求める。
【請求項３】
データを秘匿化したまま計算を行う秘密計算システムであって、
上記データを暗号化することにより暗号文を生成する暗号文生成装置と、
上記暗号文を秘匿化したまま上記暗号文を用いて所定の基礎統計量を秘密計算することにより暗号化された基礎統計量を生成する秘密計算装置と、
上記暗号化された基礎統計量を復号することにより復号された基礎統計量を生成し、上記復号された基礎統計量を用いて所定の計算を行う計算装置と、
を含む秘密計算システムであって、
前記所定の計算は、登録端末THが持つレコード数m、属性数Lの行列であるデータAに対して主成分分析を行い、各主成分p=(p1,…,pL)を求める計算であり、
前記暗号文生成装置は、登録端末THであり、
前記秘密計算装置は、n台の秘密計算サーバM1,…,Mnであり、
前記計算装置は、分析端末TAであり、
xの暗号文を[x]=([x]1,…,[x]n)のように記述するとして、
前記登録端末THは、i=1,…,nであり、前記暗号文として、[A]i, [m]i, [L]iを生成して、[A]i, [m]i, [L]iと平文m,Lを、前記秘密計算サーバMiに送信し、
i=1,…,nであり、A=(aj,k)1≦j≦m,1≦k≦Lであり、q=1,…,Lとしてsai=Σj=1maq,jであり、sajak=Σr=1mar,jar,kであり、前記秘密計算サーバMiは、前記暗号化された基礎統計量として、[s]i=([sa1]i,…,[saL]i), [S]i=([sajak]i)1≦j,k≦Lを生成して、[s]i, [S]iと[m]i, [L]iを分析端末TAに送信し、
σaj2=(1/m)saj^2-(1/m2)saj2,σak2=(1/m)sak^2-(1/m2)sak2であり、前記分析端末TAは、前記復号された基礎統計量として、s, S, m, Lを生成し、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を求め、Cに対して固有値及び固有ベクトルの計算を行い、p=(p1,…,pL)を求める。
【請求項４】
データを秘匿化したまま計算を行う秘密計算方法であって、
暗号文生成装置が、上記データを暗号化することにより暗号文を生成する暗号文生成装置と、
秘密計算装置が、上記暗号文を秘匿化したまま上記暗号文を用いて所定の基礎統計量を秘密計算することにより暗号化された基礎統計量を生成する秘密計算ステップと、
計算装置が、上記暗号化された基礎統計量を復号することにより復号された基礎統計量を生成し、上記復号された基礎統計量を用いて所定の計算を行う計算ステップと、
を含む秘密計算方法であって、
前記所定の計算は、登録端末THが持つm個のデータaとデータb間の線形モデルb=w0+w1aについて、パラメータw0,w1の推定を行う計算であり、
前記暗号文生成装置は、登録端末THであり、
前記秘密計算装置は、n台の秘密計算サーバM1,…,Mnであり、
前記計算装置は、分析端末TAであり、
xの暗号文を[x]=([x]1,…,[x]n)のように記述するとして、
i=1,…,nであり、前記登録端末THは、前記暗号文として、[a]i, [b]i, [m]iを生成して、[a]i, [b]i, [m]i と平文mを、前記秘密計算サーバMiに送信し、
i=1,…,nであり、a=(a1,…,am), b=(b1,…,bm), sa=Σj=1maj, sb=Σj=1mbj, sa^2=Σj=1maj2, sab=Σj=1majbjであり、前記秘密計算サーバMiは、前記暗号化された基礎統計量として、[sa]i, [sb]i, [sa^2]iと[sab]iを生成して、[sa]i, [sb]i, [sa^2]i,[sab]iと[m]iを分析端末TAに送信し、
前記分析端末TAは、前記復号された基礎統計量として、sa, sb, sa^2, sab, mを生成し、μa=(1/m)sa, μb=(1/m)sb, σa2=(1/m)sa^2-(1/m2)sa2, σa,b=(1/m)sab-(1/m2)sasbを計算し、w0=μb-w1μa, w1=(σa,b)/(σa2)を計算する。
【請求項５】
データを秘匿化したまま計算を行う秘密計算方法であって、
暗号文生成装置が、上記データを暗号化することにより暗号文を生成する暗号文生成装置と、
秘密計算装置が、上記暗号文を秘匿化したまま上記暗号文を用いて所定の基礎統計量を秘密計算することにより暗号化された基礎統計量を生成する秘密計算ステップと、
計算装置が、上記暗号化された基礎統計量を復号することにより復号された基礎統計量を生成し、上記復号された基礎統計量を用いて所定の計算を行う計算ステップと、
を含む秘密計算方法であって、
前記所定の計算は、登録端末THが持つレコード数m、属性数Lの行列A=(a1T,…,aLT)とレコード数mのベクトルb間の線形モデルb=w0+w1a1+…+wLaLについて、パラメータw=(w0,w1,…,wL)の推定を行う計算であり、
前記暗号文生成装置は、登録端末THであり、
前記秘密計算装置は、n台の秘密計算サーバM1,…,Mnであり、
前記計算装置は、分析端末TAであり、
xの暗号文を[x]=([x]1,…,[x]n)のように記述するとして、
i=1,…,nであり、前記登録端末THは、前記暗号文として、[A]i, [b]i, [m]i, [L]iを生成して、[A]i, [b]i, [m]i, [L]iと平文m,Lを、前記秘密計算サーバMiに送信し、
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であり、sajak=Σr=1mar,jar,kであり、前記秘密計算サーバMiは、前記暗号化された基礎統計量として、[sA]i=([sa1]i,…, [saL]i), [sb]i, [SA]i=([sajak]i)1≦j,k≦L=と[sAb]i= ([sa1b]i,…, [saLb]i)を生成して、[sA]i, [sb]i, [SA]i, [sAb]iと[m]i, [L]iを分析端末TAに送信し、
前記分析端末TAは、前記復号された基礎統計量として、sA, sb, SA, sAb, m, Lを生成し、
【数３】
0006988918.tif 000005
式（１）の線形方程式を解き、w=(w0,…,wL)を求める。
【請求項６】
データを秘匿化したまま計算を行う秘密計算方法であって、
暗号文生成装置が、上記データを暗号化することにより暗号文を生成する暗号文生成装置と、
秘密計算装置が、上記暗号文を秘匿化したまま上記暗号文を用いて所定の基礎統計量を秘密計算することにより暗号化された基礎統計量を生成する秘密計算ステップと、
計算装置が、上記暗号化された基礎統計量を復号することにより復号された基礎統計量を生成し、上記復号された基礎統計量を用いて所定の計算を行う計算ステップと、
を含む秘密計算方法であって、
前記所定の計算は、登録端末THが持つレコード数m、属性数Lの行列であるデータAに対して主成分分析を行い、各主成分p=(p1,…,pL)を求める計算であり、
前記暗号文生成装置は、登録端末THであり、
前記秘密計算装置は、n台の秘密計算サーバM1,…,Mnであり、
前記計算装置は、分析端末TAであり、
xの暗号文を[x]=([x]1,…,[x]n)のように記述するとして、
前記登録端末THは、i=1,…,nであり、前記暗号文として、[A]i, [m]i, [L]iを生成して、[A]i, [m]i, [L]iと平文m,Lを、前記秘密計算サーバMiに送信し、
i=1,…,nであり、A=(aj,k)1≦j≦m,1≦k≦Lであり、q=1,…,Lとしてsai=Σj=1maq,jであり、sajak=Σr=1mar,jar,kであり、前記秘密計算サーバMiは、前記暗号化された基礎統計量として、[s]i=([sa1]i,…,[saL]i), [S]i=([sajak]i)1≦j,k≦Lを生成して、[s]i, [S]iと[m]i, [L]iを分析端末TAに送信し、
σaj2=(1/m)saj^2-(1/m2)saj2,σak2=(1/m)sak^2-(1/m2)sak2であり、前記分析端末TAは、前記復号された基礎統計量として、s, S, m, Lを生成し、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を求め、Cに対して固有値及び固有ベクトルの計算を行い、p=(p1,…,pL)を求める。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを秘匿しつつデータ処理を行う秘密計算の技術分野に関する。例えば、秘密多変量解析の技術に関する。
【背景技術】
【０００２】
データを秘匿しつつデータ処理を行う秘密計算の従来技術として、特許文献１に記載された技術が知られている。秘密計算の従来技術では、以下の３個のフェーズが行われる。【０００３】
１． 暗号化フェーズ：データを暗号化し秘匿する。
２． 秘密計算フェーズ：暗号化したデータ、すなわち暗号文のまま、元のデータに対して目的の計算ができるアルゴリズム又はプロトコルを利用し、暗号文を処理する。
３． 復号フェーズ：秘密計算フェーズの処理の結果として得られる暗号文を復号し、目的の計算結果を取得する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１７−０２８６１７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記の従来技術は、目的の計算処理を全て２．の秘密計算フェーズで行っている。【０００６】
一般に、秘密計算のアルゴリズムは、データを暗号化せずに計算するアルゴリズムよりも処理が複雑である。このため、秘密計算のアルゴリズムの計算の処理に要する時間は、平文の計算のアルゴリズムの計算の処理に要する時間よりも長い。このため、線型方程式の解決を必要とする線形回帰、行列の固有値及び固有ベクトルの計算を必要とする主成分分析といった複雑な計算を用いるアルゴリズムを秘密計算で全て処理してしまうと、処理に要する時間が膨大になってしまう可能性がある。【０００７】
この発明の目的は、データを秘匿化したまま従来よりも速い速度で秘密計算を行うことができる秘密計算システム及び方法を提供することである。
【課題を解決するための手段】
【０００８】
この発明の一態様による秘密計算システムは、データを秘匿化したまま計算を行う秘密計算システムであって、データを暗号化することにより暗号文を生成する暗号文生成装置と、暗号文を秘匿化したまま暗号文を用いて所定の基礎統計量を秘密計算することにより暗号化された基礎統計量を生成する秘密計算装置と、暗号化された基礎統計量を復号することにより復号された基礎統計量を生成し、復号された基礎統計量を用いて所定の計算を行う計算装置と、を備えており所定の計算は、登録端末THが持つm個のデータaとデータb間の線形モデルb=w0+w1aについて、パラメータw0,w1の推定を行う計算であり、暗号文生成装置は、登録端末THであり、秘密計算装置は、n台の秘密計算サーバM1,…,Mnであり、計算装置は、分析端末TAであり、xの暗号文を[x]=([x]1,…,[x]n)のように記述するとして、i=1,…,nであり、登録端末THは、暗号文として、[a]i,[b]i,[m]iを生成して、[a]i,[b]i,[m]iと平文mを、秘密計算サーバMiに送信し、i=1,…,nであり、a=(a1,…,am),b=(b1,…,bm),sa=Σj=1maj,sb=Σj=1mbj,sa^2=Σj=1maj2,sab=Σj=1majbjであり、秘密計算サーバMiは、暗号化された基礎統計量として、[sa]i,[sb]i,[sa^2]iと[sab]iを生成して、[sa]i,[sb]i,[sa^2]i,[sab]iと[m]iを分析端末TAに送信し、分析端末TAは、復号された基礎統計量として、sa,sb,sa^2,sab,mを生成し、μa=(1/m)sa,μb=(1/m)sb,σa2=(1/m)sa^2-(1/m2)sa2,σa,b=(1/m)sab-(1/m2)sasbを計算し、w0=μb-w1μa,w1=(σa,b)/(σa2)を計算する。
この発明の一態様による秘密計算システムは、データを秘匿化したまま計算を行う秘密計算システムであって、データを暗号化することにより暗号文を生成する暗号文生成装置と、暗号文を秘匿化したまま暗号文を用いて所定の基礎統計量を秘密計算することにより暗号化された基礎統計量を生成する秘密計算装置と、暗号化された基礎統計量を復号することにより復号された基礎統計量を生成し、復号された基礎統計量を用いて所定の計算を行う計算装置と、を備えており、所定の計算は、登録端末THが持つレコード数m、属性数Lの行列A=(a1T,…,aLT)とレコード数mのベクトルb間の線形モデルb=w0+w1a1+…+wLaLについて、パラメータw=(w0,w1,…,wL)の推定を行う計算であり、暗号文生成装置は、登録端末THであり、秘密計算装置は、n台の秘密計算サーバM1,…,Mnであり、計算装置は、分析端末TAであり、xの暗号文を[x]=([x]1,…,[x]n)のように記述するとして、i=1,…,nであり、登録端末THは、暗号文として、[A]i,[b]i,[m]i,[L]iを生成して、[A]i,[b]i,[m]i,[L]iと平文m,Lを、秘密計算サーバMiに送信し、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であり、sajak=Σr=1mar,jar,kであり、秘密計算サーバMiは、暗号化された基礎統計量として、[sA]i=([sa1]i,…,[saL]i),[sb]i,[SA]i=([sajak]i)1≦j,k≦L=と[sAb]i=([sa1b]i,…,[saLb]i)を生成して、[sA]i,[sb]i,[SA]i,[sAb]iと[m]i,[L]iを分析端末TAに送信し、分析端末TAは、復号された基礎統計量として、sA,sb,SA,sAb,m,Lを生成し、
【数１】
0006988918.tif 000002
式（１）の線形方程式を解き、w=(w0,…,wL)を求める。
この発明の一態様による秘密計算システムは、データを秘匿化したまま計算を行う秘密計算システムであって、データを暗号化することにより暗号文を生成する暗号文生成装置と、暗号文を秘匿化したまま暗号文を用いて所定の基礎統計量を秘密計算することにより暗号化された基礎統計量を生成する秘密計算装置と、暗号化された基礎統計量を復号することにより復号された基礎統計量を生成し、復号された基礎統計量を用いて所定の計算を行う計算装置と、を備えており、所定の計算は、登録端末THが持つレコード数m、属性数Lの行列であるデータAに対して主成分分析を行い、各主成分p=(p1,…,pL)を求める計算であり、暗号文生成装置は、登録端末THであり、秘密計算装置は、n台の秘密計算サーバM1,…,Mnであり、計算装置は、分析端末TAであり、xの暗号文を[x]=([x]1,…,[x]n)のように記述するとして、登録端末THは、i=1,…,nであり、暗号文として、[A]i,[m]i,[L]iを生成して、[A]i,[m]i,[L]iと平文m,Lを、秘密計算サーバMiに送信し、i=1,…,nであり、A=(aj,k)1≦j≦m,1≦k≦Lであり、q=1,…,Lとしてsai=Σj=1maq,jであり、sajak=Σr=1mar,jar,kであり、秘密計算サーバMiは、暗号化された基礎統計量として、[s]i=([sa1]i,…,[saL]i),[S]i=([sajak]i)1≦j,k≦Lを生成して、[s]i,[S]iと[m]i,[L]iを分析端末TAに送信し、σaj2=(1/m)saj^2-(1/m2)saj2,σak2=(1/m)sak^2-(1/m2)sak2であり、分析端末TAは、復号された基礎統計量として、s,S,m,Lを生成し、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を求め、Cに対して固有値及び固有ベクトルの計算を行い、p=(p1,…,pL)を求める。
【発明の効果】
【０００９】
データを秘匿化したまま従来よりも速い速度で秘密計算を行うことができる。
【図面の簡単な説明】
【００１０】
【図１】秘密計算システムの例を示すブロック図。
【図２】秘密計算方法の例を説明するための流れ図。
【図３】第一実施形態を説明するための図。
【発明を実施するための形態】
【００１１】
以下、図面を参照して、この発明の一実施形態について説明する。
【００１２】
［記法］
m,Lをそれぞれ１以上の自然数とする。単一のデータをaのように記述する。また、m次のベクトルをa=(a1,…,am)のように記述する。また、m行L列の行列をA=(aj,k)1≦j≦m,1≦k≦L、または、A=(a1T,…,aLT)のように記述する。ai(i=1,…,L)はm次元ベクトルである。Tは、ベクトル又は行列の転置を意味する。
【００１３】
nを１以上の自然数とする。aの暗号文を[a]=([a]1,…,[a]n)のように記述する。[a]iを[a]のi番目のシェアと呼ぶ。ただし、n=1のとき、[a]=[a]1である。また、[a]=([a]1,…,[a]m)をm次のベクトルaの暗号文とする。同様に、[A]=([aj,k])1≦j≦m,1≦k≦Lをm行L列の行列Aの暗号文とする。
【００１４】
ベクトルa内の要素の総和saを次式のように記述する。
【００１５】
sa=Σj=1maj
また、ベクトルaとベクトルbの要素同士の積abを次式の様に記述する。
【００１６】
ab=(a1b1,…,ambm)
更に、a2=aaとする。
【００１７】
［統計量］
a又はAの性質を示す量を統計量と呼ぶ。図３に、本発明で用いる統計量の例を示す。図３では、各統計量の記号・記法、定義及び定義と等価な式が示されている。
【００１８】
なお、図３の統計量の中の、レコード数、属性数、総和、二乗和及び積和の５つの統計量の少なくとも１つを基礎統計量と呼ぶことにする。
なお、図３では、レコード数、属性数、総和、二乗和及び積和は以下のように定義されている。
レコード数m:aの要素数、または、Aの行数
属性数L:Aの列数
総和sa:Σj=1maj
二乗和s(a^2):Σj=1maj2
積和sab:Σj=1majbj
【００１９】
［技術の概要］
後述する実施形態は、基礎統計量（すなわち、例えば、レコード数、属性数、総和、二乗和及び積和の少なくとも１つ）を秘密計算によって安全に計算し、基礎統計量を平文に復号して高速に分析等の計算を行う。後述する実施形態は、以下の３つのフェーズに分かれた処理を行う。
【００２０】
１． 暗号化フェーズ：データを暗号化し、秘匿する。
２． 秘密計算フェーズ：暗号文のままで、個々のデータから基礎統計量の計算を処理する。
３． 計算フェーズ：計算された基礎統計量の暗号文を復号し、復号された基礎統計量を用いて目的とする計算を平文で処理する。
【００２１】
後述する実施形態は、基礎統計量の計算処理にのみ秘密計算を適用している点で、従来手法と異なる。この手法を適用することで、線形回帰、主成分分析等の処理に比較的時間がかかる計算を従来よりも高速に処理可能である。
【００２２】
なお、線形回帰で用いる線型方程式は、例えば以下の式（１）に示す通り、基礎統計量によって構成される。
【００２３】
【数１】
0006988918.tif 000003
【００２４】
したがって、基礎統計量を秘密計算で安全に計算した後に、例えば線型方程式を平文で解決することによって効率的にパラメータを推定することが可能である。
【００２５】
また、主成分分析は、例えば、Aの分散共分散行列V=(σas,at)1≦s,t≦L又は相関係数行列C=(ρas,at)1≦s,t≦Lに対して、固有値及び固有ベクトル計算を行うことにより実施することができる。
【００２６】
図３から、分散共分散行列は、基礎統計量から計算できることがわかる。さらに、相関係数行列も分散及び共分散から計算可能である。したがって、何れかの行列を用いる場合においても、基礎統計量さえ安全に計算することができれば、以降はその計算された基礎統計量を用いる事で主成分分析を実現できる。
【００２７】
［暗号方式］
本発明では、暗号文を復号することなく、例えば以下の演算を実現できる暗号方式を用いる。このような暗号方式を実現する手段として、参考文献１，２が知られている。
【００２８】
１．加算: [a],[b]を入力として、加算a+bの暗号文[a+b]を生成する。
２．乗算: [a],[b] を入力として、乗算abの暗号文[ab]を生成する。
３．総和: [a]を入力として、総和saの暗号文[sa]を生成する。
４．積和:[a],[b]を入力として、積和sabの暗号文[sab]を生成する。
【００２９】
〔参考文献１〕SHAMIR, Adi. "How to share a secret", Communications of the ACM, 1979, 22.11: p.612-613.
〔参考文献２〕GENTRY, Craig, et al. "Fully homomorphic encryption using ideal lattices", In: STOC. 2009. p.169-178.
【００３０】
［実施形態］
秘密計算システムの実施形態は、図１に示すように、暗号文生成装置１、管理サーバ２、秘密計算装置３及び計算装置４を例えば備えている。この例では、暗号文生成装置１は、複数の登録端末THである。また、秘密計算装置３は、n台の秘密計算サーバM1,…,Mnである。nは２以上の所定の整数である。さらに、計算装置４は、分析端末TAである。
【００３１】
暗号文生成装置１、管理サーバ２、秘密計算装置３及び計算装置４は、互いにネットワークを通じて通信可能であり、互いにデータの送受信が可能である。
【００３２】
秘密計算システムは、［暗号方式］で述べた演算を処理できる秘密計算サーバM1,…,Mnを用いる。各秘密計算サーバMi(i=1,…,n)はネットワークを通じて、別の秘密計算サーバMjにアクセス可能であり、互いにデータの送受信が可能である。
【００３３】
秘密計算方法は、秘密計算システムを構成する装置が、図２及び以下に説明するステップＳ１からＳ１１の処理を行うことにより例えば実現される。
【００３４】
暗号文生成装置１は、データを暗号化することにより暗号文を生成する（ステップＳ１）。生成された暗号文は、管理サーバ２に送信される（ステップＳ２）。
【００３５】
暗号文生成装置１は、例えば複数の登録端末THである。この場合、複数の登録端末THのそれぞれは、自身が持つデータを例えば参考文献１，２に記載された手法で秘密分散することにより、データのシェアを生成する。この生成されたシェアが暗号文の一例である。
【００３６】
管理サーバ２は、受信した暗号文を、秘密計算装置３に送信する（ステップＳ３）。
【００３７】
秘密計算装置３は、受信した暗号文を記憶部に記憶させる（ステップＳ４）。例えば、受信した暗号文は、秘密計算装置３の秘密計算サーバMi(i=1,…,n)の図示していない記憶部に記憶される。
【００３８】
計算装置４は、管理サーバ２に計算依頼を送信する（ステップＳ５）。計算装置４は、例えば分析端末TAである。この場合、分析端末TAは、計算依頼としての分析依頼を管理サーバ２に送信する。
【００３９】
管理サーバ２は、受信した計算依頼に対応する計算を行うために必要な基礎統計量の計算依頼である基礎統計量計算依頼を秘密計算装置３に送信する（ステップＳ６）。
【００４０】
秘密計算装置３は、記憶部から読み込んだ暗号文を用いて、この暗号文を秘匿化したまま、所定の基礎統計量を秘密計算することにより暗号化された基礎統計量を生成する（ステップＳ７）。
【００４１】
秘密計算装置３は、例えば秘密計算サーバM1,…,Mnである。この場合、秘密計算サーバM1,…,Mnが、共同して、例えば参考文献１，２に記載された手法を用いて、記憶部から読み込んだ暗号文を用いて、この暗号文を秘匿化したまま、所定の基礎統計量を秘密計算する。
【００４２】
生成された暗号化された基礎統計量は、管理サーバ２に送信される（ステップＳ８）。
所定の基礎統計量は、受信した基礎統計量計算依頼に対応する基礎統計量である。
【００４３】
管理サーバ２は、受信した暗号化された基礎統計量を計算装置４に送信する（ステップＳ９）。
【００４４】
計算装置４は、受信した暗号化された基礎統計量を復号することにより復号された基礎統計量を生成する（ステップＳ１０）。
【００４５】
計算装置４は、復号された基礎統計量を用いて所定の計算を行う（ステップＳ１１）。上記の実施形態のポイントの１つは、統計量のみで計算できる分析の特徴と秘密計算の性質を組み合わせた部分にある。
【００４６】
レコード数、総和、平均及び分散といった統計量は、個々のデータではなくデータ集合の特徴を示す数値である。そのため、これらの統計量のみを用いて計算する分析においては、データ集合について解ればよく、個々のデータそのものは必要としない。しかし、分析のアルゴリズム上、統計量を計算することは不可避であり、その統計量を計算するために個々のデータに触れなければならない。
【００４７】
一方で、秘密計算は、暗号文によりデータを秘匿したまま安全に計算可能だが、一般に平文による計算よりも遅い。特に、除算等の複雑な計算処理に対しては速度差が顕著に現れるため、複雑な計算を要する分析を秘密計算で全て実装することはコストが高い。反対に、［暗号方式］の欄で示した加算や乗算は秘密計算でも十分高速であり、これらの演算に基づく基礎統計量は秘密計算で高速に処理できる。
【００４８】
したがって、基礎統計量に基づく統計量から計算できる分析では、基礎統計量を計算する部分のみを秘密計算で処理することで個々のデータの中身は秘匿し、計算した基礎統計量を平文に復号することで、分析の計算を高速に処理することができる。これにより、安全性と高速性を両立させた分析が実現される。
【００４９】
なお、上記の実施形態では、管理サーバ２と計算装置４とが別装置として記述されているが、管理サーバ２と計算装置４は同一の装置に実現されていてもよい。
【００５０】
［実施例］
[[実施例１]]
実施例１は、線形単回帰分析を行う実施例である。より具体的には、実施例１は、計算装置４である分析端末TAが、秘密計算装置３であるn台の秘密計算サーバM1,…,Mnを用いて、暗号文生成装置１である登録端末THが持つm世帯の収入データaと支出データb間の以下の線形モデル
b=w0+w1a
について、パラメータw0,w1の推定を行う実施例である。
【００５１】
<暗号化フェーズ>
暗号化フェーズとして、ステップＳ１からＳ３において、以下の処理が行われる。
【００５２】
登録端末THは、例えば参考文献１，２の暗号方式を用いて、a,b,mを暗号化する。
【００５３】
登録端末THは、暗号文であるシェア[a]i, [b]i, [m]i と平文mを秘密計算サーバM1,…,Mnに対して送信する。
【００５４】
<秘密計算フェーズ>
秘密計算フェーズとして、ステップＳ７からＳ９において、以下の処理が行われる。
【００５５】
各秘密計算サーバMiは、［暗号方式］の欄で示した総和の秘密計算により、[a]i, [b]iを用いて、[sa]i, [sb]iを求める。ここで、a=(a1,…,am)としてsa=Σj=1majであり、b=(b1,…,bm)としてsb=Σj=1mbjである。
【００５６】
各秘密計算サーバMiは、［暗号方式］の欄で示した積和の秘密計算により、[a]i, [b]iを用いて、[sa^2]iと[sab]iを求める。ここで、a=(a1,…,am),b=(b1,…,bm)としてsa^2=Σj=1maj2,sab=Σj=1majbjである。
【００５７】
各秘密計算サーバMiは、求めた[sa]i,[sb]i,[sa^2]i,[sab]iと[m]iを分析端末TAに送信する。
【００５８】
<計算フェーズ>
計算フェーズとして、ステップＳ１０及びＳ１１において、以下の処理が行われる。
【００５９】
分析端末TAは、受け取ったシェアを用いて、sa, sb, sa^2, sab, mを復号する。
【００６０】
分析端末TAは、sa, sb, mを用いて、μa=(1/m)sa, μb=(1/m)sbを計算する。
【００６１】
分析端末TAは、sa, sb, sa^2, sab, mを用いて、σa2=(1/m)sa^2-(1/m2)sa2, σa,b=(1/m)sab-(1/m2)sasbを計算する。
【００６２】
分析端末TAは、w1=(σa,b)/(σa2)を計算する。
【００６３】
分析端末TAは、w0=μb-w1μaを計算する。
【００６４】
[[実施例２]]
実施例２は、線形回帰分析を行う実施例である。より具体的には、実施例２は、計算装置４である分析端末TAが、秘密計算装置３であるn台の秘密計算サーバM1,…,Mnを用いて、暗号文生成装置１である登録端末THが持つレコード数m、属性数Lの行列Aとレコード数mのベクトルb間の以下の線形モデル
b=w0+w1a1+…+wLaL
について、パラメータw=(w0,w1,…,wL)の推定を行う実施例である。
【００６５】
<暗号化フェーズ>
暗号化フェーズとして、ステップＳ１からＳ３において、以下の処理が行われる。
【００６６】
登録端末THは、例えば参考文献１，２の暗号方式を用いて、A,b,m,Lを暗号化する。
【００６７】
登録端末THは、暗号文であるシェア[A]i, [b]i, [m]i, [L]iと平文m,Lを秘密計算サーバM1,…,Mnに対して送信する。
【００６８】
<秘密計算フェーズ>
秘密計算フェーズとして、ステップＳ７からＳ９において、以下の処理が行われる。
【００６９】
各秘密計算サーバMiは、［暗号方式］の欄で示した総和の秘密計算により、[A]i, [b]iを用いて、[sA]i=([sa1]i,…, [saL]i), [sb]iを求める。ここで、q=1,…,Lとしてsaq=Σj=1maj,qであり、b=(b1,…,bm)としてsb=Σj=1mbjである。
【００７０】
各秘密計算サーバMiは、［暗号方式］の欄で示した積和により、[A]i, [b]iを用いて、[SA]i=([sajak]i)1≦j,k≦L=と[sAb]i= ([sa1b]i,…, [saLb]i)を計算する。ここで、sajak=Σr=1mar,jar,kであり、q=1,…,Lとしてsaqb=Σr=1mar,qbrである。
【００７１】
各秘密計算サーバMiは、求めた[sA]i, [sb]i, [SA]i, [sAb]iと[m]i, [L]iを分析端末TAに送信する。
【００７２】
<計算フェーズ>
計算フェーズとして、ステップＳ１０及びＳ１１において、以下の処理が行われる。
【００７３】
分析端末TAは、受け取ったシェアを用いて、sA, sb, SA, sAb, m, Lを復号する。
【００７４】
分析端末TAは、sA, sb, SA, sAb, m, Lを用いて、式（１）の線形方程式を構成する。
【００７５】
分析端末TAは、例えばGauss の消去法を用いて式（１）を解き、w=(w0,…,wL)を求める。
【００７６】
[[実施例３]]
実施例３は、主成分分析を行う実施例である。より具体的には、実施例３は、計算装置４である分析端末TAが、秘密計算装置３であるn台の秘密計算サーバM1,…,Mnを用いて、暗号文生成装置１である登録端末THが持つレコード数m、属性数Lの行列であるデータAに対して主成分分析を行い、各主成分p=(p1,…,pL)を求める実施例である。
【００７７】
<暗号化フェーズ>
暗号化フェーズとして、ステップＳ１からＳ３において、以下の処理が行われる。
【００７８】
登録端末THは、例えば参考文献１，２の暗号方式を用いて、A,m,Lを暗号化する。
【００７９】
登録端末THは、暗号文であるシェア[A]i, [m]i, [L]iと平文m,Lを秘密計算サーバM1,…,Mnに対して送信する。
【００８０】
<秘密計算フェーズ>
秘密計算フェーズとして、ステップＳ７からＳ９において、以下の処理が行われる。
【００８１】
各秘密計算サーバMiは、［暗号方式］の欄で示した総和により、[A]iを用いて、[s]i=([sa1]i,…,[saL]i)を求める。ここで、q=1,…,Lとしてsai=Σj=1maq,jである。
【００８２】
各秘密計算サーバMiは、［暗号方式］の欄で示した積和により、[A]iを用いて、[S]i=([sajak]i)1≦j,k≦Lを計算する。ここで、sajak=Σr=1mar,jar,kである。
【００８３】
各秘密計算サーバMiは、求めた[s]i, [S]iと[m]i, [L]iを分析端末TAに送信する。
【００８４】
<計算フェーズ>
計算フェーズとして、ステップＳ１０及びＳ１１において、以下の処理が行われる。
【００８５】
分析端末TAは、受け取ったシェアを用いて、s, S, m, Lを復号する。
【００８６】
分析端末TAは、s, S, m, Lを用いて、V=(σaj,ak)1≦j,k≦L=((1/m)sajak-(1/m2)sajsak)1≦j,k≦Lを求める。
【００８７】
分析端末TAは、Vを用いて、C=((σaj,ak)/(σaj2σak2)1/2)1≦j,k≦Lを求める。ここで、σaj2=(1/m)saj^2-(1/m2)saj2であり、σak2=(1/m)sak^2-(1/m2)sak2である。
【００８８】
分析端末TAは、Cに対して固有値及び固有ベクトルの計算を行い、p=(p1,…,pL)を求める。
【００８９】
［プログラム及び記録媒体］
例えば、各装置における処理をコンピュータによって実現する場合、各装置の各部が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、その各装置の処理がコンピュータ上で実現される。
【００９０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００９１】
また、各部の処理は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理の少なくとも一部をハードウェア的に実現することとしてもよい。
【００９２】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【図１】
0006988918.tif 000006
【図２】
0006988918.tif 000007
【図３】
0006988918.tif 000008