(57)【特許請求の範囲】
【請求項１】
データXを秘密分散することにより複数のシェアを生成し、生成された複数のシェアを第０サーバ装置から第ｎ−１サーバ装置に送信するユーザ装置と、
上記第０サーバ装置から第ｎ−１サーバ装置がわからない秘密分散されたシャッフルビットに従って所定の決定木を秘密協調計算により撹乱することにより撹乱後の決定木を得て、受信した複数のシェアと上記撹乱後の決定木と上記秘密分散されたシャッフルビットを用いて、上記所定の決定木におけるデータXに対応する値のn個のシェアを秘密協調計算することにより得て上記ユーザ装置に送信する上記第０サーバ装置から第ｎ−１サーバ装置と、を含み、
上記ユーザ装置は、kをn以下の所定の整数として、受信したn個のシェアの中の少なくともk個を用いて上記所定の決定木におけるデータXに対応する値を復元する、
秘匿決定木計算システム。
【請求項２】
請求項１の秘匿決定木計算システムにおいて、
上記データXはX=(X0,…,Xh-1)であり、上記所定の決定木は完全二分木かつ順序固定な決定木であり、
上記第０サーバ装置から第ｎ−１サーバ装置は、上記所定の決定木の各ノードに対してその各ノードの左側の子ノードを根とした木と右側の子ノードを根とした木をそのノードに対応する上記シャッフルビットが所定の値である場合に入れ替える処理を秘密協調計算により行うことにより上記撹乱後の決定木を得て、上記撹乱後の決定木の最上位の階層から葉ノードの階層までの撹乱後の決定木の各階層i(i=0,…,h-2)のノードにおいて、(1) そのノードに対応する上記シャッフルビットが所定の値でなくかつXiがそのノードの条件を満たす場合にはそのノードの一方の子ノードに遷移し、(2) そのノードに対応する上記シャッフルビットが所定の値でなくかつXiがそのノードの条件を満たさない場合にはそのノードの他方の子ノードに遷移し、(3) そのノードに対応する上記シャッフルビットが所定の値でありかつXiがそのノードの条件を満たす場合にはそのノードの上記他方の子ノードに遷移し、(4) そのノードに対応する上記シャッフルビットが所定の値でありかつXiがそのノードの条件を満たさない場合にはそのノードの上記一方の子ノードに遷移する処理を秘密協調計算により行うことにより最終的に遷移する葉ノードを求め、その求まった葉ノードに対応する値を上記所定の決定木におけるデータXに対応する値とする、
秘匿決定木計算システム。
【請求項３】
請求項１の秘匿決定木計算システムの上記第０サーバ装置から第ｎ−１サーバ装置である秘匿決定木計算装置。
【請求項４】
ユーザ装置が、データXを秘密分散することにより複数のシェアを生成し、生成された複数のシェアを第０サーバ装置から第ｎ−１サーバ装置に送信するステップと、
上記第０サーバ装置から第ｎ−１サーバ装置が、上記第０サーバ装置から第ｎ−１サーバ装置がわからない秘密分散されたシャッフルビットに従って所定の決定木を秘密協調計算により撹乱することにより撹乱後の決定木を得て、受信した複数のシェアと上記撹乱後の決定木と上記秘密分散されたシャッフルビットを用いて、上記所定の決定木におけるデータXに対応する値のn個のシェアを秘密協調計算することにより得て上記ユーザ装置に送信するステップと、
上記ユーザ装置が、kをn以下の所定の整数として、受信したn個のシェアの中の少なくともk個を用いて上記所定の決定木におけるデータXに対応する値を復元するステップと、
を含む秘匿決定木計算方法。
【請求項５】
請求項３の秘匿決定木計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データを秘匿したまま、秘匿されたデータに基づいた分析結果を返答する技術に関する。
【背景技術】
【０００２】
近年、多数の購買履歴から知見を得て、ある個人が商品Aを買ったならば商品Bを推薦するといったデータマイニングや推定が行われている。そのような推定の一手法として、決定木を用いた方法がある。二分木を例とすると、決定木とは多数のノードとその辺で決定される木であり、根ノードと呼ばれる階層0のノード、葉ノードと呼ばれる、それよりも下にノードが無いようなノード、およびこれら以外のノードである中間ノードがある。葉ノード以外には次の階層で左右どちらに遷移するかを定める条件式が定められており、葉ノードには推薦値が定められているものとする。
【０００３】
決定木を用いてあるデータに対する推薦値を得るには、木の根ノードから順に、データが条件式を満足するか確認し、満足すれば右に、さもなければ左に遷移し、最終的にたどり着いた葉に対応する推薦値を得る。
【０００４】
企業が何かしらの分析のために決定木を作成した場合、その決定木は企業の知見であるため、一般に公開することは難しい。
【０００５】
ところで、近年パーソナルデータや医療データ等、個人に関するデータを利活用する動きが広まっている。これらのデータは機微性が高く、データを秘匿したまま処理を行うことが望ましい。
【０００６】
ユーザ装置Uとサーバ装置Sの2 者がおり、ユーザ装置Uは自身のデータを持っており、サーバ装置Sは今までの自社サービスで得た知見等から生成した決定木を持っている。
【０００７】
このようなとき、ユーザ装置Uのデータを入力として、サーバ装置Sの持つ決定木を用いて、推定結果を得ることを考える。
【０００８】
これまで、決定木の計算には、決定木と入力の両方が必要なため、ユーザ装置Sが自身のデータをサーバに渡すこと又はサーバの決定木をユーザに渡すことのどちらかが必要であった。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、前者ではユーザのデータがサーバに知られてしまうし、後者ではサーバの持つ決定木がユーザに渡りサーバ側の知見が漏えいしてしまう可能性があった。
【００１０】
この発明の目的は、ユーザ装置のデータ及びサーバ装置の決定木を互いに秘匿したまま計算値をユーザに返答する秘匿決定木計算システム、装置、方法及びプログラムを提供することである。
【課題を解決するための手段】
【００１１】
この発明の一態様による秘匿決定木計算システムは、データXを秘密分散することにより複数のシェアを生成し、生成された複数のシェアを第０サーバ装置から第ｎ−１サーバ装置に送信するユーザ装置と、第０サーバ装置から第ｎ−１サーバ装置がわからない秘密分散されたシャッフルビットに従って所定の決定木を秘密協調計算により撹乱することにより撹乱後の決定木を得て、受信した複数のシェアと撹乱後の決定木と秘密分散されたシャッフルビットを用いて、所定の決定木におけるデータXに対応する値のn個のシェアを秘密協調計算することにより得てユーザ装置に送信する第０サーバ装置から第ｎ−１サーバ装置と、を含み、ユーザ装置は、kをn以下の所定の整数として、受信したn個のシェアの中の少なくともk個を用いて所定の決定木におけるデータXに対応する値を復元する。
【００１２】
この発明の一態様による秘匿決定木計算装置は、秘匿決定木計算システムの第０サーバ装置から第ｎ−１サーバ装置である。
【発明の効果】
【００１３】
ユーザ装置のデータ及びサーバ装置の決定木を互いに秘匿したまま計算値をユーザに返答することができる。
【図面の簡単な説明】
【００１４】
【図１】秘匿決定木計算装置の例を説明するためのブロック図。
【図２】秘匿決定木計算方法の例を説明するための流れ図。
【図３】１ビット比較プロトコルCompBit(x,y)の例を示す図。
【図４】等号判定プロトコルCompInt(X,Y,c)の例を示す図。
【図５】PlefixOR計算プロトコルPlefixOR(X)の例を示す図。
【図６】Off-line計算プロトコルの例を示す図。
【図７】On-line計算プロトコルの例を示す図。
【発明を実施するための形態】
【００１５】
まず、この発明の基礎となる事柄について説明する。
【００１６】
［記法］
x←Bは、Bが集合ならばBから一様ランダムに要素を選びxに代入することを指し、BがアルゴリズムならばBの出力をxに代入することを指し、Bが確率密度関数ならばその確率密度関数に従ったインスタンスxをサンプリングすることを指す。  また、ある数Xiについてその二進数表現をxi,0…xi,M-1とする。すなわち、Xi=Σj<M2jxi,jである。述語とは出力が{0,1}であるような関数で、[[x>?y]]とはx>yが成り立つならば1を、そうでなければ0を返すような述語である。
【００１７】
［決定木］
決定木とは、入力データを条件分岐していくことにより、最終的にその入力データに対応する値（例えば、推測値）を決定するようなアルゴリズムに用いられる木である。
【００１８】
決定木を(h,M,m,R,L,{Gi}i<m-M,{Gi}m-M≦i<m)の組と定義する。hは（最も深い）高さ、Mは葉ノードの数、mは全ノード数である。各ノードは0からm-1まで番号が割り振られ、葉ノードにはm-Mからm-1までの番号が割り振られているとする。R,L:Zm→Zmは入力ノードの右、左ノードを出力する関数である。すなわち、R(i)はノードiの右側の子ノードであり、L(i)はノードiの左側の子ノードである。Gi(i=0,…,m-M-1)はノードiに対応する述語である。各ノードの述語は比較と統合判定のみとする。例えばGiは<?bのような形式であり、条件式<?と条件値bを持つ。単に条件値Giと言った場合には、述語Giの条件値bのことを意味する。また、葉ノードiに対応するGi(i=m-M,…,m-1)は、その葉ノードiに対応する値（例えば、推薦値）である。
【００１９】
ここでは、決定木として、完全二分木かつ順序固定な決定木を想定する。
【００２０】
完全二分木とは、全ての葉ノードの高さが同一であるような二分木である。このように、完全二分な決定木全ての葉ノードの高さが同一であるような二分木を想定する。このとき、n=Σk=0h-12k, m=2h-1が成り立つ。
【００２１】
順序固定な決定木とは、深さによって参照するデータが一定であるような決定木である。すなわち、どのノードに遷移しても、深さ1ではX1、深さ2ではX2を参照するようなものである。
【００２２】
［秘密分散］
秘密分散とはある決められた数(k,n)があり、以下の2つのアルゴリズムShare,Recの組である。
【００２３】
Share:秘密aを入力とし、シェア[a]0,…,[a]n-1を出力する。
【００２４】
Rec:シェア[a]i_0,…,[a]i_K-1を入力とし、秘密sを出力する。ここで、K≧kであり、jを整数として、i_jはijを意味するとする。
【００２５】
また、準同型性としてb(-)[a]i=[b-a]iとなる演算(-)、[a]i(+)[b]i=[a+b]iとなる演算(+)が存在するものとする。これらの演算(-)(+)は既知の手法により実現することができる。
【００２６】
ここでは、例えば秘密の空間はZ2とする。
【００２７】
［乗算プロトコル］
乗算プロトコルMultとは、各サーバ装置Siの秘密分散された値[x]i,[y]iを入力として、各サーバ装置Siに乗算結果のシェア[xy]iを生成するプロトコルである。乗算プロトコルMultとして、例えば参考文献１に記載されたプロトコルを用いることができる。
【００２８】
〔参考文献１〕Ivan Damgard and Jesper Buus Nielsen, "Scalable and unconditionally secure multiparty computation", In CRYPTO, pp.572-590, 2007.
［比較，等号判定プロトコル］
ビット演算の組み合わせで比較，等号判定を行うプロトコルを実現することができる。
【００２９】
図５にMビット比較，等号判定プロトコルCompInt(X,Y,c)の具体例を示す。この等号判定プロトコルCompInt(X,Y,c)は、選択ビットcが、0ならば[[X<?Y]]を、1ならば[[X=?Y]]を出力する。
【００３０】
また、等号判定プロトコルCompInt(X,Y,c)で用いられる１ビット比較プロトコルCompBit(x,y)の具体例を図３に示す。
【００３１】
さらに、等号判定プロトコルCompInt(X,Y,c)で用いられるPlefixOR計算プロトコルPlefixOR(X)の具体例を図４に示す。PlefixOR計算プロトコルPlefixOR(X)は、入力されたXをビット表現した際に最上位で１となったビット以降全て１としたビット列を新たなXとして出力するものである。
【００３２】
［実施形態］
以下、図面を参照して秘匿決定木計算システム、装置及び方法の一実施形態について説明する。
【００３３】
秘匿決定木計算システムは、図１に示すように、ユーザ装置Uと秘匿決定木計算装置であるサーバ装置群を例えば備えている。このサーバ装置群は、第０サーバ装置S0から第ｎ−１サーバ装置Sn-1から例えば構成されている。i=0,…,n-1として、上記説明したこの発明の基礎となる事柄における「サーバ装置Si」は、「第ｉサーバ装置Si」に対応している。以下の説明においても、「第ｉサーバ装置Si」のことを「サーバ装置Si」と略記することがある。
【００３４】
この実施形態では、ユーザ装置Uのデータを秘匿したまま決定木が計算され、その推薦結果がユーザ装置Uに返答される。
【００３５】
秘匿決定木計算システムの各装置が、図２の各ステップの処理を行うことにより、秘匿決定木計算方法が実現される。この実施形態における大まかな流れは以下の通りである。まず、「Off-lineフェーズ」の処理が行われ、その後「On-line」の処理が行われる。「Off-lineフェーズ」の処理が事前に行われている場合には、「On-line」の処理に先だって「Off-lineフェーズ」の処理は行われなくてもよい。
【００３６】
「Off-line フェーズ」
ステップＡ１：サーバ装置Siは条件値Gi(i=0,…,m-M-1)及び値Gi(i=m-M,…,m-1)、比較か等号かを決定する選択ビットci∈{0,1}を秘密分散する。
【００３７】
ステップＡ２：サーバ装置Siは自身がわからないように葉以外のノードiに対してシャッフルビットri←{0,1}の乱数を生成する。
【００３８】
ステップＡ３：サーバ装置Siはシャッフルビットriに従って決定木をシャッフルする。
【００３９】
「On-line フェーズ」
ステップＢ１：ユーザ装置Uが自身のデータをSiに秘密分散する。このとき、データは1ビットずつに分けてから秘密分散を行うか、又は、ビットに分けずに分散した後サーバ側でビットに分解する。
【００４０】
ステップＢ２：サーバ装置Siは秘密分散された値とOff-lineフェーズで生成した自身の根ノードの条件値の分散値，およびシャッフルビットの分散値を用いて条件を計算し、復元する。例えば、復元した値が0の場合は左に、1の場合は右に遷移する。以降、同様に計算し、葉ノードに到達するまで計算する。
【００４１】
ステップＢ３：サーバ装置Siはユーザ装置Uに到達した葉ノードに対応する値（例えば、推薦値）のシェアをユーザ装置Uに送る。
【００４２】
ステップＢ４：ユーザ装置Uは、シェアを復元しデータに対応する値を得る。
【００４３】
ユーザのデータはX=(X0,…,Xh-1)とし、決定木は完全二分かつ順序固定であり、深さiにおいてはciを参照して比較又は等号判定を行うものとする。
【００４４】
決定木の途中のあるノードiを根とした木を考えている場合、その木のノードjに対応するノードj-（jの上付き-）とは、iの1つ上の階層で、iとは違う方向に遷移したノードmを根とする木を考えたとき、mからjへの遷移がiからjへの遷移と同一のものである。
【００４５】
以下、「Off-line フェーズ」の各ステップの処理について説明する。また、各ステップの処理を実現するためのOff-line計算プロトコルの例を図６に示す。
【００４６】
＜ステップＡ１＞
第０サーバ装置Siから第ｎ−１サーバ装置Sn-1は、各ノードjについての、条件値Gj(j=0,…,m-M-1)及び値Gj(j=m-M,…,m-1)、比較か等号かを決定する選択ビットcj∈{0,1}を秘密分散し、[Gj],[cj]を得る（ステップＡ１）。
【００４７】
この処理は、図６のOff-line計算プロトコルの「１：」に対応している。
【００４８】
＜ステップＡ２＞
第０サーバ装置Siから第ｎ−１サーバ装置Sn-1は、第０サーバ装置Siから第ｎ−１サーバ装置Sn-1がわからないように共同して葉以外のノードjに対してシャッフルビットrj←{0,1}のシェア[rj]を生成する（ステップＡ２）。
【００４９】
この処理は、図６のOff-line計算プロトコルの「２：」に対応している。
【００５０】
＜ステップＡ３＞
第０サーバ装置Siから第ｎ−１サーバ装置Sn-1は、第０サーバ装置Siから第ｎ−１サーバ装置Sn-1がわからないように秘密分散されたシャッフルビットriに従って所定の決定木を秘密協調計算により撹乱することにより撹乱後の決定木を得る（ステップＡ３）。
【００５１】
この処理は、図６のOff-line計算プロトコルの「３：」から「９：」に対応している。図６のOff-line計算プロトコルの「３：」から「９：」では、ノートiのシャッフルビットri=1の場合にはL(i)を根と見た木とR(i)を根と見た木とを入れ替え、ノートiのシャッフルビットri=0の場合にはその入れ替えないという処理を葉ノードを除く全てのノードに対して行うことにより、決定木を撹乱している。
【００５２】
このように、第０サーバ装置Siから第ｎ−１サーバ装置Sn-1は、所定の決定木の各ノードに対してその各ノードの左側の子ノードを根とした木と右側の子ノードを根とした木をそのノードに対応する上記シャッフルビットが所定の値である場合に入れ替える処理を秘密協調計算により行うことにより撹乱後の決定木を得てもよい。所定の値の例は１である。もちろん所定の値は１以外の値であってもよい。
【００５３】
以下、「On-line フェーズ」の各ステップの処理について説明する。また、各ステップの処理を実現するためのOn-line計算プロトコルの例を図７に示す。
【００５４】
＜ステップＢ１＞
ユーザ装置Uは、所定のアルゴリズムShareに基づいて、データXを秘密分散することにより複数のシェアを生成し、生成された複数のシェアを第０サーバ装置Siから第ｎ−１サーバ装置Sn-1に送信する（ステップＢ１）。
【００５５】
このステップＢ１の処理は、図７のOn-line計算プロトコルの「１：」に対応している。
【００５６】
＜ステップＢ２＞
第０サーバ装置Siから第ｎ−１サーバ装置Sn-1は、受信した複数のシェアと上記撹乱後の決定木と上記秘密分散されたシャッフルビットを用いて、上記所定の決定木におけるデータXに対応する値のn個のシェアを秘密協調計算することにより得る（ステップＢ２）。
【００５７】
このステップＢ２の処理は、図７のOn-line計算プロトコルの「２：」から「１１：」に対応している。
【００５８】
図７のOn-line計算プロトコルの「２：」から「１１：」では、撹乱後の決定木の最上位の階層から葉ノードの階層までの撹乱後の決定木の各階層i(i=0,…,h-2)のノードにおいて、(1) そのノードに対応する上記シャッフルビットが０でありかつXiがそのノードの条件を満たす場合にはそのノードの右の子ノードに遷移し、(2) そのノードに対応するシャッフルビットが０でありかつXiがそのノードの条件を満たさない場合にはそのノードの左の子ノードに遷移し、(3) そのノードに対応する上記シャッフルビットが１でありかつXiがそのノードの条件を満たす場合にはそのノードの左の子ノードに遷移し、(4) そのノードに対応するシャッフルビットが１でありかつXiがそのノードの条件を満たさない場合にはそのノードの右の子ノードに遷移する処理を秘密協調計算により行うことにより最終的に遷移する葉ノードを求め、その求まった葉ノードに対応する値を所定の決定木におけるデータXに対応する値としている。
【００５９】
このように、第０サーバ装置Siから第ｎ−１サーバ装置Sn-1は、撹乱後の決定木の最上位の階層から葉ノードの階層までの撹乱後の決定木の各階層i(i=0,…,h-2)のノードにおいて、(1) そのノードに対応する上記シャッフルビットが所定の値でなくかつXiがそのノードの条件を満たす場合にはそのノードの一方の子ノードに遷移し、(2) そのノードに対応するシャッフルビットが所定の値でなくかつXiがそのノードの条件を満たさない場合にはそのノードの他方の子ノードに遷移し、(3) そのノードに対応する上記シャッフルビットが所定の値でありかつXiがそのノードの条件を満たす場合にはそのノードの上記他方の子ノードに遷移し、(4) そのノードに対応するシャッフルビットが所定の値でありかつXiがそのノードの条件を満たさない場合にはそのノードの上記一方の子ノードに遷移する処理を秘密協調計算により行うことにより最終的に遷移する葉ノードを求め、その求まった葉ノードに対応する値を所定の決定木におけるデータXに対応する値とする。所定の値の例は１であり、一方の子ノードの例は右の子ノードであり、他方の子ノードの例は左の子ノードである。
【００６０】
所定の値は１以外の値であってもよい。また、述語を満たす場合に左の子ノードに遷移すると決まっている場合には、一方の子ノードは左の子ノードであり、他方の子ノードは右の子ノードであってもよい。
【００６１】
このように、シャッフルビットが所定の値の場合に本来遷移すべき子ノードでない方の子ノードに遷移することにより、撹乱後の決定木においても撹乱前の決定木において本来遷移すべきであった葉ノードに最終的に遷移することができ、撹乱前の決定木におけるデータに対応する葉ノードの値（例えば、推薦値）を取得することができる。
【００６２】
＜ステップＢ３＞
第０サーバ装置Siから第ｎ−１サーバ装置Sn-1は、秘密協調計算することにより得られたn個のシェアをユーザ装置Uに送信する（ステップＢ３）。
【００６３】
このステップＢ３の処理は、図７のOn-line計算プロトコルの「１２：」に対応している。
【００６４】
＜ステップＢ４＞
ユーザ装置Uは、所定のアルゴリズムRecに基づいて、受信したn個のシェアの中の少なくともk個を用いて所定の決定木におけるデータXに対応する値を復元する（ステップＢ４）。
【００６５】
このステップＢ４の処理は、図７のOn-line計算プロトコルの「１４：」に対応している。
【００６６】
このような処理を行うことにより、ユーザ装置のデータとサーバ装置の決定木を秘匿しつつ値（例えば、推薦値）を返すことができる。
【００６７】
この実施形態では、Off-line計算が必要ではあるものの、ユーザ装置からデータが来た際の計算は決定木の高さの線形オーダで可能である。すなわち、Off-lineフェーズにおいて予め乱数に基づいてシャッフルしておくことにより、On-lineフェーズでは1 つのパスのみを辿れば良く、決定木の高さの指数オーダの計算量が必要なくなる。
【００６８】
[プログラム及び記録媒体]
秘匿決定木計算装置及び方法において説明した処理は、記載の順にしたがって時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００６９】
また、秘匿決定木計算装置における各処理をコンピュータによって実現する場合、秘匿決定木計算装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、その各処理がコンピュータ上で実現される。
【００７０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７１】
また、各処理手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００７２】
［変形例］
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【図１】
0006474741.tif 000002
【図２】
0006474741.tif 000003
【図３】
0006474741.tif 000004
【図４】
0006474741.tif 000005
【図５】
0006474741.tif 000006
【図６】
0006474741.tif 000007
【図７】
0006474741.tif 000008