制御装置、計算システムおよび制御プログラム
【課題】一般的なプログラムのｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎを行う際に、より効率的に計算を行うことができる。
【解決手段】記憶部２４は、プログラムの実行結果として得られる宛先ラベルと端末装置を特定する情報とを関連付ける転送先情報を記憶する。受信部２２は、あるプログラムを実行した端末装置から、次に実行すべきプログラムの入力キーと入力キーの転送先に対応する宛先ラベルとを受信する。送信部２１は、受信部２２が受信した宛先ラベルに基づいて転送先情報から転送先の端末装置を特定し、受信部２２が受信した入力キーを転送先の端末装置へ送信する。
【解決手段】記憶部２４は、プログラムの実行結果として得られる宛先ラベルと端末装置を特定する情報とを関連付ける転送先情報を記憶する。受信部２２は、あるプログラムを実行した端末装置から、次に実行すべきプログラムの入力キーと入力キーの転送先に対応する宛先ラベルとを受信する。送信部２１は、受信部２２が受信した宛先ラベルに基づいて転送先情報から転送先の端末装置を特定し、受信部２２が受信した入力キーを転送先の端末装置へ送信する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、制御装置、計算システムおよび制御プログラムに関する。
【背景技術】
【０００２】
ネットワーク上に参加者（計算機）1〜参加者nのn人の参加者がおり、各参加者は自分の秘密情報ｘ１〜ｘｎを持っている。各参加者が保持する秘密情報ｘ１〜ｘｎを他の参加者に開示することなく、ある関数ｆ（ｘ１，・・・，ｘｎ）を計算する問題としてｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎが知られている。
【０００３】
ｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎの具体例として、ネットワーク上での投票について説明する。ネットワーク上での投票では、秘密情報ｘｊは参加者ｊの投票結果である。なお、賛成ならｘｊは１であり、反対なら０であるとする。また、関数ｆ（ｘ１，・・・，ｘｎ）は、賛成票の数を計算する関数であり、ｆ（ｘ１，・・・，ｘｎ）＝ｘ１＋・・・＋ｘｎである。
【０００４】
従来、関数ｆが論理回路として表せるような計算であれば、参加者１〜参加者ｎがお互い他の参加者１〜参加者ｎが保有する秘密情報秘密情報ｘ１〜ｘｎを知ることなく関数ｆの計算を行う方法が知られている（例えば、非特許文献１参照）。
【０００５】
具体的には、関数ｆの計算を行うプログラムを論理回路として表す。その後、論理回路を暗号化する。なお、暗合化した論理回路をＧａｒｂｌｅｄ ｃｉｒｃｕｉｔと呼ぶ。また、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔでは、入出力はある程度のビット長を持つキーとして表させる。そして、正しい入力キーを持つ者だけが、それに対応する出力値に相当するキーを計算することができる。これらのキーは、乱数により生成されるので、キーを見ただけでは、その入出力値が表す値（平文）を知ることはできない。
【０００６】
参加者１は、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔを保持する。その他の参加者２〜参加者ｎは、自分の秘密情報を表す入力キーを保持しており、これを参加者1に送る。参加者１は、受信した入力キーに基づいてＧａｒｂｌｅｄ ｃｉｒｃｕｉｔを計算し、出力値を求める。これにより、参加者２〜参加者ｎは他の参加者２〜参加者ｎが保有する秘密情報秘密情報ｘ１〜ｘｎを知ることなく関数ｆの計算結果を知ることができる。
【非特許文献１】Foundations of Cryptography Volume II Basic Applications, Cambridge University Press, May 10, 2004.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、非特許文献１の方法では、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔを評価する参加者１は回路中の各論理ゲートの値が分からない状態で計算を行うので、途中の計算結果の状態に応じて選択的に処理を行うことができないという問題がある。具体的には、途中の計算結果の状態がわからないため、通常のプログラムでのｉｆ文の処理に該当する処理を行うことができない。これにより、非特許文献１の方法では、関数ｆの計算を行うプログラムによっては効率が非常に低下する。
【０００８】
本発明は上記の課題を解決するためになされたものであり、一般的なプログラムのｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎを行う際に、より効率的に計算を行うことができる制御装置、計算システムおよび制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明は、分割されたプログラムを複数の端末装置で分担して実行する計算システムの制御装置において、前記プログラムの実行結果として得られる宛先ラベルと前記端末装置を特定する情報とを関連付ける転送先情報を記憶する記憶部と、あるプログラムを実行した前記端末装置から、次に実行すべきプログラムの入力キーと前記入力キーの転送先に対応する宛先ラベルとを受信する受信部と、前記受信部が受信した前記宛先ラベルに基づいて前記転送先情報から転送先の端末装置を特定し、前記受信部が受信した前記入力キーを前記転送先の端末装置へ送信する送信部と、を備えたことを特徴とする制御装置である。
【００１０】
また、本発明は、分割されたプログラムを複数の端末装置で分担して実行する計算システムにおいて、制御装置と、前記制御装置より送信された入力キーを受信する端末受信部と、受信した前記入力キーに基づいて前記分割されたプログラムを実行し、次に実行すべきプログラムの入力キーと前記入力キーの転送先に対応する宛先ラベルとを取得する制御部と、前記制御部が取得した前記プログラムの入力キーと前記宛先ラベルとを送信する端末送信部と、を備えた端末装置と、を備えたことを特徴とする計算システムである。
【００１１】
また、本発明は、分割されたプログラムを複数の端末装置で分担して実行する計算システムの制御をコンピュータに実行させるための制御プログラムにおいて、前記分割されたプログラムの実行結果として得られる宛先ラベルと前記端末装置を特定する情報とを関連付ける転送先情報を記憶する記憶部と、あるプログラムを実行した前記端末装置から、次に実行すべきプログラムの入力キーと前記入力キーの転送先に対応する宛先ラベルとを受信する受信部と、前記受信部が受信した前記宛先ラベルに基づいて前記転送先情報から転送先の端末装置を特定し、前記受信部が受信した前記入力キーを前記転送先の端末装置へ送信する送信部と、としてコンピュータを実行させるための制御プログラムである。
【発明の効果】
【００１２】
本発明によれば、一般的なプログラムのｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎを行う際に、より効率的に計算を行うことができる。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の一実施形態について図を参照して説明する。本実施形態のｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎを行う計算計算システムは、参加者が３人おり、３人の参加者の投票に応じて可決か否決かを判断する計算システムとする。なお、本実施形態の計算システムは、３人の参加者のうち、２人以上が賛成であれば１（可決）を出力し、それ以外であれば０（否決）を出力する。
【００１４】
図１は、本実施形態におけるｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎを行う計算システムの構成を示した構成図である。図示する例では、計算システムは参加者１１−１〜１１−３と、仲介者１２と、評価者１３−１〜１３−５（端末装置）と、制御装置１４とを含んでいる。
【００１５】
参加者１１−１〜１１−３は、投票を行う端末であり、例えばコンピュータである。仲介者１２は、計算システムで使用する情報の準備を行う端末であり、例えばコンピュータである。評価者１３−１〜１３−５はプログラムを実行する装置であり、例えばコンピュータである。また、評価者１３−１〜１３−５は、制御装置１４と通信を行うための端末送信部と端末受信部とを備える。制御装置１４は計算システムの制御および情報の転送を行う装置であり、例えばルータである。
【００１６】
図２は、本実施形態における制御装置の構成を示した構成図である。図示する例では、制御装置１４は、送信部２１と、受信部２２と、制御部２３と、記憶部２４とを備える。送信部２１は他の装置に情報を送信する。受信部２２は他の装置から送信された情報を受信する。制御部２３は制御装置１４の制御を行う。記憶部２４は制御装置１４が使用する情報を記憶する。
【００１７】
図３は、本実施形態におけるｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎを行うプログラムとＣｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ（制御フローグラフ）とを示した図である。図示する例では、プログラム３１はブロックｆと、ブロックｇと、ブロックｈとからなる。
【００１８】
このプログラムのＣｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３２は、ブロックＩＤがｆのブロックｆと、ブロックＩＤがｇのブロックｇと、ブロックＩＤがｈのブロックｈとからなる。また、Ｃｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３２のループを展開したＣｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３３は、ブロックＩＤがｆのブロックｆと、ブロックＩＤがｇ１のブロックｇ１と、ブロックＩＤがｇ２のブロックｇ２と、ブロックＩＤがｇ３のブロックｇ３と、ブロックＩＤがｈのブロックｈとからなる。
【００１９】
なお、プログラムをブロックに分割する方法は、例えば「Frances E. Allen, "Control flow analysis",ACM SIGPLAN Notices archive, Volume 5 , Issue 7 (July 1970)」に記載の方法で行う。また、本実施形態では、仲介者１２がプログラム３１をブロックに分割する。
【００２０】
次に、本実施形態におけるｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎを行うための事前準備について説明する。本実施形態では、事前準備は仲介者１２が行う。仲介者１２は、プログラム３１に基づいたＣｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３３の各ブロックにラベル（宛先ラベル）をランダムに割り当てる。
【００２１】
本実施形態では、仲介者１２は、ブロックｆにラベル３を割り当て、ブロックｇ１にラベル１を割り当て、ブロックｇ２にラベル５を割り当て、ブロックｇ３にラベル２を割り当て、ブロックｈにラベル４を割り当てる。
【００２２】
続いて、仲介者１２は、ランダムにＣｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３３の各ブロックを評価者１３−１〜１３−５に割り当てる。本実施形態では、ブロックｆを評価者１３−２に割り当て、ブロックｇ１を評価者１３−４に割り当て、ブロックｇ２を評価者１３−１に割り当て、ブロックｇ３を評価者１３−５に割り当て、ブロックｈを評価者１３−３に割り当てる。
【００２３】
続いて、仲介者１２は、Ｃｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３３の各ブロックに該当するプログラムを論理回路として表し、論理回路を暗号化する。なお、暗合化した論理回路をＧａｒｂｌｅｄ ｃｉｒｃｕｉｔと呼ぶ。
【００２４】
続いて、仲介者１２は、Ｃｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３３の各ブロックに該当するプログラムのＧａｒｂｌｅｄ ｃｉｒｃｕｉｔと、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔの入力となるキーを作成する。続いて、仲介者１２は、各ブロックを割り当てた評価者１３−１〜１３−５に作成したＧａｒｂｌｅｄ ｃｉｒｃｕｉｔを送付する。例えば、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｆ）を評価者１３−２に送付する。他のＧａｒｂｌｅｄ ｃｉｒｃｕｉｔについても同様に評価者１３−１〜１３−５に送付する。
【００２５】
続いて、仲介者１２は、Ｃｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３３の各ブロックに割り当てたラベル１〜５と、評価者１３−１〜１３−５に割り当てたＣｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３３の各ブロックとに基づいて、ラベル１〜５と評価者１３−１〜１３−５とを関連付ける表である宛先リスト（転送先情報）を作成し、制御装置１４に送付する。
【００２６】
本実施形態の宛先リストでは、ラベル１と評価者４とが関連付けられ、ラベル２と評価者５とが関連付けられ、ラベル３と評価者２とが関連付けられ、ラベル４と評価者３とが関連付けられ、ラベル５と評価者１とが関連付けられている。
【００２７】
続いて、仲介者１２は、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔの入力となるキーの入力を受け付けるＧａｒｂｌｅｄ ｃｉｒｃｕｉｔに付されているラベル１〜５をキーに付し、参加者１１−１〜１１−３に対して送付する。本実施形態では、ブロックｇ１〜ｇ３のＧａｒｂｌｅｄ ｃｉｒｃｕｉｔがキーの入力を受け付ける。仲介者１２は、ブロックｇ１が受けつけるキーにはラベル１を付し、ブロックｇ２が受け付けるキーにはラベル５を付し、ブロックｇ３が受け付けるキーにはラベル２を付す。
【００２８】
また、本実施形態では、入力となるキーとしては、参加者１１−１〜１１−３が投票する結果である。ブロックｇ１〜ｇ３が受け付けるキーの値は、賛成の値「１」と反対の値「０」との２通りの値が考えられる。
【００２９】
よって、仲介者１２は、参加者１１−１に対して、賛成の値「１」が含まれ、ラベル１が付されたキー「Ｖ［１］＝１」と、反対の値「０」が含まれ、ラベル１が付されたキー「Ｖ［１］＝０」とを作成し送付する。また、仲介者１２は、参加者１１−２に対して、賛成の値「１」が含まれ、ラベル５が付されたキー「Ｖ［２］＝１」と、反対の値「０」が含まれ、ラベル５が付されたキー「Ｖ［２］＝０」とを作成し送付する。また、仲介者１２は、参加者１１−３に対して、賛成の値「１」が含まれ、ラベル３が付されたキー「Ｖ［３］＝１」と、反対の値「０」が含まれ、ラベル３が付されたキー「Ｖ［３］＝０」とを作成し送付する。
【００３０】
なお、キーは乱数により生成されるため、キーを見ただけではキーに含まれる値を知ることができない。そのため、参加者１１−１〜１１−３が賛成の値が含まれたキーと反対の値が含まれたキーとを区別できるようにして、仲介者１２はキーを送信する。
【００３１】
図４は、本実施形態において、仲介者２がＧａｒｂｌｅｄ ｃｉｒｃｕｉｔのキーを作成した状態の計算システムの構成を示した図である。図示する例では、仲介者２は、参加者１１−１〜１１−３に送付するキーを計８個生成している。仲介者２は、このキーを参加者１１−１〜１１−３に送付する。また、制御装置４は、ラベル１〜５と評価者１３−１〜１３−５とを関連付けたあて先リストを記憶している。
【００３２】
次に、本実施形態において、参加者１１−１〜１１−３が行う投票方法について説明する。本実施形態では、参加者１１−１〜１１−３は事前準備で仲介者１２から送信されたキーを用いて投票を行う。例えば、参加者１１−１は、賛成の場合、賛成の値が含まれたキー「Ｖ［１］＝１」を制御装置１４に送信し、反対の場合、反対の値が含まれたキー「Ｖ［１］＝０」を制御装置１４に送信する。参加者１１−１と同様に、他の参加者１１−２〜１１−３も投票を行う。投票を受け付けた制御装置１４は、記憶部２３に受信したキーを記憶する。なお、先述したとおり、キーを見ただけではキーに含まれている情報が分からないため、制御装置１４は、参加者１１−１〜１１−３が投票した値を知ることはできない。
【００３３】
本実施形態では、参加者１１−１は、値「１」が含まれており、ラベル１が付されているキー「Ｖ［１］＝１」を制御装置１４に送付する。また、参加者１１−２は、値「１」が含まれており、ラベル５が付されているキー「Ｖ［２］＝１」を制御装置１４に送付する。また、参加者１１−３は、値「１」が含まれており、ラベル２が付されているキー「Ｖ［３］＝１」を制御装置１４に送付する。
【００３４】
仲介者１２による事前準備と、参加者１１−１〜１１−３による投票が終了後、仲介者１２は、ブロックｆを割り当てた評価者１３−２に対して、プログラムの実行を開始するためのキーを送信する。プログラムの実行を開始するためのキーを受け取った評価者１３−２は、自身に送信されたＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｆ）を復号し、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｆ）の出力であるキー「ｊ＝１，ｓ＝０」とラベル１とを得る。続いて、評価者１３−２は、キー「ｊ＝１，ｓ＝０」をラベル１に対して送信する。
【００３５】
なお、本実施形態では、ｓは賛成票の数を足し合わせた数である。また、ｊはプログラムの処理において、何人目の参加者の投票の処理を行っているかを示す数である。また、ｒｅｓｕｌｔは、プログラム最終的な出力結果であり、３人の参加者のうち、２人以上が賛成であれば１（可決）であり、それ以外であれば０（否決）である。
【００３６】
制御装置１４は、評価者１３−２がラベル１に対して送信したキー「ｊ＝１，ｓ＝０」を受信する。続いて、制御装置１４の制御部２３は、記憶部２４に記憶している宛先リストに基づいて、ラベル１に関連付けられている評価者１３−４を特定する。続いて、制御装置４の制御部２３は、記憶部２４が記憶しているキーのうち、ラベル１が付されているキー「Ｖ［１］＝１」を特定する。続いて、制御装置１４の制御部２３は送信部２１を介して、特定したキー「Ｖ［１］＝１」と、評価者１３−２がラベル１に対して送信したキー「ｊ＝１，ｓ＝０」とを評価者１３−４に送信する。
【００３７】
図５は、本実施形態において、評価者１３−２がＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｆ）の処理を実行した状態の計算システムの構成を示した図である。図示する例では、評価者１３−２は、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｆ）の出力であるキー「ｊ＝１，ｓ＝０」をラベル１宛に送信している。また、制御装置１４は、評価者１３−２がラベル１宛に送信したキー「ｊ＝１，ｓ＝０」の送信先である評価者１３−４を特定し、キー「ｊ＝１，ｓ＝０」と、キー「Ｖ［１］＝１」とを評価者１３−４に送信している。
【００３８】
続いて、キー「ｊ＝１，ｓ＝０」と、キー「Ｖ［１］＝１」とを受信した評価者１３−４は、自身に送信されたＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｇ１）を復号し、キー「ｊ＝１，ｓ＝０」とキー「Ｖ［１］＝１」とに基づいてＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｇ１）の出力であるキー「ｊ＝２，ｓ＝１」とラベル５とを得る。続いて、評価者１３−４は、キー「ｊ＝２，ｓ＝１」をラベル５に対して送信する。
【００３９】
制御装置１４は、評価者１３−４がラベル５に対して送信したキー「ｊ＝２，ｓ＝１」を受信する。続いて、制御装置１４の制御部２３は、記憶部２４に記憶している宛先リストに基づいて、ラベル５に関連付けられている評価者１３−１を特定する。続いて、制御装置４の制御部２３は、記憶部２４が記憶しているキーのうち、ラベル５が付されているキー「Ｖ［２］＝１」を特定する。続いて、制御装置１４の制御部２３は送信部２１を介して、特定したキー「Ｖ［２］＝１」と、評価者１３−４がラベル５に対して送信したキー「ｊ＝２，ｓ＝１」とを評価者１３−１に送信する。
【００４０】
図６は、本実施形態において、評価者１３−４がＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｇ１）の処理を実行した状態の計算システムの構成を示した図である。図示する例では、評価者１３−４は、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｇ１）の出力であるキー「ｊ＝２，ｓ＝１」をラベル５宛に送信している。また、制御装置１４は、評価者１３−４がラベル５宛に送信したキー「ｊ＝２，ｓ＝１」の送信先である評価者１３−１を特定し、キー「ｊ＝２，ｓ＝１」と、キー「Ｖ［２］＝１」とを評価者１３−１に送信している。
【００４１】
続いて、キー「ｊ＝２，ｓ＝１」と、キー「Ｖ［２］＝１」とを受信した評価者１３−１は、自身に送信されたＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｇ２）を復号し、キー「ｊ＝２，ｓ＝１」とキー「Ｖ［２］＝１」とに基づいてＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｇ２）の出力であるキー「ｊ＝３，ｓ＝２」とラベル４とを得る。続いて、評価者１３−１は、キー「ｊ＝３，ｓ＝２」をラベル４に対して送信する。
【００４２】
制御装置１４は、評価者１３−１がラベル４に対して送信したキー「ｊ＝３，ｓ＝２」を受信する。続いて、制御装置１４の制御部２３は、記憶部２４に記憶している宛先リストに基づいて、ラベル４に関連付けられている評価者１３−３を特定する。続いて、制御装置４の制御部２３は、記憶部２４が記憶しているキーのうち、ラベル３が付されているキーを検索するが、本実施形態ではラベル３が付されているキーは無い。続いて、ラベル３が付されているキーは無いため、制御装置１４の制御部２３は送信部２１を介して、評価者１３−１がラベル４に対して送信したキー「ｊ＝３，ｓ＝２」のみを評価者１３−３に送信する。
【００４３】
図７は、本実施形態において、評価者１３−１がＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｇ２）の処理を実行した状態の計算システムの構成を示した図である。図示する例では、評価者１３−１は、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｇ２）の出力であるキー「ｊ＝３，ｓ＝２」をラベル４宛に送信している。また、制御装置１４は、評価者１３−１がラベル４宛に送信したキー「ｊ＝３，ｓ＝２」の送信先である評価者１３−３を特定し、キー「ｊ＝３，ｓ＝２」を評価者１３−３に送信している。
【００４４】
続いて、キー「ｊ＝３，ｓ＝２」を受信した評価者１３−３は、自身に送信されたＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｈ）を復号し、キー「ｊ＝３，ｓ＝２」に基づいてＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｈ）の出力であるキー「Ｒｅｓｕｌｔ＝１」を得る。また、評価者１３−３は、参加者１１−１〜１１−３に対して「Ｒｅｓｕｌｔ＝１」を送信する。
【００４５】
参加者１１−１〜１１−３は、評価者１３−３が送信した「Ｒｅｓｕｌｔ＝１」を受信する。これにより、参加者１１−１〜１１−３は、投票結果を知ることができる。
【００４６】
図８は、本実施形態において、評価者１３−３がＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｈ）の処理を実行した状態の計算システムの構成を示した図である。図示する例では、評価者１３−３は、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｈ）の出力であるキー「Ｒｅｓｕｌｔ＝１」を参加者１１−１〜１１−３宛に送信している。
【００４７】
上述したとおり、本実施形態によれば、プログラムを複数に分割し、分割したプログラムを論理回路として表し、その論理回路を暗号化する（Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔ）。また、複数の暗号化した論理回路の実行順を制御する制御装置１４を設けている。
【００４８】
制御装置１４は、ラベル１〜５と評価者１３−１〜１３−５とを関連付けた宛先リストを記憶しており、評価者１３−１〜１３−５から送信されたラベル１〜５と、次に実行すべきプログラムの入力キーとを受信し、受信したラベル１〜５と宛先リストとに基づいて受信した入力キーを評価者１３−１〜１３−５に送信する。これにより、途中の計算結果の状態に応じてラベル１〜５が制御装置１４に送信され、制御装置１４は、ラベル１〜５に応じて次に実行するＧａｒｂｌｅｄ ｃｉｒｃｕｉｔを指定する。
【００４９】
すなわち、制御装置１４が途中の計算結果に応じて次に実行するＧａｒｂｌｅｄ ｃｉｒｃｕｉｔを指定する。これにより、途中の計算結果の状態に応じて選択的に処理を行うことができる。よって、一般的なプログラムのｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎを行う際に、より効率的に計算を行うことができる。
【００５０】
なお、上述した実施形態における制御装置全体あるいはその一部は、これらの機能実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現しても良い。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。
【００５１】
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時刻の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時刻プログラムを保持しているものも含んでも良い。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【００５２】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【００５３】
【図１】本発明の一実施形態における計算システムの構成を示した図である。
【図２】本実施形態における制御装置の構成を示した構成図である。
【図３】本実施形態におけるｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎを行うプログラムとＣｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈとを示した図である。
【図４】本実施形態における計算システムの構成を示した構成図である。
【図５】本実施形態における計算システムの構成を示した構成図である。
【図６】本実施形態における計算システムの構成を示した構成図である。
【図７】本実施形態における計算システムの構成を示した構成図である。
【図８】本実施形態における計算システムの構成を示した構成図である。
【符号の説明】
【００５４】
１１−１〜１１−３・・・参加者、１２・・・仲介者、１３−１〜１３−５・・・評価者、１４・・・制御装置、２１・・・送信部、２２・・・受信部、２３・・・制御部、２４・・・記憶部
【技術分野】
【０００１】
本発明は、制御装置、計算システムおよび制御プログラムに関する。
【背景技術】
【０００２】
ネットワーク上に参加者（計算機）1〜参加者nのn人の参加者がおり、各参加者は自分の秘密情報ｘ１〜ｘｎを持っている。各参加者が保持する秘密情報ｘ１〜ｘｎを他の参加者に開示することなく、ある関数ｆ（ｘ１，・・・，ｘｎ）を計算する問題としてｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎが知られている。
【０００３】
ｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎの具体例として、ネットワーク上での投票について説明する。ネットワーク上での投票では、秘密情報ｘｊは参加者ｊの投票結果である。なお、賛成ならｘｊは１であり、反対なら０であるとする。また、関数ｆ（ｘ１，・・・，ｘｎ）は、賛成票の数を計算する関数であり、ｆ（ｘ１，・・・，ｘｎ）＝ｘ１＋・・・＋ｘｎである。
【０００４】
従来、関数ｆが論理回路として表せるような計算であれば、参加者１〜参加者ｎがお互い他の参加者１〜参加者ｎが保有する秘密情報秘密情報ｘ１〜ｘｎを知ることなく関数ｆの計算を行う方法が知られている（例えば、非特許文献１参照）。
【０００５】
具体的には、関数ｆの計算を行うプログラムを論理回路として表す。その後、論理回路を暗号化する。なお、暗合化した論理回路をＧａｒｂｌｅｄ ｃｉｒｃｕｉｔと呼ぶ。また、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔでは、入出力はある程度のビット長を持つキーとして表させる。そして、正しい入力キーを持つ者だけが、それに対応する出力値に相当するキーを計算することができる。これらのキーは、乱数により生成されるので、キーを見ただけでは、その入出力値が表す値（平文）を知ることはできない。
【０００６】
参加者１は、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔを保持する。その他の参加者２〜参加者ｎは、自分の秘密情報を表す入力キーを保持しており、これを参加者1に送る。参加者１は、受信した入力キーに基づいてＧａｒｂｌｅｄ ｃｉｒｃｕｉｔを計算し、出力値を求める。これにより、参加者２〜参加者ｎは他の参加者２〜参加者ｎが保有する秘密情報秘密情報ｘ１〜ｘｎを知ることなく関数ｆの計算結果を知ることができる。
【非特許文献１】Foundations of Cryptography Volume II Basic Applications, Cambridge University Press, May 10, 2004.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、非特許文献１の方法では、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔを評価する参加者１は回路中の各論理ゲートの値が分からない状態で計算を行うので、途中の計算結果の状態に応じて選択的に処理を行うことができないという問題がある。具体的には、途中の計算結果の状態がわからないため、通常のプログラムでのｉｆ文の処理に該当する処理を行うことができない。これにより、非特許文献１の方法では、関数ｆの計算を行うプログラムによっては効率が非常に低下する。
【０００８】
本発明は上記の課題を解決するためになされたものであり、一般的なプログラムのｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎを行う際に、より効率的に計算を行うことができる制御装置、計算システムおよび制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明は、分割されたプログラムを複数の端末装置で分担して実行する計算システムの制御装置において、前記プログラムの実行結果として得られる宛先ラベルと前記端末装置を特定する情報とを関連付ける転送先情報を記憶する記憶部と、あるプログラムを実行した前記端末装置から、次に実行すべきプログラムの入力キーと前記入力キーの転送先に対応する宛先ラベルとを受信する受信部と、前記受信部が受信した前記宛先ラベルに基づいて前記転送先情報から転送先の端末装置を特定し、前記受信部が受信した前記入力キーを前記転送先の端末装置へ送信する送信部と、を備えたことを特徴とする制御装置である。
【００１０】
また、本発明は、分割されたプログラムを複数の端末装置で分担して実行する計算システムにおいて、制御装置と、前記制御装置より送信された入力キーを受信する端末受信部と、受信した前記入力キーに基づいて前記分割されたプログラムを実行し、次に実行すべきプログラムの入力キーと前記入力キーの転送先に対応する宛先ラベルとを取得する制御部と、前記制御部が取得した前記プログラムの入力キーと前記宛先ラベルとを送信する端末送信部と、を備えた端末装置と、を備えたことを特徴とする計算システムである。
【００１１】
また、本発明は、分割されたプログラムを複数の端末装置で分担して実行する計算システムの制御をコンピュータに実行させるための制御プログラムにおいて、前記分割されたプログラムの実行結果として得られる宛先ラベルと前記端末装置を特定する情報とを関連付ける転送先情報を記憶する記憶部と、あるプログラムを実行した前記端末装置から、次に実行すべきプログラムの入力キーと前記入力キーの転送先に対応する宛先ラベルとを受信する受信部と、前記受信部が受信した前記宛先ラベルに基づいて前記転送先情報から転送先の端末装置を特定し、前記受信部が受信した前記入力キーを前記転送先の端末装置へ送信する送信部と、としてコンピュータを実行させるための制御プログラムである。
【発明の効果】
【００１２】
本発明によれば、一般的なプログラムのｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎを行う際に、より効率的に計算を行うことができる。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の一実施形態について図を参照して説明する。本実施形態のｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎを行う計算計算システムは、参加者が３人おり、３人の参加者の投票に応じて可決か否決かを判断する計算システムとする。なお、本実施形態の計算システムは、３人の参加者のうち、２人以上が賛成であれば１（可決）を出力し、それ以外であれば０（否決）を出力する。
【００１４】
図１は、本実施形態におけるｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎを行う計算システムの構成を示した構成図である。図示する例では、計算システムは参加者１１−１〜１１−３と、仲介者１２と、評価者１３−１〜１３−５（端末装置）と、制御装置１４とを含んでいる。
【００１５】
参加者１１−１〜１１−３は、投票を行う端末であり、例えばコンピュータである。仲介者１２は、計算システムで使用する情報の準備を行う端末であり、例えばコンピュータである。評価者１３−１〜１３−５はプログラムを実行する装置であり、例えばコンピュータである。また、評価者１３−１〜１３−５は、制御装置１４と通信を行うための端末送信部と端末受信部とを備える。制御装置１４は計算システムの制御および情報の転送を行う装置であり、例えばルータである。
【００１６】
図２は、本実施形態における制御装置の構成を示した構成図である。図示する例では、制御装置１４は、送信部２１と、受信部２２と、制御部２３と、記憶部２４とを備える。送信部２１は他の装置に情報を送信する。受信部２２は他の装置から送信された情報を受信する。制御部２３は制御装置１４の制御を行う。記憶部２４は制御装置１４が使用する情報を記憶する。
【００１７】
図３は、本実施形態におけるｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎを行うプログラムとＣｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ（制御フローグラフ）とを示した図である。図示する例では、プログラム３１はブロックｆと、ブロックｇと、ブロックｈとからなる。
【００１８】
このプログラムのＣｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３２は、ブロックＩＤがｆのブロックｆと、ブロックＩＤがｇのブロックｇと、ブロックＩＤがｈのブロックｈとからなる。また、Ｃｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３２のループを展開したＣｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３３は、ブロックＩＤがｆのブロックｆと、ブロックＩＤがｇ１のブロックｇ１と、ブロックＩＤがｇ２のブロックｇ２と、ブロックＩＤがｇ３のブロックｇ３と、ブロックＩＤがｈのブロックｈとからなる。
【００１９】
なお、プログラムをブロックに分割する方法は、例えば「Frances E. Allen, "Control flow analysis",ACM SIGPLAN Notices archive, Volume 5 , Issue 7 (July 1970)」に記載の方法で行う。また、本実施形態では、仲介者１２がプログラム３１をブロックに分割する。
【００２０】
次に、本実施形態におけるｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎを行うための事前準備について説明する。本実施形態では、事前準備は仲介者１２が行う。仲介者１２は、プログラム３１に基づいたＣｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３３の各ブロックにラベル（宛先ラベル）をランダムに割り当てる。
【００２１】
本実施形態では、仲介者１２は、ブロックｆにラベル３を割り当て、ブロックｇ１にラベル１を割り当て、ブロックｇ２にラベル５を割り当て、ブロックｇ３にラベル２を割り当て、ブロックｈにラベル４を割り当てる。
【００２２】
続いて、仲介者１２は、ランダムにＣｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３３の各ブロックを評価者１３−１〜１３−５に割り当てる。本実施形態では、ブロックｆを評価者１３−２に割り当て、ブロックｇ１を評価者１３−４に割り当て、ブロックｇ２を評価者１３−１に割り当て、ブロックｇ３を評価者１３−５に割り当て、ブロックｈを評価者１３−３に割り当てる。
【００２３】
続いて、仲介者１２は、Ｃｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３３の各ブロックに該当するプログラムを論理回路として表し、論理回路を暗号化する。なお、暗合化した論理回路をＧａｒｂｌｅｄ ｃｉｒｃｕｉｔと呼ぶ。
【００２４】
続いて、仲介者１２は、Ｃｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３３の各ブロックに該当するプログラムのＧａｒｂｌｅｄ ｃｉｒｃｕｉｔと、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔの入力となるキーを作成する。続いて、仲介者１２は、各ブロックを割り当てた評価者１３−１〜１３−５に作成したＧａｒｂｌｅｄ ｃｉｒｃｕｉｔを送付する。例えば、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｆ）を評価者１３−２に送付する。他のＧａｒｂｌｅｄ ｃｉｒｃｕｉｔについても同様に評価者１３−１〜１３−５に送付する。
【００２５】
続いて、仲介者１２は、Ｃｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３３の各ブロックに割り当てたラベル１〜５と、評価者１３−１〜１３−５に割り当てたＣｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈ３３の各ブロックとに基づいて、ラベル１〜５と評価者１３−１〜１３−５とを関連付ける表である宛先リスト（転送先情報）を作成し、制御装置１４に送付する。
【００２６】
本実施形態の宛先リストでは、ラベル１と評価者４とが関連付けられ、ラベル２と評価者５とが関連付けられ、ラベル３と評価者２とが関連付けられ、ラベル４と評価者３とが関連付けられ、ラベル５と評価者１とが関連付けられている。
【００２７】
続いて、仲介者１２は、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔの入力となるキーの入力を受け付けるＧａｒｂｌｅｄ ｃｉｒｃｕｉｔに付されているラベル１〜５をキーに付し、参加者１１−１〜１１−３に対して送付する。本実施形態では、ブロックｇ１〜ｇ３のＧａｒｂｌｅｄ ｃｉｒｃｕｉｔがキーの入力を受け付ける。仲介者１２は、ブロックｇ１が受けつけるキーにはラベル１を付し、ブロックｇ２が受け付けるキーにはラベル５を付し、ブロックｇ３が受け付けるキーにはラベル２を付す。
【００２８】
また、本実施形態では、入力となるキーとしては、参加者１１−１〜１１−３が投票する結果である。ブロックｇ１〜ｇ３が受け付けるキーの値は、賛成の値「１」と反対の値「０」との２通りの値が考えられる。
【００２９】
よって、仲介者１２は、参加者１１−１に対して、賛成の値「１」が含まれ、ラベル１が付されたキー「Ｖ［１］＝１」と、反対の値「０」が含まれ、ラベル１が付されたキー「Ｖ［１］＝０」とを作成し送付する。また、仲介者１２は、参加者１１−２に対して、賛成の値「１」が含まれ、ラベル５が付されたキー「Ｖ［２］＝１」と、反対の値「０」が含まれ、ラベル５が付されたキー「Ｖ［２］＝０」とを作成し送付する。また、仲介者１２は、参加者１１−３に対して、賛成の値「１」が含まれ、ラベル３が付されたキー「Ｖ［３］＝１」と、反対の値「０」が含まれ、ラベル３が付されたキー「Ｖ［３］＝０」とを作成し送付する。
【００３０】
なお、キーは乱数により生成されるため、キーを見ただけではキーに含まれる値を知ることができない。そのため、参加者１１−１〜１１−３が賛成の値が含まれたキーと反対の値が含まれたキーとを区別できるようにして、仲介者１２はキーを送信する。
【００３１】
図４は、本実施形態において、仲介者２がＧａｒｂｌｅｄ ｃｉｒｃｕｉｔのキーを作成した状態の計算システムの構成を示した図である。図示する例では、仲介者２は、参加者１１−１〜１１−３に送付するキーを計８個生成している。仲介者２は、このキーを参加者１１−１〜１１−３に送付する。また、制御装置４は、ラベル１〜５と評価者１３−１〜１３−５とを関連付けたあて先リストを記憶している。
【００３２】
次に、本実施形態において、参加者１１−１〜１１−３が行う投票方法について説明する。本実施形態では、参加者１１−１〜１１−３は事前準備で仲介者１２から送信されたキーを用いて投票を行う。例えば、参加者１１−１は、賛成の場合、賛成の値が含まれたキー「Ｖ［１］＝１」を制御装置１４に送信し、反対の場合、反対の値が含まれたキー「Ｖ［１］＝０」を制御装置１４に送信する。参加者１１−１と同様に、他の参加者１１−２〜１１−３も投票を行う。投票を受け付けた制御装置１４は、記憶部２３に受信したキーを記憶する。なお、先述したとおり、キーを見ただけではキーに含まれている情報が分からないため、制御装置１４は、参加者１１−１〜１１−３が投票した値を知ることはできない。
【００３３】
本実施形態では、参加者１１−１は、値「１」が含まれており、ラベル１が付されているキー「Ｖ［１］＝１」を制御装置１４に送付する。また、参加者１１−２は、値「１」が含まれており、ラベル５が付されているキー「Ｖ［２］＝１」を制御装置１４に送付する。また、参加者１１−３は、値「１」が含まれており、ラベル２が付されているキー「Ｖ［３］＝１」を制御装置１４に送付する。
【００３４】
仲介者１２による事前準備と、参加者１１−１〜１１−３による投票が終了後、仲介者１２は、ブロックｆを割り当てた評価者１３−２に対して、プログラムの実行を開始するためのキーを送信する。プログラムの実行を開始するためのキーを受け取った評価者１３−２は、自身に送信されたＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｆ）を復号し、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｆ）の出力であるキー「ｊ＝１，ｓ＝０」とラベル１とを得る。続いて、評価者１３−２は、キー「ｊ＝１，ｓ＝０」をラベル１に対して送信する。
【００３５】
なお、本実施形態では、ｓは賛成票の数を足し合わせた数である。また、ｊはプログラムの処理において、何人目の参加者の投票の処理を行っているかを示す数である。また、ｒｅｓｕｌｔは、プログラム最終的な出力結果であり、３人の参加者のうち、２人以上が賛成であれば１（可決）であり、それ以外であれば０（否決）である。
【００３６】
制御装置１４は、評価者１３−２がラベル１に対して送信したキー「ｊ＝１，ｓ＝０」を受信する。続いて、制御装置１４の制御部２３は、記憶部２４に記憶している宛先リストに基づいて、ラベル１に関連付けられている評価者１３−４を特定する。続いて、制御装置４の制御部２３は、記憶部２４が記憶しているキーのうち、ラベル１が付されているキー「Ｖ［１］＝１」を特定する。続いて、制御装置１４の制御部２３は送信部２１を介して、特定したキー「Ｖ［１］＝１」と、評価者１３−２がラベル１に対して送信したキー「ｊ＝１，ｓ＝０」とを評価者１３−４に送信する。
【００３７】
図５は、本実施形態において、評価者１３−２がＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｆ）の処理を実行した状態の計算システムの構成を示した図である。図示する例では、評価者１３−２は、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｆ）の出力であるキー「ｊ＝１，ｓ＝０」をラベル１宛に送信している。また、制御装置１４は、評価者１３−２がラベル１宛に送信したキー「ｊ＝１，ｓ＝０」の送信先である評価者１３−４を特定し、キー「ｊ＝１，ｓ＝０」と、キー「Ｖ［１］＝１」とを評価者１３−４に送信している。
【００３８】
続いて、キー「ｊ＝１，ｓ＝０」と、キー「Ｖ［１］＝１」とを受信した評価者１３−４は、自身に送信されたＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｇ１）を復号し、キー「ｊ＝１，ｓ＝０」とキー「Ｖ［１］＝１」とに基づいてＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｇ１）の出力であるキー「ｊ＝２，ｓ＝１」とラベル５とを得る。続いて、評価者１３−４は、キー「ｊ＝２，ｓ＝１」をラベル５に対して送信する。
【００３９】
制御装置１４は、評価者１３−４がラベル５に対して送信したキー「ｊ＝２，ｓ＝１」を受信する。続いて、制御装置１４の制御部２３は、記憶部２４に記憶している宛先リストに基づいて、ラベル５に関連付けられている評価者１３−１を特定する。続いて、制御装置４の制御部２３は、記憶部２４が記憶しているキーのうち、ラベル５が付されているキー「Ｖ［２］＝１」を特定する。続いて、制御装置１４の制御部２３は送信部２１を介して、特定したキー「Ｖ［２］＝１」と、評価者１３−４がラベル５に対して送信したキー「ｊ＝２，ｓ＝１」とを評価者１３−１に送信する。
【００４０】
図６は、本実施形態において、評価者１３−４がＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｇ１）の処理を実行した状態の計算システムの構成を示した図である。図示する例では、評価者１３−４は、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｇ１）の出力であるキー「ｊ＝２，ｓ＝１」をラベル５宛に送信している。また、制御装置１４は、評価者１３−４がラベル５宛に送信したキー「ｊ＝２，ｓ＝１」の送信先である評価者１３−１を特定し、キー「ｊ＝２，ｓ＝１」と、キー「Ｖ［２］＝１」とを評価者１３−１に送信している。
【００４１】
続いて、キー「ｊ＝２，ｓ＝１」と、キー「Ｖ［２］＝１」とを受信した評価者１３−１は、自身に送信されたＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｇ２）を復号し、キー「ｊ＝２，ｓ＝１」とキー「Ｖ［２］＝１」とに基づいてＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｇ２）の出力であるキー「ｊ＝３，ｓ＝２」とラベル４とを得る。続いて、評価者１３−１は、キー「ｊ＝３，ｓ＝２」をラベル４に対して送信する。
【００４２】
制御装置１４は、評価者１３−１がラベル４に対して送信したキー「ｊ＝３，ｓ＝２」を受信する。続いて、制御装置１４の制御部２３は、記憶部２４に記憶している宛先リストに基づいて、ラベル４に関連付けられている評価者１３−３を特定する。続いて、制御装置４の制御部２３は、記憶部２４が記憶しているキーのうち、ラベル３が付されているキーを検索するが、本実施形態ではラベル３が付されているキーは無い。続いて、ラベル３が付されているキーは無いため、制御装置１４の制御部２３は送信部２１を介して、評価者１３−１がラベル４に対して送信したキー「ｊ＝３，ｓ＝２」のみを評価者１３−３に送信する。
【００４３】
図７は、本実施形態において、評価者１３−１がＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｇ２）の処理を実行した状態の計算システムの構成を示した図である。図示する例では、評価者１３−１は、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｇ２）の出力であるキー「ｊ＝３，ｓ＝２」をラベル４宛に送信している。また、制御装置１４は、評価者１３−１がラベル４宛に送信したキー「ｊ＝３，ｓ＝２」の送信先である評価者１３−３を特定し、キー「ｊ＝３，ｓ＝２」を評価者１３−３に送信している。
【００４４】
続いて、キー「ｊ＝３，ｓ＝２」を受信した評価者１３−３は、自身に送信されたＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｈ）を復号し、キー「ｊ＝３，ｓ＝２」に基づいてＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｈ）の出力であるキー「Ｒｅｓｕｌｔ＝１」を得る。また、評価者１３−３は、参加者１１−１〜１１−３に対して「Ｒｅｓｕｌｔ＝１」を送信する。
【００４５】
参加者１１−１〜１１−３は、評価者１３−３が送信した「Ｒｅｓｕｌｔ＝１」を受信する。これにより、参加者１１−１〜１１−３は、投票結果を知ることができる。
【００４６】
図８は、本実施形態において、評価者１３−３がＧａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｈ）の処理を実行した状態の計算システムの構成を示した図である。図示する例では、評価者１３−３は、Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔ（ｈ）の出力であるキー「Ｒｅｓｕｌｔ＝１」を参加者１１−１〜１１−３宛に送信している。
【００４７】
上述したとおり、本実施形態によれば、プログラムを複数に分割し、分割したプログラムを論理回路として表し、その論理回路を暗号化する（Ｇａｒｂｌｅｄ ｃｉｒｃｕｉｔ）。また、複数の暗号化した論理回路の実行順を制御する制御装置１４を設けている。
【００４８】
制御装置１４は、ラベル１〜５と評価者１３−１〜１３−５とを関連付けた宛先リストを記憶しており、評価者１３−１〜１３−５から送信されたラベル１〜５と、次に実行すべきプログラムの入力キーとを受信し、受信したラベル１〜５と宛先リストとに基づいて受信した入力キーを評価者１３−１〜１３−５に送信する。これにより、途中の計算結果の状態に応じてラベル１〜５が制御装置１４に送信され、制御装置１４は、ラベル１〜５に応じて次に実行するＧａｒｂｌｅｄ ｃｉｒｃｕｉｔを指定する。
【００４９】
すなわち、制御装置１４が途中の計算結果に応じて次に実行するＧａｒｂｌｅｄ ｃｉｒｃｕｉｔを指定する。これにより、途中の計算結果の状態に応じて選択的に処理を行うことができる。よって、一般的なプログラムのｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎを行う際に、より効率的に計算を行うことができる。
【００５０】
なお、上述した実施形態における制御装置全体あるいはその一部は、これらの機能実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現しても良い。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。
【００５１】
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時刻の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時刻プログラムを保持しているものも含んでも良い。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【００５２】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【００５３】
【図１】本発明の一実施形態における計算システムの構成を示した図である。
【図２】本実施形態における制御装置の構成を示した構成図である。
【図３】本実施形態におけるｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎを行うプログラムとＣｏｎｔｒｏｌ ｆｌｏｗ ｇｒａｐｈとを示した図である。
【図４】本実施形態における計算システムの構成を示した構成図である。
【図５】本実施形態における計算システムの構成を示した構成図である。
【図６】本実施形態における計算システムの構成を示した構成図である。
【図７】本実施形態における計算システムの構成を示した構成図である。
【図８】本実施形態における計算システムの構成を示した構成図である。
【符号の説明】
【００５４】
１１−１〜１１−３・・・参加者、１２・・・仲介者、１３−１〜１３−５・・・評価者、１４・・・制御装置、２１・・・送信部、２２・・・受信部、２３・・・制御部、２４・・・記憶部
【特許請求の範囲】
【請求項１】
分割されたプログラムを複数の端末装置で分担して実行する計算システムの制御装置において、
前記プログラムの実行結果として得られる宛先ラベルと前記端末装置を特定する情報とを関連付ける転送先情報を記憶する記憶部と、
あるプログラムを実行した前記端末装置から、次に実行すべきプログラムの入力キーと前記入力キーの転送先に対応する宛先ラベルとを受信する受信部と、
前記受信部が受信した前記宛先ラベルに基づいて前記転送先情報から転送先の端末装置を特定し、前記受信部が受信した前記入力キーを前記転送先の端末装置へ送信する送信部と、
を備えたことを特徴とする制御装置。
【請求項２】
分割されたプログラムを複数の端末装置で分担して実行する計算システムにおいて、
請求項１に記載の制御装置と、
前記制御装置より送信された入力キーを受信する端末受信部と、受信した前記入力キーに基づいて前記分割されたプログラムを実行し、次に実行すべきプログラムの入力キーと前記入力キーの転送先に対応する宛先ラベルとを取得する制御部と、前記制御部が取得した前記プログラムの入力キーと前記宛先ラベルとを送信する端末送信部と、を備えた端末装置と、
を備えたことを特徴とする計算システム。
【請求項３】
分割されたプログラムを複数の端末装置で分担して実行する計算システムの制御をコンピュータに実行させるための制御プログラムにおいて、
前記分割されたプログラムの実行結果として得られる宛先ラベルと前記端末装置を特定する情報とを関連付ける転送先情報を記憶する記憶部と、
あるプログラムを実行した前記端末装置から、次に実行すべきプログラムの入力キーと前記入力キーの転送先に対応する宛先ラベルとを受信する受信部と、
前記受信部が受信した前記宛先ラベルに基づいて前記転送先情報から転送先の端末装置を特定し、前記受信部が受信した前記入力キーを前記転送先の端末装置へ送信する送信部と、
としてコンピュータを実行させるための制御プログラム。
【請求項１】
分割されたプログラムを複数の端末装置で分担して実行する計算システムの制御装置において、
前記プログラムの実行結果として得られる宛先ラベルと前記端末装置を特定する情報とを関連付ける転送先情報を記憶する記憶部と、
あるプログラムを実行した前記端末装置から、次に実行すべきプログラムの入力キーと前記入力キーの転送先に対応する宛先ラベルとを受信する受信部と、
前記受信部が受信した前記宛先ラベルに基づいて前記転送先情報から転送先の端末装置を特定し、前記受信部が受信した前記入力キーを前記転送先の端末装置へ送信する送信部と、
を備えたことを特徴とする制御装置。
【請求項２】
分割されたプログラムを複数の端末装置で分担して実行する計算システムにおいて、
請求項１に記載の制御装置と、
前記制御装置より送信された入力キーを受信する端末受信部と、受信した前記入力キーに基づいて前記分割されたプログラムを実行し、次に実行すべきプログラムの入力キーと前記入力キーの転送先に対応する宛先ラベルとを取得する制御部と、前記制御部が取得した前記プログラムの入力キーと前記宛先ラベルとを送信する端末送信部と、を備えた端末装置と、
を備えたことを特徴とする計算システム。
【請求項３】
分割されたプログラムを複数の端末装置で分担して実行する計算システムの制御をコンピュータに実行させるための制御プログラムにおいて、
前記分割されたプログラムの実行結果として得られる宛先ラベルと前記端末装置を特定する情報とを関連付ける転送先情報を記憶する記憶部と、
あるプログラムを実行した前記端末装置から、次に実行すべきプログラムの入力キーと前記入力キーの転送先に対応する宛先ラベルとを受信する受信部と、
前記受信部が受信した前記宛先ラベルに基づいて前記転送先情報から転送先の端末装置を特定し、前記受信部が受信した前記入力キーを前記転送先の端末装置へ送信する送信部と、
としてコンピュータを実行させるための制御プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２００９−２４５２０９（Ｐ２００９−２４５２０９Ａ）
【公開日】平成２１年１０月２２日（２００９．１０．２２）
【国際特許分類】
【出願番号】特願２００８−９１５９２（Ｐ２００８−９１５９２）
【出願日】平成２０年３月３１日（２００８．３．３１）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【出願人】（５０８０９８２９１）
【Ｆターム（参考）】
【公開日】平成２１年１０月２２日（２００９．１０．２２）
【国際特許分類】
【出願日】平成２０年３月３１日（２００８．３．３１）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【出願人】（５０８０９８２９１）
【Ｆターム（参考）】
[ Back to top ]