分散計算処理システム及び分散計算処理方法
【課題】従来の分散計算処理においては、処理効率が悪く汎用的な処理対象プログラムに適用することが容易ではなかった。
【解決手段】中継ノード40a,40b,40cを含むネットワーク50を介して利用者ノード10,20と計算ノード30a,30b,30c,30dとがそれぞれ接続され、利用者ノード10,20から入力された入力値d1,d2を用いて、計算ノード30a,30b,30c,30dに処理対象プログラムの分散計算処理を行わせる。これにおいて、利用者ノード10は処理対象プログラムを3つの部分論理回路に分割して送信する。中継ノード40a,40b,40cは匿名通信及びランダム通信により部分論理回路を計算ノードに所在を秘匿して配置する。利用者ノード10,20は入力値d1,d2を計算ノード30aに配送し、部分論理回路が分散配置された計算ノード30a,30b,30dは協働して計算処理を実行する。
【解決手段】中継ノード40a,40b,40cを含むネットワーク50を介して利用者ノード10,20と計算ノード30a,30b,30c,30dとがそれぞれ接続され、利用者ノード10,20から入力された入力値d1,d2を用いて、計算ノード30a,30b,30c,30dに処理対象プログラムの分散計算処理を行わせる。これにおいて、利用者ノード10は処理対象プログラムを3つの部分論理回路に分割して送信する。中継ノード40a,40b,40cは匿名通信及びランダム通信により部分論理回路を計算ノードに所在を秘匿して配置する。利用者ノード10,20は入力値d1,d2を計算ノード30aに配送し、部分論理回路が分散配置された計算ノード30a,30b,30dは協働して計算処理を実行する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、ネットワークを介して接続された複数の計算ノードに一つの処理対象プログラムを計算処理させる分散計算処理技術に関する。
【背景技術】
【0002】
ネットワーク上に分散した複数の情報処理装置が、協働して一つの関数の計算処理を行う分散計算処理技術が知られている。この分散計算処理技術においては、各情報処理装置のセキュリティの観点から、またユーザのプライバシーの観点から、入力情報を秘密にしたままで計算処理を行いたいという要望があり、様々な研究や技術的試みが行われてきた。例えば、計算すべき関数を論理回路として表すことができる場合、秘匿性のある分散計算処理(秘密分散計算処理)についての情報処理装置間の通信プロトコルを規定して実現する方法が知られている(例えば、非特許文献1参照)。また、電子投票システム等の特定のケースを対象としたものについては、情報処理装置の秘匿性を保ちながら効率よく計算する方法が知られている(例えば、非特許文献2参照)。
【先行技術文献】
【非特許文献】
【0003】
【非特許文献1】Foundations of Cryptography Volume II Basic Applications,Cambridge University Press,May 10,2004.
【非特許文献2】岡本龍明、山本博資著、「シリーズ/情報科学の数学 現代暗号」、産業図書、1997年
【発明の概要】
【発明が解決しようとする課題】
【0004】
しかしながら、一般的なプログラムを論理回路として表し、非特許文献1に記載された技術を用いて秘密分散計算処理を行うと処理効率が悪く実用的ではない。ここで、非特許文献1記載の秘密分散計算処理の方法について、関係する部分の概略を説明する。この秘密分散計算処理では、実行すべきプログラムを論理回路に変換したものを、主に暗号理論分野において知られているGarbled Circuit(GC)に変換して用いる。このGCは、例えば論理ゲートレベルで内部ロジックを秘匿したまま論理演算を行うものであり、GCの入出力は乱数のキーとして表される。GCでは、正しい入力キーを有する者だけが、そのキーに対応付けられた入力値の論理演算の結果に対応する出力キーを得ることができる。
【0005】
このようにして、非特許文献1記載の秘密分散計算処理方法では、論理回路の構成に応じたGCの組み合わせによって論理回路全体の秘匿性を保つことはできるが、論理回路の各論理ゲートの論理値が分からない状態で計算を行うため、途中の計算結果の状態に応じて選択的な処理(すなわち、通常のプログラムにおける条件分岐処理)を簡単に行うことができない。これを実現するためには、GC化される論理回路は、条件分岐処理に係る回路を、想定される全ての条件についての分岐処理を実行させるように構成しなければならず、プログラムによってはリソースが多く必要になり処理効率が悪くなるおそれが大きい。
【0006】
また、非特許文献2に記載されたような特定の問題に特化した方法では、問題ごとに暗号理論の専門家によるプロトコル設計がされなければならず、汎用的なプログラムには適用できない。
【0007】
そこで、本発明は上記問題に鑑みてなされたものであり、相互に秘匿性を保ちながら処理対象プログラムの分散計算処理を実行させる場合に、処理効率に優れ且つ汎用的な処理対象プログラムに適用することが容易な、分散計算処理システム及び分散計算処理方法を提供することを目的とする。
【課題を解決するための手段】
【0008】
本発明は、上記の課題を解決するために、以下[1],[2]の手段を提供するものである。
[1] 複数の中継ノードを含むネットワークに利用者ノードが接続され、前記利用者ノードに入力された入力情報を用いて処理対象プログラムの分散計算処理を行う分散計算処理システムにおいて、
前記ネットワークには、複数の計算ノードが接続され、
前記利用者ノードは、
前記処理対象プログラムを論理回路に変換して複数の部分論理回路に分割する論理回路分割手段と、
前記分割された部分論理回路をデータフィールドに格納するとともに、利用者ノードアドレス情報を送信元アドレスフィールドに格納したパケットを送信する部分論理回路送信手段と、
前記複数の中継ノードのうちいずれかの中継ノードから送信されたパケットを受信し、それの送信元アドレスフィールドに格納された暗号化計算ノードアドレス情報を取り出して記憶する計算ノードアドレス情報記憶手段と、
前記入力情報をデータフィールドに格納し、前記記憶された暗号化計算ノードアドレス情報を宛先アドレスフィールドに格納したパケットを送信する入力情報送信手段と、
を備え、
前記複数の中継ノードそれぞれは、
到来したパケットを受信して、それの宛先アドレスフィールドの指定のない場合は、送信元アドレスフィールドに格納された所定の送信元アドレス情報を暗号化して前記パケットを更新し、所定の確率に基づいて他の中継ノード及び前記複数の計算ノードのうちいずれか一のノードを選択して、前記更新されたパケットを送信する匿名ランダム中継手段と、
到来したパケットを受信して、それの宛先アドレスフィールドに所定の暗号化宛先アドレス情報が格納されている場合は、その所定の暗号化宛先アドレス情報を復号し、さらに送信元アドレスフィールドに所定の送信元アドレス情報が格納されている場合にはその所定の送信元アドレス情報を暗号化して前記パケットを更新し送信する匿名中継手段と、
を備え、
前記複数の計算ノードそれぞれは、
前記複数の中継ノードのうちいずれかの中継ノードの匿名ランダム中継手段から送信されたパケットを受信し、それのデータフィールドに格納された部分論理回路を取り出して記憶する部分論理回路記憶手段と、
該計算ノードの計算ノードアドレス情報を送信元アドレスフィールドに格納するとともに、前記部分論理回路記憶手段において受信したパケットの送信元アドレスフィールドに格納された暗号化利用者ノードアドレス情報を宛先アドレスフィールドに格納したパケットを送信する応答送信手段と、
前記複数の中継ノードのうちいずれかの中継ノードの匿名中継手段から送信されたパケットを受信し、それのデータフィールドに格納された入力情報を取り出して、前記記憶された部分論理回路に入力して計算する計算処理手段と、
を備えたことを特徴とする分散計算処理システム。
[2] 複数の中継ノードを含むネットワークを介して利用者ノードと複数の計算ノードとが接続され、前記利用者ノードに入力された入力情報を用いて前記複数の計算ノードに処理対象プログラムの分散計算処理を行わせる分散計算処理方法であって、
前記利用者ノードが、
前記処理対象プログラムを論理回路に変換して複数の部分論理回路に分割する論理回路分割ステップと、
前記分割された部分論理回路をデータフィールドに格納するとともに、利用者ノードアドレス情報を送信元アドレスフィールドに格納した部分論理回路パケットを送信する部分論理回路送信ステップと、
前記複数の中継ノードのうちいずれかが、
前記送信された部分論理回路パケットを受信し、それの送信元アドレスフィールドに格納された利用者ノードアドレス情報を暗号化して前記部分論理回路パケットを更新し、所定の確率に基づいて他の中継ノード及び前記複数の計算ノードのうちいずれか一のノードを選択して、前記更新された部分論理回路パケットを送信する匿名ランダム中継ステップと、
前記複数の計算ノードのうち、部分論理回路パケットの到来した計算ノードが、
前記部分論理回路パケットを受信し、それのデータフィールドに格納された部分論理回路を取り出して記憶する部分論理回路記憶ステップと、
前記計算ノードの計算ノードアドレス情報を送信元アドレスフィールドに格納するとともに、前記部分論理回路記憶ステップにおいて受信した部分論理回路パケットの送信元アドレスフィールドに格納された暗号化利用者ノードアドレス情報を宛先アドレスフィールドに格納した応答パケットを送信する応答送信ステップと、
前記複数の中継ノードのうち前記送信された応答パケットの到来した中継ノードが、
前記応答パケットを受信し、それの宛先アドレスフィールドに格納された暗号化利用者ノードアドレス情報を復号できた場合に、送信元アドレスフィールドに格納された計算ノードアドレス情報を暗号化して前記応答パケットを更新し送信する応答中継ステップと、
前記利用者ノードが、
前記複数の中継ノードのうちいずれかの中継ノードから送信された応答パケットを受信し、それの送信元アドレスフィールドに格納された暗号化計算ノードアドレス情報を取り出して記憶する計算ノードアドレス情報記憶ステップと、
前記入力情報をデータフィールドに格納し、前記記憶された暗号化計算ノードアドレス情報を宛先アドレスフィールドに格納したデータパケットを送信する入力情報送信ステップと、
前記複数の中継ノードのうち前記送信されたデータパケットの到来した中継ノードが、
前記データパケットを受信し、それの宛先アドレスフィールドに格納された暗号化計算ノードアドレス情報を復号できた場合に、前記データパケットを更新して送信するデータ中継ステップと、
前記送信されたデータパケットを受信した計算ノードが、
それのデータフィールドに格納された入力情報を取り出して、前記記憶された部分論理回路に入力して計算する計算処理ステップと、
を有したことを特徴とする分散計算処理方法。
【発明の効果】
【0009】
本発明によれば、部分論理回路の配置場所を秘匿する一方、部分論理回路自体やこれに入力される入力情報が暗号化されない状態で分散計算処理が実行されるため、処置途中段階での選択的な処理や条件分岐処理を容易に実行することができる。さらに、本発明によれば、汎用的な処理対象プログラムに適用することが容易となる。
【図面の簡単な説明】
【0010】
【図1】本発明の実施形態である分散計算処理システムの概略の構成図である。
【図2】分散計算処理システムが秘密分散計算処理を実行する対象である処理対象プログラムの概略のフローチャートである。
【図3】分散計算処理システムが実行する秘密分散計算処理の第1フェーズの動作のうち、部分論理回路を配送する動作を説明するためのシーケンス図である。
【図4】分散計算処理システムが実行する秘密分散計算処理の第1フェーズの動作のうち、部分論理回路を配送する動作を説明するためのシーケンス図である。
【図5】分散計算処理システムが実行する秘密分散計算処理の第1フェーズの動作のうち、部分論理回路を配送する動作を説明するためのシーケンス図である。
【図6】分散計算処理システムが実行する秘密分散計算処理の第1フェーズの動作のうち、部分論理回路が取得しておくべき情報を配送する動作を説明するためのシーケンス図である。
【図7】分散計算処理システムが実行する秘密分散計算処理の第1フェーズの動作のうち、部分論理回路が取得しておくべき情報を配送する動作を説明するためのシーケンス図である。
【図8】分散計算処理システムが実行する秘密分散計算処理の第1フェーズの動作のうち、部分論理回路が取得しておくべき情報を配送する動作を説明するためのシーケンス図である。
【図9】分散計算処理システムが実行する秘密分散計算処理の第1フェーズの動作のうち、部分論理回路が取得しておくべき情報を配送する動作を説明するためのシーケンス図である。
【図10】分散計算処理システムが実行する秘密分散計算処理の第2フェーズの動作を説明するためのシーケンス図である。
【図11】分散計算処理システムが実行する秘密分散計算処理の第2フェーズの動作を説明するためのシーケンス図である。
【図12】分散計算処理システムが実行する秘密分散計算処理の第2フェーズの動作を説明するためのシーケンス図である。
【発明を実施するための形態】
【0011】
以下、本発明を実施するための形態について、図面を参照して詳細に説明する。本実施形態では、計算処理の対象となる処理対象プログラムを、2人の利用者がそれぞれ使用する2台の電子計算機から入力された秘密情報である入力値を引数として、これら入力値の秘密性を確保して分散計算処理(秘密分散計算処理)を実行する分散計算処理システムについて説明する。
【0012】
図1に、本実施形態である分散計算処理システムの概略の構成図を示す。同図において、分散計算処理システム1は、9台のノードを接続したネットワーク50により構成されており、処理対象プログラムf(a,b)(a,bは引数)を計算するものである。ノードとは、ネットワーク50に接続される電子計算機、ルータ、サーバ等の情報処理装置のことをいい、ノード間での通信を行うことができる。ネットワーク50に接続された9台のノードの内訳は、利用者P1及びP2によってそれぞれ使用され、処理対象プログラムf(a,b)に対する入力値が入力されるとともに、秘密分散計算処理により得られた結果が得られる利用者ノード10,20と、秘密分散計算処理を行う分散計算処理装置である計算ノード30a,30b,30c,30dと、ノードを中継接続する中継ノード40a,40b,40cとである。
【0013】
利用者P1が使用する利用者ノード10と、利用者P2が使用する利用者ノード20とは、コンピュータ等の電子計算機を用いることができる。利用者ノード10,20それぞれは、不図示ではあるが、処理対象プログラムを論理回路に変換して複数の部分論理回路に分割するための論理回路分割部と、部分論理回路を該利用者ノードのアドレス情報である利用者ノードアドレス情報とともに部分論理回路パケットとして送信するための部分論理回路送信部と、中継ノード40a,40b,40cのうちいずれかから送信された応答パケットを受信し、暗号化された計算ノードのアドレス情報(暗号化計算ノードアドレス情報)を取り出して記憶するための計算ノードアドレス情報記憶部と、入力情報d1,d2を暗号化計算ノードアドレス情報とともにデータパケットとして送信するための入力情報送信部とを備えている。利用者ノード10には、利用者P1によって秘密情報である入力値a=d1が入力され、利用者ノード20には、利用者P2によって秘密情報である入力値b=d2が入力されるものとする。なお、入力値d1及びd2の合計ビット数はkビットであるとする。また、利用者ノード10,20は互いのアドレス情報を知っており、両者間での通信を行うことができる。
【0014】
n=4台の計算ノード30a,30b,30c,30dのそれぞれも、コンピュータ等の電子計算機を用いることができる。計算ノード30a,30b,30c,30dそれぞれは、不図示ではあるが、中継ノード40a,40b,40cのうちいずれかの中継ノードから送信された部分論理回路パケットを受信し、部分論理回路を取り出して記憶するための部分論理回路記憶部と、その計算ノードの計算ノードアドレス情報と部分論理回路パケットを受信した際の送信元アドレスである暗号化利用者ノードアドレス情報とを含めた応答パケットを送信するための応答送信部と、中継ノード40a,40b,40cのうちいずれかの中継ノードから送信されたデータパケットを受信し、入力情報を取り出して部分論理回路記憶部に記憶された部分論理回路に入力して計算するための計算処理部とを備えている。
【0015】
中継ノード40a,40b,40cはルータを用いることができる。これら中継ノード40a,40b,40cは、それぞれ秘密鍵Ka,Kb,Kcを有している。そして、各中継ノード40a,40b,40cは、中継元から入力されたデータを、自身の秘密鍵Ka,Kb,Kcで暗号化したり、入力された暗号化データを秘密鍵Ka,Kb,Kcで復号したりして中継先に出力することができる。中継ノード40a,40b,40cそれぞれは、不図示ではあるが、到来したパケットを受信して、それに宛先アドレスの指定のない場合は、所定の送信元アドレス情報を自身の秘密鍵で暗号化して該パケットを更新し、例えば後述するランダムウォーク方式に基づいて他の中継ノード及び計算ノード30a,30b,30c,30dのうちいずれか一のノードを選択し、更新されたパケットを送信するための匿名ランダム中継部と、到来したパケットを受信して、所定の暗号化宛先アドレス情報が格納されている場合は、それを自身の秘密鍵で復号し、さらに所定の送信元アドレス情報が格納されている場合にはその所定の送信元アドレス情報を自身の秘密鍵で暗号化して該パケットを更新し送信するための匿名中継部とを備えている。匿名ランダム中継部及び匿名中継部の動作については、後に詳細を説明する。
【0016】
中継ノード40a,40b,40cを含むネットワーク50では、盗聴者から送信者と受信者との対応関係を隠すために、暗号化されたアドレス(ネットワーク層のアドレスであり、例えばIPアドレス)で指定される匿名の宛先に対してパケットを送信する匿名通信を行うことができる。また、ネットワーク50では、送信元がどこを送信先としてパケットが送信されたかを不明にさせるために、無作為に選択した宛先に対してパケットを送信するランダム通信を行うことができる。
【0017】
ここで、中継ノード40a,40b,40cを含むネットワーク50で行われる匿名通信の方法について、図1における中継ノード40aから中継ノード40bを中継して計算ノード30aにパケットを送信する場合を例として説明する。中継ノード40aは、入来したパケットに含まれる送信元の始点アドレスを中継ノード40aの秘密鍵Kaで暗号化し、その暗号化始点アドレスで元の始点アドレスを置き換えたパケットを中継ノード40bに送信する。そして、中継ノード40bは、受信したパケットに含まれる暗号化始点アドレスを中継ノード40bの秘密鍵Kbでさらに暗号化し、その2重に暗号化した2重暗号化始点アドレスで元の暗号化始点アドレスを置き換えたパケットを計算ノード30aに送信する。このようにすることにより、中継ノード40aと計算ノード30aとの間の通信を盗聴しても、元の始点アドレスを知ることができない。
【0018】
ただし、上記の方法では、中継ノード40a自身の内部メモリ等の記憶部がスキャニングされた場合には送信元の始点アドレスが知られてしまうことになる。そこで、複数の中継ノードを複数段入れ子に接続する構成をとることでこれを防ぐことができる。このように構成した場合、経路上の全ての中継ノードが盗聴されない限りは宛先アドレスを知られることなないため匿名性は高いものとなる。
【0019】
このように、匿名通信機能によれば、受信者は送信者を知ることができなくなる。しかし、送信者は予め受信者を知っていなければならないことになる。そこで、送信者が受信者を不明なものとするためにランダム通信を用いてパケットを送信するようにする。
【0020】
次に、ランダム通信機能について説明する。本実施形態において、中継ノード40a,40b,40cを含むネットワーク50で行われるランダム通信では、パケットの到着する宛先は、送信者が指定するのではなく、宛先の候補(例えば、自中継ノードが中継ノード40aである場合は、中継ノード40b,40c、及び計算ノード30a,30b,30c,30d)の中から無作為に決定される。このようなパケットの配送を実現する方式としてグラフ上のランダムウォークが公知である。このランダムウォーク方式では、j(jは2以上の整数)個の隣接ノードを有するルータは、次の転送先を隣接ノードの中から1/jずつの確率で選択する。パケットが宛先候補のノードの集合のいずれかに到達した時点で配送は完了する。このようなランダムウォーク方式の特性については様々な解析が行われている。例えば、以下の文献ではインターネットのようなスケールフリー特性を有するネットワーク上におけるランダムウォークについての解析結果がまとめられている。
【0021】
Noh,J.D.and Rieger,H.,Random Walks on Complex Networks,Physical Review Letters,vol.92,page 118701,2004.
【0022】
また、様々な統計的な特性を有したランダムウォーク方式の派生モデルも公表されており、これらを利用することで所望の特性を有した無作為なパケットの配送を実現できる。例えば、以下の文献には、ランダムウォークを拡張することにより、宛先までの到達時間を短縮する方法が述べられている。
【0023】
S.Ikeda,I.kubo,and M.Yamashita,Reducing the Hitting and the Cover Times of Ramdom Walks on Finite Graphs by Local Topological Information,Proceedings of the 2003 International Conference on VLSI,pp.203−207,2003.
【0024】
本実施形態においては、上述した公知のランダムウォーク方式を適用して宛先を確率的に選択してランダム通信を行う。よって、匿名通信機能及びランダム通信機能を併せ用いた通信を行うことにより、送信元は受信先を知らず、且つ受信先も送信元を知らないこと、及び送信されたパケットがどこに配送されたかを不明なものとすることが実現できる。そして、これにより、入力情報を暗号化することなくその秘匿性を保つことができるため、本実施形態では、途中の計算結果に応じた選択的な処理を実行させることを可能にするものである。
【0025】
次に、本実施形態である分散計算処理システムにおける秘密分散計算処理について説明する。この秘密分散計算処理は2つのフェーズから成り立つものである。第1フェーズでは、任意の利用者ノードが処理対象プログラムを論理回路に変換して複数の部分論理回路に分割し、これらの部分論理回路を匿名通信機能及びランダム通信機能を用いて計算ノードに配送する。第2フェーズでは、各利用者ノードは、入力値を暗号化することなく計算ノードに送信し、これらを受信した計算ノードは協働して計算を行い、最終的な出力値を各利用者ノードに送信する。その協働した計算の際には、各計算ノードの入出力値は暗号化されない状態でやり取りされる。以下、各フェーズについて詳細に説明する。
【0026】
[第1フェーズの動作説明]
一般的に、論理回路は、ノード及びエッジを含んで構成される有向グラフとみなすことができため、エッジを介して連結されたノードを含むような関係を有した部分論理回路に分割することができる。図2に、分散計算処理システム1が秘密分散計算処理を実行する対象である処理対象プログラムf(a,b)の概略のフローチャートを示す。同図は、処理対象プログラムf(a,b)が3つの部分論理回路G,H,Iに分割された様子を示している。すなわち、部分論理回路Gでは、入力値a,bに基づき所定の計算を実行し、その結果に対し所定の条件に基づいてTRUE(真)であった場合は、部分論理回路Hの処理に移行する一方、FALSE(偽)であった場合は、部分論理回路Iの処理に移行する。部分論理回路Hでの処理の後は、条件分岐に戻る。また、部分論理回路Iでの処理によって最終的な結果が得られる。このように、本実施形態における処理対象プログラムf(a,b)には条件分岐処理が含まれているものとする。
【0027】
図3−図9に、分散計算処理システム1が実行する秘密分散計算処理の第1フェーズの動作を表したシーケンス図を示し、これらを併せ参照して分散計算処理システム1の第1フェーズの動作を説明する。なお、利用者ノード10,20の各アドレスをA,B、中継ノード40a,40b,40cの各アドレスをR1,R2,R3、計算ノード30a,30b,30c,30dの各アドレスをC1,C2,C3,C4として説明する。
【0028】
図3において、第1フェーズでは、まず任意の利用者ノード、例えば利用者P1が使用する利用者ノード10が、処理対象プログラムf(a,b)を3つの部分論理回路G,H,Iに分割する(S301)。3つの部分論理回路G,H,Iは、均等な大きさになるように分割され、部分論理回路G,H,Iの各入力値はsビットであるとする。
【0029】
次に、利用者ノード10は、これらの部分論理回路G,H,Iを計算ノードに配送する。まず、利用者ノード10は、部分論理回路Gを計算ノードに配送するが、ここでは、ランダム通信機能によって、中継ノード40a→中継ノード40bの経路を辿って計算ノード30aに配送されるものとして説明する。
【0030】
部分論理回路Gを計算ノード30aに配送する場合には、以下の3つの条件を満たす必要がある。
(1)利用者ノード10(利用者P1)は、どこが配送先であるかを知ってはならない。
(2)配送先である計算ノード30aは、どこが配送元であるかを知ってはならない。
(3)中継ノード40a,40bは、配送元及び配送先の両方を知ってはならない(但し、いずれか一方を知ることに問題はない。)
【0031】
上記(1)−(3)の条件を満たすために、利用者ノード10は、以下の手順にしたがって部分論理回路Gを配送する。まず、利用者ノード10は、送信元アドレスフィールドに自身の利用者ノードアドレス情報であるアドレスAを格納し、データフィールドに部分論理回路Gを格納した部分論理回路パケットを生成する。そして、利用者ノード10は、その部分論理回路パケットを隣接する中継ノード40aに送信する(S302)。
【0032】
次に、中継ノード40aは、受信した部分論理回路パケットの送信元アドレスフィールドに格納されているアドレスAを取り出して秘密鍵Kaで暗号化し、そのアドレスAの暗号化アドレスであるEKa(A)で送信元アドレスフィールドを更新する(S303)。そして、中継ノード40aは、ランダム通信機能によって無作為に次の送信先ノードを決定し、更新された部分論理回路パケットを決定されたノードである中継ノード40bに送信する(S304)。
【0033】
ランダム通信により中継ノード40aから送信された部分論理回路パケットを受信した中継ノード40bは、上記のステップS303及びS304と同様の処理を実行する。具体的には、中継ノード40bは、受信した部分論理回路パケットの送信元アドレスフィールドに格納されている暗号化アドレスEKa(A)を取り出して秘密鍵Kbで暗号化し、暗号化アドレスEKa(A)をさらに暗号化した2重暗号化アドレスであるEKb(EKa(A))で送信元アドレスフィールドを更新する(S305)。そして、中継ノード40bは、ランダム通信機能によって無作為に次の送信先ノードを決定し、更新された部分論理回路パケットを決定されたノードである計算ノード30aに送信する(S306)。
【0034】
ランダム通信により中継ノード40bから送信された部分論理回路パケットを受信した計算ノード30aは、受信した部分論理回路パケットのデータフィールドに格納されている部分論理回路Gを部分論理回路記憶部に記憶する(S307)。
【0035】
以上によれば、計算ノード30aが受信した部分論理回路パケットの送信元アドレスフィールドに格納された利用者ノード10のアドレスAは、経路中の中継ノード40a,40bによってそれぞれ暗号化されているため、計算ノード30aは、利用者ノード10を配送元として特定することができない。また、中継ノード40a,40bによるランダム通信によって部分論理回路パケットが配送されているため、配送元である利用者ノード10は配送先の計算ノードを特定することができない。さらに、中継ノード40a,40bは、配送元である利用者ノード10と配送先である計算ノード30aとの両方を特定することができない。よって、利用者ノード10は、匿名性に関する前記3つの条件(1)−(3)を満たしながら、部分論理回路Gを計算ノード30aに配送することができる。
【0036】
次に、部分論理回路Gを取得した計算ノード30aは、利用者ノード10に対して受信確認の応答を返信する。この応答は、部分論理回路パケットの配送経路と同一の経路を逆向きに辿って利用者ノード10に配送される。具体的には、まず、計算ノード30aは、宛先アドレスフィールドに2重暗号化アドレス(暗号化利用者ノードアドレス情報)であるEKb(EKa(A))を格納し、送信元アドレスフィールドに自身の計算ノードアドレス情報であるアドレスC1を格納した応答パケットを生成する。そして、計算ノード30aは、その応答パケットを送信する(S308)。
【0037】
計算ノード30aから送信された応答パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した応答パケットの宛先アドレスフィールドに格納された2重暗号化アドレスEKb(EKa(A))を復号できるノードは、秘密鍵Kbを有している中継ノード40bのみであるので、中継ノード40bが応答パケットを正式に受信したものとなる。
【0038】
応答パケットを正式に受信した中継ノード40bは、応答パケットの宛先アドレスフィールドに格納されている2重暗号化アドレス(暗号化宛先アドレス情報)であるEKb(EKa(A))を取り出して秘密鍵Kbで復号し、その復号された暗号化アドレスEKa(A)で宛先アドレスフィールドを更新する。そして、送信元アドレスフィールドに格納されている送信元アドレス情報であるアドレスC1を取り出して秘密鍵Kbで暗号化し、そのアドレスC1の暗号化アドレス(暗号化計算ノードアドレス情報)であるEKb(C1)で送信元アドレスフィールドを更新する(S309)。
【0039】
次に、中継ノード40bは、その更新された応答パケットを送信する(S310)。中継ノード40bから送信された応答パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した応答パケットの宛先アドレスフィールドに格納された暗号化アドレスEKa(A)を復号できるノードは、秘密鍵Kaを有している中継ノード40aのみであるので、中継ノード40aが応答パケットを正式に受信したものとなる。
【0040】
応答パケットを正式に受信した中継ノード40aは、応答パケットの宛先アドレスフィールドに格納されている暗号化アドレスEKa(A)を取り出して秘密鍵Kaで復号し、その復号されたアドレスAで宛先アドレスフィールドを更新する。そして、送信元アドレスフィールドに格納されている暗号化アドレスEKb(C1)を取り出して秘密鍵Kaで暗号化し、その暗号化アドレスEKb(C1)の2重暗号化アドレスであるEKa(EKb(C1))で送信元アドレスフィールドを更新する(S311)。
【0041】
次に、中継ノード40aは、その更新された応答パケットを送信し、利用者ノード10はこれを受信する(S312)。そして、応答パケットを受信した利用者ノード10は、部分論理回路Gと、応答パケットの宛先アドレスフィールドに格納されている2重暗号化アドレス(暗号化計算ノードアドレス情報)であるEKa(EKb(C1))とを関連付けて計算ノードアドレス情報記憶部に記憶する(S313)。
【0042】
上述したステップS302−S313の処理と同様に、利用者ノード10は、部分論理回路H,Iを計算ノードに配送して確認応答を受信する。図4に、利用者ノード10が部分論理回路Hを計算ノードに配送する手順を表したシーケンス図を示し、図5に、利用者ノード10が部分論理回路Iを計算ノードに配送する手順を表したシーケンス図を示す。図4については、利用者ノード10が配送する部分論理回路Hは、ランダム通信機能によって中継ノード40a→中継ノード40bの経路を辿って計算ノード30bに配送された場合を例としたものである。また、図5については、利用者ノード10が配送する部分論理回路Iは、ランダム通信機能によって中継ノード40a→中継ノード40cの経路を辿って計算ノード30dに配送された場合を例としたものである。なお、図4及び図5のシーケンス図についての動作の説明は、図3のシーケンス図に基づく動作説明と同様であるため、ここではその詳細説明を省略する。
【0043】
図3−図5に示したシーケンス図に基づく動作により、利用者ノード10,20は、部分論理回路Gとこれの配送先アドレスが暗号化されたEKa(EKb(C1))との組み合わせ、部分論理回路Hとこれの配送先アドレスが暗号化されたEKa(EKb(C2))との組み合わせ、及び部分論理回路Iとこれの配送先アドレスが暗号化されたEKa(EKc(C4))との組み合わせを、それぞれの計算ノードアドレス情報記憶部に記憶させることとなる。すなわち、利用者ノード10,20は、全ての部分論理回路G,H,Iと、これらが配送された計算ノード30a,30b,30dの暗号化されたアドレスの対応関係を知る状態となる。
【0044】
ところで、図2に示した処理対象プログラムのフローチャートによれば、部分論理回路Gを実行した後は、条件に応じて部分論理回路H又は部分論理回路Iが実行されることになる。そのため、部分論理回路Gの配送先ノードである計算ノード30aは、部分論理回路H及び部分論理回路Iを実行する計算ノード30b,30dのアドレス、すなわち暗号化されたアドレスC2,C4を知っている必要がある。そこで、利用者ノード10は、EKa(EKb(C2))及びEKa(EKc(C4))を計算ノード30aに送信する。
【0045】
図6に、利用者ノード10が暗号化されたアドレスC2,C4を計算ノード30aに配送する手順を表したシーケンス図を示して具体的に説明する。同図において、利用者ノード10は、宛先アドレスフィールドに暗号化されたアドレスであるEKa(EKb(C1))を格納し、データフィールドに部分論理回路H,Iの暗号化された所在置アドレスであるEKa(EKb(C2))及びEKa(EKc(C4))を格納した接続情報パケットを生成する。そして、利用者ノード10は、その接続情報パケットを送信する(S601)。
【0046】
利用者ノード10から送信された接続情報パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した接続情報パケットの宛先アドレスフィールドに格納された2重暗号化アドレスEKa(EKb(C1))を復号できるノードは、秘密鍵Kaを有している中継ノード40aのみであるので、中継ノード40aは接続情報パケットを正式に受信したものとなる。
【0047】
接続情報パケットを受信した中継ノード40aは、接続情報パケットの宛先アドレスフィールドに格納されている2重暗号化アドレスEKa(EKb(C1))を取り出して秘密鍵Kaで復号し、その復号された暗号化アドレスEKb(C1)で宛先アドレスフィールドを更新する(S602)。そして、中継ノード40aは、その更新された接続情報パケットを送信する(S603)。
【0048】
中継ノード40aから送信された接続情報パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した接続情報パケットの宛先アドレスフィールドに格納された暗号化アドレスEKb(C1)を復号できるノードは、秘密鍵Kbを有している中継ノード40bのみであるので、中継ノード40bは接続情報パケットを正式に受信したものとなる。
【0049】
接続情報パケットを受信した中継ノード40bは、接続情報パケットの宛先アドレスフィールドに格納されている暗号化アドレスEKb(C1)を取り出して秘密鍵Kbで復号し、その復号されたアドレスC1で宛先アドレスフィールドを更新する(S604)。そして、中継ノード40bは、その更新された接続情報パケットを送信する(S605)。
【0050】
中継ノード40bから送信された接続情報パケットを受信した計算ノード30aは、接続情報パケットのデータフィールドに格納されたEKa(EKb(C2))及びEKa(EKc(C4))を取り出して部分論理回路記憶部に記憶する(S606)。
【0051】
また、部分論理回路Hの配送先ノードである計算ノード30bも、部分論理回路Hを実行した後は、条件に応じて部分論理回路H又は部分論理回路Iが実行されることになるので、計算ノード30bも、部分論理回路H及び部分論理回路Iを実行する計算ノード30b,30dの暗号化されたアドレスC2,C4を知っている必要がある。このため、利用者ノード10は、EKa(EKb(C2))及びEKa(EKc(C4))を計算ノード30bに送信する。
【0052】
図7に、利用者ノード10が暗号化されたアドレスC2,C4を計算ノード30bに配送する手順を表したシーケンス図を示すが、同図のシーケンス図についての動作の説明は、図6のシーケンス図に基づく動作説明と同様であるため、ここではその詳細説明を省略する。
【0053】
さらにまた、部分論理回路Iの配送先ノードである計算ノード30dは、部分論理回路Iを実行した後は利用者ノードA,Bに実行結果を送信する必要があるため、計算ノード30dは、利用者ノード10,20の暗号化されたアドレスA,Bを知っている必要がある。このため、利用者ノード10は、アドレスAを匿名通信機能を用いて暗号化しながら計算ノード30dに送信する。また、利用者ノード20も、アドレスBを匿名通信機能を用いて暗号化しながら計算ノード30dに送信する。
【0054】
図8に、利用者ノード10が自身のアドレスを計算ノード30dに配送する手順を表したシーケンス図を示して具体的に説明する。同図において、利用者ノード10は、宛先アドレスフィールドに暗号化されたアドレスであるEKa(EKc(C4))を格納し、送信元アドレスフィールドに自身のアドレスAを格納した接続情報パケットを生成する。そして、利用者ノード10は、その接続情報パケットを送信する(S801)。
【0055】
利用者ノード10から送信された接続情報パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した接続情報パケットの宛先アドレスフィールドに格納された2重暗号化アドレスEKa(EKc(C4))を復号できるノードは、秘密鍵Kaを有している中継ノード40aのみであるので、中継ノード40aが接続情報パケットを正式に受信したものとなる。
【0056】
接続情報パケットを正式に受信した中継ノード40aは、接続情報パケットの宛先アドレスフィールドに格納されている2重暗号化アドレス(暗号化宛先アドレス情報)EKa(EKc(C4))を取り出して秘密鍵Kaで復号し、その復号された暗号化アドレスEKc(C4)で宛先アドレスフィールドを更新する。そして、送信元アドレスフィールドに格納されている送信元アドレス情報であるアドレスAを取り出して秘密鍵Kaで暗号化し、そのアドレスAの暗号化アドレスであるEKa(A)で送信元アドレスフィールドを更新する(S802)。
【0057】
次に、中継ノード40aは、その更新された接続情報パケットを送信する(S803)。中継ノード40aから送信された接続情報パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した接続情報パケットの宛先アドレスフィールドに格納された暗号化アドレスEKc(C4)を復号できるノードは、秘密鍵Kcを有している中継ノード40cのみであるので、中継ノード40cが接続情報パケットを正式に受信したものとなる。
【0058】
接続情報パケットを正式に受信した中継ノード40cは、接続情報パケットの宛先アドレスフィールドに格納されている暗号化アドレスEKc(C4)を取り出して秘密鍵Kcで復号し、その復号されたアドレスC4で宛先アドレスフィールドを更新する。そして、送信元アドレスフィールドに格納されている暗号化アドレスEKa(A)を取り出して秘密鍵Kcで暗号化し、その暗号化アドレスEKa(A)の2重暗号化アドレスであるEKc(EKa(A))で送信元アドレスフィールドを更新する(S804)。
【0059】
次に、中継ノード40cは、その更新された接続情報パケットを送信し、計算ノード30dはこれを受信する(S805)。そして、接続情報パケットを受信した計算ノード30dは、接続情報パケットの送信元アドレスフィールドに格納されている2重暗号化アドレスEKc(EKa(A))を部分論理回路記憶部に記憶する(S806)。
【0060】
次に、図9に、利用者ノード20が自身のアドレスを計算ノード30dに配送する手順を表したシーケンス図を示すが、ステップS901−S906の処理については、図8のシーケンス図におけるS801−S806の処理と同様であるため、ここではその詳細説明を省略する。ステップS906の処理に続けて、利用者ノード10は、部分論理回路Gとこれの配送先アドレスが暗号化されたEKa(EKb(C1))との組み合わせ、部分論理回路Hとこれの配送先アドレスが暗号化されたEKa(EKb(C2))との組み合わせ、及び部分論理回路Iとこれの配送先アドレスが暗号化されたEKa(EKc(C4))との組み合わせを、利用者ノード20に対して送信する。そして、利用者ノード20は、これらを受信して部分論理回路記憶部に記憶する(S907)。
【0061】
以上により、計算ノード30a,30bは、部分論理回路H,Iの所在アドレスC2,C4を暗号化したEKa(EKb(C2)),EKa(EKc(C4))をそれぞれの部分論理回路記憶部に記憶し、計算ノード30dは、利用者ノード10,20の所在アドレスA,Bを暗号化したEKc(EKa(A)),EKc(EKa(B))を部分論理回路記憶部に記憶する。
【0062】
[第2フェーズの動作説明]
第2フェーズでは、利用者ノード10,20に入力値d1,d2が入力されることにより、分散計算処理システム1が処理対象プログラムf(d1,d2)を実行し、その最終的な結果を利用者ノード10,20に供給する処理が実行される。図10−図12に、分散計算処理システム1が実行する秘密分散計算処理の第2フェーズの動作を表したシーケンス図を示し、これらを併せ参照して分散計算処理システム1の第2フェーズの動作を説明する。
【0063】
図10において、第2フェーズでは、まず利用者P1の入力操作によって入力値d1が利用者ノード10に入力される(S1001)。次に、利用者ノード10は、宛先アドレスフィールドに部分論理回路Gの所在する暗号化アドレスであるEKa(EKb(C1))を格納し、データフィールドに入力値d1を格納したデータパケットを生成する。そして、利用者ノード10は、そのデータパケットを送信する(S1002)。
【0064】
利用者ノード10から送信されたデータパケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信したデータパケットの宛先アドレスフィールドに格納された2重暗号化アドレスEKa(EKb(C1))を復号できるノードは、秘密鍵Kaを有している中継ノード40aのみであるので、中継ノード40aは接続情報パケットを正式に受信したものとなる。
【0065】
データパケットを受信した中継ノード40aは、データパケットの宛先アドレスフィールドに格納されている2重暗号化アドレスEKa(EKb(C1))を取り出して秘密鍵Kaで復号し、その復号された暗号化アドレスEKb(C1)で宛先アドレスフィールドを更新する(S1003)。そして、中継ノード40aは、その更新されたデータパケットを送信する(S1004)。
【0066】
中継ノード40aから送信されたデータパケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した接続情報パケットの宛先アドレスフィールドに格納された暗号化アドレスEKb(C1)を復号できるノードは、秘密鍵Kbを有している中継ノード40bのみであるので、中継ノード40bは接続情報パケットを正式に受信したものとなる。
【0067】
データパケットを受信した中継ノード40bは、接続情報パケットの宛先アドレスフィールドに格納されている暗号化アドレスEKb(C1)を取り出して秘密鍵Kbで復号し、その復号されたアドレスC1で宛先アドレスフィールドを更新する(S1005)。そして、中継ノード40bは、その更新されたデータパケットを送信する。そして、中継ノード40bから送信されたデータパケットを受信した計算ノード30aは、データパケットのデータフィールドに格納された入力値d1を取り出して部分論理回路記憶部に記憶する(S1006)。
【0068】
利用者ノード20側についても、同様の処理が実行される。すなわち、利用者P2の入力操作によって入力値d2が利用者ノード20に入力されると(S1011)、ステップS1002−S1006の処理と同様の処理が実行される(S1012−S1016)。
【0069】
部分論理回路Gが配置された計算ノード30aに、処理対象プログラムf(a,b)の入力値であるa=d1,b=d2が配送されたのち、計算ノード30aは入力値d1,d2を用いた部分論理回路Gの処理を実行して中間出力値G(d1,d2)を出力する(S1017)。計算ノード30における部分論理回路Gの処理においては、部分論理回路G及び中間出力値G(d1,d2)は暗号化されていないため、図2に示した処理対象プログラムf(a,b)のフローチャートにおける所定の条件について容易に判定処理を行うことができ、それに伴う分岐処理を適切に行うことができる。
【0070】
次に、部分論理回路Gからの中間出力値G(d1,d2)に基づく所定の条件の判定結果がFALSEであった場合についての秘密分散計算処理のフローチャートを図11に示してその動作を説明する。条件の判定結果がFALSEである場合、次に実行される部分論理回路は部分論理回路Iである。よって、同図に示すように、計算ノード30aは、宛先アドレスフィールドに部分論理回路Iの所在する暗号化アドレスであるEKa(EKc(C4))を格納し、データフィールドに中間出力値G(d1,d2)を格納したデータパケットを生成する。そして、計算ノード30aは、そのデータパケットを送信する(S1101)。
【0071】
そして、図10に示したシーケンスと同様なシーケンスの匿名通信を行うことにより、中間出力値G(d1,d2)は計算ノード30dに配送される(S1102−S1105)。部分論理回路Iが配置された計算ノード30dに、処理対象プログラムf(d1,d2)の中間出力値G(d1,d2)が配送されたのち、計算ノード30dは中間出力値G(d1,d2)を入力値として用いた部分論理回路Iの処理を実行して最終出力値f(d1,d2)を出力する(S1106)。
【0072】
次に、部分論理回路Iからの最終出力値f(d1,d2)を利用者ノード10,20にそれぞれ配送する動作について、図12にフローチャートを示して説明する。同図に示すように、まず計算ノード30dは、宛先アドレスフィールドに利用者ノード10の所在する暗号化アドレスであるEKc(EKa(A))を格納し、データフィールドに最終出力値f(d1,d2)を格納したデータパケットを生成する。そして、計算ノード30dは、そのデータパケットを送信する(S1201)。そして、図10に示したシーケンスと同様なシーケンスの匿名通信を行うことにより、最終出力値f(d1,d2)は利用者ノード10に配送される(S1202−S1205)。そして、利用者ノード10は、最終出力値f(d1,d2)を取得する(S1206)。
【0073】
同様にして、計算ノード30dは、最終出力値f(d1,d2)を利用者ノード20に配送し、利用者ノード20はこれを取得する(S1211−S1216)。
【0074】
以上、本実施形態の分散計算処理システムの動作について説明したが、この分散計算処理システムで用いる部分論理回路G,H,Iはそれぞれ暗号化されていないため、盗聴による計算の秘匿性が問題となる。n台の計算ノードのうち、m台(但し、n>m)の計算ノードが、悪意のある盗聴者PEによって盗聴されたとする。盗聴者PEは、盗聴している計算ノードについての各状態、具体的には、他のノードとの間でやり取りされる入出力値やメモリの内容を取得することができるものとする。これによれば、盗聴者PEは、n個の部分論理回路のうち、m個の部分論理回路の入力値を観測することができる。但し、通信は匿名化されているので、盗聴者PEは、観測した部分論理回路の入力値が、元の論理回路全体のうちどこの部分論理回路であるかを特定することができない。したがって、盗聴者PEは、元のn個の値のうち、その一部分であるm個を、順番が不明な状態で観測しているのと同等である。
【0075】
これは、kビットの入力とs×mビットの出力を有する情報チャネルと置き換えて考えることができる。これにおいて、順序が不明でその一部しか観測できないということは、通信路にノイズが存在することに相当する。ノイズの存在する通信路では、そこに入力されたkビットの情報の全ては伝送されず、ノイズの分だけ減少した情報量eビット(e<k)が伝送される。これにより、盗聴者PEが、秘密情報である入力値d1,d2に関して得ることのできる情報量eビットをkビットよりも小さくすることができる。よって、さらに部分論理回路をより細かく分割する(すなわち、nを大きくする)ことにより、ノイズ成分を大きくし、eビットをより小さくすることができる。したがって、利用者ノードは、必要や用途に応じて分割数nを増減して所望の秘匿性を確保することができる。
【0076】
以上、詳述したとおり、本実施形態によれば、処理対象プログラムが論理回路に変換され、さらに複数の部分論理回路に分割されて匿名通信機能及びランダム通信機能によって複数の計算ノードに配置される。これによって、配送元及び配送先は互いのアドレスを知ることができず、配信元はどの部分論理回路がどこの計算ノードに配置されたかを知ることができない。また、全てのパケットの通信は、暗号化されたアドレスによって行われるため、通信経路中で中継される中継ノードも入出力両方のアドレスを知ることができない。これにより、ネットワーク50のノードの一部が盗聴されたとしても各ノードの通信接続関係が不明であるため、情報の秘匿性を確保することができる。
【0077】
また、本実施形態によれば、部分論理回路自体や部分論理回路の入出力値は暗号化されない状態で処理されるため、部分論理回路を選択的に処理したり条件分岐処理をしたりすることが容易に行える。よって、従来のように、全ての選択肢を処理させていたような非効率な処理をする必要がないため、リソース消費を経済的に抑えることができるとともに処理効率を飛躍的に改善することができる。
【0078】
なお、本発明の実施形態による分散計算処理装置の処理を実行させるための分散計算処理用プログラムをコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませて実行させることにより、本実施形態による分散計算処理を行うようにしてもよい。なお、ここでいうコンピュータシステムとは、オペレーティングシステムや周辺機器等のハードウェアを含むものであってもよい。また、コンピュータシステムは、WWWシステムを利用している場合であれば、ホームページ提供環境(あるいは表示環境)も含むものとする。また、コンピュータ読み取り可能な記録媒体とは、フレキシブルディスク、光磁気ディスク、ROM、フラッシュメモリ等の書き込み可能な不揮発性メモリ、CD−ROM等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【0079】
さらにコンピュータ読み取り可能な記録媒体は、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ(例えばDRAM)のように、一定時間プログラムを保持しているものも含むものとする。また、上記のプログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する伝送媒体は、インターネット等のネットワーク(通信網)や電話回線等の通信回線(通信線)のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル(差分プログラム)であっても良い。
【0080】
以上、本発明の実施形態について詳述したが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【0081】
1 分散計算処理システム
10,20 利用者ノード
30a,30b,30c,30d 計算ノード
40a,40b,40c 中継ノード
50 ネットワーク
d1,d2 入力値
Ka,Kb,Kc 秘密鍵
P1,P2 利用者
【技術分野】
【0001】
本発明は、ネットワークを介して接続された複数の計算ノードに一つの処理対象プログラムを計算処理させる分散計算処理技術に関する。
【背景技術】
【0002】
ネットワーク上に分散した複数の情報処理装置が、協働して一つの関数の計算処理を行う分散計算処理技術が知られている。この分散計算処理技術においては、各情報処理装置のセキュリティの観点から、またユーザのプライバシーの観点から、入力情報を秘密にしたままで計算処理を行いたいという要望があり、様々な研究や技術的試みが行われてきた。例えば、計算すべき関数を論理回路として表すことができる場合、秘匿性のある分散計算処理(秘密分散計算処理)についての情報処理装置間の通信プロトコルを規定して実現する方法が知られている(例えば、非特許文献1参照)。また、電子投票システム等の特定のケースを対象としたものについては、情報処理装置の秘匿性を保ちながら効率よく計算する方法が知られている(例えば、非特許文献2参照)。
【先行技術文献】
【非特許文献】
【0003】
【非特許文献1】Foundations of Cryptography Volume II Basic Applications,Cambridge University Press,May 10,2004.
【非特許文献2】岡本龍明、山本博資著、「シリーズ/情報科学の数学 現代暗号」、産業図書、1997年
【発明の概要】
【発明が解決しようとする課題】
【0004】
しかしながら、一般的なプログラムを論理回路として表し、非特許文献1に記載された技術を用いて秘密分散計算処理を行うと処理効率が悪く実用的ではない。ここで、非特許文献1記載の秘密分散計算処理の方法について、関係する部分の概略を説明する。この秘密分散計算処理では、実行すべきプログラムを論理回路に変換したものを、主に暗号理論分野において知られているGarbled Circuit(GC)に変換して用いる。このGCは、例えば論理ゲートレベルで内部ロジックを秘匿したまま論理演算を行うものであり、GCの入出力は乱数のキーとして表される。GCでは、正しい入力キーを有する者だけが、そのキーに対応付けられた入力値の論理演算の結果に対応する出力キーを得ることができる。
【0005】
このようにして、非特許文献1記載の秘密分散計算処理方法では、論理回路の構成に応じたGCの組み合わせによって論理回路全体の秘匿性を保つことはできるが、論理回路の各論理ゲートの論理値が分からない状態で計算を行うため、途中の計算結果の状態に応じて選択的な処理(すなわち、通常のプログラムにおける条件分岐処理)を簡単に行うことができない。これを実現するためには、GC化される論理回路は、条件分岐処理に係る回路を、想定される全ての条件についての分岐処理を実行させるように構成しなければならず、プログラムによってはリソースが多く必要になり処理効率が悪くなるおそれが大きい。
【0006】
また、非特許文献2に記載されたような特定の問題に特化した方法では、問題ごとに暗号理論の専門家によるプロトコル設計がされなければならず、汎用的なプログラムには適用できない。
【0007】
そこで、本発明は上記問題に鑑みてなされたものであり、相互に秘匿性を保ちながら処理対象プログラムの分散計算処理を実行させる場合に、処理効率に優れ且つ汎用的な処理対象プログラムに適用することが容易な、分散計算処理システム及び分散計算処理方法を提供することを目的とする。
【課題を解決するための手段】
【0008】
本発明は、上記の課題を解決するために、以下[1],[2]の手段を提供するものである。
[1] 複数の中継ノードを含むネットワークに利用者ノードが接続され、前記利用者ノードに入力された入力情報を用いて処理対象プログラムの分散計算処理を行う分散計算処理システムにおいて、
前記ネットワークには、複数の計算ノードが接続され、
前記利用者ノードは、
前記処理対象プログラムを論理回路に変換して複数の部分論理回路に分割する論理回路分割手段と、
前記分割された部分論理回路をデータフィールドに格納するとともに、利用者ノードアドレス情報を送信元アドレスフィールドに格納したパケットを送信する部分論理回路送信手段と、
前記複数の中継ノードのうちいずれかの中継ノードから送信されたパケットを受信し、それの送信元アドレスフィールドに格納された暗号化計算ノードアドレス情報を取り出して記憶する計算ノードアドレス情報記憶手段と、
前記入力情報をデータフィールドに格納し、前記記憶された暗号化計算ノードアドレス情報を宛先アドレスフィールドに格納したパケットを送信する入力情報送信手段と、
を備え、
前記複数の中継ノードそれぞれは、
到来したパケットを受信して、それの宛先アドレスフィールドの指定のない場合は、送信元アドレスフィールドに格納された所定の送信元アドレス情報を暗号化して前記パケットを更新し、所定の確率に基づいて他の中継ノード及び前記複数の計算ノードのうちいずれか一のノードを選択して、前記更新されたパケットを送信する匿名ランダム中継手段と、
到来したパケットを受信して、それの宛先アドレスフィールドに所定の暗号化宛先アドレス情報が格納されている場合は、その所定の暗号化宛先アドレス情報を復号し、さらに送信元アドレスフィールドに所定の送信元アドレス情報が格納されている場合にはその所定の送信元アドレス情報を暗号化して前記パケットを更新し送信する匿名中継手段と、
を備え、
前記複数の計算ノードそれぞれは、
前記複数の中継ノードのうちいずれかの中継ノードの匿名ランダム中継手段から送信されたパケットを受信し、それのデータフィールドに格納された部分論理回路を取り出して記憶する部分論理回路記憶手段と、
該計算ノードの計算ノードアドレス情報を送信元アドレスフィールドに格納するとともに、前記部分論理回路記憶手段において受信したパケットの送信元アドレスフィールドに格納された暗号化利用者ノードアドレス情報を宛先アドレスフィールドに格納したパケットを送信する応答送信手段と、
前記複数の中継ノードのうちいずれかの中継ノードの匿名中継手段から送信されたパケットを受信し、それのデータフィールドに格納された入力情報を取り出して、前記記憶された部分論理回路に入力して計算する計算処理手段と、
を備えたことを特徴とする分散計算処理システム。
[2] 複数の中継ノードを含むネットワークを介して利用者ノードと複数の計算ノードとが接続され、前記利用者ノードに入力された入力情報を用いて前記複数の計算ノードに処理対象プログラムの分散計算処理を行わせる分散計算処理方法であって、
前記利用者ノードが、
前記処理対象プログラムを論理回路に変換して複数の部分論理回路に分割する論理回路分割ステップと、
前記分割された部分論理回路をデータフィールドに格納するとともに、利用者ノードアドレス情報を送信元アドレスフィールドに格納した部分論理回路パケットを送信する部分論理回路送信ステップと、
前記複数の中継ノードのうちいずれかが、
前記送信された部分論理回路パケットを受信し、それの送信元アドレスフィールドに格納された利用者ノードアドレス情報を暗号化して前記部分論理回路パケットを更新し、所定の確率に基づいて他の中継ノード及び前記複数の計算ノードのうちいずれか一のノードを選択して、前記更新された部分論理回路パケットを送信する匿名ランダム中継ステップと、
前記複数の計算ノードのうち、部分論理回路パケットの到来した計算ノードが、
前記部分論理回路パケットを受信し、それのデータフィールドに格納された部分論理回路を取り出して記憶する部分論理回路記憶ステップと、
前記計算ノードの計算ノードアドレス情報を送信元アドレスフィールドに格納するとともに、前記部分論理回路記憶ステップにおいて受信した部分論理回路パケットの送信元アドレスフィールドに格納された暗号化利用者ノードアドレス情報を宛先アドレスフィールドに格納した応答パケットを送信する応答送信ステップと、
前記複数の中継ノードのうち前記送信された応答パケットの到来した中継ノードが、
前記応答パケットを受信し、それの宛先アドレスフィールドに格納された暗号化利用者ノードアドレス情報を復号できた場合に、送信元アドレスフィールドに格納された計算ノードアドレス情報を暗号化して前記応答パケットを更新し送信する応答中継ステップと、
前記利用者ノードが、
前記複数の中継ノードのうちいずれかの中継ノードから送信された応答パケットを受信し、それの送信元アドレスフィールドに格納された暗号化計算ノードアドレス情報を取り出して記憶する計算ノードアドレス情報記憶ステップと、
前記入力情報をデータフィールドに格納し、前記記憶された暗号化計算ノードアドレス情報を宛先アドレスフィールドに格納したデータパケットを送信する入力情報送信ステップと、
前記複数の中継ノードのうち前記送信されたデータパケットの到来した中継ノードが、
前記データパケットを受信し、それの宛先アドレスフィールドに格納された暗号化計算ノードアドレス情報を復号できた場合に、前記データパケットを更新して送信するデータ中継ステップと、
前記送信されたデータパケットを受信した計算ノードが、
それのデータフィールドに格納された入力情報を取り出して、前記記憶された部分論理回路に入力して計算する計算処理ステップと、
を有したことを特徴とする分散計算処理方法。
【発明の効果】
【0009】
本発明によれば、部分論理回路の配置場所を秘匿する一方、部分論理回路自体やこれに入力される入力情報が暗号化されない状態で分散計算処理が実行されるため、処置途中段階での選択的な処理や条件分岐処理を容易に実行することができる。さらに、本発明によれば、汎用的な処理対象プログラムに適用することが容易となる。
【図面の簡単な説明】
【0010】
【図1】本発明の実施形態である分散計算処理システムの概略の構成図である。
【図2】分散計算処理システムが秘密分散計算処理を実行する対象である処理対象プログラムの概略のフローチャートである。
【図3】分散計算処理システムが実行する秘密分散計算処理の第1フェーズの動作のうち、部分論理回路を配送する動作を説明するためのシーケンス図である。
【図4】分散計算処理システムが実行する秘密分散計算処理の第1フェーズの動作のうち、部分論理回路を配送する動作を説明するためのシーケンス図である。
【図5】分散計算処理システムが実行する秘密分散計算処理の第1フェーズの動作のうち、部分論理回路を配送する動作を説明するためのシーケンス図である。
【図6】分散計算処理システムが実行する秘密分散計算処理の第1フェーズの動作のうち、部分論理回路が取得しておくべき情報を配送する動作を説明するためのシーケンス図である。
【図7】分散計算処理システムが実行する秘密分散計算処理の第1フェーズの動作のうち、部分論理回路が取得しておくべき情報を配送する動作を説明するためのシーケンス図である。
【図8】分散計算処理システムが実行する秘密分散計算処理の第1フェーズの動作のうち、部分論理回路が取得しておくべき情報を配送する動作を説明するためのシーケンス図である。
【図9】分散計算処理システムが実行する秘密分散計算処理の第1フェーズの動作のうち、部分論理回路が取得しておくべき情報を配送する動作を説明するためのシーケンス図である。
【図10】分散計算処理システムが実行する秘密分散計算処理の第2フェーズの動作を説明するためのシーケンス図である。
【図11】分散計算処理システムが実行する秘密分散計算処理の第2フェーズの動作を説明するためのシーケンス図である。
【図12】分散計算処理システムが実行する秘密分散計算処理の第2フェーズの動作を説明するためのシーケンス図である。
【発明を実施するための形態】
【0011】
以下、本発明を実施するための形態について、図面を参照して詳細に説明する。本実施形態では、計算処理の対象となる処理対象プログラムを、2人の利用者がそれぞれ使用する2台の電子計算機から入力された秘密情報である入力値を引数として、これら入力値の秘密性を確保して分散計算処理(秘密分散計算処理)を実行する分散計算処理システムについて説明する。
【0012】
図1に、本実施形態である分散計算処理システムの概略の構成図を示す。同図において、分散計算処理システム1は、9台のノードを接続したネットワーク50により構成されており、処理対象プログラムf(a,b)(a,bは引数)を計算するものである。ノードとは、ネットワーク50に接続される電子計算機、ルータ、サーバ等の情報処理装置のことをいい、ノード間での通信を行うことができる。ネットワーク50に接続された9台のノードの内訳は、利用者P1及びP2によってそれぞれ使用され、処理対象プログラムf(a,b)に対する入力値が入力されるとともに、秘密分散計算処理により得られた結果が得られる利用者ノード10,20と、秘密分散計算処理を行う分散計算処理装置である計算ノード30a,30b,30c,30dと、ノードを中継接続する中継ノード40a,40b,40cとである。
【0013】
利用者P1が使用する利用者ノード10と、利用者P2が使用する利用者ノード20とは、コンピュータ等の電子計算機を用いることができる。利用者ノード10,20それぞれは、不図示ではあるが、処理対象プログラムを論理回路に変換して複数の部分論理回路に分割するための論理回路分割部と、部分論理回路を該利用者ノードのアドレス情報である利用者ノードアドレス情報とともに部分論理回路パケットとして送信するための部分論理回路送信部と、中継ノード40a,40b,40cのうちいずれかから送信された応答パケットを受信し、暗号化された計算ノードのアドレス情報(暗号化計算ノードアドレス情報)を取り出して記憶するための計算ノードアドレス情報記憶部と、入力情報d1,d2を暗号化計算ノードアドレス情報とともにデータパケットとして送信するための入力情報送信部とを備えている。利用者ノード10には、利用者P1によって秘密情報である入力値a=d1が入力され、利用者ノード20には、利用者P2によって秘密情報である入力値b=d2が入力されるものとする。なお、入力値d1及びd2の合計ビット数はkビットであるとする。また、利用者ノード10,20は互いのアドレス情報を知っており、両者間での通信を行うことができる。
【0014】
n=4台の計算ノード30a,30b,30c,30dのそれぞれも、コンピュータ等の電子計算機を用いることができる。計算ノード30a,30b,30c,30dそれぞれは、不図示ではあるが、中継ノード40a,40b,40cのうちいずれかの中継ノードから送信された部分論理回路パケットを受信し、部分論理回路を取り出して記憶するための部分論理回路記憶部と、その計算ノードの計算ノードアドレス情報と部分論理回路パケットを受信した際の送信元アドレスである暗号化利用者ノードアドレス情報とを含めた応答パケットを送信するための応答送信部と、中継ノード40a,40b,40cのうちいずれかの中継ノードから送信されたデータパケットを受信し、入力情報を取り出して部分論理回路記憶部に記憶された部分論理回路に入力して計算するための計算処理部とを備えている。
【0015】
中継ノード40a,40b,40cはルータを用いることができる。これら中継ノード40a,40b,40cは、それぞれ秘密鍵Ka,Kb,Kcを有している。そして、各中継ノード40a,40b,40cは、中継元から入力されたデータを、自身の秘密鍵Ka,Kb,Kcで暗号化したり、入力された暗号化データを秘密鍵Ka,Kb,Kcで復号したりして中継先に出力することができる。中継ノード40a,40b,40cそれぞれは、不図示ではあるが、到来したパケットを受信して、それに宛先アドレスの指定のない場合は、所定の送信元アドレス情報を自身の秘密鍵で暗号化して該パケットを更新し、例えば後述するランダムウォーク方式に基づいて他の中継ノード及び計算ノード30a,30b,30c,30dのうちいずれか一のノードを選択し、更新されたパケットを送信するための匿名ランダム中継部と、到来したパケットを受信して、所定の暗号化宛先アドレス情報が格納されている場合は、それを自身の秘密鍵で復号し、さらに所定の送信元アドレス情報が格納されている場合にはその所定の送信元アドレス情報を自身の秘密鍵で暗号化して該パケットを更新し送信するための匿名中継部とを備えている。匿名ランダム中継部及び匿名中継部の動作については、後に詳細を説明する。
【0016】
中継ノード40a,40b,40cを含むネットワーク50では、盗聴者から送信者と受信者との対応関係を隠すために、暗号化されたアドレス(ネットワーク層のアドレスであり、例えばIPアドレス)で指定される匿名の宛先に対してパケットを送信する匿名通信を行うことができる。また、ネットワーク50では、送信元がどこを送信先としてパケットが送信されたかを不明にさせるために、無作為に選択した宛先に対してパケットを送信するランダム通信を行うことができる。
【0017】
ここで、中継ノード40a,40b,40cを含むネットワーク50で行われる匿名通信の方法について、図1における中継ノード40aから中継ノード40bを中継して計算ノード30aにパケットを送信する場合を例として説明する。中継ノード40aは、入来したパケットに含まれる送信元の始点アドレスを中継ノード40aの秘密鍵Kaで暗号化し、その暗号化始点アドレスで元の始点アドレスを置き換えたパケットを中継ノード40bに送信する。そして、中継ノード40bは、受信したパケットに含まれる暗号化始点アドレスを中継ノード40bの秘密鍵Kbでさらに暗号化し、その2重に暗号化した2重暗号化始点アドレスで元の暗号化始点アドレスを置き換えたパケットを計算ノード30aに送信する。このようにすることにより、中継ノード40aと計算ノード30aとの間の通信を盗聴しても、元の始点アドレスを知ることができない。
【0018】
ただし、上記の方法では、中継ノード40a自身の内部メモリ等の記憶部がスキャニングされた場合には送信元の始点アドレスが知られてしまうことになる。そこで、複数の中継ノードを複数段入れ子に接続する構成をとることでこれを防ぐことができる。このように構成した場合、経路上の全ての中継ノードが盗聴されない限りは宛先アドレスを知られることなないため匿名性は高いものとなる。
【0019】
このように、匿名通信機能によれば、受信者は送信者を知ることができなくなる。しかし、送信者は予め受信者を知っていなければならないことになる。そこで、送信者が受信者を不明なものとするためにランダム通信を用いてパケットを送信するようにする。
【0020】
次に、ランダム通信機能について説明する。本実施形態において、中継ノード40a,40b,40cを含むネットワーク50で行われるランダム通信では、パケットの到着する宛先は、送信者が指定するのではなく、宛先の候補(例えば、自中継ノードが中継ノード40aである場合は、中継ノード40b,40c、及び計算ノード30a,30b,30c,30d)の中から無作為に決定される。このようなパケットの配送を実現する方式としてグラフ上のランダムウォークが公知である。このランダムウォーク方式では、j(jは2以上の整数)個の隣接ノードを有するルータは、次の転送先を隣接ノードの中から1/jずつの確率で選択する。パケットが宛先候補のノードの集合のいずれかに到達した時点で配送は完了する。このようなランダムウォーク方式の特性については様々な解析が行われている。例えば、以下の文献ではインターネットのようなスケールフリー特性を有するネットワーク上におけるランダムウォークについての解析結果がまとめられている。
【0021】
Noh,J.D.and Rieger,H.,Random Walks on Complex Networks,Physical Review Letters,vol.92,page 118701,2004.
【0022】
また、様々な統計的な特性を有したランダムウォーク方式の派生モデルも公表されており、これらを利用することで所望の特性を有した無作為なパケットの配送を実現できる。例えば、以下の文献には、ランダムウォークを拡張することにより、宛先までの到達時間を短縮する方法が述べられている。
【0023】
S.Ikeda,I.kubo,and M.Yamashita,Reducing the Hitting and the Cover Times of Ramdom Walks on Finite Graphs by Local Topological Information,Proceedings of the 2003 International Conference on VLSI,pp.203−207,2003.
【0024】
本実施形態においては、上述した公知のランダムウォーク方式を適用して宛先を確率的に選択してランダム通信を行う。よって、匿名通信機能及びランダム通信機能を併せ用いた通信を行うことにより、送信元は受信先を知らず、且つ受信先も送信元を知らないこと、及び送信されたパケットがどこに配送されたかを不明なものとすることが実現できる。そして、これにより、入力情報を暗号化することなくその秘匿性を保つことができるため、本実施形態では、途中の計算結果に応じた選択的な処理を実行させることを可能にするものである。
【0025】
次に、本実施形態である分散計算処理システムにおける秘密分散計算処理について説明する。この秘密分散計算処理は2つのフェーズから成り立つものである。第1フェーズでは、任意の利用者ノードが処理対象プログラムを論理回路に変換して複数の部分論理回路に分割し、これらの部分論理回路を匿名通信機能及びランダム通信機能を用いて計算ノードに配送する。第2フェーズでは、各利用者ノードは、入力値を暗号化することなく計算ノードに送信し、これらを受信した計算ノードは協働して計算を行い、最終的な出力値を各利用者ノードに送信する。その協働した計算の際には、各計算ノードの入出力値は暗号化されない状態でやり取りされる。以下、各フェーズについて詳細に説明する。
【0026】
[第1フェーズの動作説明]
一般的に、論理回路は、ノード及びエッジを含んで構成される有向グラフとみなすことができため、エッジを介して連結されたノードを含むような関係を有した部分論理回路に分割することができる。図2に、分散計算処理システム1が秘密分散計算処理を実行する対象である処理対象プログラムf(a,b)の概略のフローチャートを示す。同図は、処理対象プログラムf(a,b)が3つの部分論理回路G,H,Iに分割された様子を示している。すなわち、部分論理回路Gでは、入力値a,bに基づき所定の計算を実行し、その結果に対し所定の条件に基づいてTRUE(真)であった場合は、部分論理回路Hの処理に移行する一方、FALSE(偽)であった場合は、部分論理回路Iの処理に移行する。部分論理回路Hでの処理の後は、条件分岐に戻る。また、部分論理回路Iでの処理によって最終的な結果が得られる。このように、本実施形態における処理対象プログラムf(a,b)には条件分岐処理が含まれているものとする。
【0027】
図3−図9に、分散計算処理システム1が実行する秘密分散計算処理の第1フェーズの動作を表したシーケンス図を示し、これらを併せ参照して分散計算処理システム1の第1フェーズの動作を説明する。なお、利用者ノード10,20の各アドレスをA,B、中継ノード40a,40b,40cの各アドレスをR1,R2,R3、計算ノード30a,30b,30c,30dの各アドレスをC1,C2,C3,C4として説明する。
【0028】
図3において、第1フェーズでは、まず任意の利用者ノード、例えば利用者P1が使用する利用者ノード10が、処理対象プログラムf(a,b)を3つの部分論理回路G,H,Iに分割する(S301)。3つの部分論理回路G,H,Iは、均等な大きさになるように分割され、部分論理回路G,H,Iの各入力値はsビットであるとする。
【0029】
次に、利用者ノード10は、これらの部分論理回路G,H,Iを計算ノードに配送する。まず、利用者ノード10は、部分論理回路Gを計算ノードに配送するが、ここでは、ランダム通信機能によって、中継ノード40a→中継ノード40bの経路を辿って計算ノード30aに配送されるものとして説明する。
【0030】
部分論理回路Gを計算ノード30aに配送する場合には、以下の3つの条件を満たす必要がある。
(1)利用者ノード10(利用者P1)は、どこが配送先であるかを知ってはならない。
(2)配送先である計算ノード30aは、どこが配送元であるかを知ってはならない。
(3)中継ノード40a,40bは、配送元及び配送先の両方を知ってはならない(但し、いずれか一方を知ることに問題はない。)
【0031】
上記(1)−(3)の条件を満たすために、利用者ノード10は、以下の手順にしたがって部分論理回路Gを配送する。まず、利用者ノード10は、送信元アドレスフィールドに自身の利用者ノードアドレス情報であるアドレスAを格納し、データフィールドに部分論理回路Gを格納した部分論理回路パケットを生成する。そして、利用者ノード10は、その部分論理回路パケットを隣接する中継ノード40aに送信する(S302)。
【0032】
次に、中継ノード40aは、受信した部分論理回路パケットの送信元アドレスフィールドに格納されているアドレスAを取り出して秘密鍵Kaで暗号化し、そのアドレスAの暗号化アドレスであるEKa(A)で送信元アドレスフィールドを更新する(S303)。そして、中継ノード40aは、ランダム通信機能によって無作為に次の送信先ノードを決定し、更新された部分論理回路パケットを決定されたノードである中継ノード40bに送信する(S304)。
【0033】
ランダム通信により中継ノード40aから送信された部分論理回路パケットを受信した中継ノード40bは、上記のステップS303及びS304と同様の処理を実行する。具体的には、中継ノード40bは、受信した部分論理回路パケットの送信元アドレスフィールドに格納されている暗号化アドレスEKa(A)を取り出して秘密鍵Kbで暗号化し、暗号化アドレスEKa(A)をさらに暗号化した2重暗号化アドレスであるEKb(EKa(A))で送信元アドレスフィールドを更新する(S305)。そして、中継ノード40bは、ランダム通信機能によって無作為に次の送信先ノードを決定し、更新された部分論理回路パケットを決定されたノードである計算ノード30aに送信する(S306)。
【0034】
ランダム通信により中継ノード40bから送信された部分論理回路パケットを受信した計算ノード30aは、受信した部分論理回路パケットのデータフィールドに格納されている部分論理回路Gを部分論理回路記憶部に記憶する(S307)。
【0035】
以上によれば、計算ノード30aが受信した部分論理回路パケットの送信元アドレスフィールドに格納された利用者ノード10のアドレスAは、経路中の中継ノード40a,40bによってそれぞれ暗号化されているため、計算ノード30aは、利用者ノード10を配送元として特定することができない。また、中継ノード40a,40bによるランダム通信によって部分論理回路パケットが配送されているため、配送元である利用者ノード10は配送先の計算ノードを特定することができない。さらに、中継ノード40a,40bは、配送元である利用者ノード10と配送先である計算ノード30aとの両方を特定することができない。よって、利用者ノード10は、匿名性に関する前記3つの条件(1)−(3)を満たしながら、部分論理回路Gを計算ノード30aに配送することができる。
【0036】
次に、部分論理回路Gを取得した計算ノード30aは、利用者ノード10に対して受信確認の応答を返信する。この応答は、部分論理回路パケットの配送経路と同一の経路を逆向きに辿って利用者ノード10に配送される。具体的には、まず、計算ノード30aは、宛先アドレスフィールドに2重暗号化アドレス(暗号化利用者ノードアドレス情報)であるEKb(EKa(A))を格納し、送信元アドレスフィールドに自身の計算ノードアドレス情報であるアドレスC1を格納した応答パケットを生成する。そして、計算ノード30aは、その応答パケットを送信する(S308)。
【0037】
計算ノード30aから送信された応答パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した応答パケットの宛先アドレスフィールドに格納された2重暗号化アドレスEKb(EKa(A))を復号できるノードは、秘密鍵Kbを有している中継ノード40bのみであるので、中継ノード40bが応答パケットを正式に受信したものとなる。
【0038】
応答パケットを正式に受信した中継ノード40bは、応答パケットの宛先アドレスフィールドに格納されている2重暗号化アドレス(暗号化宛先アドレス情報)であるEKb(EKa(A))を取り出して秘密鍵Kbで復号し、その復号された暗号化アドレスEKa(A)で宛先アドレスフィールドを更新する。そして、送信元アドレスフィールドに格納されている送信元アドレス情報であるアドレスC1を取り出して秘密鍵Kbで暗号化し、そのアドレスC1の暗号化アドレス(暗号化計算ノードアドレス情報)であるEKb(C1)で送信元アドレスフィールドを更新する(S309)。
【0039】
次に、中継ノード40bは、その更新された応答パケットを送信する(S310)。中継ノード40bから送信された応答パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した応答パケットの宛先アドレスフィールドに格納された暗号化アドレスEKa(A)を復号できるノードは、秘密鍵Kaを有している中継ノード40aのみであるので、中継ノード40aが応答パケットを正式に受信したものとなる。
【0040】
応答パケットを正式に受信した中継ノード40aは、応答パケットの宛先アドレスフィールドに格納されている暗号化アドレスEKa(A)を取り出して秘密鍵Kaで復号し、その復号されたアドレスAで宛先アドレスフィールドを更新する。そして、送信元アドレスフィールドに格納されている暗号化アドレスEKb(C1)を取り出して秘密鍵Kaで暗号化し、その暗号化アドレスEKb(C1)の2重暗号化アドレスであるEKa(EKb(C1))で送信元アドレスフィールドを更新する(S311)。
【0041】
次に、中継ノード40aは、その更新された応答パケットを送信し、利用者ノード10はこれを受信する(S312)。そして、応答パケットを受信した利用者ノード10は、部分論理回路Gと、応答パケットの宛先アドレスフィールドに格納されている2重暗号化アドレス(暗号化計算ノードアドレス情報)であるEKa(EKb(C1))とを関連付けて計算ノードアドレス情報記憶部に記憶する(S313)。
【0042】
上述したステップS302−S313の処理と同様に、利用者ノード10は、部分論理回路H,Iを計算ノードに配送して確認応答を受信する。図4に、利用者ノード10が部分論理回路Hを計算ノードに配送する手順を表したシーケンス図を示し、図5に、利用者ノード10が部分論理回路Iを計算ノードに配送する手順を表したシーケンス図を示す。図4については、利用者ノード10が配送する部分論理回路Hは、ランダム通信機能によって中継ノード40a→中継ノード40bの経路を辿って計算ノード30bに配送された場合を例としたものである。また、図5については、利用者ノード10が配送する部分論理回路Iは、ランダム通信機能によって中継ノード40a→中継ノード40cの経路を辿って計算ノード30dに配送された場合を例としたものである。なお、図4及び図5のシーケンス図についての動作の説明は、図3のシーケンス図に基づく動作説明と同様であるため、ここではその詳細説明を省略する。
【0043】
図3−図5に示したシーケンス図に基づく動作により、利用者ノード10,20は、部分論理回路Gとこれの配送先アドレスが暗号化されたEKa(EKb(C1))との組み合わせ、部分論理回路Hとこれの配送先アドレスが暗号化されたEKa(EKb(C2))との組み合わせ、及び部分論理回路Iとこれの配送先アドレスが暗号化されたEKa(EKc(C4))との組み合わせを、それぞれの計算ノードアドレス情報記憶部に記憶させることとなる。すなわち、利用者ノード10,20は、全ての部分論理回路G,H,Iと、これらが配送された計算ノード30a,30b,30dの暗号化されたアドレスの対応関係を知る状態となる。
【0044】
ところで、図2に示した処理対象プログラムのフローチャートによれば、部分論理回路Gを実行した後は、条件に応じて部分論理回路H又は部分論理回路Iが実行されることになる。そのため、部分論理回路Gの配送先ノードである計算ノード30aは、部分論理回路H及び部分論理回路Iを実行する計算ノード30b,30dのアドレス、すなわち暗号化されたアドレスC2,C4を知っている必要がある。そこで、利用者ノード10は、EKa(EKb(C2))及びEKa(EKc(C4))を計算ノード30aに送信する。
【0045】
図6に、利用者ノード10が暗号化されたアドレスC2,C4を計算ノード30aに配送する手順を表したシーケンス図を示して具体的に説明する。同図において、利用者ノード10は、宛先アドレスフィールドに暗号化されたアドレスであるEKa(EKb(C1))を格納し、データフィールドに部分論理回路H,Iの暗号化された所在置アドレスであるEKa(EKb(C2))及びEKa(EKc(C4))を格納した接続情報パケットを生成する。そして、利用者ノード10は、その接続情報パケットを送信する(S601)。
【0046】
利用者ノード10から送信された接続情報パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した接続情報パケットの宛先アドレスフィールドに格納された2重暗号化アドレスEKa(EKb(C1))を復号できるノードは、秘密鍵Kaを有している中継ノード40aのみであるので、中継ノード40aは接続情報パケットを正式に受信したものとなる。
【0047】
接続情報パケットを受信した中継ノード40aは、接続情報パケットの宛先アドレスフィールドに格納されている2重暗号化アドレスEKa(EKb(C1))を取り出して秘密鍵Kaで復号し、その復号された暗号化アドレスEKb(C1)で宛先アドレスフィールドを更新する(S602)。そして、中継ノード40aは、その更新された接続情報パケットを送信する(S603)。
【0048】
中継ノード40aから送信された接続情報パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した接続情報パケットの宛先アドレスフィールドに格納された暗号化アドレスEKb(C1)を復号できるノードは、秘密鍵Kbを有している中継ノード40bのみであるので、中継ノード40bは接続情報パケットを正式に受信したものとなる。
【0049】
接続情報パケットを受信した中継ノード40bは、接続情報パケットの宛先アドレスフィールドに格納されている暗号化アドレスEKb(C1)を取り出して秘密鍵Kbで復号し、その復号されたアドレスC1で宛先アドレスフィールドを更新する(S604)。そして、中継ノード40bは、その更新された接続情報パケットを送信する(S605)。
【0050】
中継ノード40bから送信された接続情報パケットを受信した計算ノード30aは、接続情報パケットのデータフィールドに格納されたEKa(EKb(C2))及びEKa(EKc(C4))を取り出して部分論理回路記憶部に記憶する(S606)。
【0051】
また、部分論理回路Hの配送先ノードである計算ノード30bも、部分論理回路Hを実行した後は、条件に応じて部分論理回路H又は部分論理回路Iが実行されることになるので、計算ノード30bも、部分論理回路H及び部分論理回路Iを実行する計算ノード30b,30dの暗号化されたアドレスC2,C4を知っている必要がある。このため、利用者ノード10は、EKa(EKb(C2))及びEKa(EKc(C4))を計算ノード30bに送信する。
【0052】
図7に、利用者ノード10が暗号化されたアドレスC2,C4を計算ノード30bに配送する手順を表したシーケンス図を示すが、同図のシーケンス図についての動作の説明は、図6のシーケンス図に基づく動作説明と同様であるため、ここではその詳細説明を省略する。
【0053】
さらにまた、部分論理回路Iの配送先ノードである計算ノード30dは、部分論理回路Iを実行した後は利用者ノードA,Bに実行結果を送信する必要があるため、計算ノード30dは、利用者ノード10,20の暗号化されたアドレスA,Bを知っている必要がある。このため、利用者ノード10は、アドレスAを匿名通信機能を用いて暗号化しながら計算ノード30dに送信する。また、利用者ノード20も、アドレスBを匿名通信機能を用いて暗号化しながら計算ノード30dに送信する。
【0054】
図8に、利用者ノード10が自身のアドレスを計算ノード30dに配送する手順を表したシーケンス図を示して具体的に説明する。同図において、利用者ノード10は、宛先アドレスフィールドに暗号化されたアドレスであるEKa(EKc(C4))を格納し、送信元アドレスフィールドに自身のアドレスAを格納した接続情報パケットを生成する。そして、利用者ノード10は、その接続情報パケットを送信する(S801)。
【0055】
利用者ノード10から送信された接続情報パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した接続情報パケットの宛先アドレスフィールドに格納された2重暗号化アドレスEKa(EKc(C4))を復号できるノードは、秘密鍵Kaを有している中継ノード40aのみであるので、中継ノード40aが接続情報パケットを正式に受信したものとなる。
【0056】
接続情報パケットを正式に受信した中継ノード40aは、接続情報パケットの宛先アドレスフィールドに格納されている2重暗号化アドレス(暗号化宛先アドレス情報)EKa(EKc(C4))を取り出して秘密鍵Kaで復号し、その復号された暗号化アドレスEKc(C4)で宛先アドレスフィールドを更新する。そして、送信元アドレスフィールドに格納されている送信元アドレス情報であるアドレスAを取り出して秘密鍵Kaで暗号化し、そのアドレスAの暗号化アドレスであるEKa(A)で送信元アドレスフィールドを更新する(S802)。
【0057】
次に、中継ノード40aは、その更新された接続情報パケットを送信する(S803)。中継ノード40aから送信された接続情報パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した接続情報パケットの宛先アドレスフィールドに格納された暗号化アドレスEKc(C4)を復号できるノードは、秘密鍵Kcを有している中継ノード40cのみであるので、中継ノード40cが接続情報パケットを正式に受信したものとなる。
【0058】
接続情報パケットを正式に受信した中継ノード40cは、接続情報パケットの宛先アドレスフィールドに格納されている暗号化アドレスEKc(C4)を取り出して秘密鍵Kcで復号し、その復号されたアドレスC4で宛先アドレスフィールドを更新する。そして、送信元アドレスフィールドに格納されている暗号化アドレスEKa(A)を取り出して秘密鍵Kcで暗号化し、その暗号化アドレスEKa(A)の2重暗号化アドレスであるEKc(EKa(A))で送信元アドレスフィールドを更新する(S804)。
【0059】
次に、中継ノード40cは、その更新された接続情報パケットを送信し、計算ノード30dはこれを受信する(S805)。そして、接続情報パケットを受信した計算ノード30dは、接続情報パケットの送信元アドレスフィールドに格納されている2重暗号化アドレスEKc(EKa(A))を部分論理回路記憶部に記憶する(S806)。
【0060】
次に、図9に、利用者ノード20が自身のアドレスを計算ノード30dに配送する手順を表したシーケンス図を示すが、ステップS901−S906の処理については、図8のシーケンス図におけるS801−S806の処理と同様であるため、ここではその詳細説明を省略する。ステップS906の処理に続けて、利用者ノード10は、部分論理回路Gとこれの配送先アドレスが暗号化されたEKa(EKb(C1))との組み合わせ、部分論理回路Hとこれの配送先アドレスが暗号化されたEKa(EKb(C2))との組み合わせ、及び部分論理回路Iとこれの配送先アドレスが暗号化されたEKa(EKc(C4))との組み合わせを、利用者ノード20に対して送信する。そして、利用者ノード20は、これらを受信して部分論理回路記憶部に記憶する(S907)。
【0061】
以上により、計算ノード30a,30bは、部分論理回路H,Iの所在アドレスC2,C4を暗号化したEKa(EKb(C2)),EKa(EKc(C4))をそれぞれの部分論理回路記憶部に記憶し、計算ノード30dは、利用者ノード10,20の所在アドレスA,Bを暗号化したEKc(EKa(A)),EKc(EKa(B))を部分論理回路記憶部に記憶する。
【0062】
[第2フェーズの動作説明]
第2フェーズでは、利用者ノード10,20に入力値d1,d2が入力されることにより、分散計算処理システム1が処理対象プログラムf(d1,d2)を実行し、その最終的な結果を利用者ノード10,20に供給する処理が実行される。図10−図12に、分散計算処理システム1が実行する秘密分散計算処理の第2フェーズの動作を表したシーケンス図を示し、これらを併せ参照して分散計算処理システム1の第2フェーズの動作を説明する。
【0063】
図10において、第2フェーズでは、まず利用者P1の入力操作によって入力値d1が利用者ノード10に入力される(S1001)。次に、利用者ノード10は、宛先アドレスフィールドに部分論理回路Gの所在する暗号化アドレスであるEKa(EKb(C1))を格納し、データフィールドに入力値d1を格納したデータパケットを生成する。そして、利用者ノード10は、そのデータパケットを送信する(S1002)。
【0064】
利用者ノード10から送信されたデータパケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信したデータパケットの宛先アドレスフィールドに格納された2重暗号化アドレスEKa(EKb(C1))を復号できるノードは、秘密鍵Kaを有している中継ノード40aのみであるので、中継ノード40aは接続情報パケットを正式に受信したものとなる。
【0065】
データパケットを受信した中継ノード40aは、データパケットの宛先アドレスフィールドに格納されている2重暗号化アドレスEKa(EKb(C1))を取り出して秘密鍵Kaで復号し、その復号された暗号化アドレスEKb(C1)で宛先アドレスフィールドを更新する(S1003)。そして、中継ノード40aは、その更新されたデータパケットを送信する(S1004)。
【0066】
中継ノード40aから送信されたデータパケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した接続情報パケットの宛先アドレスフィールドに格納された暗号化アドレスEKb(C1)を復号できるノードは、秘密鍵Kbを有している中継ノード40bのみであるので、中継ノード40bは接続情報パケットを正式に受信したものとなる。
【0067】
データパケットを受信した中継ノード40bは、接続情報パケットの宛先アドレスフィールドに格納されている暗号化アドレスEKb(C1)を取り出して秘密鍵Kbで復号し、その復号されたアドレスC1で宛先アドレスフィールドを更新する(S1005)。そして、中継ノード40bは、その更新されたデータパケットを送信する。そして、中継ノード40bから送信されたデータパケットを受信した計算ノード30aは、データパケットのデータフィールドに格納された入力値d1を取り出して部分論理回路記憶部に記憶する(S1006)。
【0068】
利用者ノード20側についても、同様の処理が実行される。すなわち、利用者P2の入力操作によって入力値d2が利用者ノード20に入力されると(S1011)、ステップS1002−S1006の処理と同様の処理が実行される(S1012−S1016)。
【0069】
部分論理回路Gが配置された計算ノード30aに、処理対象プログラムf(a,b)の入力値であるa=d1,b=d2が配送されたのち、計算ノード30aは入力値d1,d2を用いた部分論理回路Gの処理を実行して中間出力値G(d1,d2)を出力する(S1017)。計算ノード30における部分論理回路Gの処理においては、部分論理回路G及び中間出力値G(d1,d2)は暗号化されていないため、図2に示した処理対象プログラムf(a,b)のフローチャートにおける所定の条件について容易に判定処理を行うことができ、それに伴う分岐処理を適切に行うことができる。
【0070】
次に、部分論理回路Gからの中間出力値G(d1,d2)に基づく所定の条件の判定結果がFALSEであった場合についての秘密分散計算処理のフローチャートを図11に示してその動作を説明する。条件の判定結果がFALSEである場合、次に実行される部分論理回路は部分論理回路Iである。よって、同図に示すように、計算ノード30aは、宛先アドレスフィールドに部分論理回路Iの所在する暗号化アドレスであるEKa(EKc(C4))を格納し、データフィールドに中間出力値G(d1,d2)を格納したデータパケットを生成する。そして、計算ノード30aは、そのデータパケットを送信する(S1101)。
【0071】
そして、図10に示したシーケンスと同様なシーケンスの匿名通信を行うことにより、中間出力値G(d1,d2)は計算ノード30dに配送される(S1102−S1105)。部分論理回路Iが配置された計算ノード30dに、処理対象プログラムf(d1,d2)の中間出力値G(d1,d2)が配送されたのち、計算ノード30dは中間出力値G(d1,d2)を入力値として用いた部分論理回路Iの処理を実行して最終出力値f(d1,d2)を出力する(S1106)。
【0072】
次に、部分論理回路Iからの最終出力値f(d1,d2)を利用者ノード10,20にそれぞれ配送する動作について、図12にフローチャートを示して説明する。同図に示すように、まず計算ノード30dは、宛先アドレスフィールドに利用者ノード10の所在する暗号化アドレスであるEKc(EKa(A))を格納し、データフィールドに最終出力値f(d1,d2)を格納したデータパケットを生成する。そして、計算ノード30dは、そのデータパケットを送信する(S1201)。そして、図10に示したシーケンスと同様なシーケンスの匿名通信を行うことにより、最終出力値f(d1,d2)は利用者ノード10に配送される(S1202−S1205)。そして、利用者ノード10は、最終出力値f(d1,d2)を取得する(S1206)。
【0073】
同様にして、計算ノード30dは、最終出力値f(d1,d2)を利用者ノード20に配送し、利用者ノード20はこれを取得する(S1211−S1216)。
【0074】
以上、本実施形態の分散計算処理システムの動作について説明したが、この分散計算処理システムで用いる部分論理回路G,H,Iはそれぞれ暗号化されていないため、盗聴による計算の秘匿性が問題となる。n台の計算ノードのうち、m台(但し、n>m)の計算ノードが、悪意のある盗聴者PEによって盗聴されたとする。盗聴者PEは、盗聴している計算ノードについての各状態、具体的には、他のノードとの間でやり取りされる入出力値やメモリの内容を取得することができるものとする。これによれば、盗聴者PEは、n個の部分論理回路のうち、m個の部分論理回路の入力値を観測することができる。但し、通信は匿名化されているので、盗聴者PEは、観測した部分論理回路の入力値が、元の論理回路全体のうちどこの部分論理回路であるかを特定することができない。したがって、盗聴者PEは、元のn個の値のうち、その一部分であるm個を、順番が不明な状態で観測しているのと同等である。
【0075】
これは、kビットの入力とs×mビットの出力を有する情報チャネルと置き換えて考えることができる。これにおいて、順序が不明でその一部しか観測できないということは、通信路にノイズが存在することに相当する。ノイズの存在する通信路では、そこに入力されたkビットの情報の全ては伝送されず、ノイズの分だけ減少した情報量eビット(e<k)が伝送される。これにより、盗聴者PEが、秘密情報である入力値d1,d2に関して得ることのできる情報量eビットをkビットよりも小さくすることができる。よって、さらに部分論理回路をより細かく分割する(すなわち、nを大きくする)ことにより、ノイズ成分を大きくし、eビットをより小さくすることができる。したがって、利用者ノードは、必要や用途に応じて分割数nを増減して所望の秘匿性を確保することができる。
【0076】
以上、詳述したとおり、本実施形態によれば、処理対象プログラムが論理回路に変換され、さらに複数の部分論理回路に分割されて匿名通信機能及びランダム通信機能によって複数の計算ノードに配置される。これによって、配送元及び配送先は互いのアドレスを知ることができず、配信元はどの部分論理回路がどこの計算ノードに配置されたかを知ることができない。また、全てのパケットの通信は、暗号化されたアドレスによって行われるため、通信経路中で中継される中継ノードも入出力両方のアドレスを知ることができない。これにより、ネットワーク50のノードの一部が盗聴されたとしても各ノードの通信接続関係が不明であるため、情報の秘匿性を確保することができる。
【0077】
また、本実施形態によれば、部分論理回路自体や部分論理回路の入出力値は暗号化されない状態で処理されるため、部分論理回路を選択的に処理したり条件分岐処理をしたりすることが容易に行える。よって、従来のように、全ての選択肢を処理させていたような非効率な処理をする必要がないため、リソース消費を経済的に抑えることができるとともに処理効率を飛躍的に改善することができる。
【0078】
なお、本発明の実施形態による分散計算処理装置の処理を実行させるための分散計算処理用プログラムをコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませて実行させることにより、本実施形態による分散計算処理を行うようにしてもよい。なお、ここでいうコンピュータシステムとは、オペレーティングシステムや周辺機器等のハードウェアを含むものであってもよい。また、コンピュータシステムは、WWWシステムを利用している場合であれば、ホームページ提供環境(あるいは表示環境)も含むものとする。また、コンピュータ読み取り可能な記録媒体とは、フレキシブルディスク、光磁気ディスク、ROM、フラッシュメモリ等の書き込み可能な不揮発性メモリ、CD−ROM等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【0079】
さらにコンピュータ読み取り可能な記録媒体は、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ(例えばDRAM)のように、一定時間プログラムを保持しているものも含むものとする。また、上記のプログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する伝送媒体は、インターネット等のネットワーク(通信網)や電話回線等の通信回線(通信線)のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル(差分プログラム)であっても良い。
【0080】
以上、本発明の実施形態について詳述したが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【0081】
1 分散計算処理システム
10,20 利用者ノード
30a,30b,30c,30d 計算ノード
40a,40b,40c 中継ノード
50 ネットワーク
d1,d2 入力値
Ka,Kb,Kc 秘密鍵
P1,P2 利用者
【特許請求の範囲】
【請求項1】
複数の中継ノードを含むネットワークに利用者ノードが接続され、前記利用者ノードに入力された入力情報を用いて処理対象プログラムの分散計算処理を行う分散計算処理システムにおいて、
前記ネットワークには、複数の計算ノードが接続され、
前記利用者ノードは、
前記処理対象プログラムを論理回路に変換して複数の部分論理回路に分割する論理回路分割手段と、
前記分割された部分論理回路をデータフィールドに格納するとともに、利用者ノードアドレス情報を送信元アドレスフィールドに格納したパケットを送信する部分論理回路送信手段と、
前記複数の中継ノードのうちいずれかの中継ノードから送信されたパケットを受信し、それの送信元アドレスフィールドに格納された暗号化計算ノードアドレス情報を取り出して記憶する計算ノードアドレス情報記憶手段と、
前記入力情報をデータフィールドに格納し、前記記憶された暗号化計算ノードアドレス情報を宛先アドレスフィールドに格納したパケットを送信する入力情報送信手段と、
を備え、
前記複数の中継ノードそれぞれは、
到来したパケットを受信して、それの宛先アドレスフィールドの指定のない場合は、送信元アドレスフィールドに格納された所定の送信元アドレス情報を暗号化して前記パケットを更新し、所定の確率に基づいて他の中継ノード及び前記複数の計算ノードのうちいずれか一のノードを選択して、前記更新されたパケットを送信する匿名ランダム中継手段と、
到来したパケットを受信して、それの宛先アドレスフィールドに所定の暗号化宛先アドレス情報が格納されている場合は、その所定の暗号化宛先アドレス情報を復号し、さらに送信元アドレスフィールドに所定の送信元アドレス情報が格納されている場合にはその所定の送信元アドレス情報を暗号化して前記パケットを更新し送信する匿名中継手段と、
を備え、
前記複数の計算ノードそれぞれは、
前記複数の中継ノードのうちいずれかの中継ノードの匿名ランダム中継手段から送信されたパケットを受信し、それのデータフィールドに格納された部分論理回路を取り出して記憶する部分論理回路記憶手段と、
該計算ノードの計算ノードアドレス情報を送信元アドレスフィールドに格納するとともに、前記部分論理回路記憶手段において受信したパケットの送信元アドレスフィールドに格納された暗号化利用者ノードアドレス情報を宛先アドレスフィールドに格納したパケットを送信する応答送信手段と、
前記複数の中継ノードのうちいずれかの中継ノードの匿名中継手段から送信されたパケットを受信し、それのデータフィールドに格納された入力情報を取り出して、前記記憶された部分論理回路に入力して計算する計算処理手段と、
を備えたことを特徴とする分散計算処理システム。
【請求項2】
複数の中継ノードを含むネットワークを介して利用者ノードと複数の計算ノードとが接続され、前記利用者ノードに入力された入力情報を用いて前記複数の計算ノードに処理対象プログラムの分散計算処理を行わせる分散計算処理方法であって、
前記利用者ノードが、
前記処理対象プログラムを論理回路に変換して複数の部分論理回路に分割する論理回路分割ステップと、
前記分割された部分論理回路をデータフィールドに格納するとともに、利用者ノードアドレス情報を送信元アドレスフィールドに格納した部分論理回路パケットを送信する部分論理回路送信ステップと、
前記複数の中継ノードのうちいずれかが、
前記送信された部分論理回路パケットを受信し、それの送信元アドレスフィールドに格納された利用者ノードアドレス情報を暗号化して前記部分論理回路パケットを更新し、所定の確率に基づいて他の中継ノード及び前記複数の計算ノードのうちいずれか一のノードを選択して、前記更新された部分論理回路パケットを送信する匿名ランダム中継ステップと、
前記複数の計算ノードのうち、部分論理回路パケットの到来した計算ノードが、
前記部分論理回路パケットを受信し、それのデータフィールドに格納された部分論理回路を取り出して記憶する部分論理回路記憶ステップと、
前記計算ノードの計算ノードアドレス情報を送信元アドレスフィールドに格納するとともに、前記部分論理回路記憶ステップにおいて受信した部分論理回路パケットの送信元アドレスフィールドに格納された暗号化利用者ノードアドレス情報を宛先アドレスフィールドに格納した応答パケットを送信する応答送信ステップと、
前記複数の中継ノードのうち前記送信された応答パケットの到来した中継ノードが、
前記応答パケットを受信し、それの宛先アドレスフィールドに格納された暗号化利用者ノードアドレス情報を復号できた場合に、送信元アドレスフィールドに格納された計算ノードアドレス情報を暗号化して前記応答パケットを更新し送信する応答中継ステップと、
前記利用者ノードが、
前記複数の中継ノードのうちいずれかの中継ノードから送信された応答パケットを受信し、それの送信元アドレスフィールドに格納された暗号化計算ノードアドレス情報を取り出して記憶する計算ノードアドレス情報記憶ステップと、
前記入力情報をデータフィールドに格納し、前記記憶された暗号化計算ノードアドレス情報を宛先アドレスフィールドに格納したデータパケットを送信する入力情報送信ステップと、
前記複数の中継ノードのうち前記送信されたデータパケットの到来した中継ノードが、
前記データパケットを受信し、それの宛先アドレスフィールドに格納された暗号化計算ノードアドレス情報を復号できた場合に、前記データパケットを更新して送信するデータ中継ステップと、
前記送信されたデータパケットを受信した計算ノードが、
それのデータフィールドに格納された入力情報を取り出して、前記記憶された部分論理回路に入力して計算する計算処理ステップと、
を有したことを特徴とする分散計算処理方法。
【請求項1】
複数の中継ノードを含むネットワークに利用者ノードが接続され、前記利用者ノードに入力された入力情報を用いて処理対象プログラムの分散計算処理を行う分散計算処理システムにおいて、
前記ネットワークには、複数の計算ノードが接続され、
前記利用者ノードは、
前記処理対象プログラムを論理回路に変換して複数の部分論理回路に分割する論理回路分割手段と、
前記分割された部分論理回路をデータフィールドに格納するとともに、利用者ノードアドレス情報を送信元アドレスフィールドに格納したパケットを送信する部分論理回路送信手段と、
前記複数の中継ノードのうちいずれかの中継ノードから送信されたパケットを受信し、それの送信元アドレスフィールドに格納された暗号化計算ノードアドレス情報を取り出して記憶する計算ノードアドレス情報記憶手段と、
前記入力情報をデータフィールドに格納し、前記記憶された暗号化計算ノードアドレス情報を宛先アドレスフィールドに格納したパケットを送信する入力情報送信手段と、
を備え、
前記複数の中継ノードそれぞれは、
到来したパケットを受信して、それの宛先アドレスフィールドの指定のない場合は、送信元アドレスフィールドに格納された所定の送信元アドレス情報を暗号化して前記パケットを更新し、所定の確率に基づいて他の中継ノード及び前記複数の計算ノードのうちいずれか一のノードを選択して、前記更新されたパケットを送信する匿名ランダム中継手段と、
到来したパケットを受信して、それの宛先アドレスフィールドに所定の暗号化宛先アドレス情報が格納されている場合は、その所定の暗号化宛先アドレス情報を復号し、さらに送信元アドレスフィールドに所定の送信元アドレス情報が格納されている場合にはその所定の送信元アドレス情報を暗号化して前記パケットを更新し送信する匿名中継手段と、
を備え、
前記複数の計算ノードそれぞれは、
前記複数の中継ノードのうちいずれかの中継ノードの匿名ランダム中継手段から送信されたパケットを受信し、それのデータフィールドに格納された部分論理回路を取り出して記憶する部分論理回路記憶手段と、
該計算ノードの計算ノードアドレス情報を送信元アドレスフィールドに格納するとともに、前記部分論理回路記憶手段において受信したパケットの送信元アドレスフィールドに格納された暗号化利用者ノードアドレス情報を宛先アドレスフィールドに格納したパケットを送信する応答送信手段と、
前記複数の中継ノードのうちいずれかの中継ノードの匿名中継手段から送信されたパケットを受信し、それのデータフィールドに格納された入力情報を取り出して、前記記憶された部分論理回路に入力して計算する計算処理手段と、
を備えたことを特徴とする分散計算処理システム。
【請求項2】
複数の中継ノードを含むネットワークを介して利用者ノードと複数の計算ノードとが接続され、前記利用者ノードに入力された入力情報を用いて前記複数の計算ノードに処理対象プログラムの分散計算処理を行わせる分散計算処理方法であって、
前記利用者ノードが、
前記処理対象プログラムを論理回路に変換して複数の部分論理回路に分割する論理回路分割ステップと、
前記分割された部分論理回路をデータフィールドに格納するとともに、利用者ノードアドレス情報を送信元アドレスフィールドに格納した部分論理回路パケットを送信する部分論理回路送信ステップと、
前記複数の中継ノードのうちいずれかが、
前記送信された部分論理回路パケットを受信し、それの送信元アドレスフィールドに格納された利用者ノードアドレス情報を暗号化して前記部分論理回路パケットを更新し、所定の確率に基づいて他の中継ノード及び前記複数の計算ノードのうちいずれか一のノードを選択して、前記更新された部分論理回路パケットを送信する匿名ランダム中継ステップと、
前記複数の計算ノードのうち、部分論理回路パケットの到来した計算ノードが、
前記部分論理回路パケットを受信し、それのデータフィールドに格納された部分論理回路を取り出して記憶する部分論理回路記憶ステップと、
前記計算ノードの計算ノードアドレス情報を送信元アドレスフィールドに格納するとともに、前記部分論理回路記憶ステップにおいて受信した部分論理回路パケットの送信元アドレスフィールドに格納された暗号化利用者ノードアドレス情報を宛先アドレスフィールドに格納した応答パケットを送信する応答送信ステップと、
前記複数の中継ノードのうち前記送信された応答パケットの到来した中継ノードが、
前記応答パケットを受信し、それの宛先アドレスフィールドに格納された暗号化利用者ノードアドレス情報を復号できた場合に、送信元アドレスフィールドに格納された計算ノードアドレス情報を暗号化して前記応答パケットを更新し送信する応答中継ステップと、
前記利用者ノードが、
前記複数の中継ノードのうちいずれかの中継ノードから送信された応答パケットを受信し、それの送信元アドレスフィールドに格納された暗号化計算ノードアドレス情報を取り出して記憶する計算ノードアドレス情報記憶ステップと、
前記入力情報をデータフィールドに格納し、前記記憶された暗号化計算ノードアドレス情報を宛先アドレスフィールドに格納したデータパケットを送信する入力情報送信ステップと、
前記複数の中継ノードのうち前記送信されたデータパケットの到来した中継ノードが、
前記データパケットを受信し、それの宛先アドレスフィールドに格納された暗号化計算ノードアドレス情報を復号できた場合に、前記データパケットを更新して送信するデータ中継ステップと、
前記送信されたデータパケットを受信した計算ノードが、
それのデータフィールドに格納された入力情報を取り出して、前記記憶された部分論理回路に入力して計算する計算処理ステップと、
を有したことを特徴とする分散計算処理方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【公開番号】特開2010−231516(P2010−231516A)
【公開日】平成22年10月14日(2010.10.14)
【国際特許分類】
【出願番号】特願2009−78483(P2009−78483)
【出願日】平成21年3月27日(2009.3.27)
【出願人】(000208891)KDDI株式会社 (2,700)
【出願人】(508098291)
【Fターム(参考)】
【公開日】平成22年10月14日(2010.10.14)
【国際特許分類】
【出願日】平成21年3月27日(2009.3.27)
【出願人】(000208891)KDDI株式会社 (2,700)
【出願人】(508098291)
【Fターム(参考)】
[ Back to top ]