(57)【特許請求の範囲】
【請求項１】
複数の計算装置と中継装置を備えており、前記複数の計算装置のそれぞれは１つ以上の計算ステップを含む計算手順に従い計算処理を行い、前記複数の計算装置のそれぞれは各計算ステップを実行すると中間値を生成して他の計算装置のそれぞれに送信すると共に、前記他の計算装置のそれぞれから中間値を受信するまで次のステップの実行を待機するシステムであって、
前記複数の計算装置のそれぞれは、１つの計算ステップで生成した前記他の計算装置のそれぞれに送信する中間値を１つの中間値メッセージに含めて前記中継装置に送信し、
前記中継装置は、宛先の計算装置を同じとし、かつ、当該宛先の計算装置以外の総ての計算装置それぞれにおいて同じ計算ステップで生成された中間値を受信すると、当該中間値を当該宛先の計算装置への１つの中間値メッセージに含めて送信する、
ことを特徴とするシステム。
【請求項２】
前記複数の計算装置のそれぞれは前記他の計算装置のそれぞれに送信する中間値を、前記他の計算装置毎に異なる暗号鍵で暗号化し、
前記複数の計算装置のそれぞれは前記他の計算装置毎に使用する暗号鍵を生成するために、前記他の計算装置それぞれに送信する値を１つの暗号鍵交換メッセージに含めて前記中継装置に送信し、
前記中継装置は、各計算装置から受信する暗号鍵交換メッセージそれぞれに含まれる値のうち、宛先の計算装置を同じとする値を、当該宛先の計算装置への１つの暗号鍵交換メッセージに含めて当該宛先の計算装置に送信する、
ことを特徴とする請求項１に記載のシステム。
【請求項３】
複数の計算装置と中継装置を備えており、前記複数の計算装置のそれぞれは１つ以上の計算ステップを含む計算手順に従い計算処理を行うシステムの前記計算装置であって、
前記計算手順に従い各計算ステップを実行すると、他の計算装置のそれぞれに送信する中間値を生成し、前記他の計算装置のそれぞれが生成した中間値を受信するまで次のステップの実行を待機する計算処理手段と、
前記計算処理手段が生成した前記他の計算装置のそれぞれに送信する中間値を１つの中間値メッセージに含めて前記中継装置に送信し、前記中継装置から、前記他の計算装置のそれぞれが生成し、かつ、同じ計算ステップで生成された中間値を含む１つの中間値メッセージを受信すると、受信した中間値メッセージに含まれる中間値を前記計算処理手段に出力するメッセージ処理手段と、
を備えていることを特徴とする計算装置。
【請求項４】
前記他の計算装置のそれぞれと送受信する中間値を暗号化するための暗号鍵を生成するための値を生成する鍵生成手段を更に備えており、
前記メッセージ処理手段は、前記鍵生成手段が生成した前記他の計算装置のそれぞれに送信する暗号鍵を生成するための値を１つの暗号鍵交換メッセージに含めて前記中継装置に送信し、前記中継装置から、前記他の計算装置のそれぞれが生成した暗号鍵を生成するための値を含む１つの暗号鍵交換メッセージを受信すると、受信した暗号鍵交換メッセージに含まれる値を前記鍵生成手段に出力する、
ことを特徴とする請求項３に記載の計算装置。
【請求項５】
請求項３又は４に記載の計算装置としてコンピュータを機能させることを特徴とするプログラム。
【請求項６】
複数の計算装置と中継装置を備えており、前記複数の計算装置のそれぞれは１つ以上の計算ステップを含む計算手順に従い計算処理を行い、前記複数の計算装置のそれぞれは各計算ステップを実行すると中間値を生成して他の計算装置のそれぞれに送信すると共に、前記他の計算装置のそれぞれから中間値を受信するまで次のステップの実行を待機するシステムの中継装置であって、
保存手段と、
第１の計算装置から、計算ステップを示す情報と、前記第１の計算装置以外の計算装置のそれぞれに送信する中間値と、を含む中間値メッセージを受信すると、前記計算ステップにおいて生成された第２の計算装置宛の中間値を、前記第２の計算装置以外の総ての計算装置から受信したかを判定し、総ての計算装置から受信していなければ、前記第１の計算装置から受信した前記第２の計算装置宛の中間値を前記保存手段に保存し、総ての計算装置から受信していれば、前記第１の計算装置から受信した前記第２の計算装置宛の中間値と、前記保存手段に保存されている、前記第１の計算装置と前記第２の計算装置の両計算装置以外の計算装置から受信した前記計算ステップにおいて生成された前記第２の計算装置宛の中間値と、を含む１つの中間メッセージを生成して、前記第２の計算装置に送信するメッセージ処理手段と、
を備えていることを特徴とする中継装置。
【請求項７】
前記中継装置は、複数の装置により構成される、
ことを特徴とする請求項６に記載の中継装置。
【請求項８】
請求項６又は７に記載の中継装置としてコンピュータを機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の計算装置が相互に情報を交換しながら計算処理を進めるシステムにおける交換する情報の送受信技術に関する。
【背景技術】
【０００２】
現在、大多数の人々が携帯電話といった携帯端末を所持しており、例えば、これら携帯端末を利用して、アンケート等に答えてもらうことで、多くの情報をすばやく収集することができる。具体的には、例えば、年代別に興味がある商品等に関する情報や、インフルエンザ等が流行した場合、地域毎及び年代別の患者数等に関する情報等、情報の収集者が必要とする情報を素早く収集することができる。
【０００３】
ここで、情報を収集する者には、個々の情報提供者の回答そのものではなく、その回答から計算により求めた統計的な情報、例えば、合計、平均、分散等の情報を提供するシステムを考える。また、このシステムにおいては、個人情報の保護の観点から、各情報提供者が提供する情報の内容については、他の情報提供者のみならず、情報の収集者にも秘密にするものとする。例えば、情報の収集者がある病気にかかったことがあるか否かの年代別の分布を調べる場合、収集者が取得できるのは各年代別の当該病気にかかったことがある人の合計値のみであり、個々の提供者が病気にかかったことがあるか否かについては収集者にさえ秘密するものとする。
【０００４】
上記システムを実現するための技術として、非特許文献１から３は、Ｓｅｃｕｒｅ  Ｍｕｌｔｉ−ｐａｒｔｙ  Ｃｏｍｐｕｔａｔｉｏｎ（ＳＭＣ）を開示している。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｂｅｎ−Ｏｒ，  Ｍ．，  Ｇｏｌｄｗａｓｓｅｒ，  Ｓ．，  ａｎｄ  Ｗｉｇｄｅｒｓｏｎ，  Ａ．，"Ｃｏｍｐｌｅｔｅｎｅｓｓ  ｔｈｅｏｒｅｍｓ  ｆｏｒ  ｎｏｎ−ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｆａｕｌｔ−ｔｏｌｅｒａｎｔ  ｄｉｓｔｒｉｂｕｔｅｄ  ｃｏｍｐｕｔａｔｉｏｎ，"  Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ｔｗｅｎｔｉｅｔｈ  ａｎｎｕａｌ  ＡＣＭ  ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｔｈｅｏｒｙ  ｏｆ  ｃｏｍｔｉｎｇ  （１９８８），ＡＣＭ，  ｐｐ．  １−１０
【非特許文献２】Ｇｏｌｄｒｅｉｃｈ，  Ｏ.，  ｅｔ  ａｌ．，"Ｈｏｗ  ｔｏ  ｐｌａｙ  ａｎｙ  ｍｅｎｔａｌ  ｇａｍｅ，"  Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ｎｉｎｅｔｅｅｎｔｈ  ａｎｎｕａｌ  ＡＣＭ  ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｔｈｅｏｒｙ  ｏｆ  ｃｏｍｐｕｔｉｎｇ（１９８７），ＡＣＭ，  ｐｐ.２１８−２２９
【非特許文献３】Ｇｏｌｄｒｅｉｃｈ，  Ｏ.，"Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｙ，"  Ｖｏｌｕｍｅ  ２，  Ｂａｓｉｃ  Ａｐｐｌｉｃａｔｉｏｎｓ．  Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，  ２００４年
【発明の概要】
【発明が解決しようとする課題】
【０００６】
以下、図５を用いて、装置Ａ〜Ｃが取得した情報の統計値をＳＭＣにより収集するシステムにおける処理の概略を説明する。なお、各装置Ａ〜Ｃにおける計算処理の手順は、各装置Ａ〜Ｃにあらかじめ通知されているものとする。まず、各装置Ａ〜Ｃは、それぞれ、入力として情報Ｘａ、Ｘｂ、Ｘｃを取得する。この情報は、装置Ａ〜Ｃが何らかのセンサにより取得した情報であっても、装置Ａ〜Ｃのユーザが、例えば、質問等の答えることにより入力した情報であっても良い。装置Ａ〜Ｃは、所定の計算式に従い入力された情報Ｘａ、Ｘｂ、Ｘｃから、それぞれ、中間値ａｂ１、ａｃ１、ｂａ１、ｂｃ１、ｃａ１、ｃｂ１を生成する。ここで、本例において、中間値ｂａ１及びｃａ１は、装置Ａが更なる計算を行うために必要であり、中間値ａｂ１及びｃｂ１は、装置Ｂが更なる計算を行うために必要であり、中間値ａｃ１及びｂｃ１は、装置Ｃが更なる計算を行うために必要であるものとする。そのため、装置Ａ〜Ｃは、図５に示す様に生成した中間値を、それぞれ中間値を必要とする他の装置に送信する。
【０００７】
装置Ａは、他の装置Ｂ及びＣから中間値ｂａ１及びｃａ１を受信することで、計算処理を再開し、続いて、中間値ａｂ２及びａｃ２を生成する。中間値ａｂ２は装置Ｂが更なる計算を行うために必要であり、中間値ａｃ２は装置Ｃが更なる計算を行うために必要であるので、装置Ａは、図５に示す様に生成した中間値を、それを必要とする他の装置に送信する。装置Ｂ及びＣも図５に示す様に中間値を生成し、生成した中間値を、それを必要とする他の装置に送信する。各装置Ａ〜Ｃは、必要な中間値を受信後に計算を再開し、最終値Ｙａ、Ｙｂ、Ｙｃを生成する。装置Ａ〜Ｃは、生成した最終値Ｙａ、Ｙｂ、Ｙｃを、情報を収集する装置に送信し、情報を収集する装置は、最終値Ｙａ、Ｙｂ、Ｙｃから所定の計算式で統計値を得る。
【０００８】
ＳＭＣにおいては、各装置Ａ〜Ｃは、他の装置の中間値をそれぞれ取得するが、各中間値からはその中間値の送信元の装置における入力値を知ることができない様になっている。例えば、装置Ｂは、装置Ａから中間値ａｂ１及びａｂ２を受信するが、中間値ａｂ１及びａｂ２からは装置Ａの入力値Ｘａを知ることはできない。また、情報を収集する装置は、最終値Ｙａ、Ｙｂ、Ｙｃから各装置における入力値の統計値を得ることができるが、個々の入力値を知ることはできない様になっている。なお、例えば、装置Ａがある段階で送信する中間値ａｂ１及びａｃ１を共に受信すると、装置Ａにおける入力値Ｘａを算出可能となる場合があるので、各装置間における通信は暗号化される。
【０００９】
上記従来技術においては、各装置間にフルメッシュの通信路を必要とする。ここで、フルメッシュ通信においては、システムに参加する装置の台数が増えると、各装置の負担が増大する。特に、各装置は中間値を生成するたびに、Ｎ−１個の伝送路に対して個別に信号を送信する必要があるため、計算処理を行う装置がバッテリで動作する携帯装置の場合には、バッテリの消費が早くなるという問題が生じる。
【００１０】
本発明は、複数の計算装置が中間値を交換しながら計算処理を進めるシステムであって、計算装置の通信負荷を減少させるシステム、当該システムで使用する中継装置及び計算装置並びにプログラムを提供するものである。
【課題を解決するための手段】
【００１１】
本発明によるシステムは、
複数の計算装置と中継装置を備えており、前記複数の計算装置のそれぞれは１つ以上の計算ステップを含む計算手順に従い計算処理を行い、前記複数の計算装置のそれぞれは各計算ステップを実行すると中間値を生成して他の計算装置のそれぞれに送信すると共に、前記他の計算装置のそれぞれから中間値を受信するまで次のステップの実行を待機するシステムであって、前記複数の計算装置のそれぞれは、１つの計算ステップで生成した前記他の計算装置のそれぞれに送信する中間値を１つの中間値メッセージに含めて前記中継装置に送信し、前記中継装置は、宛先の計算装置を同じとし、かつ、当該宛先の計算装置以外の総ての計算装置それぞれにおいて同じ計算ステップで生成された中間値を受信すると、当該中間値を当該宛先の計算装置への１つの中間値メッセージに含めて送信する、
ことを特徴とする。
【００１２】
本発明による計算装置は、
複数の計算装置と中継装置を備えており、前記複数の計算装置のそれぞれは１つ以上の計算ステップを含む計算手順に従い計算処理を行うシステムの前記計算装置であって、前記計算手順に従い各計算ステップを実行すると、他の計算装置のそれぞれに送信する中間値を生成し、前記他の計算装置のそれぞれが生成した中間値を受信するまで次のステップの実行を待機する計算処理手段と、前記計算処理手段が生成した前記他の計算装置のそれぞれに送信する中間値を１つの中間値メッセージに含めて前記中継装置に送信し、前記中継装置から、前記他の計算装置のそれぞれが生成し、かつ、同じ計算ステップで生成された中間値を含む１つの中間値メッセージを受信すると、受信した中間値メッセージに含まれる中間値を前記計算処理手段に出力するメッセージ処理手段と、を備えていることを特徴とする。
【００１３】
本発明による中継装置は、
複数の計算装置と中継装置を備えており、前記複数の計算装置のそれぞれは１つ以上の計算ステップを含む計算手順に従い計算処理を行い、前記複数の計算装置のそれぞれは各計算ステップを実行すると中間値を生成して他の計算装置のそれぞれに送信すると共に、他の計算装置のそれぞれから中間値を受信するまで次のステップの実行を待機するシステムの中継装置であって、保存手段と、第１の計算装置から、計算ステップを示す情報及び第１の計算装置以外の計算装置のそれぞれに送信する中間値を含む中間値メッセージを受信すると、前記計算ステップにおいて生成された第２の計算装置宛の中間値を、第２の計算装置以外の総ての計算装置から受信したかを判定し、総ての計算装置から受信していなければ、第１の計算装置から受信した第２の計算装置宛の中間値を前記保存手段に保存し、総ての計算装置から受信していれば、第１の計算装置から受信した第２の計算装置宛の中間値と、前記保存手段に保存されている第１の計算装置及び第２の計算装置以外の計算装置から受信した前記計算ステップにおいて生成された第２の計算装置宛の中間値と、を含む１つの中間メッセージを生成して、第２の計算装置に送信するメッセージ処理手段と、を備えていることを特徴とする。
【発明の効果】
【００１４】
計算装置の通信負荷を減らすことが可能になる。
【図面の簡単な説明】
【００１５】
【図１】一実施形態におけるシステム構成図。
【図２】一実施形態における中間値メッセージの送受信を示す図。
【図３】一実施形態における中間値メッセージのフォーマットを示す図。
【図４】一実施形態における中継装置と計算装置の構成図。
【図５】従来技術における中間値の送受信を示す図。
【発明を実施するための形態】
【００１６】
以下では、本発明の例示的な一実施形態について図面を参照して詳細に説明する。なお、説明に使用する各図において、発明の理解に必要ではない構成要素については省略している。
【００１７】
図１は、本実施形態における計算処理を行うための通信システムの構成図である。図１に示す様に、複数の計算装置１、中継装置２及び開始装置３はネットワーク４に接続している。なお、計算装置１及び開始装置３は、例えば、携帯型又は固定型のコンピュータや、コンピュータを含む電話等の装置である。また、中継装置２は携帯型又は固定型のコンピュータである。
【００１８】
開始装置３は、計算装置１に、関数等を含む計算の手順を示す情報を通知し、各計算装置１から前記計算の手順に従って計算された値を受信して、各計算装置１が取得した情報の統計情報を取得する装置である。なお、開始装置３が各計算装置１に通知する計算の手順はＳＭＣに従うものである。
【００１９】
また、計算装置１は、開始装置３から受信する計算の手順に従い、取得した情報に基づき開始装置３に送信する値を計算して、計算した値を開始装置３に送信する。なお、各計算装置１は、その計算処理において他の計算装置１における計算の中間結果、つまり、中間値を必要とし、よって、各計算装置１は、他の計算装置１にその計算装置１が必要とする中間値を通知する。より具体的には、各計算装置１における計算手順は、複数の計算ステップを含んでいる。各計算ステップにおいて、各計算装置１は他の計算装置１に通知する中間値を生成する。各計算装置１は１つの計算ステップを実行して中間値を生成すると、生成した中間値を他の計算装置１に通知し、他の計算装置１から中間値を受信するまで次の計算ステップの実行を待機する。各計算装置１は、他の計算装置１から中間値を受信すると、次のステップの実行を開始する。
【００２０】
本実施形態においては、開始装置３と計算装置１とは直接通信することはなく、中継装置２経由で情報の送受信を行う。また、計算装置１間においても、直接通信することはなく、中継装置２経由で情報の送受信を行う。つまり、開始装置３と各計算装置１の直接の通信相手は総て中継装置２である。なお、開始装置３と計算装置１は、その役割における分類であり、例えば、開始装置３は、ある場面においては他の開始装置３から依頼された計算を実行する計算装置１となり、逆に、計算装置１は、ある場面においては他の計算装置１に処理を依頼する開始装置３となり得る。
【００２１】
続いて、本実施形態における計算処理を図２に示す。なお、図２は図５における従来技術での処理と対比させるため、計算装置１である装置Ａ〜Ｃが必要とする他の装置における中間値は図５と同じとしている。
【００２２】
図５に示す様に、装置Ａは、１つの計算ステップを実行して中間値ａｂ１及びａｃ１を生成すると、これら中間値を含む１つの中間値メッセージを中継装置２に送信する。同様に、装置Ｂ及びＣも、１つの計算ステップを実行して中間値を生成後、これら中間値を含む１つの中間値メッセージを中継装置２に送信する。中継装置２は、装置Ｂより受信する中間値メッセージから中間値ｂａ１を取出し、装置Ｃより受信する中間値メッセージから中間値ｃａ１を取出し、中間値ｂａ１及び中間値ｃａ１を含む１つの中間値メッセージを生成して装置Ａに送信する。つまり、ある計算ステップで装置Ｂが生成した中間値ｂａ１と、同じ計算ステップで装置Ｃが生成した中間値ｃａ１を１つの中間値メッセージで装置Ａに送信する。同様に、中継装置２は、装置Ａ及びＣからの同じ計算ステップにおける中間値メッセージに含まれる、装置Ｂが必要とする中間値ａｂ１及びｃｂ１を、１つの中間値メッセージで装置Ｂに送信し、装置Ａ及びＢからの同じ計算ステップにおける中間値メッセージに含まれる、装置Ｃが必要とする中間値ａｃ１及びｂｃ１を、１つの中間値メッセージで装置Ｃに送信する。中間値ａｂ２、ａｃ２、ｂａ２、ｂｃ２、ｃａ２及びｃｂ２についても同様である。この様に、各計算装置は、各計算ステップの実行後、中間値をそれぞれ宛先となる装置に直接送信するのではなく、１つのメッセージに含めて中継装置２に送信する。中継装置２は、各計算装置から受信する同じ計算ステップにおける中間値メッセージに含まれる中間値を、宛先の計算装置毎に組み替えて、それら中間値を１つのメッセージに含めて、宛先となる計算装置にそれぞれ送信する。
【００２３】
なお、装置Ａが中継装置２に送信する中間値ａｂ１は、装置Ａ及びＢで共有している暗号化鍵で暗号化されており、中間値ａｃ１は、装置Ａ及びＣで共有している暗号化鍵で暗号化されているものとする。ここで、各計算装置１間で使用する暗号鍵は、予め各計算装置１に保存されているものとするが、例えば、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎの鍵交換アルゴリズムで生成することができる。よく知られている様に、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎの鍵交換アルゴリズムにおいては、鍵を共有する２者が、生成した乱数に基づき計算した値を交換することで共有鍵を生成する。このＤｉｆｆｉｅ−Ｈｅｌｌｍａｎの鍵交換アルゴリズムも、図２のシーケンスによって実行することができる。つまり、図２において、装置Ａが、装置Ｂ宛の値と、装置Ｃ宛の値を１つの鍵交換メッセージに含めて中継装置２に送信し、中継装置は、装置Ｂ及び装置Ｃから受信する鍵交換メッセージにそれぞれ含まれる装置Ａ宛の値を、１つの鍵交換メッセージに含めて装置Ａに送信することで、装置Ａは、装置Ｂと共有する鍵と、装置Ｃと共有する鍵をそれぞれ生成することができる。
【００２４】
図３（Ａ）は、計算装置１が中継装置２に送信する中間値又は鍵交換メッセージの例である。セッションＩＤフィールドは、後述する様に、開始装置３が開始した処理を識別するための識別子である。送信元フィールドは、メッセージの送信元の計算装置の識別子を含み、カウンタは、中間値メッセージの場合、含まれる中間値が生成された計算ステップを示すカウンタである。続いて、サイズ１フィールドは、その後に続く宛先１フィールドと、データ１フィールドの合計サイズを示す情報を含み、宛先１フィールドは、データ１フィールドに含まれる中間値又は暗号鍵を生成するための値の宛先となる装置の識別子を含んでいる。なお、装置識別子としては、装置の通信用アドレスを使用することも、例えば、中継装置２が付与する任意の値を使用することもできる。なお、サイズ２フィールド、宛先２フィールド及びデータ２フィールドも同様である。なお、図３（Ａ）は、図２に対応して２つの中間値又は暗号鍵を生成するための値を送信するメッセージであるが、これらフィールドは、送信先の計算装置１の数に応じて増減されるものである。
【００２５】
図３（Ｂ）は、中継装置２が各計算装置１に送信する中間値又は鍵交換メッセージの例である。セッションＩＤフィールド及びカウンタ・フィールドは、図３（Ａ）と同様であり、宛先フィールドは、宛先となる計算装置１の識別子が格納される。続いて、サイズ１フィールドは、その後に続く送信元１フィールドと、データ１フィールドの合計サイズを示す情報を含み、送信元１フィールドは、データ１フィールドに含まれる中間値又は暗号鍵を生成するための値の送信元となる装置の識別子を含んでいる。サイズ２フィールド、送信元２フィールド及びデータ２フィールドも同様である。なお、図３（Ｂ）は、図２に対応して２つの中間値又は暗号鍵を生成するための値を送信するメッセージであるが、これらフィールドは、送信先の計算装置１の数に応じて増減されるものである。
【００２６】
続いて、図１に示すシステム全体の動作について説明する。まず、事前準備として、各計算装置１は、中継装置２に対して、通信アドレスやポート番号といった通信するために必要な情報を登録しておく。さらに、計算装置１は、開始装置３が計算装置１を選択するための任意の情報を登録しておくこともできる。そして、計算処理は、開始装置３が、中継装置２に対して開始要求メッセージを送信することにより開始される。開始要求メッセージには、計算処理に参加させる計算装置１のリストと、各計算装置１における計算の手順を示す情報とを含める。ここで、開始装置３は、計算処理に参加させる計算装置１を、中継装置２にあらかじめ登録された情報に基づき選択する。なお、中継装置２と開始装置３間における、計算処理に参加させる計算装置１の選択の情報を送受する方法は任意である。また、開始装置３が計算処理に参加させる計算装置１を選択するのではなく、例えば、必要な数のみを送信し、中継装置２が選択する形態であっても良い。
【００２７】
中継装置２は、開始要求メッセージを受信すると、セッションＩＤを生成し、計算処理を依頼する計算装置１の識別情報と、生成したセッションＩＤを関連づけて保存する。セッションＩＤは、以後、当該開始要求メッセージで開始した計算処理に関する通信で使用される。そのため、中継装置２は、生成したセッションＩＤを開始装置３に通知する。さらに、中継装置２は、計算処理を依頼する計算装置１のそれぞれに対して、計算手順を示す情報と、計算処理を依頼している計算装置１のリストと、セッションＩＤを含む処理依頼メッセージを送信する。なお、処理依頼メッセージに含まれる計算装置１のリストは、計算装置１の識別子のリストであり、この識別子は中継装置２が付与した識別子であっても、通信用のアドレスであっても良い。しかしながら、各計算装置１が相互にその身元を秘匿するためには、中継装置２が付与した識別子を使用することが好ましい。
【００２８】
その後は、図２にて説明した様に、各計算装置１は、計算手順に従い、中間値を他の計算装置に中継装置２経由で送信し、最終結果である最終値を得る。これら最終値は、中継装置２経由で開始装置３に送信される。なお、開始装置３に送信される最終値は、任意の方法、例えば、開始装置３の公開鍵暗号や、開始装置３と計算装置１それぞれとの秘密の共有鍵を使用して暗号化される。最後に、開始装置３は各計算装置１から受信する最終値を入力として所定の計算を行うことにより所望の情報を取得する。
【００２９】
図４（Ａ）は、本実施形態による中継装置２の構成図である。ノード管理部２１は、計算装置１についてのノード情報を保持している。具体的には、ノード情報は、各計算装置１が登録した通信アドレスやポート番号といった、通信するために必要な情報を含んでいる。さらに、通信アドレス以外で計算装置１を識別するのであれば、中継装置２が付与した識別子がノード情報には含まれことになる。さらに、ノード情報は、開始装置３が計算装置１を選択するための任意の情報を含むことができる。
【００３０】
メッセージ処理部２３は、開始装置３から、開始要求メッセージを受信するとセッションＩＤを生成し、計算処理を依頼する計算装置１の識別情報と、生成したセッションＩＤを関連づけて保存部２２に保存する。また、生成したセッションＩＤを開始装置３に通知する。さらに、計算処理を依頼する計算装置１のそれぞれに対して、計算手順を示す情報と、計算処理を依頼している計算装置１のリストと、セッションＩＤを含む処理依頼メッセージを送信する。
【００３１】
さらに、メッセージ処理部２３は、図３（Ａ）に示す中間値メッセージを計算装置１から受信すると、受信した中間値メッセージに含まれる中間値により、当該中間メッセージに対応する計算ステップで生成された、ある計算装置１宛の中間値が総て揃うか否かを判定する。揃わない場合には、受信した中間値メッセージに含まれる当該計算装置１宛の中間値を保存部２２に保存する。なお、この処理は受信した中間値メッセージに含まれる各中間値の宛先となる計算装置１に対してそれぞれ行われる。一方、揃う場合には、受信した中間値メッセージに含まれる当該計算装置１宛の中間値と、既に受信して保存部２２に保存している、当該計算ステップで生成された当該計算装置１宛の中間値を含む１つの中間値メッセージを生成して、当該計算装置１に送信する。なお、計算ステップは、中間値メッセージのカウンタ・フィールドから判定する。最後に、メッセージ処理部２３は、各計算装置１から最終値を受信すると、受信した最終値を開始装置３に送信する。また、メッセージ処理部２３は、計算装置１間での鍵交換メッセージを受信した場合も、中間値メッセージと同様に、その宛先毎に値を組み替えて送信する。
【００３２】
図４（Ｂ）は、本実施形態による計算装置１の構成図である。メッセージ処理部１２は、中継装置２から、処理依頼メッセージを受信すると、計算装置１のリストと、セッションＩＤを保存する。そして、計算処理部１３は、処理依頼メッセージに含まれる手順に従い計算処理を実行する。また、メッセージ処理部１２は、計算処理部１３が、１つの計算ステップを実行して他の計算装置１に送信すべき中間値を生成すると、生成した中間値及びどの計算ステップであるかを示す番号を含む中間値メッセージを中継装置２に送信する。また、中継装置２から計算ステップを示す番号を含む中間値メッセージを受信すると、含まれる中間値を計算処理部１３に出力する。計算処理部１３は、ある計算ステップにおいて他の計算装置１が生成した中間値を受信するまで待機し、これら中間値を受信後、次の計算ステップの実行を開始する。また、計算処理部１３が、計算手順に従い最終的に開始装置３に送信する最終値を生成すると、メッセージ処理部１２は、この最終値を中継装置２に送信する。
【００３３】
また、鍵生成部１１は、他の計算装置１のそれぞれと共有する暗号化の鍵を生成するための値を、他の計算装置１のそれぞれについて生成してメッセージ処理部１２に出力する。メッセージ処理部１２は、他の計算装置１のそれぞれについて生成した暗号鍵を生成するための値を鍵交換メッセージに含めて中継装置１に送信する。また、鍵生成部１１は、メッセージ処理部１２が中継装置１から受信した鍵交換メッセージに含まれる、他の計算装置１のそれぞれが生成した暗号鍵を生成するための値を受け取ると、各計算装置１と共有する暗号鍵をそれぞれ生成する。
【００３４】
以上の構成により、各計算装置１は、各計算ステップにおける中間値を送信するための通信回数を減らすことができ、よって、通信負荷を軽減することができる。
【００３５】
なお、上述した実施形態においては、中継装置２が１台の装置であるものとしたが、ネットワーク４経由で相互に通信可能である複数の装置により構成することもできる。この場合、計算装置１はいずれかの中継装置２のノード管理部２１に自装置の情報を登録して、登録した中継装置２とのみ通信を行う。なお、計算装置１が中継装置２に登録した情報は、各中継装置２で共有される。つまり、各中継装置２は、自装置と通信する計算装置１に加えて、他の中継装置２と通信する計算装置１についても認識する。なお、このとき各中継装置は、自装置とは直接通信しない計算装置１が、どの中継装置２と通信しているのかについてもノード管理部２１に登録する。
【００３６】
また、中継装置２は、開始要求メッセージを受信すると、自装置と直接通信する計算装置１に対しては、直接、処理依頼メッセージを送信し、それ以外の計算装置１には、これら計算装置１が直接通信する中継装置２に処理依頼メッセージを送信する。他の中継装置２から処理依頼メッセージを受信した中継装置２は、自装置と直接通信する計算装置１に対して処理依頼メッセージを送信する。
【００３７】
また、中間値の組み替えについても、各中間値を、その宛先となる計算装置１と直接通信する中継装置２に集め、各中継装置２は、ある計算ステップにおける、自装置が直接通信する計算装置１宛の総ての中間値を受信すると、１つの中間値メッセージに含めて宛先となる計算装置１に送信する。なお、中継装置２間の中間値の送信方法は任意である。
【００３８】
なお、上記計算装置１及び中継装置２は、コンピュータを上述した計算装置１や中継装置２として動作させるプログラムにより実現することができる。これらコンピュータプログラムは、コンピュータが読み取り可能な記憶媒体に記憶されて、又は、ネットワーク経由で配布が可能なものである。
【図１】
0005820314.tif 000002
【図２】
0005820314.tif 000003
【図３】
0005820314.tif 000004
【図４】
0005820314.tif 000005
【図５】
0005820314.tif 000006