分散ルーティング処理装置およびコンピュータプログラム
【課題】フルメッシュに通信リンクが存在しない通信ネットワークを対象にした分散ルーティング処理でノードの秘密情報を当該管理者以外の者に秘匿すること。
【解決手段】自ノードの局所トポロジー情報を用いて閾値秘密分散法により複数の分散情報を生成する秘密分散部１３と、自局所ノード群内のノード間で複数の分散情報を分散して保持する分散情報格納部１５と、複数の分散情報を変換分散情報構成要素に変換する分散情報変換部１７と、自局所ノード群に隣接する局所ノード群との間で変換分散情報構成要素を交換して変換分散情報を生成する変換分散情報交換部１８と、自局所ノード群内の各ノードと連携して所定の関数を分散して計算するＳＭＣを解決するＳＭＣ部と、自局所ノード群内の各ノードと連携して次ホップ情報の複数の分散情報から次ホップ情報を復元する秘密分散復元部１４と、を備える。
【解決手段】自ノードの局所トポロジー情報を用いて閾値秘密分散法により複数の分散情報を生成する秘密分散部１３と、自局所ノード群内のノード間で複数の分散情報を分散して保持する分散情報格納部１５と、複数の分散情報を変換分散情報構成要素に変換する分散情報変換部１７と、自局所ノード群に隣接する局所ノード群との間で変換分散情報構成要素を交換して変換分散情報を生成する変換分散情報交換部１８と、自局所ノード群内の各ノードと連携して所定の関数を分散して計算するＳＭＣを解決するＳＭＣ部と、自局所ノード群内の各ノードと連携して次ホップ情報の複数の分散情報から次ホップ情報を復元する秘密分散復元部１４と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散ルーティング処理装置およびコンピュータプログラムに関する。
【背景技術】
【０００２】
従来、複数（Ｎ台）の通信装置（以下、ノードと称する）と、ノード間を結ぶ通信路（以下、通信リンクと称する）とからなる通信ネットワークにおいて、Ｎ台のノード間で通信して分散ルーティング処理を行う技術が知られている。この分散ルーティング処理とは、Ｎ入力・Ｎ出力の関数［（Ｙ＿１，Ｙ＿２，・・・，Ｙ＿Ｎ）＝Ｆ（Ｘ＿１，Ｘ＿２，・・・，Ｘ＿Ｎ）］を計算する処理である。但し、Ｎは通信ネットワークを構成するノードの台数である。Ｘ＿ｉはノードｉから入力される局所トポロジー情報である。Ｙ＿ｉはノードｉへ出力する次ホップ情報である。ｉは１からＮまでの自然数である。局所トポロジー情報Ｘ＿ｉとは、ノードｉと他のノードとの間の接続関係（通信リンクの有無）を示す情報である。次ホップ情報Ｙ＿ｉとは、あるノードにメッセージを届けるために、ノードｉがメッセージをどのノードに転送すればよいのかを示す情報である。
【０００３】
任意の関数ＦをＮ台のノードで分散して計算する問題はＳＭＣ（Secure Multi-party computation）として知られている。このＳＭＣを解決する方法として、例えば非特許文献１，２，３などに、汎用的な計算手順（ＳＭＣプロトコル）が開示されている。従来のＳＭＣ技術では、通信ネットワーク内の全ノード間に通信リンクが存在する、所謂フルメッシュに通信リンクが存在する通信ネットワークを対象にして、通信ネットワークを構成するＮ台のノードのうち単一の管理者に属するノードの台数がある閾値未満であるという条件下で、汎用的なＳＭＣプロトコルを用いて、関数ＦをＮ台のノードで分散して計算している。これにより、ノードｉの管理者以外の者には、ノードｉの秘密情報を開示しないようにすることができる。ノードｉの秘密情報とは、ノードｉに係る入力情報（局所トポロジー情報）Ｘ＿ｉ及び出力情報（次ホップ情報）Ｙ＿ｉ、並びに入力情報Ｘ＿ｉを用いて関数Ｆを計算する途中で発生した情報を指す。
【０００４】
一方、フルメッシュに通信リンクが存在しない通信ネットワークを対象にした従来の分散ルーティング処理技術として、例えば非特許文献４などに記載されるBellman-Fordアルゴリズムが知られている。この従来の分散ルーティング処理技術では、以下の４つの手順（Ｓ１０１からＳ１０４）を用いている。
Ｓ１０１：各ノードｉからの局所トポロジー情報Ｘ＿ｉの入力。
Ｓ１０２：各ノードｉにおいて局所トポロジー情報Ｘ＿ｉを用いた計算。
Ｓ１０３：各ノードｉから、通信リンクが存在する他のノードへ、情報の転送。
Ｓ１０４：各ノードｉへ次ホップ情報の出力。
このBellman-Fordアルゴリズムでは、ノードｉの秘密情報を他のノードに対して秘匿することは考慮されていない。従って、ノードｉの秘密情報がノードｉの管理者以外の者に漏洩する可能性がある。
【０００５】
また、非特許文献５には閾値秘密分散法が開示されている。閾値秘密分散法では、秘密情報から閾値以上の個数の分散情報を生成する。その分散情報は、当該閾値以上の個数の分散情報を使用しないと、元の秘密情報を復元することができないものである。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Goldreich, O. Foundations of Cryptography, volume 2, Basic Applications. Cambridge University Press, 2004.
【非特許文献２】Goldreich, O., Micali, S., and Wigderson, A. How to play any mental game. In Proceedings of the nineteenth annual ACM symposium on Theory of computing (1987), ACM, pp. 218-229.
【非特許文献３】Ben-Or, M., Goldwasser, S., and Wigderson, A. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the twentieth annual ACM symposium on Theory of computing (1988), ACM, pp. 1-10.
【非特許文献４】Lynch, N.A., Distributed algorithms, Morgan Kaufmann, 1996.
【非特許文献５】Shamir, A. How to share a secret. Communications of the ACM 22, 11 (1979), 612-613.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、上述したBellman-Fordアルゴリズムに代表される従来の分散ルーティング処理技術では、フルメッシュに通信リンクが存在しない通信ネットワークを対象にしているが、ノードｉの秘密情報をノードｉの管理者以外の者に秘匿することができない。一方、上述した汎用的なＳＭＣプロトコルを用いる場合には、フルメッシュに通信リンクが存在する通信ネットワークを対象にする必要がある。
【０００８】
本発明は、このような事情を考慮してなされたもので、フルメッシュに通信リンクが存在しない通信ネットワークを対象にした分散ルーティング処理において、ノードの秘密情報を当該ノードの管理者以外の者に秘匿することができる分散ルーティング処理装置およびコンピュータプログラムを提供することを課題とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するために、本発明に係る分散ルーティング処理装置は、複数のノードから構成される通信ネットワークであって、前記複数のノードは複数の局所ノード群に分類され、一の前記局所ノード群は一管理者に属するノードの数が閾値秘密分散法における所定の閾値未満であり、一の前記局所ノード群内の全てのノード間には通信路が存在し、２つの前記局所ノード群間に通信路が存在する場合に当該２つの局所ノード群をお互いに隣接する局所ノード群であると定義した、前記通信ネットワークにおいて、ノードごとに設けられ、局所トポロジー情報から次ホップ情報を求める分散ルーティング処理装置であり、自分散ルーティング処理装置が設けられているノード（自ノード）からの局所トポロジー情報を入力する入力部と、前記入力された局所トポロジー情報を用いて前記閾値による閾値秘密分散法により前記閾値以上の個数の分散情報を生成する秘密分散部と、自ノードが属する局所ノード群内のノード間で、前記閾値以上の個数の分散情報を分散して保持する分散情報格納部と、前記閾値以上の個数の第１の分散情報を、「前記第１の分散情報とは異なり、且つ、前記閾値以上の個数の第２の分散情報（変換分散情報）であって前記閾値以上の個数の変換分散情報を用いて前記第１の分散情報の元の情報を復元することができる変換分散情報」を構成する要素（変換分散情報構成要素）に変換する分散情報変換部と、自ノードが属する局所ノード群に隣接する局所ノード群との間で変換分散情報構成要素を交換して変換分散情報を生成する変換分散情報交換部と、自ノードが属する局所ノード群内の各ノードの分散ルーティング処理装置と連携して、局所トポロジー情報の分散情報から次ホップ情報の分散情報を求めるために必要な所定の関数を分散して計算するＳＭＣ（Secure Multi-party computation）を解決するＳＭＣ部と、自ノードが属する局所ノード群内の各ノードの分散ルーティング処理装置と連携して、次ホップ情報の前記閾値以上の個数の分散情報から次ホップ情報を復元する秘密分散復元部と、前記復元された次ホップ情報を自ノードへ出力する出力部と、を備えたことを特徴とする。
【００１０】
本発明に係るコンピュータプログラムは、複数のノードから構成される通信ネットワークであって、前記複数のノードは複数の局所ノード群に分類され、一の前記局所ノード群は一管理者に属するノードの数が閾値秘密分散法における所定の閾値未満であり、一の前記局所ノード群内の全てのノード間には通信路が存在し、２つの前記局所ノード群間に通信路が存在する場合に当該２つの局所ノード群をお互いに隣接する局所ノード群であると定義した、前記通信ネットワークにおいて、ノードごとに、局所トポロジー情報から次ホップ情報を求める分散ルーティング処理を行うためのコンピュータプログラムであって、自分散ルーティング処理装置が設けられているノード（自ノード）からの局所トポロジー情報を入力する入力ステップと、前記入力された局所トポロジー情報を用いて前記閾値による閾値秘密分散法により前記閾値以上の個数の分散情報を生成する秘密分散ステップと、自ノードが属する局所ノード群内のノード間で、前記閾値以上の個数の分散情報を分散して保持する分散情報格納ステップと、前記閾値以上の個数の第１の分散情報を、「前記第１の分散情報とは異なり、且つ、前記閾値以上の個数の第２の分散情報（変換分散情報）であって前記閾値以上の個数の変換分散情報を用いて前記第１の分散情報の元の情報を復元することができる変換分散情報」を構成する要素（変換分散情報構成要素）に変換する分散情報変換ステップと、自ノードが属する局所ノード群に隣接する局所ノード群との間で変換分散情報構成要素を交換して変換分散情報を生成する変換分散情報交換ステップと、自ノードが属する局所ノード群内の各ノードの分散ルーティング処理装置と連携して、局所トポロジー情報の分散情報から次ホップ情報の分散情報を求めるために必要な所定の関数を分散して計算するＳＭＣ（Secure Multi-party computation）を解決するＳＭＣステップと、自ノードが属する局所ノード群内の各ノードの分散ルーティング処理装置と連携して、次ホップ情報の前記閾値以上の個数の分散情報から次ホップ情報を復元する秘密分散復元ステップと、前記復元された次ホップ情報を自ノードへ出力する出力ステップと、をコンピュータに実行させるためのコンピュータプログラムであることを特徴とする。
これにより、前述の分散ルーティング処理装置がコンピュータを利用して実現できるようになる。
【発明の効果】
【００１１】
本発明によれば、フルメッシュに通信リンクが存在しない通信ネットワークを対象にした分散ルーティング処理において、ノードの秘密情報を当該ノードの管理者以外の者に秘匿することができるという効果が得られる。
【図面の簡単な説明】
【００１２】
【図１】本発明の一実施形態に係る分散ルーティング処理装置１の構成を示すブロック図である。
【図２】本発明の一実施形態に係る分散ルーティング処理対象の通信ネットワーク１００の構成例である。
【図３】本発明の一実施形態に係る分散ルーティング処理のフローチャートである。
【図４】本発明に係る分散ルーティング処理対象の通信ネットワーク３００の一実施例である。
【図５】図４に示す通信ネットワーク３００における局所ノード群の設定例である。
【図６】図４に示す通信ネットワーク３００における局所ノード群の一実施例である。
【発明を実施するための形態】
【００１３】
以下、図面を参照し、本発明の実施形態について説明する。
図１は、本発明の一実施形態に係る分散ルーティング処理装置１の構成を示すブロック図である。図１において、分散ルーティング処理装置１は、入力部１１と出力部１２と秘密分散部１３と秘密分散復元部１４と分散情報格納部１５とＳＭＣ部１６と分散情報変換部１７と変換分散情報交換部１８とを備える。
【００１４】
図２は、本実施形態に係る、分散ルーティング処理を行う対象である通信ネットワーク１００の構成例である。図２において、通信ネットワーク１００は、複数（Ｎ台）のノードから構成されている。通信ネットワーク１００には、通信リンクが存在しないノード間がある。つまり、通信ネットワーク１００は、フルメッシュに通信リンクが存在しない通信ネットワークである。通信ネットワーク１００を構成するＮ台のノードは、複数（７個）の局所ノード群１０１〜１０７に分類されている。
【００１５】
一の局所ノード群は、一管理者に属するノードの数が閾値秘密分散法における所定の閾値未満であり、且つ、局所ノード群内の全てのノード間には通信リンクが存在する（フルメッシュに通信リンクが存在する）ように、設定される。又、２つの局所ノード群間に通信リンクが存在する場合に、当該２つの局所ノード群をお互いに隣接する局所ノード群であると定義する。
【００１６】
例えば、図２において、局所ノード群１０１は８台のノードから構成される。この局所ノード群１０１に対して、閾値秘密分散法における閾値は３に設定されている。従って、局所ノード群１０１においては、一管理者に属するノードの数は３未満である。具体的には、局所ノード群１０１において、管理者Ａに属するのはノードｎ１，ｎ２の２台、管理者Ｂに属するのはノードｎ３の１台、管理者Ｃに属するのはノードｎ４の１台、管理者Ｄに属するのはノードｎ５の１台、管理者Ｅに属するのはノードｎ６の１台、管理者Ｆに属するのはノードｎ７，ｎ８の２台、である。
【００１７】
なお、ノードの管理者とは、当該ノードが格納する情報を知ることできる全ての者を指す。ノードの管理者としては、例えば、ノードの所有者、ノードの所有者からノードの使用権を与えられている者、ノードの使用権限を不当に取得している攻撃者などが挙げられる。
【００１８】
さらに、局所ノード群１０１において、全てのノード間には通信リンクが存在する。図２の例では、局所ノード群１０１内の全ノードｎ１〜ｎ８は、局所的な通信ネットワーク２００に接続している。通信ネットワーク２００は、ノードｎ１〜ｎ８に対して、全ノード間の通信リンクを提供する。これにより、局所ノード群１０１内には、フルメッシュに通信リンクが存在している。
【００１９】
又、図２の通信ネットワーク１００において、局所ノード群間に通信リンクが存在する２つの局所ノード群はお互いに隣接する局所ノード群である。具体的には、局所ノード群１０１と局所ノード群１０２は、お互いに隣接する局所ノード群である。同様に、局所ノード群１０１と局所ノード群１０３、局所ノード群１０２と局所ノード群１０４、局所ノード群１０３と局所ノード群１０４、局所ノード群１０４と局所ノード群１０５、局所ノード群１０４と局所ノード群１０６、局所ノード群１０５と局所ノード群１０７は、それぞれに、お互いに隣接する局所ノード群である。
【００２０】
分散ルーティング処理装置１は、分散ルーティング処理を行う対象である通信ネットワークを構成する各ノードに設けられる。図２の通信ネットワーク１００においては、通信ネットワーク１００を構成するＮ台のノードに対して、ノードごとに、分散ルーティング処理装置１が設けられる。例えば、局所ノード群１０１においては、局所ノード群１０１内の全ノードｎ１〜ｎ８がそれぞれに分散ルーティング処理装置１を有する。
【００２１】
以下、図２に示される、Ｎ台のノードから構成される通信ネットワーク１００、を分散ルーティング処理の対象として説明を行う。この分散ルーティング処理では、Ｎ入力・Ｎ出力の関数［（Ｙ＿１，Ｙ＿２，・・・，Ｙ＿Ｎ）＝Ｆ（Ｘ＿１，Ｘ＿２，・・・，Ｘ＿Ｎ）］を計算する。但し、Ｘ＿ｉはノードｉから入力される局所トポロジー情報である。Ｙ＿ｉはノードｉへ出力する次ホップ情報である。
【００２２】
図１において、入力部１１は、自分散ルーティング処理装置１が設けられているノード（以下、自ノードと称する）ｉから局所トポロジー情報Ｘ＿ｉを入力する。出力部１２は、自ノードｉに対して、分散ルーティング処理の結果のうち次ホップ情報Ｙ＿ｉのみを出力する。
【００２３】
秘密分散部１３は、局所トポロジー情報Ｘ＿ｉを用いて、所定の閾値による閾値秘密分散法により当該閾値以上の個数の分散情報を生成する。秘密分散部１３は、その閾値以上の個数の分散情報を、自ノードが属する局所ノード群（以下、自局所ノード群と称する）内の各ノードで分散して保持させる。
【００２４】
例えば、図２の局所ノード群１０１では、閾値が３であるので、局所トポロジー情報Ｘ＿ｉから３個以上の所定個数（ここでは、８個とする）の分散情報を生成する。そして、その８個の分散情報を、局所ノード群１０１内の各ノードｎ１〜ｎ８でそれぞれ１個ずつ保持する。これにより、局所ノード群１０１では、一管理者に属するノードの数は最大２台であるので、一管理者は、最大で２個の分散情報しか手に入れることができず、該分散情報からは元の局所トポロジー情報Ｘ＿ｉを復元することができない。
【００２５】
なお、閾値秘密分散法としては、非特許文献５に開示されるものを利用することができる。又は、排他的論理和演算を用いて、情報ｘを「ｘ＝ｘ＿１ ＸＯＲ ｘ＿２」となるような、２個の情報ｘ＿１，ｘ＿２に分割する方法を利用することができる。但し、「ＸＯＲ」はビット毎の排他的論理和演算を表す。
【００２６】
秘密分散復元部１４は、自局所ノード群内の各ノードと連携して、次ホップ情報Ｙ＿ｉの複数（閾値秘密分散法における閾値以上の個数）の分散情報から次ホップ情報Ｙ＿ｉを復元する。
【００２７】
例えば、図２の局所ノード群１０１では、閾値が３であるので、次ホップ情報Ｙ＿ｉの３個以上の所定個数（ここでは、８個とする）の分散情報から次ホップ情報Ｙ＿ｉを復元する。その次ホップ情報Ｙ＿ｉの８個の分散情報は、局所ノード群１０１内の各ノードｎ１〜ｎ８でそれぞれ１個ずつ保持されている。このため、ノードｉ（ここでは、ノードｎ１とする）の分散ルーティング処理装置１は、次ホップ情報Ｙ＿ｉの１個の分散情報を保持しているが、残りの７個の分散情報は他の７台のノードｎ２〜ｎ８から取得する。そして、ノードｎ１の分散ルーティング処理装置１は、次ホップ情報Ｙ＿ｉの８個の分散情報から次ホップ情報Ｙ＿ｉを復元する。
【００２８】
分散情報格納部１５は、自ノードで管理する分散情報を保持する。
【００２９】
ＳＭＣ部１６は、所定の関数［ｙ＝ｆ（ｘ）］をＭ台のノードで分散して計算するＳＭＣを解決する。但し、ｘは分散情報である。関数ｆは、分散情報ｘから分散情報ｙを与える。所定の関数［ｙ＝ｆ（ｘ）］としては、局所トポロジー情報Ｘ＿ｉの分散情報から次ホップ情報Ｙ＿ｉの分散情報を求めるために必要な関数が準備される。ＳＭＣを解決する方法には、例えば非特許文献１，２，３などに記載される汎用的な計算手順（ＳＭＣプロトコル）を利用する。
【００３０】
ＳＭＣ部１６は、自局所ノード群内のＭ台のノードのみによって、所定の関数ｆを分散して計算する。一局所ノード群内の全ノード間には通信リンクが存在する。つまり、一局所ノード群内にはフルメッシュに通信リンクが存在する。さらに、一局所ノード群を構成するＭ台のノードのうち一管理者に属するノードの台数は閾値秘密分散法における閾値未満である。
【００３１】
例えば、図２の局所ノード群１０１では、Ｍは８であり、８台のノードｎ１〜ｎ８に対してフルメッシュに通信リンクが存在する。さらに、閾値秘密分散法における閾値は３であり、一管理者に属するノードの数は３未満である。そして、８台のノードｎ１〜ｎ８の各ＳＭＣ部１６によって、所定の関数ｆを分散して計算する。
【００３２】
分散情報変換部１７は、元情報から生成された複数（閾値秘密分散法における閾値以上の個数）の分散情報を、「該分散情報とは異なり且つ複数（閾値秘密分散法における閾値以上の個数）の分散情報（変換分散情報）」を構成する要素（以下、変換分散情報構成要素と称する）、に変換する。但し、閾値秘密分散法における閾値以上の個数の変換分散情報を用いて、元情報を復元することができるようにする。
【００３３】
変換分散情報交換部１８は、自局所ノード群に隣接する局所ノード群（以下、隣接局所ノード群と称する）との間で変換分散情報構成要素を交換して変換分散情報を生成する。変換分散情報交換部１８は、分散情報変換部１７が生成した変換分散情報構成要素を隣接局所ノード群へ送信する。また、変換分散情報交換部１８は、隣接局所ノード群から変換分散情報構成要素を受信する。例えば、図２の通信ネットワーク１００では、局所ノード群１０１内の各ノードｎ１〜ｎ８は、隣接局所ノード群１０２，１０３との間で変換分散情報構成要素を交換する。そして、変換分散情報交換部１８は、隣接局所ノード群から受信した変換分散情報構成要素を用いて変換分散情報を生成する。
【００３４】
ここで、変換分散情報の生成方法の例を説明する。ここでは、閾値秘密分散法における閾値を２とする。元情報をｘとする。元情報ｘから生成された２個の分散情報をｘ＿１，ｘ＿２とする。但し、「ｘ＝ｘ＿１ ＸＯＲ ｘ＿２」である。分散情報ｘ＿１は、ノードｎａで保持している。分散情報ｘ＿２は、ノードｎａが属する局所ノード群内の他のノードｎｂで保持している。このとき、ノードｎａでは、「ｘ＿１＝ｘ＿１１ ＸＯＲ ｘ＿１２」となるｘ＿１１とｘ＿１２を生成する。ノードｎｂでは、「ｘ＿２＝ｘ＿２１ ＸＯＲ ｘ＿２２」となるｘ＿２１とｘ＿２２を生成する。そして、ノードｎａとノードｎｂは、生成した情報を、隣接局所ノード群へ送信する。ここでは、隣接局所ノード群のノードｎｃ，ｎｄへ送信するとする。このとき、ノードｎａは、生成した情報のうち一方の情報ｘ＿１１をノードｎｃへ送信し、もう一方の情報ｘ＿１２をノードｎｄへ送信する。ノードｎｂは、生成した情報のうち一方の情報ｘ＿２１をノードｎｃへ送信し、もう一方の情報ｘ＿２２をノードｎｄへ送信する。隣接局所ノード群において、ノードｎｃは、「ｘ＿３＝ｘ＿１１ ＸＯＲ ｘ＿２１」を計算することにより、変換分散情報ｘ＿３を得る。従って、ｘ＿１１及びｘ＿２１は変換分散情報ｘ＿３の変換分散情報構成要素である。ノードｎｄは、「ｘ＿４＝ｘ＿１２ ＸＯＲ ｘ＿２２」を計算することにより、変換分散情報ｘ＿４を得る。従って、ｘ＿１２及びｘ＿２２は変換分散情報ｘ＿４の変換分散情報構成要素である。そして、隣接局所ノード群において、変換分散情報ｘ＿３はノードｎｃで、変換分散情報ｘ＿４はノードｎｄで、それぞれ分散して保持される。この２個の変換分散情報ｘ＿３，ｘ＿４によれば、「ｘ＝ｘ＿３ ＸＯＲ ｘ＿４」となり、元情報ｘを復元することができる。
【００３５】
次に、図３を参照して、本実施形態に係る分散ルーティング処理の手順を説明する。図３は、本実施形態に係る分散ルーティング処理のフローチャートである。
ステップＳ１：通信ネットワーク１００内のＮ台のノードｉは、それぞれに、自己の分散ルーティング処理装置１へ局所トポロジー情報Ｘ＿ｉを入力する。
【００３６】
ステップＳ２：ノードｉの分散ルーティング処理装置１は、局所トポロジー情報Ｘ＿ｉを用いて、所定の閾値による閾値秘密分散法により当該閾値以上の個数の分散情報を生成する。この分散情報は、自局所ノード群内の各ノードで分散して保持される。
【００３７】
ステップＳ３：ノードｉの分散ルーティング処理装置１は、自ノードｉで保持している分散情報を変換分散情報構成要素に変換する。
【００３８】
ステップＳ４：ノードｉの分散ルーティング処理装置１は、隣接局所ノード群との間で変換分散情報構成要素を交換する。そして、ノードｉの分散ルーティング処理装置１は、隣接局所ノード群から受信した変換分散情報構成要素を用いて変換分散情報を生成する。
【００３９】
ステップＳ５：ノードｉの分散ルーティング処理装置１は、自局所ノード群内のＭ台のノードのみによって、所定の関数［ｙ＝ｆ（ｘ）］を分散して計算する。但し、ｘは、自局所ノード群内のＭ台のノードがそれぞれに保持する分散情報である。なお、分散情報とは変換分散情報を含む。所定の関数［ｙ＝ｆ（ｘ）］は、局所トポロジー情報Ｘ＿ｉの分散情報から次ホップ情報Ｙ＿ｉの分散情報を求めるために必要な関数であり、予め準備される。
【００４０】
ステップＳ６：ノードｉの分散ルーティング処理装置１は、上記ステップＳ３からＳ５の処理を終了する条件を判定する。上記ステップＳ３からＳ５の処理は、通信ネットワーク１００内で最も離れた２つのノード間のホップ数（グラフ理論では「ネットワークの直径」と称される）と同じ回数だけ繰り返す必要がある。この終了条件を、満足する場合にはステップＳ７に進み、満足しない場合にはステップＳ３に戻る。
【００４１】
ステップＳ７：ノードｉの分散ルーティング処理装置１は、自局所ノード群内の各ノードから、閾値秘密分散法における閾値以上の個数だけ次ホップ情報Ｙ＿ｉの分散情報を取得する。そして、ノードｉの分散ルーティング処理装置１は、次ホップ情報Ｙ＿ｉの複数（閾値秘密分散法における閾値以上の個数）の分散情報から、次ホップ情報Ｙ＿ｉを復元する。
【００４２】
ステップＳ８：ノードｉの分散ルーティング処理装置１は、次ホップ情報Ｙ＿ｉを自ノードｉへ出力する。
【実施例】
【００４３】
次に、本実施形態に係る一実施例を説明する。本実施例では、図４に示される、６台のノードから構成される通信ネットワーク３００、を分散ルーティング処理の対象とする。本実施例では、分散ルーティング処理として、最短パスルーティングを扱う。最短パスルーティングでは、２つのノード間の通信パスが最短パスとなるような次ホップ情報を求める。最短パスとは、２つのノード間の通信パスが有する通信リンクの距離の合計が最小となる通信パスである。
【００４４】
図４において、ノード＃１とノード＃２間には通信リンクが存在し、当該通信リンクの距離は１である。ノード＃２とノード＃３間には通信リンクが存在し、当該通信リンクの距離は３である。ノード＃２とノード＃４間には通信リンクが存在し、当該通信リンクの距離は１である。ノード＃３とノード＃５間には通信リンクが存在し、当該通信リンクの距離は１である。ノード＃４とノード＃５間には通信リンクが存在し、当該通信リンクの距離は２である。ノード＃５とノード＃６間には通信リンクが存在し、当該通信リンクの距離は１である。
【００４５】
通信ネットワーク３００には、通信リンクが存在しないノード間がある。つまり、通信ネットワーク３００は、フルメッシュに通信リンクが存在しない通信ネットワークである。
【００４６】
本実施例では、図５に示されるように、局所ノード群が設定されている。局所ノード群Ｇ２は、ノード＃１とノード＃２から構成される。局所ノード群Ｇ３は、ノード＃３とノード＃５から構成される。局所ノード群Ｇ４は、ノード＃２とノード＃４から構成される。局所ノード群Ｇ５は、ノード＃５とノード＃６から構成される。各局所ノード群Ｇ２，Ｇ３，Ｇ４，Ｇ５内は、全てのノード間に通信リンクが存在する（フルメッシュに通信リンクが存在する）。
【００４７】
局所ノード群Ｇ２，Ｇ３，Ｇ４，Ｇ５において、閾値秘密分散法における閾値は２に設定されている。従って、局所ノード群Ｇ２，Ｇ３，Ｇ４，Ｇ５において、一管理者に属するノードの数は２未満である。
【００４８】
図６は、通信ネットワーク３００における局所ノード群の構成である。局所ノード群Ｇ２と局所ノード群Ｇ３との間には通信リンクが存在し、局所ノード群Ｇ２と局所ノード群Ｇ３とはお互いに隣接する局所ノード群である。同様に、局所ノード群Ｇ２と局所ノード群Ｇ４、局所ノード群Ｇ３と局所ノード群Ｇ５、局所ノード群Ｇ４と局所ノード群Ｇ５は、それぞれに、お互いに隣接する局所ノード群である。
【００４９】
図４において、例えば、ノード＃６からノード＃１への最短パスは、ノード＃６→ノード＃５→ノード＃４→ノード＃２→ノード＃１である。従って、ノード＃５から見ると、宛先ノード＃１に対応する次ホップはノード＃４となる。各ノードが予め知っている局所トポロジー情報は、自分との間に通信リンクが存在するノード（以下、隣接ノードと称する）の識別子（ＩＤ）と、自分と隣接ノード間の通信リンクの距離だけである。従って、ノード＃５単独では、宛先ノード＃１に対応する次ホップがノード＃４であるという情報は導出できない。そこで、本実施例では、そのような次ホップ情報を、各ノードが自身の局所トポロジー情報を他のノードに開示せずに求めることを図る。
【００５０】
本実施例では、各ノード＃１〜＃６は、それぞれに、図１の分散ルーティング処理装置１を備える。本実施例では、以下を定義する。
【００５１】
［ｘ］＿ｉ：局所ノード群ｉにおいて秘密情報ｘから閾値秘密分散法により生成されて各ノードに分散されて保持されている分散情報。各ノードでは、分散情報格納部１５が分散情報を保持している。
【００５２】
［ｘ］＿ｉ＝ＳＨＡＲＥ（ｉ，ｘ）：局所ノード群ｉにおいて、閾値秘密分散法により秘密情報ｘから分散情報を生成し、分散情報を各ノードに分散して保持させる動作。局所ノード群ｉ内の各ノードの秘密分散部１３は互いに通信して、本動作を行う。本動作によって、分散情報［ｘ］＿ｉとなる。
【００５３】
［ｙ］＿ｉ＝ＣＯＭＰＵＴＥ（ｉ，ｆ，［ｘ］＿ｉ）：局所ノード群ｉにおいて、分散情報［ｘ］＿ｉを引数として所定の関数［ｙ＝ｆ（ｘ）］を計算し、分散情報［ｙ］＿ｉを得る動作。局所ノード群ｉ内の各ノードのＳＭＣ部１６は、互いに通信して、所定の関数［ｙ＝ｆ（ｘ）］を分散して計算するＳＭＣを解決する。分散情報［ｙ］＿ｉは、局所ノード群ｉ内の各ノードに分散されて保持される。各ノードでは、分散情報格納部１５が分散情報を保持する。
【００５４】
［ｘ］＿ｊ＝ＴＲＡＮＳＦＥＲ（ｉ，ｊ，［ｘ］＿ｉ）：局所ノード群ｉが分散情報［ｘ］＿ｉを変換分散情報構成要素に変換して局所ノード群ｊへ送信し、局所ノード群ｊが該変換分散情報構成要素を用いて変換分散情報［ｘ］＿ｊを生成する、動作。局所ノード群ｉの各ノードの分散情報変換部１７は、分散情報［ｘ］＿ｉを変換分散情報構成要素に変換する。次いで、局所ノード群ｉの各ノードの変換分散情報交換部１８は、局所ノード群ｊの各ノードの変換分散情報交換部１８へ、変換分散情報構成要素を送信する。局所ノード群ｊの各ノードの変換分散情報交換部１８は、受信した変換分散情報構成要素を用いて変換分散情報［ｘ］＿ｊを生成する。局所ノード群ｊにおいて、変換分散情報［ｘ］＿ｊは各ノードに分散されて保持される。局所ノード群ｊの各ノードでは、分散情報格納部１５が変換分散情報を保持する。
【００５５】
ｘ＝ＲＥＣＯＶＥＲ（ｉ，［ｘ］＿ｉ）：局所ノード群ｉにおいて、分散情報［ｘ］＿ｉから秘密情報ｘを復元する動作。なお、分散情報とは変換分散情報を含む。局所ノード群ｉ内の各ノードの秘密分散復元部１４は互いに通信して、本動作を行う。
【００５６】
本実施例では、非特許文献４などに記載されるBellman-Fordアルゴリズムを用いて、最短パスルーティングを行う分散ルーティング処理を実行する。Bellman-Fordアルゴリズムでは全ノードについて最短パスを同時に計算するが、ここでは、説明の便宜上、図４においてノード＃１への最短パスのみを計算する簡略化されたBellman-Fordアルゴリズムを用いて、以下に説明する。
【００５７】
局所ノード群Ｇ２は以下の動作を行う。
［４］＿Ｇ２＝ＳＨＡＲＥ（Ｇ２，４）。ここで、秘密情報「４」はノード＃１からノード＃３までの通信パスの距離である（図４参照）。
［４］＿Ｇ３＝ＴＲＡＮＳＦＥＲ（Ｇ２，Ｇ３，［４］＿Ｇ２）。これにより、秘密情報「４」が変換分散情報［４］＿Ｇ３として局所ノード群Ｇ３へ伝達される。
［２］＿Ｇ２＝ＳＨＡＲＥ（Ｇ２，２）。ここで、秘密情報「２」はノード＃１からノード＃４までの通信パスの距離である（図４参照）。
［２］＿Ｇ４＝ＴＲＡＮＳＦＥＲ（Ｇ２，Ｇ４，［２］＿Ｇ２）。これにより、秘密情報「２」が変換分散情報［２］＿Ｇ４として局所ノード群Ｇ４へ伝達される。
【００５８】
局所ノード群Ｇ３は以下の動作を行う。
［１］＿Ｇ３＝ＳＨＡＲＥ（Ｇ３，１）。ここで、秘密情報「１」はノード＃３からノード＃５までの通信パスの距離である（図４参照）。
［５］＿Ｇ３＝ＣＯＭＰＵＴＥ（Ｇ３，＋，［４］＿Ｇ３，［１］＿Ｇ３）。ここで、所定の関数［ｙ＝ｆ（ｘ）］は、変換分散情報［４］＿Ｇ３と分散情報［１］＿Ｇ３とを引数として加算を行うものである。この結果として得られた分散情報［５］＿Ｇ３は秘密情報「５」の分散情報であり、当該秘密情報「５」はノード＃１からノード＃３を経由したノード＃５までの通信パスの距離である（図４参照）。
［５］＿Ｇ５＝ＴＲＡＮＳＦＥＲ（Ｇ３，Ｇ５，［５］＿Ｇ３）。これにより、秘密情報「５」が変換分散情報［５］＿Ｇ５として局所ノード群Ｇ５へ伝達される。
【００５９】
局所ノード群Ｇ４は以下の動作を行う。
［２］＿Ｇ４＝ＳＨＡＲＥ（Ｇ４，２）。ここで、秘密情報「２」はノード＃４からノード＃５までの通信パスの距離である（図４参照）。
［４］＿Ｇ４＝ＣＯＭＰＵＴＥ（Ｇ４，＋，［２］＿Ｇ４，［２］＿Ｇ４）。ここで、所定の関数［ｙ＝ｆ（ｘ）］は、変換分散情報［２］＿Ｇ４と分散情報［２］＿Ｇ４とを引数として加算を行うものである。この結果として得られた分散情報［４］＿Ｇ４は秘密情報「４」の分散情報であり、当該秘密情報「４」はノード＃１からノード＃４を経由したノード＃５までの通信パスの距離である（図４参照）。
［４］＿Ｇ５＝ＴＲＡＮＳＦＥＲ（Ｇ４，Ｇ５，［４］＿Ｇ４）。これにより、秘密情報「４」が変換分散情報［４］＿Ｇ５として局所ノード群Ｇ５へ伝達される。
【００６０】
局所ノード群Ｇ５は以下の動作を行う。
［＃４］＿Ｇ５＝ＣＯＭＰＵＴＥ（Ｇ５，ａｒｇｍｉｎ，［５］＿Ｇ５，［４］＿Ｇ５）。ここで、所定の関数［ｙ＝ｆ（ｘ）］は、変換分散情報［５］＿Ｇ５と変換分散情報［４］＿Ｇ５とを引数として、最短の距離である方の隣接ノード（次ホップ）のＩＤを求めるものである。この結果として得られた分散情報［＃４］＿Ｇ５は秘密情報「＃４」の分散情報であり、当該秘密情報「＃４」はノード＃４のＩＤである。
＃４＝ＲＥＣＯＶＥＲ（Ｇ５，［＃４］＿Ｇ５）。これにより、秘密情報「＃４」が復元される。秘密情報「＃４」は、ノード＃５において、宛先ノード＃１に対応する次ホップのＩＤである。これにより、ノード＃５において、宛先ノード＃１に対応する次ホップがノード＃４であるという、次ホップ情報が得られる。この次ホップ情報はノード＃５へ出力される。
【００６１】
本実施例において、秘密情報および途中の計算結果は全て分散された状態で保持されるため、各ノードの秘密情報は他のノードに対して秘匿される。
【００６２】
上述したように本実施形態によれば、任意の分散ルーティングを、ＳＭＣの要件を満たしながら実行することができる。これにより、フルメッシュに通信リンクが存在しない通信ネットワークを対象にした分散ルーティング処理において、ノードｉの秘密情報をノードｉの管理者以外の者に秘匿することができるという効果が得られる。又、任意の分散ルーティングに適用できるので、適用範囲が広い。
【００６３】
以上、本発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【００６４】
なお、本発明に適用可能な通信ネットワークとしては、物理ノードと物理通信リンクから成る物理ネットワークであってもよく、又は、peer-to-peer技術もしくはオーバーレイネットワーク技術もしくは計算機仮想化技術等を用いて作られた論理ノードと論理通信リンクから成る論理ネットワークであってもよい。
【００６５】
例えば、peer-to-peerネットワークや、仮想化された計算機から構成される仮想化されたネットワークのような、管理者が複数存在し、各ノードは異なる管理者に属する場合があり、したがって各ノードの管理者と、ノードに格納される分散ルーティング中の情報の所有者とが必ずしも一致しない環境において、各ノードの秘密情報を開示せずに分散ルーティングを実行することができる。
【００６６】
また、図３に示す各ステップを実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、分散ルーティング処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものであってもよい。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＤＶＤ（Digital Versatile Disk）等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【００６７】
さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Dynamic Random Access Memory））のように、一定時間プログラムを保持しているものも含むものとする。
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【符号の説明】
【００６８】
１…分散ルーティング処理装置、１１…入力部、１２…出力部、１３…秘密分散部、１４…秘密分散復元部、１５…分散情報格納部、１６…ＳＭＣ部、１７…分散情報変換部、１８…変換分散情報交換部
【技術分野】
【０００１】
本発明は、分散ルーティング処理装置およびコンピュータプログラムに関する。
【背景技術】
【０００２】
従来、複数（Ｎ台）の通信装置（以下、ノードと称する）と、ノード間を結ぶ通信路（以下、通信リンクと称する）とからなる通信ネットワークにおいて、Ｎ台のノード間で通信して分散ルーティング処理を行う技術が知られている。この分散ルーティング処理とは、Ｎ入力・Ｎ出力の関数［（Ｙ＿１，Ｙ＿２，・・・，Ｙ＿Ｎ）＝Ｆ（Ｘ＿１，Ｘ＿２，・・・，Ｘ＿Ｎ）］を計算する処理である。但し、Ｎは通信ネットワークを構成するノードの台数である。Ｘ＿ｉはノードｉから入力される局所トポロジー情報である。Ｙ＿ｉはノードｉへ出力する次ホップ情報である。ｉは１からＮまでの自然数である。局所トポロジー情報Ｘ＿ｉとは、ノードｉと他のノードとの間の接続関係（通信リンクの有無）を示す情報である。次ホップ情報Ｙ＿ｉとは、あるノードにメッセージを届けるために、ノードｉがメッセージをどのノードに転送すればよいのかを示す情報である。
【０００３】
任意の関数ＦをＮ台のノードで分散して計算する問題はＳＭＣ（Secure Multi-party computation）として知られている。このＳＭＣを解決する方法として、例えば非特許文献１，２，３などに、汎用的な計算手順（ＳＭＣプロトコル）が開示されている。従来のＳＭＣ技術では、通信ネットワーク内の全ノード間に通信リンクが存在する、所謂フルメッシュに通信リンクが存在する通信ネットワークを対象にして、通信ネットワークを構成するＮ台のノードのうち単一の管理者に属するノードの台数がある閾値未満であるという条件下で、汎用的なＳＭＣプロトコルを用いて、関数ＦをＮ台のノードで分散して計算している。これにより、ノードｉの管理者以外の者には、ノードｉの秘密情報を開示しないようにすることができる。ノードｉの秘密情報とは、ノードｉに係る入力情報（局所トポロジー情報）Ｘ＿ｉ及び出力情報（次ホップ情報）Ｙ＿ｉ、並びに入力情報Ｘ＿ｉを用いて関数Ｆを計算する途中で発生した情報を指す。
【０００４】
一方、フルメッシュに通信リンクが存在しない通信ネットワークを対象にした従来の分散ルーティング処理技術として、例えば非特許文献４などに記載されるBellman-Fordアルゴリズムが知られている。この従来の分散ルーティング処理技術では、以下の４つの手順（Ｓ１０１からＳ１０４）を用いている。
Ｓ１０１：各ノードｉからの局所トポロジー情報Ｘ＿ｉの入力。
Ｓ１０２：各ノードｉにおいて局所トポロジー情報Ｘ＿ｉを用いた計算。
Ｓ１０３：各ノードｉから、通信リンクが存在する他のノードへ、情報の転送。
Ｓ１０４：各ノードｉへ次ホップ情報の出力。
このBellman-Fordアルゴリズムでは、ノードｉの秘密情報を他のノードに対して秘匿することは考慮されていない。従って、ノードｉの秘密情報がノードｉの管理者以外の者に漏洩する可能性がある。
【０００５】
また、非特許文献５には閾値秘密分散法が開示されている。閾値秘密分散法では、秘密情報から閾値以上の個数の分散情報を生成する。その分散情報は、当該閾値以上の個数の分散情報を使用しないと、元の秘密情報を復元することができないものである。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Goldreich, O. Foundations of Cryptography, volume 2, Basic Applications. Cambridge University Press, 2004.
【非特許文献２】Goldreich, O., Micali, S., and Wigderson, A. How to play any mental game. In Proceedings of the nineteenth annual ACM symposium on Theory of computing (1987), ACM, pp. 218-229.
【非特許文献３】Ben-Or, M., Goldwasser, S., and Wigderson, A. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the twentieth annual ACM symposium on Theory of computing (1988), ACM, pp. 1-10.
【非特許文献４】Lynch, N.A., Distributed algorithms, Morgan Kaufmann, 1996.
【非特許文献５】Shamir, A. How to share a secret. Communications of the ACM 22, 11 (1979), 612-613.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、上述したBellman-Fordアルゴリズムに代表される従来の分散ルーティング処理技術では、フルメッシュに通信リンクが存在しない通信ネットワークを対象にしているが、ノードｉの秘密情報をノードｉの管理者以外の者に秘匿することができない。一方、上述した汎用的なＳＭＣプロトコルを用いる場合には、フルメッシュに通信リンクが存在する通信ネットワークを対象にする必要がある。
【０００８】
本発明は、このような事情を考慮してなされたもので、フルメッシュに通信リンクが存在しない通信ネットワークを対象にした分散ルーティング処理において、ノードの秘密情報を当該ノードの管理者以外の者に秘匿することができる分散ルーティング処理装置およびコンピュータプログラムを提供することを課題とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するために、本発明に係る分散ルーティング処理装置は、複数のノードから構成される通信ネットワークであって、前記複数のノードは複数の局所ノード群に分類され、一の前記局所ノード群は一管理者に属するノードの数が閾値秘密分散法における所定の閾値未満であり、一の前記局所ノード群内の全てのノード間には通信路が存在し、２つの前記局所ノード群間に通信路が存在する場合に当該２つの局所ノード群をお互いに隣接する局所ノード群であると定義した、前記通信ネットワークにおいて、ノードごとに設けられ、局所トポロジー情報から次ホップ情報を求める分散ルーティング処理装置であり、自分散ルーティング処理装置が設けられているノード（自ノード）からの局所トポロジー情報を入力する入力部と、前記入力された局所トポロジー情報を用いて前記閾値による閾値秘密分散法により前記閾値以上の個数の分散情報を生成する秘密分散部と、自ノードが属する局所ノード群内のノード間で、前記閾値以上の個数の分散情報を分散して保持する分散情報格納部と、前記閾値以上の個数の第１の分散情報を、「前記第１の分散情報とは異なり、且つ、前記閾値以上の個数の第２の分散情報（変換分散情報）であって前記閾値以上の個数の変換分散情報を用いて前記第１の分散情報の元の情報を復元することができる変換分散情報」を構成する要素（変換分散情報構成要素）に変換する分散情報変換部と、自ノードが属する局所ノード群に隣接する局所ノード群との間で変換分散情報構成要素を交換して変換分散情報を生成する変換分散情報交換部と、自ノードが属する局所ノード群内の各ノードの分散ルーティング処理装置と連携して、局所トポロジー情報の分散情報から次ホップ情報の分散情報を求めるために必要な所定の関数を分散して計算するＳＭＣ（Secure Multi-party computation）を解決するＳＭＣ部と、自ノードが属する局所ノード群内の各ノードの分散ルーティング処理装置と連携して、次ホップ情報の前記閾値以上の個数の分散情報から次ホップ情報を復元する秘密分散復元部と、前記復元された次ホップ情報を自ノードへ出力する出力部と、を備えたことを特徴とする。
【００１０】
本発明に係るコンピュータプログラムは、複数のノードから構成される通信ネットワークであって、前記複数のノードは複数の局所ノード群に分類され、一の前記局所ノード群は一管理者に属するノードの数が閾値秘密分散法における所定の閾値未満であり、一の前記局所ノード群内の全てのノード間には通信路が存在し、２つの前記局所ノード群間に通信路が存在する場合に当該２つの局所ノード群をお互いに隣接する局所ノード群であると定義した、前記通信ネットワークにおいて、ノードごとに、局所トポロジー情報から次ホップ情報を求める分散ルーティング処理を行うためのコンピュータプログラムであって、自分散ルーティング処理装置が設けられているノード（自ノード）からの局所トポロジー情報を入力する入力ステップと、前記入力された局所トポロジー情報を用いて前記閾値による閾値秘密分散法により前記閾値以上の個数の分散情報を生成する秘密分散ステップと、自ノードが属する局所ノード群内のノード間で、前記閾値以上の個数の分散情報を分散して保持する分散情報格納ステップと、前記閾値以上の個数の第１の分散情報を、「前記第１の分散情報とは異なり、且つ、前記閾値以上の個数の第２の分散情報（変換分散情報）であって前記閾値以上の個数の変換分散情報を用いて前記第１の分散情報の元の情報を復元することができる変換分散情報」を構成する要素（変換分散情報構成要素）に変換する分散情報変換ステップと、自ノードが属する局所ノード群に隣接する局所ノード群との間で変換分散情報構成要素を交換して変換分散情報を生成する変換分散情報交換ステップと、自ノードが属する局所ノード群内の各ノードの分散ルーティング処理装置と連携して、局所トポロジー情報の分散情報から次ホップ情報の分散情報を求めるために必要な所定の関数を分散して計算するＳＭＣ（Secure Multi-party computation）を解決するＳＭＣステップと、自ノードが属する局所ノード群内の各ノードの分散ルーティング処理装置と連携して、次ホップ情報の前記閾値以上の個数の分散情報から次ホップ情報を復元する秘密分散復元ステップと、前記復元された次ホップ情報を自ノードへ出力する出力ステップと、をコンピュータに実行させるためのコンピュータプログラムであることを特徴とする。
これにより、前述の分散ルーティング処理装置がコンピュータを利用して実現できるようになる。
【発明の効果】
【００１１】
本発明によれば、フルメッシュに通信リンクが存在しない通信ネットワークを対象にした分散ルーティング処理において、ノードの秘密情報を当該ノードの管理者以外の者に秘匿することができるという効果が得られる。
【図面の簡単な説明】
【００１２】
【図１】本発明の一実施形態に係る分散ルーティング処理装置１の構成を示すブロック図である。
【図２】本発明の一実施形態に係る分散ルーティング処理対象の通信ネットワーク１００の構成例である。
【図３】本発明の一実施形態に係る分散ルーティング処理のフローチャートである。
【図４】本発明に係る分散ルーティング処理対象の通信ネットワーク３００の一実施例である。
【図５】図４に示す通信ネットワーク３００における局所ノード群の設定例である。
【図６】図４に示す通信ネットワーク３００における局所ノード群の一実施例である。
【発明を実施するための形態】
【００１３】
以下、図面を参照し、本発明の実施形態について説明する。
図１は、本発明の一実施形態に係る分散ルーティング処理装置１の構成を示すブロック図である。図１において、分散ルーティング処理装置１は、入力部１１と出力部１２と秘密分散部１３と秘密分散復元部１４と分散情報格納部１５とＳＭＣ部１６と分散情報変換部１７と変換分散情報交換部１８とを備える。
【００１４】
図２は、本実施形態に係る、分散ルーティング処理を行う対象である通信ネットワーク１００の構成例である。図２において、通信ネットワーク１００は、複数（Ｎ台）のノードから構成されている。通信ネットワーク１００には、通信リンクが存在しないノード間がある。つまり、通信ネットワーク１００は、フルメッシュに通信リンクが存在しない通信ネットワークである。通信ネットワーク１００を構成するＮ台のノードは、複数（７個）の局所ノード群１０１〜１０７に分類されている。
【００１５】
一の局所ノード群は、一管理者に属するノードの数が閾値秘密分散法における所定の閾値未満であり、且つ、局所ノード群内の全てのノード間には通信リンクが存在する（フルメッシュに通信リンクが存在する）ように、設定される。又、２つの局所ノード群間に通信リンクが存在する場合に、当該２つの局所ノード群をお互いに隣接する局所ノード群であると定義する。
【００１６】
例えば、図２において、局所ノード群１０１は８台のノードから構成される。この局所ノード群１０１に対して、閾値秘密分散法における閾値は３に設定されている。従って、局所ノード群１０１においては、一管理者に属するノードの数は３未満である。具体的には、局所ノード群１０１において、管理者Ａに属するのはノードｎ１，ｎ２の２台、管理者Ｂに属するのはノードｎ３の１台、管理者Ｃに属するのはノードｎ４の１台、管理者Ｄに属するのはノードｎ５の１台、管理者Ｅに属するのはノードｎ６の１台、管理者Ｆに属するのはノードｎ７，ｎ８の２台、である。
【００１７】
なお、ノードの管理者とは、当該ノードが格納する情報を知ることできる全ての者を指す。ノードの管理者としては、例えば、ノードの所有者、ノードの所有者からノードの使用権を与えられている者、ノードの使用権限を不当に取得している攻撃者などが挙げられる。
【００１８】
さらに、局所ノード群１０１において、全てのノード間には通信リンクが存在する。図２の例では、局所ノード群１０１内の全ノードｎ１〜ｎ８は、局所的な通信ネットワーク２００に接続している。通信ネットワーク２００は、ノードｎ１〜ｎ８に対して、全ノード間の通信リンクを提供する。これにより、局所ノード群１０１内には、フルメッシュに通信リンクが存在している。
【００１９】
又、図２の通信ネットワーク１００において、局所ノード群間に通信リンクが存在する２つの局所ノード群はお互いに隣接する局所ノード群である。具体的には、局所ノード群１０１と局所ノード群１０２は、お互いに隣接する局所ノード群である。同様に、局所ノード群１０１と局所ノード群１０３、局所ノード群１０２と局所ノード群１０４、局所ノード群１０３と局所ノード群１０４、局所ノード群１０４と局所ノード群１０５、局所ノード群１０４と局所ノード群１０６、局所ノード群１０５と局所ノード群１０７は、それぞれに、お互いに隣接する局所ノード群である。
【００２０】
分散ルーティング処理装置１は、分散ルーティング処理を行う対象である通信ネットワークを構成する各ノードに設けられる。図２の通信ネットワーク１００においては、通信ネットワーク１００を構成するＮ台のノードに対して、ノードごとに、分散ルーティング処理装置１が設けられる。例えば、局所ノード群１０１においては、局所ノード群１０１内の全ノードｎ１〜ｎ８がそれぞれに分散ルーティング処理装置１を有する。
【００２１】
以下、図２に示される、Ｎ台のノードから構成される通信ネットワーク１００、を分散ルーティング処理の対象として説明を行う。この分散ルーティング処理では、Ｎ入力・Ｎ出力の関数［（Ｙ＿１，Ｙ＿２，・・・，Ｙ＿Ｎ）＝Ｆ（Ｘ＿１，Ｘ＿２，・・・，Ｘ＿Ｎ）］を計算する。但し、Ｘ＿ｉはノードｉから入力される局所トポロジー情報である。Ｙ＿ｉはノードｉへ出力する次ホップ情報である。
【００２２】
図１において、入力部１１は、自分散ルーティング処理装置１が設けられているノード（以下、自ノードと称する）ｉから局所トポロジー情報Ｘ＿ｉを入力する。出力部１２は、自ノードｉに対して、分散ルーティング処理の結果のうち次ホップ情報Ｙ＿ｉのみを出力する。
【００２３】
秘密分散部１３は、局所トポロジー情報Ｘ＿ｉを用いて、所定の閾値による閾値秘密分散法により当該閾値以上の個数の分散情報を生成する。秘密分散部１３は、その閾値以上の個数の分散情報を、自ノードが属する局所ノード群（以下、自局所ノード群と称する）内の各ノードで分散して保持させる。
【００２４】
例えば、図２の局所ノード群１０１では、閾値が３であるので、局所トポロジー情報Ｘ＿ｉから３個以上の所定個数（ここでは、８個とする）の分散情報を生成する。そして、その８個の分散情報を、局所ノード群１０１内の各ノードｎ１〜ｎ８でそれぞれ１個ずつ保持する。これにより、局所ノード群１０１では、一管理者に属するノードの数は最大２台であるので、一管理者は、最大で２個の分散情報しか手に入れることができず、該分散情報からは元の局所トポロジー情報Ｘ＿ｉを復元することができない。
【００２５】
なお、閾値秘密分散法としては、非特許文献５に開示されるものを利用することができる。又は、排他的論理和演算を用いて、情報ｘを「ｘ＝ｘ＿１ ＸＯＲ ｘ＿２」となるような、２個の情報ｘ＿１，ｘ＿２に分割する方法を利用することができる。但し、「ＸＯＲ」はビット毎の排他的論理和演算を表す。
【００２６】
秘密分散復元部１４は、自局所ノード群内の各ノードと連携して、次ホップ情報Ｙ＿ｉの複数（閾値秘密分散法における閾値以上の個数）の分散情報から次ホップ情報Ｙ＿ｉを復元する。
【００２７】
例えば、図２の局所ノード群１０１では、閾値が３であるので、次ホップ情報Ｙ＿ｉの３個以上の所定個数（ここでは、８個とする）の分散情報から次ホップ情報Ｙ＿ｉを復元する。その次ホップ情報Ｙ＿ｉの８個の分散情報は、局所ノード群１０１内の各ノードｎ１〜ｎ８でそれぞれ１個ずつ保持されている。このため、ノードｉ（ここでは、ノードｎ１とする）の分散ルーティング処理装置１は、次ホップ情報Ｙ＿ｉの１個の分散情報を保持しているが、残りの７個の分散情報は他の７台のノードｎ２〜ｎ８から取得する。そして、ノードｎ１の分散ルーティング処理装置１は、次ホップ情報Ｙ＿ｉの８個の分散情報から次ホップ情報Ｙ＿ｉを復元する。
【００２８】
分散情報格納部１５は、自ノードで管理する分散情報を保持する。
【００２９】
ＳＭＣ部１６は、所定の関数［ｙ＝ｆ（ｘ）］をＭ台のノードで分散して計算するＳＭＣを解決する。但し、ｘは分散情報である。関数ｆは、分散情報ｘから分散情報ｙを与える。所定の関数［ｙ＝ｆ（ｘ）］としては、局所トポロジー情報Ｘ＿ｉの分散情報から次ホップ情報Ｙ＿ｉの分散情報を求めるために必要な関数が準備される。ＳＭＣを解決する方法には、例えば非特許文献１，２，３などに記載される汎用的な計算手順（ＳＭＣプロトコル）を利用する。
【００３０】
ＳＭＣ部１６は、自局所ノード群内のＭ台のノードのみによって、所定の関数ｆを分散して計算する。一局所ノード群内の全ノード間には通信リンクが存在する。つまり、一局所ノード群内にはフルメッシュに通信リンクが存在する。さらに、一局所ノード群を構成するＭ台のノードのうち一管理者に属するノードの台数は閾値秘密分散法における閾値未満である。
【００３１】
例えば、図２の局所ノード群１０１では、Ｍは８であり、８台のノードｎ１〜ｎ８に対してフルメッシュに通信リンクが存在する。さらに、閾値秘密分散法における閾値は３であり、一管理者に属するノードの数は３未満である。そして、８台のノードｎ１〜ｎ８の各ＳＭＣ部１６によって、所定の関数ｆを分散して計算する。
【００３２】
分散情報変換部１７は、元情報から生成された複数（閾値秘密分散法における閾値以上の個数）の分散情報を、「該分散情報とは異なり且つ複数（閾値秘密分散法における閾値以上の個数）の分散情報（変換分散情報）」を構成する要素（以下、変換分散情報構成要素と称する）、に変換する。但し、閾値秘密分散法における閾値以上の個数の変換分散情報を用いて、元情報を復元することができるようにする。
【００３３】
変換分散情報交換部１８は、自局所ノード群に隣接する局所ノード群（以下、隣接局所ノード群と称する）との間で変換分散情報構成要素を交換して変換分散情報を生成する。変換分散情報交換部１８は、分散情報変換部１７が生成した変換分散情報構成要素を隣接局所ノード群へ送信する。また、変換分散情報交換部１８は、隣接局所ノード群から変換分散情報構成要素を受信する。例えば、図２の通信ネットワーク１００では、局所ノード群１０１内の各ノードｎ１〜ｎ８は、隣接局所ノード群１０２，１０３との間で変換分散情報構成要素を交換する。そして、変換分散情報交換部１８は、隣接局所ノード群から受信した変換分散情報構成要素を用いて変換分散情報を生成する。
【００３４】
ここで、変換分散情報の生成方法の例を説明する。ここでは、閾値秘密分散法における閾値を２とする。元情報をｘとする。元情報ｘから生成された２個の分散情報をｘ＿１，ｘ＿２とする。但し、「ｘ＝ｘ＿１ ＸＯＲ ｘ＿２」である。分散情報ｘ＿１は、ノードｎａで保持している。分散情報ｘ＿２は、ノードｎａが属する局所ノード群内の他のノードｎｂで保持している。このとき、ノードｎａでは、「ｘ＿１＝ｘ＿１１ ＸＯＲ ｘ＿１２」となるｘ＿１１とｘ＿１２を生成する。ノードｎｂでは、「ｘ＿２＝ｘ＿２１ ＸＯＲ ｘ＿２２」となるｘ＿２１とｘ＿２２を生成する。そして、ノードｎａとノードｎｂは、生成した情報を、隣接局所ノード群へ送信する。ここでは、隣接局所ノード群のノードｎｃ，ｎｄへ送信するとする。このとき、ノードｎａは、生成した情報のうち一方の情報ｘ＿１１をノードｎｃへ送信し、もう一方の情報ｘ＿１２をノードｎｄへ送信する。ノードｎｂは、生成した情報のうち一方の情報ｘ＿２１をノードｎｃへ送信し、もう一方の情報ｘ＿２２をノードｎｄへ送信する。隣接局所ノード群において、ノードｎｃは、「ｘ＿３＝ｘ＿１１ ＸＯＲ ｘ＿２１」を計算することにより、変換分散情報ｘ＿３を得る。従って、ｘ＿１１及びｘ＿２１は変換分散情報ｘ＿３の変換分散情報構成要素である。ノードｎｄは、「ｘ＿４＝ｘ＿１２ ＸＯＲ ｘ＿２２」を計算することにより、変換分散情報ｘ＿４を得る。従って、ｘ＿１２及びｘ＿２２は変換分散情報ｘ＿４の変換分散情報構成要素である。そして、隣接局所ノード群において、変換分散情報ｘ＿３はノードｎｃで、変換分散情報ｘ＿４はノードｎｄで、それぞれ分散して保持される。この２個の変換分散情報ｘ＿３，ｘ＿４によれば、「ｘ＝ｘ＿３ ＸＯＲ ｘ＿４」となり、元情報ｘを復元することができる。
【００３５】
次に、図３を参照して、本実施形態に係る分散ルーティング処理の手順を説明する。図３は、本実施形態に係る分散ルーティング処理のフローチャートである。
ステップＳ１：通信ネットワーク１００内のＮ台のノードｉは、それぞれに、自己の分散ルーティング処理装置１へ局所トポロジー情報Ｘ＿ｉを入力する。
【００３６】
ステップＳ２：ノードｉの分散ルーティング処理装置１は、局所トポロジー情報Ｘ＿ｉを用いて、所定の閾値による閾値秘密分散法により当該閾値以上の個数の分散情報を生成する。この分散情報は、自局所ノード群内の各ノードで分散して保持される。
【００３７】
ステップＳ３：ノードｉの分散ルーティング処理装置１は、自ノードｉで保持している分散情報を変換分散情報構成要素に変換する。
【００３８】
ステップＳ４：ノードｉの分散ルーティング処理装置１は、隣接局所ノード群との間で変換分散情報構成要素を交換する。そして、ノードｉの分散ルーティング処理装置１は、隣接局所ノード群から受信した変換分散情報構成要素を用いて変換分散情報を生成する。
【００３９】
ステップＳ５：ノードｉの分散ルーティング処理装置１は、自局所ノード群内のＭ台のノードのみによって、所定の関数［ｙ＝ｆ（ｘ）］を分散して計算する。但し、ｘは、自局所ノード群内のＭ台のノードがそれぞれに保持する分散情報である。なお、分散情報とは変換分散情報を含む。所定の関数［ｙ＝ｆ（ｘ）］は、局所トポロジー情報Ｘ＿ｉの分散情報から次ホップ情報Ｙ＿ｉの分散情報を求めるために必要な関数であり、予め準備される。
【００４０】
ステップＳ６：ノードｉの分散ルーティング処理装置１は、上記ステップＳ３からＳ５の処理を終了する条件を判定する。上記ステップＳ３からＳ５の処理は、通信ネットワーク１００内で最も離れた２つのノード間のホップ数（グラフ理論では「ネットワークの直径」と称される）と同じ回数だけ繰り返す必要がある。この終了条件を、満足する場合にはステップＳ７に進み、満足しない場合にはステップＳ３に戻る。
【００４１】
ステップＳ７：ノードｉの分散ルーティング処理装置１は、自局所ノード群内の各ノードから、閾値秘密分散法における閾値以上の個数だけ次ホップ情報Ｙ＿ｉの分散情報を取得する。そして、ノードｉの分散ルーティング処理装置１は、次ホップ情報Ｙ＿ｉの複数（閾値秘密分散法における閾値以上の個数）の分散情報から、次ホップ情報Ｙ＿ｉを復元する。
【００４２】
ステップＳ８：ノードｉの分散ルーティング処理装置１は、次ホップ情報Ｙ＿ｉを自ノードｉへ出力する。
【実施例】
【００４３】
次に、本実施形態に係る一実施例を説明する。本実施例では、図４に示される、６台のノードから構成される通信ネットワーク３００、を分散ルーティング処理の対象とする。本実施例では、分散ルーティング処理として、最短パスルーティングを扱う。最短パスルーティングでは、２つのノード間の通信パスが最短パスとなるような次ホップ情報を求める。最短パスとは、２つのノード間の通信パスが有する通信リンクの距離の合計が最小となる通信パスである。
【００４４】
図４において、ノード＃１とノード＃２間には通信リンクが存在し、当該通信リンクの距離は１である。ノード＃２とノード＃３間には通信リンクが存在し、当該通信リンクの距離は３である。ノード＃２とノード＃４間には通信リンクが存在し、当該通信リンクの距離は１である。ノード＃３とノード＃５間には通信リンクが存在し、当該通信リンクの距離は１である。ノード＃４とノード＃５間には通信リンクが存在し、当該通信リンクの距離は２である。ノード＃５とノード＃６間には通信リンクが存在し、当該通信リンクの距離は１である。
【００４５】
通信ネットワーク３００には、通信リンクが存在しないノード間がある。つまり、通信ネットワーク３００は、フルメッシュに通信リンクが存在しない通信ネットワークである。
【００４６】
本実施例では、図５に示されるように、局所ノード群が設定されている。局所ノード群Ｇ２は、ノード＃１とノード＃２から構成される。局所ノード群Ｇ３は、ノード＃３とノード＃５から構成される。局所ノード群Ｇ４は、ノード＃２とノード＃４から構成される。局所ノード群Ｇ５は、ノード＃５とノード＃６から構成される。各局所ノード群Ｇ２，Ｇ３，Ｇ４，Ｇ５内は、全てのノード間に通信リンクが存在する（フルメッシュに通信リンクが存在する）。
【００４７】
局所ノード群Ｇ２，Ｇ３，Ｇ４，Ｇ５において、閾値秘密分散法における閾値は２に設定されている。従って、局所ノード群Ｇ２，Ｇ３，Ｇ４，Ｇ５において、一管理者に属するノードの数は２未満である。
【００４８】
図６は、通信ネットワーク３００における局所ノード群の構成である。局所ノード群Ｇ２と局所ノード群Ｇ３との間には通信リンクが存在し、局所ノード群Ｇ２と局所ノード群Ｇ３とはお互いに隣接する局所ノード群である。同様に、局所ノード群Ｇ２と局所ノード群Ｇ４、局所ノード群Ｇ３と局所ノード群Ｇ５、局所ノード群Ｇ４と局所ノード群Ｇ５は、それぞれに、お互いに隣接する局所ノード群である。
【００４９】
図４において、例えば、ノード＃６からノード＃１への最短パスは、ノード＃６→ノード＃５→ノード＃４→ノード＃２→ノード＃１である。従って、ノード＃５から見ると、宛先ノード＃１に対応する次ホップはノード＃４となる。各ノードが予め知っている局所トポロジー情報は、自分との間に通信リンクが存在するノード（以下、隣接ノードと称する）の識別子（ＩＤ）と、自分と隣接ノード間の通信リンクの距離だけである。従って、ノード＃５単独では、宛先ノード＃１に対応する次ホップがノード＃４であるという情報は導出できない。そこで、本実施例では、そのような次ホップ情報を、各ノードが自身の局所トポロジー情報を他のノードに開示せずに求めることを図る。
【００５０】
本実施例では、各ノード＃１〜＃６は、それぞれに、図１の分散ルーティング処理装置１を備える。本実施例では、以下を定義する。
【００５１】
［ｘ］＿ｉ：局所ノード群ｉにおいて秘密情報ｘから閾値秘密分散法により生成されて各ノードに分散されて保持されている分散情報。各ノードでは、分散情報格納部１５が分散情報を保持している。
【００５２】
［ｘ］＿ｉ＝ＳＨＡＲＥ（ｉ，ｘ）：局所ノード群ｉにおいて、閾値秘密分散法により秘密情報ｘから分散情報を生成し、分散情報を各ノードに分散して保持させる動作。局所ノード群ｉ内の各ノードの秘密分散部１３は互いに通信して、本動作を行う。本動作によって、分散情報［ｘ］＿ｉとなる。
【００５３】
［ｙ］＿ｉ＝ＣＯＭＰＵＴＥ（ｉ，ｆ，［ｘ］＿ｉ）：局所ノード群ｉにおいて、分散情報［ｘ］＿ｉを引数として所定の関数［ｙ＝ｆ（ｘ）］を計算し、分散情報［ｙ］＿ｉを得る動作。局所ノード群ｉ内の各ノードのＳＭＣ部１６は、互いに通信して、所定の関数［ｙ＝ｆ（ｘ）］を分散して計算するＳＭＣを解決する。分散情報［ｙ］＿ｉは、局所ノード群ｉ内の各ノードに分散されて保持される。各ノードでは、分散情報格納部１５が分散情報を保持する。
【００５４】
［ｘ］＿ｊ＝ＴＲＡＮＳＦＥＲ（ｉ，ｊ，［ｘ］＿ｉ）：局所ノード群ｉが分散情報［ｘ］＿ｉを変換分散情報構成要素に変換して局所ノード群ｊへ送信し、局所ノード群ｊが該変換分散情報構成要素を用いて変換分散情報［ｘ］＿ｊを生成する、動作。局所ノード群ｉの各ノードの分散情報変換部１７は、分散情報［ｘ］＿ｉを変換分散情報構成要素に変換する。次いで、局所ノード群ｉの各ノードの変換分散情報交換部１８は、局所ノード群ｊの各ノードの変換分散情報交換部１８へ、変換分散情報構成要素を送信する。局所ノード群ｊの各ノードの変換分散情報交換部１８は、受信した変換分散情報構成要素を用いて変換分散情報［ｘ］＿ｊを生成する。局所ノード群ｊにおいて、変換分散情報［ｘ］＿ｊは各ノードに分散されて保持される。局所ノード群ｊの各ノードでは、分散情報格納部１５が変換分散情報を保持する。
【００５５】
ｘ＝ＲＥＣＯＶＥＲ（ｉ，［ｘ］＿ｉ）：局所ノード群ｉにおいて、分散情報［ｘ］＿ｉから秘密情報ｘを復元する動作。なお、分散情報とは変換分散情報を含む。局所ノード群ｉ内の各ノードの秘密分散復元部１４は互いに通信して、本動作を行う。
【００５６】
本実施例では、非特許文献４などに記載されるBellman-Fordアルゴリズムを用いて、最短パスルーティングを行う分散ルーティング処理を実行する。Bellman-Fordアルゴリズムでは全ノードについて最短パスを同時に計算するが、ここでは、説明の便宜上、図４においてノード＃１への最短パスのみを計算する簡略化されたBellman-Fordアルゴリズムを用いて、以下に説明する。
【００５７】
局所ノード群Ｇ２は以下の動作を行う。
［４］＿Ｇ２＝ＳＨＡＲＥ（Ｇ２，４）。ここで、秘密情報「４」はノード＃１からノード＃３までの通信パスの距離である（図４参照）。
［４］＿Ｇ３＝ＴＲＡＮＳＦＥＲ（Ｇ２，Ｇ３，［４］＿Ｇ２）。これにより、秘密情報「４」が変換分散情報［４］＿Ｇ３として局所ノード群Ｇ３へ伝達される。
［２］＿Ｇ２＝ＳＨＡＲＥ（Ｇ２，２）。ここで、秘密情報「２」はノード＃１からノード＃４までの通信パスの距離である（図４参照）。
［２］＿Ｇ４＝ＴＲＡＮＳＦＥＲ（Ｇ２，Ｇ４，［２］＿Ｇ２）。これにより、秘密情報「２」が変換分散情報［２］＿Ｇ４として局所ノード群Ｇ４へ伝達される。
【００５８】
局所ノード群Ｇ３は以下の動作を行う。
［１］＿Ｇ３＝ＳＨＡＲＥ（Ｇ３，１）。ここで、秘密情報「１」はノード＃３からノード＃５までの通信パスの距離である（図４参照）。
［５］＿Ｇ３＝ＣＯＭＰＵＴＥ（Ｇ３，＋，［４］＿Ｇ３，［１］＿Ｇ３）。ここで、所定の関数［ｙ＝ｆ（ｘ）］は、変換分散情報［４］＿Ｇ３と分散情報［１］＿Ｇ３とを引数として加算を行うものである。この結果として得られた分散情報［５］＿Ｇ３は秘密情報「５」の分散情報であり、当該秘密情報「５」はノード＃１からノード＃３を経由したノード＃５までの通信パスの距離である（図４参照）。
［５］＿Ｇ５＝ＴＲＡＮＳＦＥＲ（Ｇ３，Ｇ５，［５］＿Ｇ３）。これにより、秘密情報「５」が変換分散情報［５］＿Ｇ５として局所ノード群Ｇ５へ伝達される。
【００５９】
局所ノード群Ｇ４は以下の動作を行う。
［２］＿Ｇ４＝ＳＨＡＲＥ（Ｇ４，２）。ここで、秘密情報「２」はノード＃４からノード＃５までの通信パスの距離である（図４参照）。
［４］＿Ｇ４＝ＣＯＭＰＵＴＥ（Ｇ４，＋，［２］＿Ｇ４，［２］＿Ｇ４）。ここで、所定の関数［ｙ＝ｆ（ｘ）］は、変換分散情報［２］＿Ｇ４と分散情報［２］＿Ｇ４とを引数として加算を行うものである。この結果として得られた分散情報［４］＿Ｇ４は秘密情報「４」の分散情報であり、当該秘密情報「４」はノード＃１からノード＃４を経由したノード＃５までの通信パスの距離である（図４参照）。
［４］＿Ｇ５＝ＴＲＡＮＳＦＥＲ（Ｇ４，Ｇ５，［４］＿Ｇ４）。これにより、秘密情報「４」が変換分散情報［４］＿Ｇ５として局所ノード群Ｇ５へ伝達される。
【００６０】
局所ノード群Ｇ５は以下の動作を行う。
［＃４］＿Ｇ５＝ＣＯＭＰＵＴＥ（Ｇ５，ａｒｇｍｉｎ，［５］＿Ｇ５，［４］＿Ｇ５）。ここで、所定の関数［ｙ＝ｆ（ｘ）］は、変換分散情報［５］＿Ｇ５と変換分散情報［４］＿Ｇ５とを引数として、最短の距離である方の隣接ノード（次ホップ）のＩＤを求めるものである。この結果として得られた分散情報［＃４］＿Ｇ５は秘密情報「＃４」の分散情報であり、当該秘密情報「＃４」はノード＃４のＩＤである。
＃４＝ＲＥＣＯＶＥＲ（Ｇ５，［＃４］＿Ｇ５）。これにより、秘密情報「＃４」が復元される。秘密情報「＃４」は、ノード＃５において、宛先ノード＃１に対応する次ホップのＩＤである。これにより、ノード＃５において、宛先ノード＃１に対応する次ホップがノード＃４であるという、次ホップ情報が得られる。この次ホップ情報はノード＃５へ出力される。
【００６１】
本実施例において、秘密情報および途中の計算結果は全て分散された状態で保持されるため、各ノードの秘密情報は他のノードに対して秘匿される。
【００６２】
上述したように本実施形態によれば、任意の分散ルーティングを、ＳＭＣの要件を満たしながら実行することができる。これにより、フルメッシュに通信リンクが存在しない通信ネットワークを対象にした分散ルーティング処理において、ノードｉの秘密情報をノードｉの管理者以外の者に秘匿することができるという効果が得られる。又、任意の分散ルーティングに適用できるので、適用範囲が広い。
【００６３】
以上、本発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【００６４】
なお、本発明に適用可能な通信ネットワークとしては、物理ノードと物理通信リンクから成る物理ネットワークであってもよく、又は、peer-to-peer技術もしくはオーバーレイネットワーク技術もしくは計算機仮想化技術等を用いて作られた論理ノードと論理通信リンクから成る論理ネットワークであってもよい。
【００６５】
例えば、peer-to-peerネットワークや、仮想化された計算機から構成される仮想化されたネットワークのような、管理者が複数存在し、各ノードは異なる管理者に属する場合があり、したがって各ノードの管理者と、ノードに格納される分散ルーティング中の情報の所有者とが必ずしも一致しない環境において、各ノードの秘密情報を開示せずに分散ルーティングを実行することができる。
【００６６】
また、図３に示す各ステップを実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、分散ルーティング処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものであってもよい。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＤＶＤ（Digital Versatile Disk）等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【００６７】
さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Dynamic Random Access Memory））のように、一定時間プログラムを保持しているものも含むものとする。
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【符号の説明】
【００６８】
１…分散ルーティング処理装置、１１…入力部、１２…出力部、１３…秘密分散部、１４…秘密分散復元部、１５…分散情報格納部、１６…ＳＭＣ部、１７…分散情報変換部、１８…変換分散情報交換部
【特許請求の範囲】
【請求項１】
複数のノードから構成される通信ネットワークであって、前記複数のノードは複数の局所ノード群に分類され、一の前記局所ノード群は一管理者に属するノードの数が閾値秘密分散法における所定の閾値未満であり、一の前記局所ノード群内の全てのノード間には通信路が存在し、２つの前記局所ノード群間に通信路が存在する場合に当該２つの局所ノード群をお互いに隣接する局所ノード群であると定義した、前記通信ネットワークにおいて、ノードごとに設けられ、局所トポロジー情報から次ホップ情報を求める分散ルーティング処理装置であり、
自分散ルーティング処理装置が設けられているノード（自ノード）からの局所トポロジー情報を入力する入力部と、
前記入力された局所トポロジー情報を用いて前記閾値による閾値秘密分散法により前記閾値以上の個数の分散情報を生成する秘密分散部と、
自ノードが属する局所ノード群内のノード間で、前記閾値以上の個数の分散情報を分散して保持する分散情報格納部と、
前記閾値以上の個数の第１の分散情報を、「前記第１の分散情報とは異なり、且つ、前記閾値以上の個数の第２の分散情報（変換分散情報）であって前記閾値以上の個数の変換分散情報を用いて前記第１の分散情報の元の情報を復元することができる変換分散情報」を構成する要素（変換分散情報構成要素）に変換する分散情報変換部と、
自ノードが属する局所ノード群に隣接する局所ノード群との間で変換分散情報構成要素を交換して変換分散情報を生成する変換分散情報交換部と、
自ノードが属する局所ノード群内の各ノードの分散ルーティング処理装置と連携して、局所トポロジー情報の分散情報から次ホップ情報の分散情報を求めるために必要な所定の関数を分散して計算するＳＭＣ（Secure Multi-party computation）を解決するＳＭＣ部と、
自ノードが属する局所ノード群内の各ノードの分散ルーティング処理装置と連携して、次ホップ情報の前記閾値以上の個数の分散情報から次ホップ情報を復元する秘密分散復元部と、
前記復元された次ホップ情報を自ノードへ出力する出力部と、
を備えたことを特徴とする分散ルーティング処理装置。
【請求項２】
複数のノードから構成される通信ネットワークであって、前記複数のノードは複数の局所ノード群に分類され、一の前記局所ノード群は一管理者に属するノードの数が閾値秘密分散法における所定の閾値未満であり、一の前記局所ノード群内の全てのノード間には通信路が存在し、２つの前記局所ノード群間に通信路が存在する場合に当該２つの局所ノード群をお互いに隣接する局所ノード群であると定義した、前記通信ネットワークにおいて、ノードごとに、局所トポロジー情報から次ホップ情報を求める分散ルーティング処理を行うためのコンピュータプログラムであって、
自分散ルーティング処理装置が設けられているノード（自ノード）からの局所トポロジー情報を入力する入力ステップと、
前記入力された局所トポロジー情報を用いて前記閾値による閾値秘密分散法により前記閾値以上の個数の分散情報を生成する秘密分散ステップと、
自ノードが属する局所ノード群内のノード間で、前記閾値以上の個数の分散情報を分散して保持する分散情報格納ステップと、
前記閾値以上の個数の第１の分散情報を、「前記第１の分散情報とは異なり、且つ、前記閾値以上の個数の第２の分散情報（変換分散情報）であって前記閾値以上の個数の変換分散情報を用いて前記第１の分散情報の元の情報を復元することができる変換分散情報」を構成する要素（変換分散情報構成要素）に変換する分散情報変換ステップと、
自ノードが属する局所ノード群に隣接する局所ノード群との間で変換分散情報構成要素を交換して変換分散情報を生成する変換分散情報交換ステップと、
自ノードが属する局所ノード群内の各ノードの分散ルーティング処理装置と連携して、局所トポロジー情報の分散情報から次ホップ情報の分散情報を求めるために必要な所定の関数を分散して計算するＳＭＣ（Secure Multi-party computation）を解決するＳＭＣステップと、
自ノードが属する局所ノード群内の各ノードの分散ルーティング処理装置と連携して、次ホップ情報の前記閾値以上の個数の分散情報から次ホップ情報を復元する秘密分散復元ステップと、
前記復元された次ホップ情報を自ノードへ出力する出力ステップと、
をコンピュータに実行させるためのコンピュータプログラム。
【請求項１】
複数のノードから構成される通信ネットワークであって、前記複数のノードは複数の局所ノード群に分類され、一の前記局所ノード群は一管理者に属するノードの数が閾値秘密分散法における所定の閾値未満であり、一の前記局所ノード群内の全てのノード間には通信路が存在し、２つの前記局所ノード群間に通信路が存在する場合に当該２つの局所ノード群をお互いに隣接する局所ノード群であると定義した、前記通信ネットワークにおいて、ノードごとに設けられ、局所トポロジー情報から次ホップ情報を求める分散ルーティング処理装置であり、
自分散ルーティング処理装置が設けられているノード（自ノード）からの局所トポロジー情報を入力する入力部と、
前記入力された局所トポロジー情報を用いて前記閾値による閾値秘密分散法により前記閾値以上の個数の分散情報を生成する秘密分散部と、
自ノードが属する局所ノード群内のノード間で、前記閾値以上の個数の分散情報を分散して保持する分散情報格納部と、
前記閾値以上の個数の第１の分散情報を、「前記第１の分散情報とは異なり、且つ、前記閾値以上の個数の第２の分散情報（変換分散情報）であって前記閾値以上の個数の変換分散情報を用いて前記第１の分散情報の元の情報を復元することができる変換分散情報」を構成する要素（変換分散情報構成要素）に変換する分散情報変換部と、
自ノードが属する局所ノード群に隣接する局所ノード群との間で変換分散情報構成要素を交換して変換分散情報を生成する変換分散情報交換部と、
自ノードが属する局所ノード群内の各ノードの分散ルーティング処理装置と連携して、局所トポロジー情報の分散情報から次ホップ情報の分散情報を求めるために必要な所定の関数を分散して計算するＳＭＣ（Secure Multi-party computation）を解決するＳＭＣ部と、
自ノードが属する局所ノード群内の各ノードの分散ルーティング処理装置と連携して、次ホップ情報の前記閾値以上の個数の分散情報から次ホップ情報を復元する秘密分散復元部と、
前記復元された次ホップ情報を自ノードへ出力する出力部と、
を備えたことを特徴とする分散ルーティング処理装置。
【請求項２】
複数のノードから構成される通信ネットワークであって、前記複数のノードは複数の局所ノード群に分類され、一の前記局所ノード群は一管理者に属するノードの数が閾値秘密分散法における所定の閾値未満であり、一の前記局所ノード群内の全てのノード間には通信路が存在し、２つの前記局所ノード群間に通信路が存在する場合に当該２つの局所ノード群をお互いに隣接する局所ノード群であると定義した、前記通信ネットワークにおいて、ノードごとに、局所トポロジー情報から次ホップ情報を求める分散ルーティング処理を行うためのコンピュータプログラムであって、
自分散ルーティング処理装置が設けられているノード（自ノード）からの局所トポロジー情報を入力する入力ステップと、
前記入力された局所トポロジー情報を用いて前記閾値による閾値秘密分散法により前記閾値以上の個数の分散情報を生成する秘密分散ステップと、
自ノードが属する局所ノード群内のノード間で、前記閾値以上の個数の分散情報を分散して保持する分散情報格納ステップと、
前記閾値以上の個数の第１の分散情報を、「前記第１の分散情報とは異なり、且つ、前記閾値以上の個数の第２の分散情報（変換分散情報）であって前記閾値以上の個数の変換分散情報を用いて前記第１の分散情報の元の情報を復元することができる変換分散情報」を構成する要素（変換分散情報構成要素）に変換する分散情報変換ステップと、
自ノードが属する局所ノード群に隣接する局所ノード群との間で変換分散情報構成要素を交換して変換分散情報を生成する変換分散情報交換ステップと、
自ノードが属する局所ノード群内の各ノードの分散ルーティング処理装置と連携して、局所トポロジー情報の分散情報から次ホップ情報の分散情報を求めるために必要な所定の関数を分散して計算するＳＭＣ（Secure Multi-party computation）を解決するＳＭＣステップと、
自ノードが属する局所ノード群内の各ノードの分散ルーティング処理装置と連携して、次ホップ情報の前記閾値以上の個数の分散情報から次ホップ情報を復元する秘密分散復元ステップと、
前記復元された次ホップ情報を自ノードへ出力する出力ステップと、
をコンピュータに実行させるためのコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１２−２１６９０４（Ｐ２０１２−２１６９０４Ａ）
【公開日】平成２４年１１月８日（２０１２．１１．８）
【国際特許分類】
【出願番号】特願２０１１−７９０２３（Ｐ２０１１−７９０２３）
【出願日】平成２３年３月３１日（２０１１．３．３１）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【出願人】（５０４１３７９１２）国立大学法人 東京大学 (1,942)
【Ｆターム（参考）】
【公開日】平成２４年１１月８日（２０１２．１１．８）
【国際特許分類】
【出願日】平成２３年３月３１日（２０１１．３．３１）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【出願人】（５０４１３７９１２）国立大学法人 東京大学 (1,942)
【Ｆターム（参考）】
[ Back to top ]