(57)【要約】  秘匿決定木計算システムは、nを所定の正の整数として、データDをn個のシェア[D]j(j=0,…,n-1)に秘密分散し、n個のシェア[D]j(j=0,…,n-1)をそれぞれ第０サーバ装置から第ｎ−１サーバ装置に送信するユーザ装置と、n個のシェア[D]j(j=0,…,n-1)を用いて所定の決定木におけるデータDに対応する値outのn個のシェア[out]0,…,[out]n-1を秘密協調計算することにより得てユーザ装置に送信する第０サーバ装置から第ｎ−１サーバ装置と、を含み、kをn以下の所定の整数として、ユーザ装置は、受信したn個のシェア[out]0,…,[out]n-1の中の少なくともk個を用いて所定の決定木におけるデータDに対応する値outを復元する。
2017126434.tif 000002
【特許請求の範囲】
【請求項１】
nを所定の正の整数として、データDをn個のシェア[D]j(j=0,…,n-1)に秘密分散し、上記n個のシェア[D]j(j=0,…,n-1)をそれぞれ第０サーバ装置から第ｎ−１サーバ装置に送信するユーザ装置と、
上記n個のシェア[D]j(j=0,…,n-1)を用いて所定の決定木におけるデータDに対応する値outのn個のシェア[out]0,…,[out]n-1を秘密協調計算することにより得て上記ユーザ装置に送信する上記第０サーバ装置から第ｎ−１サーバ装置と、を含み、
kをn以下の所定の整数として、上記ユーザ装置は、受信したn個のシェア[out]0,…,[out]n-1の中の少なくともk個を用いて上記所定の決定木におけるデータDに対応する値outを復元する、
秘匿決定木計算システム。
【請求項２】
請求項１の秘匿決定木計算システムにおいて、
上記第０サーバ装置から第ｎ−１サーバ装置は、上記所定の決定木の各葉ノードiに対して、上記データDが上記所定の決定木の根ノードからその各葉ノードiに至るまでの各ノードの条件を満たす場合には１となり、上記データDが上記所定の決定木の根ノードからその各葉ノードiに至るまでの各ノードの少なくとも１個の条件を満たさない場合には０となるその各葉ノードiに対応するflagiを上記n個のシェア[D]j(j=0,…,n-1)を用いて秘密協調計算し、上記所定の決定木の各葉ノードiに対応する値とflagiとの積和を秘密協調計算し、その計算結果を上記所定の決定木におけるデータDに対応する値outのn個のシェア[out]0,…,[out]n-1とする、
秘匿決定木計算システム。
【請求項３】
請求項１の秘匿決定木計算システムの上記第０サーバ装置から第ｎ−１サーバ装置である秘匿決定木計算装置。
【請求項４】
ユーザ装置が、nを所定の正の整数として、データDをn個のシェア[D]j(j=0,…,n-1)に秘密分散し、上記n個のシェア[D]j(j=0,…,n-1)をそれぞれ第０サーバ装置から第ｎ−１サーバ装置に送信するステップと、
上記第０サーバ装置から第ｎ−１サーバ装置が、上記n個のシェア[D]j(j=0,…,n-1)を用いて所定の決定木におけるデータDに対応する値outのn個のシェア[out]0,…,[out]n-1を秘密協調計算することにより得て上記ユーザ装置に送信するステップと、
ユーザ装置が、kをn以下の所定の整数として、受信したn個のシェア[out]0,…,[out]n-1の中の少なくともk個を用いて上記所定の決定木におけるデータDに対応する値outを復元するステップと、
を含む秘匿決定木計算方法。
【請求項５】
請求項３の秘匿決定木計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データを秘匿したまま、秘匿されたデータに基づいた計算結果を返答する技術に関する。
【背景技術】
【０００２】
近年、多数の購買履歴から知見を得て、ある個人が商品Aを買ったならば商品Bを推薦するといったデータマイニングや推定が行われている。そのような推定の一手法として、決定木を用いた方法がある。決定木として二分木を例に挙げて説明すると、決定木とは多数のノードと辺で決定される木であり、ノードには、根ノードと呼ばれる階層0のノード、葉ノードと呼ばれる、それよりも下にノードが無いようなノード、およびこれら以外のノードである中間ノードがある。葉ノード以外のノードには次の階層で左右どちらに遷移するかを定める条件式が定められており、葉ノードには推薦値が定められているものとする。【０００３】
決定木を用いてあるデータに対する推薦値を得るには、木の根ノードから順に、データが条件式を満足するか確認し、満足すれば右に、さもなければ左に遷移する処理を繰り返す。最終的にたどり着いた葉に対応する推薦値が、そのあるデータに対する推薦値となる。【０００４】
企業が何かしらの分析のために決定木を作成した場合、その決定木は企業の知見であるため、一般に公開することは難しい。【０００５】
ところで、近年パーソナルデータや医療データ等、個人に関するデータを利活用する動きが広まっている。これらのデータは機微性が高く、データを秘匿したまま処理を行うことが望ましい。【０００６】
ユーザ装置Uとサーバ装置Sの2 者がおり、ユーザ装置Uは自身のデータを持っており、サーバ装置Sは今までの自社サービスで得た知見等から生成した決定木を持っているとする。【０００７】
このようなとき、ユーザ装置Uのデータを入力として、サーバ装置Sの持つ決定木を用いて、推定結果を得ることを考える。【０００８】
これまで、決定木の計算には、決定木とデータの入力の両方が必要なため、ユーザ装置Sが自身のデータをサーバ装置Sに渡すこと又はサーバ装置Sの決定木をユーザ装置Uに渡すことのどちらかが必要であった。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、前者ではユーザ装置Uのデータがサーバ装置Sに知られてしまうし、後者ではサーバ装置Sの持つ決定木がユーザ装置Uに渡りサーバ装置S側の知見が漏えいしてしまう可能性があった。【００１０】
この発明の目的は、ユーザ装置のデータ及びサーバ装置の決定木を互いに秘匿したまま計算値をユーザに返答する秘匿決定木計算システム、装置、方法及びプログラムを提供することである。
【課題を解決するための手段】
【００１１】
この発明の一態様による秘匿決定木計算システムは、nを所定の正の整数として、データDをn個のシェア[D]j(j=0,…,n-1)に秘密分散し、n個のシェア[D]j(j=0,…,n-1)をそれぞれ第０サーバ装置から第ｎ−１サーバ装置に送信するユーザ装置と、n個のシェア[D]j(j=0,…,n-1)を用いて所定の決定木におけるデータDに対応する値outのn個のシェア[out]0,…,[out]n-1を秘密協調計算することにより得てユーザ装置に送信する第０サーバ装置から第ｎ−１サーバ装置と、を含み、kをn以下の所定の整数として、ユーザ装置は、受信したn個のシェア[out]0,…,[out]n-1の中の少なくともk個を用いて所定の決定木におけるデータDに対応する値outを復元する。【００１２】
この発明の一態様による秘匿決定木計算装置は、秘匿決定木計算システムの第０サーバ装置から第ｎ−１サーバ装置である。
【発明の効果】
【００１３】
ユーザ装置のデータ及びサーバ装置の決定木を互いに秘匿したまま計算値をユーザ装置に返答することができる。
【図面の簡単な説明】
【００１４】
【図１】秘匿決定木計算装置の例を説明するためのブロック図。
【図２】秘匿決定木計算方法の例を説明するための流れ図。
【図３】基本的な決定木計算プロトコルの例を示す図。
【発明を実施するための形態】
【００１５】
まず、この発明の基礎となる事柄について説明する。
【００１６】
［記法］
x←Bは、Bが集合ならばBから一様ランダムに要素を選びxに代入することを指し、BがアルゴリズムならばBの出力をxに代入することを指し、Bが確率密度関数ならばその確率密度関数に従ったインスタンスxをサンプリングすることを指す。
【００１７】
述語とは出力が{0,1}であるような関数であり、述語a>?bとはa>bが成り立つならば1を、そうでなければ0を返すような述語である。
【００１８】
［決定木］
決定木を(h,M,m,R,L,{Gi}i<m-M,{outi}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に対応する述語である。各ノードの述語は比較と統合判定のみとする。例えばGiは<?bのような形式であり、条件式<?と条件値bを持つ。記法の簡単にするため、Gの条件式が<?,>?,≦?,≧?のときG∈Comparison、Gの条件式が=?のときG∈Equalityと書く。outiは葉ノードiに対応する値（例えば、推薦値）である。
【００１９】
また、path(i)は葉ノードiを入力とし、根ノード0から葉ノードiに到達するために通る全ノードの集合を出力するアルゴリズムとし、LR(i,j)は葉ノードiと途中のノードj∈path(i)を入力とし、jの1階層下のノードが、jの右／左の時にright／leftを出力するアルゴリズムとする。
【００２０】
［秘密分散］
秘密分散とは、ある決められた数(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となる演算(+)、b(×)[a]i=[ab]iとなる演算(×)が存在するものとする。これらの演算(-)(+)(×)は既知の手法により実現することができる。
【００２４】
［乗算プロトコル］
乗算プロトコルMultとは、各サーバ装置Siの秘密分散された値[a]i,[b]iを入力として、各サーバ装置Siに乗算結果のシェア[ab]iを生成するプロトコルである。乗算プロトコルMultとして、例えば参考文献１に記載されたプロトコルを用いることができる。
【００２５】
〔参考文献１〕Ivan Damgard and Jesper Buus Nielsen, "Scalable and unconditionally secure multiparty computation", In CRYPTO, pp.572-590, 2007.
【００２６】
［公開値との比較，等号判定プロトコル］
公開値との比較プロトコルCompPubとは、各サーバ装置Siの秘密分散された値[a]iと、述語G∈Comparisonを入力として、各サーバ装置Siに述語結果のシェア[G(a)]iを生成するプロトコルである。比較プロトコルCompPubとして、例えば参考文献２に記載されたプロトコルを用いることができる。
【００２７】
〔参考文献２〕Ivan Damgard, Matthias Fitzi, Eike Kiltz, Jesper Buus Nielsen and Tomas Toft, "Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation", In TCC, pp.285-304, 2006.
【００２８】
また、乗算プロトコルと準同型性を利用してAND、OR、NOT回路等を構成することにより、比較プロトコルCompPubを実現してもよい。
【００２９】
公開値との等号判定プロトコルEqPubとは、各サーバ装置Siの秘密分散された値[a]iと、述語G∈Equalityを入力として、各サーバ装置Siに述語結果のシェア[G(a)]iを生成するプロトコルである。例えば参考文献２に記載されたプロトコルを用いることができる。また、乗算プロトコルと準同型性を利用してAND、OR、NOT回路等を構成することにより、等号判定プロトコルEqPubを実現してもよい。
【００３０】
［実施形態］
以下、図面を参照して秘匿決定木計算システム、装置及び方法の一実施形態について説明する。
【００３１】
秘匿決定木計算システムは、図１に示すように、ユーザ装置Uと秘匿決定木計算装置であるサーバ装置群を例えば備えている。このサーバ装置群は、第０サーバ装置S0から第ｎ−１サーバ装置Sn-1から例えば構成されている。i=0,…,n-1として、上記説明したこの発明の基礎となる事柄における「サーバ装置Si」は、「第ｉサーバ装置Si」に対応している。以下の説明においても、「第ｉサーバ装置Si」のことを「サーバ装置Si」と略記することがある。
【００３２】
この実施形態では、ユーザ装置Uのデータを秘匿したまま決定木が計算され、その計算結果がユーザ装置Uに返答される。
【００３３】
秘匿決定木計算システムの各装置が、図２の各ステップの処理を行うことにより、秘匿決定木計算方法が実現される。この実施形態における大まかな流れは以下の通りである。
【００３４】
ステップＳ１： ユーザ装置Uが自身のデータを各サーバ装置Siに秘密分散する。
【００３５】
ステップＳ２：各サーバ装置Siは秘密分散された値と自身の決定木を用いてデータに対応する値（例えば、推薦値）のシェアを秘密協調計算する。
【００３６】
ステップＳ３：各サーバ装置Siはユーザ装置Uにデータに対応する値（例えば、推薦値）のシェアを送り、ユーザ装置Uはシェアを復元しデータに対応する値を得る。
【００３７】
簡単のためユーザ装置UのデータはDのみとしたが、ユーザ装置Uのデータが複数あるも同様に構成可能である。すなわち、複数のデータをそれぞれ秘密分散し、各ノードで適宜適切なデータを参照してもよい。
【００３８】
以下、各ステップの処理について説明する。また、各ステップの処理を実現するための基本的な決定木計算プロトコルの例を図３に示す。
【００３９】
＜ステップＳ１＞
ユーザ装置は、所定のアルゴリズムShareに基づいて、データDをn個のシェア[D]j(j=0,…,n-1)に秘密分散し、上記n個のシェア[D]j(j=0,…,n-1)をそれぞれ第０サーバ装置から第ｎ−１サーバ装置に送信する（ステップＳ１）。nは所定の正の整数である。
【００４０】
ステップＳ１の処理は、図３の基本的な決定木計算プロトコルの「１：」に対応している。
【００４１】
＜ステップＳ２＞
第０サーバ装置S0から第ｎ−１サーバ装置Sn-1は、受信したn個のシェア[D]j(j=0,…,n-1)を用いて所定の決定木におけるデータDに対応する値outのn個のシェア[out]0,…,[out]n-1を秘密協調計算することにより得てユーザ装置Uに送信する（ステップＳ２）。
【００４２】
ステップＳ２の処理は、図３の基本的な決定木計算プロトコルの「２：」から「１５：」に対応している。
【００４３】
具体的には、第０サーバ装置S0から第ｎ−１サーバ装置Sn-1は、所定の決定木の各葉ノードiに対して、データDが所定の決定木の根ノードからその各葉ノードiに至るまでの各ノードの条件を満たす場合には１となり、データDが所定の決定木の根ノードからその各葉ノードiに至るまでの各ノードの少なくとも１個の条件を満たさない場合には０となるその各葉ノードiに対応するflagiをn個のシェア[D]j(j=0,…,n-1)を用いて秘密協調計算する。この処理は、図３の基本的な決定木計算プロトコルの「２：」から「１４：」に対応している。
【００４４】
そして、第０サーバ装置S0から第ｎ−１サーバ装置Sn-1は、所定の決定木の各葉ノードiに対応する値とflagiとの積和を秘密協調計算し、その計算結果を上記所定の決定木におけるデータDに対応する値outのn個のシェア[out]0,…,[out]n-1とする。この処理は、図３の基本的な決定木計算プロトコルの「１５：」に対応している。
【００４５】
＜ステップＳ３＞
ユーザ装置Uは、所定のアルゴリズムRecに基づいて、受信したn個のシェア[out]0,…,[out]n-1の中の少なくともk個を用いて所定の決定木におけるデータDに対応する値outを復元する（ステップＳ３）。kは、n以下の所定の整数である。
【００４６】
ステップＳ３の処理は、図３の基本的な決定木計算プロトコルの「１６：」に対応している。
【００４７】
上記のステップＳ１からステップＳ３の処理により、例えば、ユーザ装置のデータとサーバ装置の決定木を秘匿しつつリコメンド結果を返すことができ、不必要な個人に関する情報が漏洩するのを防ぐことができる。
【００４８】
通常の決定木の計算の各ステップを秘密計算に置き換えただけでは、「決定木のどのパスを通ったのか」という情報がサーバにわかり、ひいては個人のデータの部分情報がサーバにわかってしまう可能性がある。
【００４９】
これに対して、上記の実施形態では、全ての葉ノードに対して、「ユーザ装置のデータがこの葉ノードに到達するならば1、しなければ0」となるflagを計算し、flagと推薦結果との積和を取ることにより，最終的な値のシェアを生成している。この方法は、個人の情報が決定木のどのパスを通ったとしてもサーバ装置側の処理が変化せず、サーバ装置側にユーザ装置のデータの情報が漏れない。
【００５０】
[プログラム及び記録媒体]
秘匿決定木計算システム、装置及び方法において説明した処理は、記載の順にしたがって時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００５１】
また、秘匿決定木計算装置における各処理をコンピュータによって実現する場合、秘匿決定木計算装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、その各処理がコンピュータ上で実現される。
【００５２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００５３】
また、各処理手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００５４】
［変形例］
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【図１】
2017126434.tif 000003
【図２】
2017126434.tif 000004
【図３】
2017126434.tif 000005
【手続補正書】
【提出日】平成30年6月20日(2018.6.20)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
これまで、決定木の計算には、決定木とデータの入力の両方が必要なため、ユーザ装置Uが自身のデータをサーバ装置Sに渡すこと又はサーバ装置Sの決定木をユーザ装置Uに渡すことのどちらかが必要であった。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
［決定木］
決定木を(h,M,m,R,L,{Gi}i<m-M,{outi}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に対応する述語である。各ノードの述語は比較と等号判定のみとする。例えばGiは<?bのような形式であり、条件式<?と条件値bを持つ。記法の簡単にするため、Gの条件式が<?,>?,≦?,≧?のときG∈Comparison、Gの条件式が=?のときG∈Equalityと書く。outiは葉ノードiに対応する値（例えば、推薦値）である。
【国際調査報告】
2017126434.tif 000006
2017126434.tif 000007
2017126434.tif 000008
2017126434.tif 000009