(57)【要約】【課題】従来の分散計算処理においては、処理効率が悪く汎用的な処理対象プログラムに適用することが容易ではなかった。【解決手段】中継ノード４０ａ，４０ｂ，４０ｃを含むネットワーク５０を介して利用者ノード１０，２０と計算ノード３０ａ，３０ｂ，３０ｃ，３０ｄとがそれぞれ接続され、利用者ノード１０，２０から入力された入力値ｄ１，ｄ２を用いて、計算ノード３０ａ，３０ｂ，３０ｃ，３０ｄに処理対象プログラムの分散計算処理を行わせる。これにおいて、利用者ノード１０は処理対象プログラムを３つの部分論理回路に分割して送信する。中継ノード４０ａ，４０ｂ，４０ｃは匿名通信及びランダム通信により部分論理回路を計算ノードに所在を秘匿して配置する。利用者ノード１０，２０は入力値ｄ１，ｄ２を計算ノード３０ａに配送し、部分論理回路が分散配置された計算ノード３０ａ，３０ｂ，３０ｄは協働して計算処理を実行する。【選択図】図１
2010231516.tif 000002
【特許請求の範囲】
【請求項１】
複数の中継ノードを含むネットワークに利用者ノードが接続され、前記利用者ノードに入力された入力情報を用いて処理対象プログラムの分散計算処理を行う分散計算処理システムにおいて、
前記ネットワークには、複数の計算ノードが接続され、
前記利用者ノードは、
前記処理対象プログラムを論理回路に変換して複数の部分論理回路に分割する論理回路分割手段と、
前記分割された部分論理回路をデータフィールドに格納するとともに、利用者ノードアドレス情報を送信元アドレスフィールドに格納したパケットを送信する部分論理回路送信手段と、
前記複数の中継ノードのうちいずれかの中継ノードから送信されたパケットを受信し、それの送信元アドレスフィールドに格納された暗号化計算ノードアドレス情報を取り出して記憶する計算ノードアドレス情報記憶手段と、
前記入力情報をデータフィールドに格納し、前記記憶された暗号化計算ノードアドレス情報を宛先アドレスフィールドに格納したパケットを送信する入力情報送信手段と、
を備え、
前記複数の中継ノードそれぞれは、
到来したパケットを受信して、それの宛先アドレスフィールドの指定のない場合は、送信元アドレスフィールドに格納された所定の送信元アドレス情報を暗号化して前記パケットを更新し、所定の確率に基づいて他の中継ノード及び前記複数の計算ノードのうちいずれか一のノードを選択して、前記更新されたパケットを送信する匿名ランダム中継手段と、
到来したパケットを受信して、それの宛先アドレスフィールドに所定の暗号化宛先アドレス情報が格納されている場合は、その所定の暗号化宛先アドレス情報を復号し、さらに送信元アドレスフィールドに所定の送信元アドレス情報が格納されている場合にはその所定の送信元アドレス情報を暗号化して前記パケットを更新し送信する匿名中継手段と、
を備え、
前記複数の計算ノードそれぞれは、
前記複数の中継ノードのうちいずれかの中継ノードの匿名ランダム中継手段から送信されたパケットを受信し、それのデータフィールドに格納された部分論理回路を取り出して記憶する部分論理回路記憶手段と、
該計算ノードの計算ノードアドレス情報を送信元アドレスフィールドに格納するとともに、前記部分論理回路記憶手段において受信したパケットの送信元アドレスフィールドに格納された暗号化利用者ノードアドレス情報を宛先アドレスフィールドに格納したパケットを送信する応答送信手段と、
前記複数の中継ノードのうちいずれかの中継ノードの匿名中継手段から送信されたパケットを受信し、それのデータフィールドに格納された入力情報を取り出して、前記記憶された部分論理回路に入力して計算する計算処理手段と、
を備えたことを特徴とする分散計算処理システム。
【請求項２】
複数の中継ノードを含むネットワークを介して利用者ノードと複数の計算ノードとが接続され、前記利用者ノードに入力された入力情報を用いて前記複数の計算ノードに処理対象プログラムの分散計算処理を行わせる分散計算処理方法であって、
前記利用者ノードが、
前記処理対象プログラムを論理回路に変換して複数の部分論理回路に分割する論理回路分割ステップと、
前記分割された部分論理回路をデータフィールドに格納するとともに、利用者ノードアドレス情報を送信元アドレスフィールドに格納した部分論理回路パケットを送信する部分論理回路送信ステップと、
前記複数の中継ノードのうちいずれかが、
前記送信された部分論理回路パケットを受信し、それの送信元アドレスフィールドに格納された利用者ノードアドレス情報を暗号化して前記部分論理回路パケットを更新し、所定の確率に基づいて他の中継ノード及び前記複数の計算ノードのうちいずれか一のノードを選択して、前記更新された部分論理回路パケットを送信する匿名ランダム中継ステップと、
前記複数の計算ノードのうち、部分論理回路パケットの到来した計算ノードが、
前記部分論理回路パケットを受信し、それのデータフィールドに格納された部分論理回路を取り出して記憶する部分論理回路記憶ステップと、
前記計算ノードの計算ノードアドレス情報を送信元アドレスフィールドに格納するとともに、前記部分論理回路記憶ステップにおいて受信した部分論理回路パケットの送信元アドレスフィールドに格納された暗号化利用者ノードアドレス情報を宛先アドレスフィールドに格納した応答パケットを送信する応答送信ステップと、
前記複数の中継ノードのうち前記送信された応答パケットの到来した中継ノードが、
前記応答パケットを受信し、それの宛先アドレスフィールドに格納された暗号化利用者ノードアドレス情報を復号できた場合に、送信元アドレスフィールドに格納された計算ノードアドレス情報を暗号化して前記応答パケットを更新し送信する応答中継ステップと、
前記利用者ノードが、
前記複数の中継ノードのうちいずれかの中継ノードから送信された応答パケットを受信し、それの送信元アドレスフィールドに格納された暗号化計算ノードアドレス情報を取り出して記憶する計算ノードアドレス情報記憶ステップと、
前記入力情報をデータフィールドに格納し、前記記憶された暗号化計算ノードアドレス情報を宛先アドレスフィールドに格納したデータパケットを送信する入力情報送信ステップと、
前記複数の中継ノードのうち前記送信されたデータパケットの到来した中継ノードが、
前記データパケットを受信し、それの宛先アドレスフィールドに格納された暗号化計算ノードアドレス情報を復号できた場合に、前記データパケットを更新して送信するデータ中継ステップと、
前記送信されたデータパケットを受信した計算ノードが、
それのデータフィールドに格納された入力情報を取り出して、前記記憶された部分論理回路に入力して計算する計算処理ステップと、
を有したことを特徴とする分散計算処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークを介して接続された複数の計算ノードに一つの処理対象プログラムを計算処理させる分散計算処理技術に関する。
【背景技術】
【０００２】
ネットワーク上に分散した複数の情報処理装置が、協働して一つの関数の計算処理を行う分散計算処理技術が知られている。この分散計算処理技術においては、各情報処理装置のセキュリティの観点から、またユーザのプライバシーの観点から、入力情報を秘密にしたままで計算処理を行いたいという要望があり、様々な研究や技術的試みが行われてきた。例えば、計算すべき関数を論理回路として表すことができる場合、秘匿性のある分散計算処理（秘密分散計算処理）についての情報処理装置間の通信プロトコルを規定して実現する方法が知られている（例えば、非特許文献１参照）。また、電子投票システム等の特定のケースを対象としたものについては、情報処理装置の秘匿性を保ちながら効率よく計算する方法が知られている（例えば、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｖｏｌｕｍｅ  ＩＩ  Ｂａｓｉｃ  Ａｐｐｌｉｃａｔｉｏｎｓ，Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，Ｍａｙ  １０，２００４．
【非特許文献２】岡本龍明、山本博資著、「シリーズ／情報科学の数学  現代暗号」、産業図書、１９９７年
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、一般的なプログラムを論理回路として表し、非特許文献１に記載された技術を用いて秘密分散計算処理を行うと処理効率が悪く実用的ではない。ここで、非特許文献１記載の秘密分散計算処理の方法について、関係する部分の概略を説明する。この秘密分散計算処理では、実行すべきプログラムを論理回路に変換したものを、主に暗号理論分野において知られているＧａｒｂｌｅｄ  Ｃｉｒｃｕｉｔ（ＧＣ）に変換して用いる。このＧＣは、例えば論理ゲートレベルで内部ロジックを秘匿したまま論理演算を行うものであり、ＧＣの入出力は乱数のキーとして表される。ＧＣでは、正しい入力キーを有する者だけが、そのキーに対応付けられた入力値の論理演算の結果に対応する出力キーを得ることができる。
【０００５】
このようにして、非特許文献１記載の秘密分散計算処理方法では、論理回路の構成に応じたＧＣの組み合わせによって論理回路全体の秘匿性を保つことはできるが、論理回路の各論理ゲートの論理値が分からない状態で計算を行うため、途中の計算結果の状態に応じて選択的な処理（すなわち、通常のプログラムにおける条件分岐処理）を簡単に行うことができない。これを実現するためには、ＧＣ化される論理回路は、条件分岐処理に係る回路を、想定される全ての条件についての分岐処理を実行させるように構成しなければならず、プログラムによってはリソースが多く必要になり処理効率が悪くなるおそれが大きい。
【０００６】
また、非特許文献２に記載されたような特定の問題に特化した方法では、問題ごとに暗号理論の専門家によるプロトコル設計がされなければならず、汎用的なプログラムには適用できない。
【０００７】
そこで、本発明は上記問題に鑑みてなされたものであり、相互に秘匿性を保ちながら処理対象プログラムの分散計算処理を実行させる場合に、処理効率に優れ且つ汎用的な処理対象プログラムに適用することが容易な、分散計算処理システム及び分散計算処理方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、上記の課題を解決するために、以下［１］，［２］の手段を提供するものである。
［１］  複数の中継ノードを含むネットワークに利用者ノードが接続され、前記利用者ノードに入力された入力情報を用いて処理対象プログラムの分散計算処理を行う分散計算処理システムにおいて、
前記ネットワークには、複数の計算ノードが接続され、
前記利用者ノードは、
前記処理対象プログラムを論理回路に変換して複数の部分論理回路に分割する論理回路分割手段と、
前記分割された部分論理回路をデータフィールドに格納するとともに、利用者ノードアドレス情報を送信元アドレスフィールドに格納したパケットを送信する部分論理回路送信手段と、
前記複数の中継ノードのうちいずれかの中継ノードから送信されたパケットを受信し、それの送信元アドレスフィールドに格納された暗号化計算ノードアドレス情報を取り出して記憶する計算ノードアドレス情報記憶手段と、
前記入力情報をデータフィールドに格納し、前記記憶された暗号化計算ノードアドレス情報を宛先アドレスフィールドに格納したパケットを送信する入力情報送信手段と、
を備え、
前記複数の中継ノードそれぞれは、
到来したパケットを受信して、それの宛先アドレスフィールドの指定のない場合は、送信元アドレスフィールドに格納された所定の送信元アドレス情報を暗号化して前記パケットを更新し、所定の確率に基づいて他の中継ノード及び前記複数の計算ノードのうちいずれか一のノードを選択して、前記更新されたパケットを送信する匿名ランダム中継手段と、
到来したパケットを受信して、それの宛先アドレスフィールドに所定の暗号化宛先アドレス情報が格納されている場合は、その所定の暗号化宛先アドレス情報を復号し、さらに送信元アドレスフィールドに所定の送信元アドレス情報が格納されている場合にはその所定の送信元アドレス情報を暗号化して前記パケットを更新し送信する匿名中継手段と、
を備え、
前記複数の計算ノードそれぞれは、
前記複数の中継ノードのうちいずれかの中継ノードの匿名ランダム中継手段から送信されたパケットを受信し、それのデータフィールドに格納された部分論理回路を取り出して記憶する部分論理回路記憶手段と、
該計算ノードの計算ノードアドレス情報を送信元アドレスフィールドに格納するとともに、前記部分論理回路記憶手段において受信したパケットの送信元アドレスフィールドに格納された暗号化利用者ノードアドレス情報を宛先アドレスフィールドに格納したパケットを送信する応答送信手段と、
前記複数の中継ノードのうちいずれかの中継ノードの匿名中継手段から送信されたパケットを受信し、それのデータフィールドに格納された入力情報を取り出して、前記記憶された部分論理回路に入力して計算する計算処理手段と、
を備えたことを特徴とする分散計算処理システム。
［２］  複数の中継ノードを含むネットワークを介して利用者ノードと複数の計算ノードとが接続され、前記利用者ノードに入力された入力情報を用いて前記複数の計算ノードに処理対象プログラムの分散計算処理を行わせる分散計算処理方法であって、
前記利用者ノードが、
前記処理対象プログラムを論理回路に変換して複数の部分論理回路に分割する論理回路分割ステップと、
前記分割された部分論理回路をデータフィールドに格納するとともに、利用者ノードアドレス情報を送信元アドレスフィールドに格納した部分論理回路パケットを送信する部分論理回路送信ステップと、
前記複数の中継ノードのうちいずれかが、
前記送信された部分論理回路パケットを受信し、それの送信元アドレスフィールドに格納された利用者ノードアドレス情報を暗号化して前記部分論理回路パケットを更新し、所定の確率に基づいて他の中継ノード及び前記複数の計算ノードのうちいずれか一のノードを選択して、前記更新された部分論理回路パケットを送信する匿名ランダム中継ステップと、
前記複数の計算ノードのうち、部分論理回路パケットの到来した計算ノードが、
前記部分論理回路パケットを受信し、それのデータフィールドに格納された部分論理回路を取り出して記憶する部分論理回路記憶ステップと、
前記計算ノードの計算ノードアドレス情報を送信元アドレスフィールドに格納するとともに、前記部分論理回路記憶ステップにおいて受信した部分論理回路パケットの送信元アドレスフィールドに格納された暗号化利用者ノードアドレス情報を宛先アドレスフィールドに格納した応答パケットを送信する応答送信ステップと、
前記複数の中継ノードのうち前記送信された応答パケットの到来した中継ノードが、
前記応答パケットを受信し、それの宛先アドレスフィールドに格納された暗号化利用者ノードアドレス情報を復号できた場合に、送信元アドレスフィールドに格納された計算ノードアドレス情報を暗号化して前記応答パケットを更新し送信する応答中継ステップと、
前記利用者ノードが、
前記複数の中継ノードのうちいずれかの中継ノードから送信された応答パケットを受信し、それの送信元アドレスフィールドに格納された暗号化計算ノードアドレス情報を取り出して記憶する計算ノードアドレス情報記憶ステップと、
前記入力情報をデータフィールドに格納し、前記記憶された暗号化計算ノードアドレス情報を宛先アドレスフィールドに格納したデータパケットを送信する入力情報送信ステップと、
前記複数の中継ノードのうち前記送信されたデータパケットの到来した中継ノードが、
前記データパケットを受信し、それの宛先アドレスフィールドに格納された暗号化計算ノードアドレス情報を復号できた場合に、前記データパケットを更新して送信するデータ中継ステップと、
前記送信されたデータパケットを受信した計算ノードが、
それのデータフィールドに格納された入力情報を取り出して、前記記憶された部分論理回路に入力して計算する計算処理ステップと、
を有したことを特徴とする分散計算処理方法。
【発明の効果】
【０００９】
本発明によれば、部分論理回路の配置場所を秘匿する一方、部分論理回路自体やこれに入力される入力情報が暗号化されない状態で分散計算処理が実行されるため、処置途中段階での選択的な処理や条件分岐処理を容易に実行することができる。さらに、本発明によれば、汎用的な処理対象プログラムに適用することが容易となる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施形態である分散計算処理システムの概略の構成図である。
【図２】分散計算処理システムが秘密分散計算処理を実行する対象である処理対象プログラムの概略のフローチャートである。
【図３】分散計算処理システムが実行する秘密分散計算処理の第１フェーズの動作のうち、部分論理回路を配送する動作を説明するためのシーケンス図である。
【図４】分散計算処理システムが実行する秘密分散計算処理の第１フェーズの動作のうち、部分論理回路を配送する動作を説明するためのシーケンス図である。
【図５】分散計算処理システムが実行する秘密分散計算処理の第１フェーズの動作のうち、部分論理回路を配送する動作を説明するためのシーケンス図である。
【図６】分散計算処理システムが実行する秘密分散計算処理の第１フェーズの動作のうち、部分論理回路が取得しておくべき情報を配送する動作を説明するためのシーケンス図である。
【図７】分散計算処理システムが実行する秘密分散計算処理の第１フェーズの動作のうち、部分論理回路が取得しておくべき情報を配送する動作を説明するためのシーケンス図である。
【図８】分散計算処理システムが実行する秘密分散計算処理の第１フェーズの動作のうち、部分論理回路が取得しておくべき情報を配送する動作を説明するためのシーケンス図である。
【図９】分散計算処理システムが実行する秘密分散計算処理の第１フェーズの動作のうち、部分論理回路が取得しておくべき情報を配送する動作を説明するためのシーケンス図である。
【図１０】分散計算処理システムが実行する秘密分散計算処理の第２フェーズの動作を説明するためのシーケンス図である。
【図１１】分散計算処理システムが実行する秘密分散計算処理の第２フェーズの動作を説明するためのシーケンス図である。
【図１２】分散計算処理システムが実行する秘密分散計算処理の第２フェーズの動作を説明するためのシーケンス図である。
【発明を実施するための形態】
【００１１】
以下、本発明を実施するための形態について、図面を参照して詳細に説明する。本実施形態では、計算処理の対象となる処理対象プログラムを、２人の利用者がそれぞれ使用する２台の電子計算機から入力された秘密情報である入力値を引数として、これら入力値の秘密性を確保して分散計算処理（秘密分散計算処理）を実行する分散計算処理システムについて説明する。
【００１２】
図１に、本実施形態である分散計算処理システムの概略の構成図を示す。同図において、分散計算処理システム１は、９台のノードを接続したネットワーク５０により構成されており、処理対象プログラムｆ（ａ，ｂ）（ａ，ｂは引数）を計算するものである。ノードとは、ネットワーク５０に接続される電子計算機、ルータ、サーバ等の情報処理装置のことをいい、ノード間での通信を行うことができる。ネットワーク５０に接続された９台のノードの内訳は、利用者Ｐ１及びＰ２によってそれぞれ使用され、処理対象プログラムｆ（ａ，ｂ）に対する入力値が入力されるとともに、秘密分散計算処理により得られた結果が得られる利用者ノード１０，２０と、秘密分散計算処理を行う分散計算処理装置である計算ノード３０ａ，３０ｂ，３０ｃ，３０ｄと、ノードを中継接続する中継ノード４０ａ，４０ｂ，４０ｃとである。
【００１３】
利用者Ｐ１が使用する利用者ノード１０と、利用者Ｐ２が使用する利用者ノード２０とは、コンピュータ等の電子計算機を用いることができる。利用者ノード１０，２０それぞれは、不図示ではあるが、処理対象プログラムを論理回路に変換して複数の部分論理回路に分割するための論理回路分割部と、部分論理回路を該利用者ノードのアドレス情報である利用者ノードアドレス情報とともに部分論理回路パケットとして送信するための部分論理回路送信部と、中継ノード４０ａ，４０ｂ，４０ｃのうちいずれかから送信された応答パケットを受信し、暗号化された計算ノードのアドレス情報（暗号化計算ノードアドレス情報）を取り出して記憶するための計算ノードアドレス情報記憶部と、入力情報ｄ１，ｄ２を暗号化計算ノードアドレス情報とともにデータパケットとして送信するための入力情報送信部とを備えている。利用者ノード１０には、利用者Ｐ１によって秘密情報である入力値ａ＝ｄ１が入力され、利用者ノード２０には、利用者Ｐ２によって秘密情報である入力値ｂ＝ｄ２が入力されるものとする。なお、入力値ｄ１及びｄ２の合計ビット数はｋビットであるとする。また、利用者ノード１０，２０は互いのアドレス情報を知っており、両者間での通信を行うことができる。
【００１４】
ｎ＝４台の計算ノード３０ａ，３０ｂ，３０ｃ，３０ｄのそれぞれも、コンピュータ等の電子計算機を用いることができる。計算ノード３０ａ，３０ｂ，３０ｃ，３０ｄそれぞれは、不図示ではあるが、中継ノード４０ａ，４０ｂ，４０ｃのうちいずれかの中継ノードから送信された部分論理回路パケットを受信し、部分論理回路を取り出して記憶するための部分論理回路記憶部と、その計算ノードの計算ノードアドレス情報と部分論理回路パケットを受信した際の送信元アドレスである暗号化利用者ノードアドレス情報とを含めた応答パケットを送信するための応答送信部と、中継ノード４０ａ，４０ｂ，４０ｃのうちいずれかの中継ノードから送信されたデータパケットを受信し、入力情報を取り出して部分論理回路記憶部に記憶された部分論理回路に入力して計算するための計算処理部とを備えている。
【００１５】
中継ノード４０ａ，４０ｂ，４０ｃはルータを用いることができる。これら中継ノード４０ａ，４０ｂ，４０ｃは、それぞれ秘密鍵Ｋａ，Ｋｂ，Ｋｃを有している。そして、各中継ノード４０ａ，４０ｂ，４０ｃは、中継元から入力されたデータを、自身の秘密鍵Ｋａ，Ｋｂ，Ｋｃで暗号化したり、入力された暗号化データを秘密鍵Ｋａ，Ｋｂ，Ｋｃで復号したりして中継先に出力することができる。中継ノード４０ａ，４０ｂ，４０ｃそれぞれは、不図示ではあるが、到来したパケットを受信して、それに宛先アドレスの指定のない場合は、所定の送信元アドレス情報を自身の秘密鍵で暗号化して該パケットを更新し、例えば後述するランダムウォーク方式に基づいて他の中継ノード及び計算ノード３０ａ，３０ｂ，３０ｃ，３０ｄのうちいずれか一のノードを選択し、更新されたパケットを送信するための匿名ランダム中継部と、到来したパケットを受信して、所定の暗号化宛先アドレス情報が格納されている場合は、それを自身の秘密鍵で復号し、さらに所定の送信元アドレス情報が格納されている場合にはその所定の送信元アドレス情報を自身の秘密鍵で暗号化して該パケットを更新し送信するための匿名中継部とを備えている。匿名ランダム中継部及び匿名中継部の動作については、後に詳細を説明する。
【００１６】
中継ノード４０ａ，４０ｂ，４０ｃを含むネットワーク５０では、盗聴者から送信者と受信者との対応関係を隠すために、暗号化されたアドレス（ネットワーク層のアドレスであり、例えばＩＰアドレス）で指定される匿名の宛先に対してパケットを送信する匿名通信を行うことができる。また、ネットワーク５０では、送信元がどこを送信先としてパケットが送信されたかを不明にさせるために、無作為に選択した宛先に対してパケットを送信するランダム通信を行うことができる。
【００１７】
ここで、中継ノード４０ａ，４０ｂ，４０ｃを含むネットワーク５０で行われる匿名通信の方法について、図１における中継ノード４０ａから中継ノード４０ｂを中継して計算ノード３０ａにパケットを送信する場合を例として説明する。中継ノード４０ａは、入来したパケットに含まれる送信元の始点アドレスを中継ノード４０ａの秘密鍵Ｋａで暗号化し、その暗号化始点アドレスで元の始点アドレスを置き換えたパケットを中継ノード４０ｂに送信する。そして、中継ノード４０ｂは、受信したパケットに含まれる暗号化始点アドレスを中継ノード４０ｂの秘密鍵Ｋｂでさらに暗号化し、その２重に暗号化した２重暗号化始点アドレスで元の暗号化始点アドレスを置き換えたパケットを計算ノード３０ａに送信する。このようにすることにより、中継ノード４０ａと計算ノード３０ａとの間の通信を盗聴しても、元の始点アドレスを知ることができない。
【００１８】
ただし、上記の方法では、中継ノード４０ａ自身の内部メモリ等の記憶部がスキャニングされた場合には送信元の始点アドレスが知られてしまうことになる。そこで、複数の中継ノードを複数段入れ子に接続する構成をとることでこれを防ぐことができる。このように構成した場合、経路上の全ての中継ノードが盗聴されない限りは宛先アドレスを知られることなないため匿名性は高いものとなる。
【００１９】
このように、匿名通信機能によれば、受信者は送信者を知ることができなくなる。しかし、送信者は予め受信者を知っていなければならないことになる。そこで、送信者が受信者を不明なものとするためにランダム通信を用いてパケットを送信するようにする。
【００２０】
次に、ランダム通信機能について説明する。本実施形態において、中継ノード４０ａ，４０ｂ，４０ｃを含むネットワーク５０で行われるランダム通信では、パケットの到着する宛先は、送信者が指定するのではなく、宛先の候補（例えば、自中継ノードが中継ノード４０ａである場合は、中継ノード４０ｂ，４０ｃ、及び計算ノード３０ａ，３０ｂ，３０ｃ，３０ｄ）の中から無作為に決定される。このようなパケットの配送を実現する方式としてグラフ上のランダムウォークが公知である。このランダムウォーク方式では、ｊ（ｊは２以上の整数）個の隣接ノードを有するルータは、次の転送先を隣接ノードの中から１／ｊずつの確率で選択する。パケットが宛先候補のノードの集合のいずれかに到達した時点で配送は完了する。このようなランダムウォーク方式の特性については様々な解析が行われている。例えば、以下の文献ではインターネットのようなスケールフリー特性を有するネットワーク上におけるランダムウォークについての解析結果がまとめられている。
【００２１】
Ｎｏｈ，Ｊ．Ｄ．ａｎｄ  Ｒｉｅｇｅｒ，Ｈ．，Ｒａｎｄｏｍ  Ｗａｌｋｓ  ｏｎ  Ｃｏｍｐｌｅｘ  Ｎｅｔｗｏｒｋｓ，Ｐｈｙｓｉｃａｌ  Ｒｅｖｉｅｗ  Ｌｅｔｔｅｒｓ，ｖｏｌ．９２，ｐａｇｅ  １１８７０１，２００４．
【００２２】
また、様々な統計的な特性を有したランダムウォーク方式の派生モデルも公表されており、これらを利用することで所望の特性を有した無作為なパケットの配送を実現できる。例えば、以下の文献には、ランダムウォークを拡張することにより、宛先までの到達時間を短縮する方法が述べられている。
【００２３】
Ｓ．Ｉｋｅｄａ，Ｉ．ｋｕｂｏ，ａｎｄ  Ｍ．Ｙａｍａｓｈｉｔａ，Ｒｅｄｕｃｉｎｇ  ｔｈｅ  Ｈｉｔｔｉｎｇ  ａｎｄ  ｔｈｅ  Ｃｏｖｅｒ  Ｔｉｍｅｓ  ｏｆ  Ｒａｍｄｏｍ  Ｗａｌｋｓ  ｏｎ  Ｆｉｎｉｔｅ  Ｇｒａｐｈｓ  ｂｙ  Ｌｏｃａｌ  Ｔｏｐｏｌｏｇｉｃａｌ  Ｉｎｆｏｒｍａｔｉｏｎ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２００３  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  ＶＬＳＩ，ｐｐ．２０３−２０７，２００３．
【００２４】
本実施形態においては、上述した公知のランダムウォーク方式を適用して宛先を確率的に選択してランダム通信を行う。よって、匿名通信機能及びランダム通信機能を併せ用いた通信を行うことにより、送信元は受信先を知らず、且つ受信先も送信元を知らないこと、及び送信されたパケットがどこに配送されたかを不明なものとすることが実現できる。そして、これにより、入力情報を暗号化することなくその秘匿性を保つことができるため、本実施形態では、途中の計算結果に応じた選択的な処理を実行させることを可能にするものである。
【００２５】
次に、本実施形態である分散計算処理システムにおける秘密分散計算処理について説明する。この秘密分散計算処理は２つのフェーズから成り立つものである。第１フェーズでは、任意の利用者ノードが処理対象プログラムを論理回路に変換して複数の部分論理回路に分割し、これらの部分論理回路を匿名通信機能及びランダム通信機能を用いて計算ノードに配送する。第２フェーズでは、各利用者ノードは、入力値を暗号化することなく計算ノードに送信し、これらを受信した計算ノードは協働して計算を行い、最終的な出力値を各利用者ノードに送信する。その協働した計算の際には、各計算ノードの入出力値は暗号化されない状態でやり取りされる。以下、各フェーズについて詳細に説明する。
【００２６】
［第１フェーズの動作説明］
一般的に、論理回路は、ノード及びエッジを含んで構成される有向グラフとみなすことができため、エッジを介して連結されたノードを含むような関係を有した部分論理回路に分割することができる。図２に、分散計算処理システム１が秘密分散計算処理を実行する対象である処理対象プログラムｆ（ａ，ｂ）の概略のフローチャートを示す。同図は、処理対象プログラムｆ（ａ，ｂ）が３つの部分論理回路Ｇ，Ｈ，Ｉに分割された様子を示している。すなわち、部分論理回路Ｇでは、入力値ａ，ｂに基づき所定の計算を実行し、その結果に対し所定の条件に基づいてＴＲＵＥ（真）であった場合は、部分論理回路Ｈの処理に移行する一方、ＦＡＬＳＥ（偽）であった場合は、部分論理回路Ｉの処理に移行する。部分論理回路Ｈでの処理の後は、条件分岐に戻る。また、部分論理回路Ｉでの処理によって最終的な結果が得られる。このように、本実施形態における処理対象プログラムｆ（ａ，ｂ）には条件分岐処理が含まれているものとする。
【００２７】
図３−図９に、分散計算処理システム１が実行する秘密分散計算処理の第１フェーズの動作を表したシーケンス図を示し、これらを併せ参照して分散計算処理システム１の第１フェーズの動作を説明する。なお、利用者ノード１０，２０の各アドレスをＡ，Ｂ、中継ノード４０ａ，４０ｂ，４０ｃの各アドレスをＲ１，Ｒ２，Ｒ３、計算ノード３０ａ，３０ｂ，３０ｃ，３０ｄの各アドレスをＣ１，Ｃ２，Ｃ３，Ｃ４として説明する。
【００２８】
図３において、第１フェーズでは、まず任意の利用者ノード、例えば利用者Ｐ１が使用する利用者ノード１０が、処理対象プログラムｆ（ａ，ｂ）を３つの部分論理回路Ｇ，Ｈ，Ｉに分割する（Ｓ３０１）。３つの部分論理回路Ｇ，Ｈ，Ｉは、均等な大きさになるように分割され、部分論理回路Ｇ，Ｈ，Ｉの各入力値はｓビットであるとする。
【００２９】
次に、利用者ノード１０は、これらの部分論理回路Ｇ，Ｈ，Ｉを計算ノードに配送する。まず、利用者ノード１０は、部分論理回路Ｇを計算ノードに配送するが、ここでは、ランダム通信機能によって、中継ノード４０ａ→中継ノード４０ｂの経路を辿って計算ノード３０ａに配送されるものとして説明する。
【００３０】
部分論理回路Ｇを計算ノード３０ａに配送する場合には、以下の３つの条件を満たす必要がある。
（１）利用者ノード１０（利用者Ｐ１）は、どこが配送先であるかを知ってはならない。
（２）配送先である計算ノード３０ａは、どこが配送元であるかを知ってはならない。
（３）中継ノード４０ａ，４０ｂは、配送元及び配送先の両方を知ってはならない（但し、いずれか一方を知ることに問題はない。）
【００３１】
上記（１）−（３）の条件を満たすために、利用者ノード１０は、以下の手順にしたがって部分論理回路Ｇを配送する。まず、利用者ノード１０は、送信元アドレスフィールドに自身の利用者ノードアドレス情報であるアドレスＡを格納し、データフィールドに部分論理回路Ｇを格納した部分論理回路パケットを生成する。そして、利用者ノード１０は、その部分論理回路パケットを隣接する中継ノード４０ａに送信する（Ｓ３０２）。
【００３２】
次に、中継ノード４０ａは、受信した部分論理回路パケットの送信元アドレスフィールドに格納されているアドレスＡを取り出して秘密鍵Ｋａで暗号化し、そのアドレスＡの暗号化アドレスであるＥＫａ（Ａ）で送信元アドレスフィールドを更新する（Ｓ３０３）。そして、中継ノード４０ａは、ランダム通信機能によって無作為に次の送信先ノードを決定し、更新された部分論理回路パケットを決定されたノードである中継ノード４０ｂに送信する（Ｓ３０４）。
【００３３】
ランダム通信により中継ノード４０ａから送信された部分論理回路パケットを受信した中継ノード４０ｂは、上記のステップＳ３０３及びＳ３０４と同様の処理を実行する。具体的には、中継ノード４０ｂは、受信した部分論理回路パケットの送信元アドレスフィールドに格納されている暗号化アドレスＥＫａ（Ａ）を取り出して秘密鍵Ｋｂで暗号化し、暗号化アドレスＥＫａ（Ａ）をさらに暗号化した２重暗号化アドレスであるＥＫｂ（ＥＫａ（Ａ））で送信元アドレスフィールドを更新する（Ｓ３０５）。そして、中継ノード４０ｂは、ランダム通信機能によって無作為に次の送信先ノードを決定し、更新された部分論理回路パケットを決定されたノードである計算ノード３０ａに送信する（Ｓ３０６）。
【００３４】
ランダム通信により中継ノード４０ｂから送信された部分論理回路パケットを受信した計算ノード３０ａは、受信した部分論理回路パケットのデータフィールドに格納されている部分論理回路Ｇを部分論理回路記憶部に記憶する（Ｓ３０７）。
【００３５】
以上によれば、計算ノード３０ａが受信した部分論理回路パケットの送信元アドレスフィールドに格納された利用者ノード１０のアドレスＡは、経路中の中継ノード４０ａ，４０ｂによってそれぞれ暗号化されているため、計算ノード３０ａは、利用者ノード１０を配送元として特定することができない。また、中継ノード４０ａ，４０ｂによるランダム通信によって部分論理回路パケットが配送されているため、配送元である利用者ノード１０は配送先の計算ノードを特定することができない。さらに、中継ノード４０ａ，４０ｂは、配送元である利用者ノード１０と配送先である計算ノード３０ａとの両方を特定することができない。よって、利用者ノード１０は、匿名性に関する前記３つの条件（１）−（３）を満たしながら、部分論理回路Ｇを計算ノード３０ａに配送することができる。
【００３６】
次に、部分論理回路Ｇを取得した計算ノード３０ａは、利用者ノード１０に対して受信確認の応答を返信する。この応答は、部分論理回路パケットの配送経路と同一の経路を逆向きに辿って利用者ノード１０に配送される。具体的には、まず、計算ノード３０ａは、宛先アドレスフィールドに２重暗号化アドレス（暗号化利用者ノードアドレス情報）であるＥＫｂ（ＥＫａ（Ａ））を格納し、送信元アドレスフィールドに自身の計算ノードアドレス情報であるアドレスＣ１を格納した応答パケットを生成する。そして、計算ノード３０ａは、その応答パケットを送信する（Ｓ３０８）。
【００３７】
計算ノード３０ａから送信された応答パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した応答パケットの宛先アドレスフィールドに格納された２重暗号化アドレスＥＫｂ（ＥＫａ（Ａ））を復号できるノードは、秘密鍵Ｋｂを有している中継ノード４０ｂのみであるので、中継ノード４０ｂが応答パケットを正式に受信したものとなる。
【００３８】
応答パケットを正式に受信した中継ノード４０ｂは、応答パケットの宛先アドレスフィールドに格納されている２重暗号化アドレス（暗号化宛先アドレス情報）であるＥＫｂ（ＥＫａ（Ａ））を取り出して秘密鍵Ｋｂで復号し、その復号された暗号化アドレスＥＫａ（Ａ）で宛先アドレスフィールドを更新する。そして、送信元アドレスフィールドに格納されている送信元アドレス情報であるアドレスＣ１を取り出して秘密鍵Ｋｂで暗号化し、そのアドレスＣ１の暗号化アドレス（暗号化計算ノードアドレス情報）であるＥＫｂ（Ｃ１）で送信元アドレスフィールドを更新する（Ｓ３０９）。
【００３９】
次に、中継ノード４０ｂは、その更新された応答パケットを送信する（Ｓ３１０）。中継ノード４０ｂから送信された応答パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した応答パケットの宛先アドレスフィールドに格納された暗号化アドレスＥＫａ（Ａ）を復号できるノードは、秘密鍵Ｋａを有している中継ノード４０ａのみであるので、中継ノード４０ａが応答パケットを正式に受信したものとなる。
【００４０】
応答パケットを正式に受信した中継ノード４０ａは、応答パケットの宛先アドレスフィールドに格納されている暗号化アドレスＥＫａ（Ａ）を取り出して秘密鍵Ｋａで復号し、その復号されたアドレスＡで宛先アドレスフィールドを更新する。そして、送信元アドレスフィールドに格納されている暗号化アドレスＥＫｂ（Ｃ１）を取り出して秘密鍵Ｋａで暗号化し、その暗号化アドレスＥＫｂ（Ｃ１）の２重暗号化アドレスであるＥＫａ（ＥＫｂ（Ｃ１））で送信元アドレスフィールドを更新する（Ｓ３１１）。
【００４１】
次に、中継ノード４０ａは、その更新された応答パケットを送信し、利用者ノード１０はこれを受信する（Ｓ３１２）。そして、応答パケットを受信した利用者ノード１０は、部分論理回路Ｇと、応答パケットの宛先アドレスフィールドに格納されている２重暗号化アドレス（暗号化計算ノードアドレス情報）であるＥＫａ（ＥＫｂ（Ｃ１））とを関連付けて計算ノードアドレス情報記憶部に記憶する（Ｓ３１３）。
【００４２】
上述したステップＳ３０２−Ｓ３１３の処理と同様に、利用者ノード１０は、部分論理回路Ｈ，Ｉを計算ノードに配送して確認応答を受信する。図４に、利用者ノード１０が部分論理回路Ｈを計算ノードに配送する手順を表したシーケンス図を示し、図５に、利用者ノード１０が部分論理回路Ｉを計算ノードに配送する手順を表したシーケンス図を示す。図４については、利用者ノード１０が配送する部分論理回路Ｈは、ランダム通信機能によって中継ノード４０ａ→中継ノード４０ｂの経路を辿って計算ノード３０ｂに配送された場合を例としたものである。また、図５については、利用者ノード１０が配送する部分論理回路Ｉは、ランダム通信機能によって中継ノード４０ａ→中継ノード４０ｃの経路を辿って計算ノード３０ｄに配送された場合を例としたものである。なお、図４及び図５のシーケンス図についての動作の説明は、図３のシーケンス図に基づく動作説明と同様であるため、ここではその詳細説明を省略する。
【００４３】
図３−図５に示したシーケンス図に基づく動作により、利用者ノード１０，２０は、部分論理回路Ｇとこれの配送先アドレスが暗号化されたＥＫａ（ＥＫｂ（Ｃ１））との組み合わせ、部分論理回路Ｈとこれの配送先アドレスが暗号化されたＥＫａ（ＥＫｂ（Ｃ２））との組み合わせ、及び部分論理回路Ｉとこれの配送先アドレスが暗号化されたＥＫａ（ＥＫｃ（Ｃ４））との組み合わせを、それぞれの計算ノードアドレス情報記憶部に記憶させることとなる。すなわち、利用者ノード１０，２０は、全ての部分論理回路Ｇ，Ｈ，Ｉと、これらが配送された計算ノード３０ａ，３０ｂ，３０ｄの暗号化されたアドレスの対応関係を知る状態となる。
【００４４】
ところで、図２に示した処理対象プログラムのフローチャートによれば、部分論理回路Ｇを実行した後は、条件に応じて部分論理回路Ｈ又は部分論理回路Ｉが実行されることになる。そのため、部分論理回路Ｇの配送先ノードである計算ノード３０ａは、部分論理回路Ｈ及び部分論理回路Ｉを実行する計算ノード３０ｂ，３０ｄのアドレス、すなわち暗号化されたアドレスＣ２，Ｃ４を知っている必要がある。そこで、利用者ノード１０は、ＥＫａ（ＥＫｂ（Ｃ２））及びＥＫａ（ＥＫｃ（Ｃ４））を計算ノード３０ａに送信する。
【００４５】
図６に、利用者ノード１０が暗号化されたアドレスＣ２，Ｃ４を計算ノード３０ａに配送する手順を表したシーケンス図を示して具体的に説明する。同図において、利用者ノード１０は、宛先アドレスフィールドに暗号化されたアドレスであるＥＫａ（ＥＫｂ（Ｃ１））を格納し、データフィールドに部分論理回路Ｈ，Ｉの暗号化された所在置アドレスであるＥＫａ（ＥＫｂ（Ｃ２））及びＥＫａ（ＥＫｃ（Ｃ４））を格納した接続情報パケットを生成する。そして、利用者ノード１０は、その接続情報パケットを送信する（Ｓ６０１）。
【００４６】
利用者ノード１０から送信された接続情報パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した接続情報パケットの宛先アドレスフィールドに格納された２重暗号化アドレスＥＫａ（ＥＫｂ（Ｃ１））を復号できるノードは、秘密鍵Ｋａを有している中継ノード４０ａのみであるので、中継ノード４０ａは接続情報パケットを正式に受信したものとなる。
【００４７】
接続情報パケットを受信した中継ノード４０ａは、接続情報パケットの宛先アドレスフィールドに格納されている２重暗号化アドレスＥＫａ（ＥＫｂ（Ｃ１））を取り出して秘密鍵Ｋａで復号し、その復号された暗号化アドレスＥＫｂ（Ｃ１）で宛先アドレスフィールドを更新する（Ｓ６０２）。そして、中継ノード４０ａは、その更新された接続情報パケットを送信する（Ｓ６０３）。
【００４８】
中継ノード４０ａから送信された接続情報パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した接続情報パケットの宛先アドレスフィールドに格納された暗号化アドレスＥＫｂ（Ｃ１）を復号できるノードは、秘密鍵Ｋｂを有している中継ノード４０ｂのみであるので、中継ノード４０ｂは接続情報パケットを正式に受信したものとなる。
【００４９】
接続情報パケットを受信した中継ノード４０ｂは、接続情報パケットの宛先アドレスフィールドに格納されている暗号化アドレスＥＫｂ（Ｃ１）を取り出して秘密鍵Ｋｂで復号し、その復号されたアドレスＣ１で宛先アドレスフィールドを更新する（Ｓ６０４）。そして、中継ノード４０ｂは、その更新された接続情報パケットを送信する（Ｓ６０５）。
【００５０】
中継ノード４０ｂから送信された接続情報パケットを受信した計算ノード３０ａは、接続情報パケットのデータフィールドに格納されたＥＫａ（ＥＫｂ（Ｃ２））及びＥＫａ（ＥＫｃ（Ｃ４））を取り出して部分論理回路記憶部に記憶する（Ｓ６０６）。
【００５１】
また、部分論理回路Ｈの配送先ノードである計算ノード３０ｂも、部分論理回路Ｈを実行した後は、条件に応じて部分論理回路Ｈ又は部分論理回路Ｉが実行されることになるので、計算ノード３０ｂも、部分論理回路Ｈ及び部分論理回路Ｉを実行する計算ノード３０ｂ，３０ｄの暗号化されたアドレスＣ２，Ｃ４を知っている必要がある。このため、利用者ノード１０は、ＥＫａ（ＥＫｂ（Ｃ２））及びＥＫａ（ＥＫｃ（Ｃ４））を計算ノード３０ｂに送信する。
【００５２】
図７に、利用者ノード１０が暗号化されたアドレスＣ２，Ｃ４を計算ノード３０ｂに配送する手順を表したシーケンス図を示すが、同図のシーケンス図についての動作の説明は、図６のシーケンス図に基づく動作説明と同様であるため、ここではその詳細説明を省略する。
【００５３】
さらにまた、部分論理回路Ｉの配送先ノードである計算ノード３０ｄは、部分論理回路Ｉを実行した後は利用者ノードＡ，Ｂに実行結果を送信する必要があるため、計算ノード３０ｄは、利用者ノード１０，２０の暗号化されたアドレスＡ，Ｂを知っている必要がある。このため、利用者ノード１０は、アドレスＡを匿名通信機能を用いて暗号化しながら計算ノード３０ｄに送信する。また、利用者ノード２０も、アドレスＢを匿名通信機能を用いて暗号化しながら計算ノード３０ｄに送信する。
【００５４】
図８に、利用者ノード１０が自身のアドレスを計算ノード３０ｄに配送する手順を表したシーケンス図を示して具体的に説明する。同図において、利用者ノード１０は、宛先アドレスフィールドに暗号化されたアドレスであるＥＫａ（ＥＫｃ（Ｃ４））を格納し、送信元アドレスフィールドに自身のアドレスＡを格納した接続情報パケットを生成する。そして、利用者ノード１０は、その接続情報パケットを送信する（Ｓ８０１）。
【００５５】
利用者ノード１０から送信された接続情報パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した接続情報パケットの宛先アドレスフィールドに格納された２重暗号化アドレスＥＫａ（ＥＫｃ（Ｃ４））を復号できるノードは、秘密鍵Ｋａを有している中継ノード４０ａのみであるので、中継ノード４０ａが接続情報パケットを正式に受信したものとなる。
【００５６】
接続情報パケットを正式に受信した中継ノード４０ａは、接続情報パケットの宛先アドレスフィールドに格納されている２重暗号化アドレス（暗号化宛先アドレス情報）ＥＫａ（ＥＫｃ（Ｃ４））を取り出して秘密鍵Ｋａで復号し、その復号された暗号化アドレスＥＫｃ（Ｃ４）で宛先アドレスフィールドを更新する。そして、送信元アドレスフィールドに格納されている送信元アドレス情報であるアドレスＡを取り出して秘密鍵Ｋａで暗号化し、そのアドレスＡの暗号化アドレスであるＥＫａ（Ａ）で送信元アドレスフィールドを更新する（Ｓ８０２）。
【００５７】
次に、中継ノード４０ａは、その更新された接続情報パケットを送信する（Ｓ８０３）。中継ノード４０ａから送信された接続情報パケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した接続情報パケットの宛先アドレスフィールドに格納された暗号化アドレスＥＫｃ（Ｃ４）を復号できるノードは、秘密鍵Ｋｃを有している中継ノード４０ｃのみであるので、中継ノード４０ｃが接続情報パケットを正式に受信したものとなる。
【００５８】
接続情報パケットを正式に受信した中継ノード４０ｃは、接続情報パケットの宛先アドレスフィールドに格納されている暗号化アドレスＥＫｃ（Ｃ４）を取り出して秘密鍵Ｋｃで復号し、その復号されたアドレスＣ４で宛先アドレスフィールドを更新する。そして、送信元アドレスフィールドに格納されている暗号化アドレスＥＫａ（Ａ）を取り出して秘密鍵Ｋｃで暗号化し、その暗号化アドレスＥＫａ（Ａ）の２重暗号化アドレスであるＥＫｃ（ＥＫａ（Ａ））で送信元アドレスフィールドを更新する（Ｓ８０４）。
【００５９】
次に、中継ノード４０ｃは、その更新された接続情報パケットを送信し、計算ノード３０ｄはこれを受信する（Ｓ８０５）。そして、接続情報パケットを受信した計算ノード３０ｄは、接続情報パケットの送信元アドレスフィールドに格納されている２重暗号化アドレスＥＫｃ（ＥＫａ（Ａ））を部分論理回路記憶部に記憶する（Ｓ８０６）。
【００６０】
次に、図９に、利用者ノード２０が自身のアドレスを計算ノード３０ｄに配送する手順を表したシーケンス図を示すが、ステップＳ９０１−Ｓ９０６の処理については、図８のシーケンス図におけるＳ８０１−Ｓ８０６の処理と同様であるため、ここではその詳細説明を省略する。ステップＳ９０６の処理に続けて、利用者ノード１０は、部分論理回路Ｇとこれの配送先アドレスが暗号化されたＥＫａ（ＥＫｂ（Ｃ１））との組み合わせ、部分論理回路Ｈとこれの配送先アドレスが暗号化されたＥＫａ（ＥＫｂ（Ｃ２））との組み合わせ、及び部分論理回路Ｉとこれの配送先アドレスが暗号化されたＥＫａ（ＥＫｃ（Ｃ４））との組み合わせを、利用者ノード２０に対して送信する。そして、利用者ノード２０は、これらを受信して部分論理回路記憶部に記憶する（Ｓ９０７）。
【００６１】
以上により、計算ノード３０ａ，３０ｂは、部分論理回路Ｈ，Ｉの所在アドレスＣ２，Ｃ４を暗号化したＥＫａ（ＥＫｂ（Ｃ２）），ＥＫａ（ＥＫｃ（Ｃ４））をそれぞれの部分論理回路記憶部に記憶し、計算ノード３０ｄは、利用者ノード１０，２０の所在アドレスＡ，Ｂを暗号化したＥＫｃ（ＥＫａ（Ａ）），ＥＫｃ（ＥＫａ（Ｂ））を部分論理回路記憶部に記憶する。
【００６２】
［第２フェーズの動作説明］
第２フェーズでは、利用者ノード１０，２０に入力値ｄ１，ｄ２が入力されることにより、分散計算処理システム１が処理対象プログラムｆ（ｄ１，ｄ２）を実行し、その最終的な結果を利用者ノード１０，２０に供給する処理が実行される。図１０−図１２に、分散計算処理システム１が実行する秘密分散計算処理の第２フェーズの動作を表したシーケンス図を示し、これらを併せ参照して分散計算処理システム１の第２フェーズの動作を説明する。
【００６３】
図１０において、第２フェーズでは、まず利用者Ｐ１の入力操作によって入力値ｄ１が利用者ノード１０に入力される（Ｓ１００１）。次に、利用者ノード１０は、宛先アドレスフィールドに部分論理回路Ｇの所在する暗号化アドレスであるＥＫａ（ＥＫｂ（Ｃ１））を格納し、データフィールドに入力値ｄ１を格納したデータパケットを生成する。そして、利用者ノード１０は、そのデータパケットを送信する（Ｓ１００２）。
【００６４】
利用者ノード１０から送信されたデータパケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信したデータパケットの宛先アドレスフィールドに格納された２重暗号化アドレスＥＫａ（ＥＫｂ（Ｃ１））を復号できるノードは、秘密鍵Ｋａを有している中継ノード４０ａのみであるので、中継ノード４０ａは接続情報パケットを正式に受信したものとなる。
【００６５】
データパケットを受信した中継ノード４０ａは、データパケットの宛先アドレスフィールドに格納されている２重暗号化アドレスＥＫａ（ＥＫｂ（Ｃ１））を取り出して秘密鍵Ｋａで復号し、その復号された暗号化アドレスＥＫｂ（Ｃ１）で宛先アドレスフィールドを更新する（Ｓ１００３）。そして、中継ノード４０ａは、その更新されたデータパケットを送信する（Ｓ１００４）。
【００６６】
中継ノード４０ａから送信されたデータパケットの宛先アドレスは暗号化されているが、隣接するルータはこれを受信する。受信した接続情報パケットの宛先アドレスフィールドに格納された暗号化アドレスＥＫｂ（Ｃ１）を復号できるノードは、秘密鍵Ｋｂを有している中継ノード４０ｂのみであるので、中継ノード４０ｂは接続情報パケットを正式に受信したものとなる。
【００６７】
データパケットを受信した中継ノード４０ｂは、接続情報パケットの宛先アドレスフィールドに格納されている暗号化アドレスＥＫｂ（Ｃ１）を取り出して秘密鍵Ｋｂで復号し、その復号されたアドレスＣ１で宛先アドレスフィールドを更新する（Ｓ１００５）。そして、中継ノード４０ｂは、その更新されたデータパケットを送信する。そして、中継ノード４０ｂから送信されたデータパケットを受信した計算ノード３０ａは、データパケットのデータフィールドに格納された入力値ｄ１を取り出して部分論理回路記憶部に記憶する（Ｓ１００６）。
【００６８】
利用者ノード２０側についても、同様の処理が実行される。すなわち、利用者Ｐ２の入力操作によって入力値ｄ２が利用者ノード２０に入力されると（Ｓ１０１１）、ステップＳ１００２−Ｓ１００６の処理と同様の処理が実行される（Ｓ１０１２−Ｓ１０１６）。
【００６９】
部分論理回路Ｇが配置された計算ノード３０ａに、処理対象プログラムｆ（ａ，ｂ）の入力値であるａ＝ｄ１，ｂ＝ｄ２が配送されたのち、計算ノード３０ａは入力値ｄ１，ｄ２を用いた部分論理回路Ｇの処理を実行して中間出力値Ｇ（ｄ１，ｄ２）を出力する（Ｓ１０１７）。計算ノード３０における部分論理回路Ｇの処理においては、部分論理回路Ｇ及び中間出力値Ｇ（ｄ１，ｄ２）は暗号化されていないため、図２に示した処理対象プログラムｆ（ａ，ｂ）のフローチャートにおける所定の条件について容易に判定処理を行うことができ、それに伴う分岐処理を適切に行うことができる。
【００７０】
次に、部分論理回路Ｇからの中間出力値Ｇ（ｄ１，ｄ２）に基づく所定の条件の判定結果がＦＡＬＳＥであった場合についての秘密分散計算処理のフローチャートを図１１に示してその動作を説明する。条件の判定結果がＦＡＬＳＥである場合、次に実行される部分論理回路は部分論理回路Ｉである。よって、同図に示すように、計算ノード３０ａは、宛先アドレスフィールドに部分論理回路Ｉの所在する暗号化アドレスであるＥＫａ（ＥＫｃ（Ｃ４））を格納し、データフィールドに中間出力値Ｇ（ｄ１，ｄ２）を格納したデータパケットを生成する。そして、計算ノード３０ａは、そのデータパケットを送信する（Ｓ１１０１）。
【００７１】
そして、図１０に示したシーケンスと同様なシーケンスの匿名通信を行うことにより、中間出力値Ｇ（ｄ１，ｄ２）は計算ノード３０ｄに配送される（Ｓ１１０２−Ｓ１１０５）。部分論理回路Ｉが配置された計算ノード３０ｄに、処理対象プログラムｆ（ｄ１，ｄ２）の中間出力値Ｇ（ｄ１，ｄ２）が配送されたのち、計算ノード３０ｄは中間出力値Ｇ（ｄ１，ｄ２）を入力値として用いた部分論理回路Ｉの処理を実行して最終出力値ｆ（ｄ１，ｄ２）を出力する（Ｓ１１０６）。
【００７２】
次に、部分論理回路Ｉからの最終出力値ｆ（ｄ１，ｄ２）を利用者ノード１０，２０にそれぞれ配送する動作について、図１２にフローチャートを示して説明する。同図に示すように、まず計算ノード３０ｄは、宛先アドレスフィールドに利用者ノード１０の所在する暗号化アドレスであるＥＫｃ（ＥＫａ（Ａ））を格納し、データフィールドに最終出力値ｆ（ｄ１，ｄ２）を格納したデータパケットを生成する。そして、計算ノード３０ｄは、そのデータパケットを送信する（Ｓ１２０１）。そして、図１０に示したシーケンスと同様なシーケンスの匿名通信を行うことにより、最終出力値ｆ（ｄ１，ｄ２）は利用者ノード１０に配送される（Ｓ１２０２−Ｓ１２０５）。そして、利用者ノード１０は、最終出力値ｆ（ｄ１，ｄ２）を取得する（Ｓ１２０６）。
【００７３】
同様にして、計算ノード３０ｄは、最終出力値ｆ（ｄ１，ｄ２）を利用者ノード２０に配送し、利用者ノード２０はこれを取得する（Ｓ１２１１−Ｓ１２１６）。
【００７４】
以上、本実施形態の分散計算処理システムの動作について説明したが、この分散計算処理システムで用いる部分論理回路Ｇ，Ｈ，Ｉはそれぞれ暗号化されていないため、盗聴による計算の秘匿性が問題となる。ｎ台の計算ノードのうち、ｍ台（但し、ｎ＞ｍ）の計算ノードが、悪意のある盗聴者ＰＥによって盗聴されたとする。盗聴者ＰＥは、盗聴している計算ノードについての各状態、具体的には、他のノードとの間でやり取りされる入出力値やメモリの内容を取得することができるものとする。これによれば、盗聴者ＰＥは、ｎ個の部分論理回路のうち、ｍ個の部分論理回路の入力値を観測することができる。但し、通信は匿名化されているので、盗聴者ＰＥは、観測した部分論理回路の入力値が、元の論理回路全体のうちどこの部分論理回路であるかを特定することができない。したがって、盗聴者ＰＥは、元のｎ個の値のうち、その一部分であるｍ個を、順番が不明な状態で観測しているのと同等である。
【００７５】
これは、ｋビットの入力とｓ×ｍビットの出力を有する情報チャネルと置き換えて考えることができる。これにおいて、順序が不明でその一部しか観測できないということは、通信路にノイズが存在することに相当する。ノイズの存在する通信路では、そこに入力されたｋビットの情報の全ては伝送されず、ノイズの分だけ減少した情報量ｅビット（ｅ＜ｋ）が伝送される。これにより、盗聴者ＰＥが、秘密情報である入力値ｄ１，ｄ２に関して得ることのできる情報量ｅビットをｋビットよりも小さくすることができる。よって、さらに部分論理回路をより細かく分割する（すなわち、ｎを大きくする）ことにより、ノイズ成分を大きくし、ｅビットをより小さくすることができる。したがって、利用者ノードは、必要や用途に応じて分割数ｎを増減して所望の秘匿性を確保することができる。
【００７６】
以上、詳述したとおり、本実施形態によれば、処理対象プログラムが論理回路に変換され、さらに複数の部分論理回路に分割されて匿名通信機能及びランダム通信機能によって複数の計算ノードに配置される。これによって、配送元及び配送先は互いのアドレスを知ることができず、配信元はどの部分論理回路がどこの計算ノードに配置されたかを知ることができない。また、全てのパケットの通信は、暗号化されたアドレスによって行われるため、通信経路中で中継される中継ノードも入出力両方のアドレスを知ることができない。これにより、ネットワーク５０のノードの一部が盗聴されたとしても各ノードの通信接続関係が不明であるため、情報の秘匿性を確保することができる。
【００７７】
また、本実施形態によれば、部分論理回路自体や部分論理回路の入出力値は暗号化されない状態で処理されるため、部分論理回路を選択的に処理したり条件分岐処理をしたりすることが容易に行える。よって、従来のように、全ての選択肢を処理させていたような非効率な処理をする必要がないため、リソース消費を経済的に抑えることができるとともに処理効率を飛躍的に改善することができる。
【００７８】
なお、本発明の実施形態による分散計算処理装置の処理を実行させるための分散計算処理用プログラムをコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませて実行させることにより、本実施形態による分散計算処理を行うようにしてもよい。なお、ここでいうコンピュータシステムとは、オペレーティングシステムや周辺機器等のハードウェアを含むものであってもよい。また、コンピュータシステムは、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、コンピュータ読み取り可能な記録媒体とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【００７９】
さらにコンピュータ読み取り可能な記録媒体は、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。また、上記のプログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する伝送媒体は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００８０】
以上、本発明の実施形態について詳述したが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００８１】
１  分散計算処理システム
１０，２０  利用者ノード
３０ａ，３０ｂ，３０ｃ，３０ｄ  計算ノード
４０ａ，４０ｂ，４０ｃ  中継ノード
５０  ネットワーク
ｄ１，ｄ２  入力値
Ｋａ，Ｋｂ，Ｋｃ  秘密鍵
Ｐ１，Ｐ２  利用者
【図１】
2010231516.tif 000003
【図２】
2010231516.tif 000004
【図３】
2010231516.tif 000005
【図４】
2010231516.tif 000006
【図５】
2010231516.tif 000007
【図６】
2010231516.tif 000008
【図７】
2010231516.tif 000009
【図８】
2010231516.tif 000010
【図９】
2010231516.tif 000011
【図１０】
2010231516.tif 000012
【図１１】
2010231516.tif 000013
【図１２】
2010231516.tif 000014