(57)【要約】      （修正有）【課題】異なる値に対して同一の結果が得られる関数を用いることで、高い安全性を満たすと共に高効率化を達成するビットコミットメントプロトコルが実現可能な情報処理装置を提供する。【解決手段】情報処理装置１００は異なる複数の値に対して同じ結果を算出できる関数Ｆ及び、前記値並びに情報処理装置２００へコミットする値との関係性Ｒを予め情報処理装置２００との間で共有させた状態で、前記関数Ｆを適用すると同じ結果になる値を生成するビットコミットメント関数処理部１１０を備え、ビットコミットメント関数処理部１１０は、前記関係性Ｒの適用により情報処理装置２００へコミットする値を決定するコミット段階と、前記コミット段階でコミットした値を公開する公開段階とを実行し、前記コミット段階と、前記公開段階とで、前記値から前記コミットする値に対応するそれぞれ異なる値を選択して通信部１２０より情報処理装置２００へ送信する。【選択図】図６
2014090235.tif 000002
【特許請求の範囲】
【請求項１】
異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置へコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記関数Ｆを適用すると同じ結果になる値ｘ１、・・・、ｘｎを生成する関数処理部を備え、
前記関数処理部は、前記関係性Ｒの適用により前記他の装置へコミットする値を決定するコミット段階と、前記コミット段階でコミットした値を公開する公開段階とを実行し、前記コミット段階と、前記公開段階とで、前記値ｘ１、・・・、ｘｎから前記コミットする値に対応するそれぞれ異なる値を選択して前記他の装置へ送信する、情報処理装置。
【請求項２】
前記関係性Ｒは、前記コミット段階で前記他の装置に送信する値に対して、前記公開段階の前では前記他の装置は前記コミットした値が予測出来ないよう定められている、請求項１に記載の情報処理装置。
【請求項３】
前記関係性Ｒは、前記値ｘ１、・・・、ｘｎの大小関係によって値が決まるよう定められている、請求項１に記載の情報処理装置。
【請求項４】
前記ｎの値は２である、請求項１に記載の情報処理装置。
【請求項５】
前記ｎの値は３以上であり、
前記関数処理部は、前記関係性Ｒの適用により前記コミット段階で前記値ｘ１、・・・、ｘｎから一の値を選択して前記他の装置へ送信し、前記公開段階で他の前記値を全て前記他の装置へ送信する、請求項１に記載の情報処理装置。
【請求項６】
前記ｎの値は３以上であり、
前記関数処理部は、所定の制限に従って前記値ｘ１、・・・、ｘｎを生成して前記所定の制限の情報を前記他の装置との間で共有させ、前記関係性Ｒの適用により前記コミット段階で前記値ｘ１、・・・、ｘｎから一の値を選択して前記他の装置へ送信し、前記公開段階で他の前記値を全て前記他の装置へ送信する、請求項１に記載の情報処理装置。
【請求項７】
前記関数Ｆは、ａ本のｂ変数の２次多項式（ａ、ｂはいずれも２以上の整数）で構成される関数である、請求項１に記載の情報処理装置。
【請求項８】
異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置がコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記他の装置から送信された前記値に対して前記関数Ｆを適用する関数処理部を備え、
前記関数処理部は、前記関係性Ｒの適用により前記他の装置がコミットした値に対応する第１の値を受信するコミット段階と、前記他の装置がコミットした値を公開するための第２の値を受信する公開段階とを実行し、
前記関数処理部は、前記公開段階で、前記第１の値と前記第２の値とが異なり、かつ前記第１の値及び前記第２の値に前記関数Ｆを適用すると同じ結果になるかどうか判断する、情報処理装置。
【請求項９】
前記関数処理部は、前記第１の値及び前記第２の値に前記関数Ｆを適用して同じ結果になると、前記第１の値及び前記第２の値に対して関係性Ｒを適用した結果を出力する、請求項８に記載の情報処理装置。
【請求項１０】
前記ｎの値は３以上であり、所定の制限に従って前記他の装置で前記値ｘ１、・・・、ｘｎが生成された場合に前記所定の制限の情報を前記他の装置との間で共有し、
前記関数処理部は、前記公開段階で、前記他の装置から受信した値が前記所定の制限の下で生成されたかどうか判断する、請求項８に記載の情報処理装置。
【請求項１１】
前記関数Ｆは、ａ本のｂ変数の２次多項式（ａ、ｂはいずれも２以上の整数）で構成される関数である、請求項８に記載の情報処理装置。
【請求項１２】
第１の情報処理装置及び第２の情報処理装置を備え、
異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに前記第１の情報処理装置が前記第２の情報処理装置へコミットする値との関係性Ｒを前記第１の情報処理装置及び前記第２の情報処理装置の間で共有させ、
前記第１の情報処理装置は、
前記関数Ｆを適用すると同じ結果になる値ｘ１、・・・、ｘｎを生成する第１の関数処理部を備え、
前記第１の関数処理部は、前記関係性Ｒの適用により前記第２の情報処理装置へコミットする値を決定するコミット段階と、前記コミット段階でコミットした値を公開する公開段階とを実行し、前記コミット段階と、前記公開段階とで、前記値ｘ１、・・・、ｘｎから前記コミットする値に対応するそれぞれ異なる値を選択して、前記コミット段階で第１の値を、前記公開段階で第２の値を前記第２の情報処理装置へ送信し、
前記第２の情報処理装置は、
前記第１の情報処理装置から送信された前記値に対して前記関数Ｆを適用する第２の関数処理部を備え、
前記第２の関数処理部は、前記関係性Ｒの適用により前記第１の情報処理装置がコミットした値に対応する第１の値を受信するコミット段階と、前記第１の情報処理装置がコミットした値を公開するための第２の値を受信する公開段階とを実行し、
前記関数処理部は、前記公開段階で、前記第１の値と前記第２の値とが異なり、かつ前記第１の値及び前記第２の値に前記関数Ｆを適用すると同じ結果になるかどうか判断する、情報処理システム。
【請求項１３】
異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置へコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記関数Ｆを適用すると同じ結果になる値ｘ１、・・・、ｘｎを生成する生成ステップと、
前記関係性Ｒの適用により前記他の装置へコミットする値を決定するコミットステップと、
前記コミットステップでコミットした値を公開する公開ステップと、
を備え、
前記コミットステップと、前記公開ステップとで、前記値ｘ１、・・・、ｘｎから前記コミットする値に対応するそれぞれ異なる値が選択されて前記他の装置へ送信される、情報処理方法。
【請求項１４】
異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置がコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記関係性Ｒの適用により前記他の装置がコミットした値に対応する第１の値を受信するコミットステップと、
前記他の装置がコミットした値を公開するための第２の値を受信する公開ステップと、
前記第１の値と前記第２の値とが異なり、かつ前記第１の値及び前記第２の値に前記関数Ｆを適用すると同じ結果になるかどうか判断する関数適用ステップと、
を備える、情報処理方法。
【請求項１５】
コンピュータに、
異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置へコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記関数Ｆを適用すると同じ結果になる値ｘ１、・・・、ｘｎを生成する生成ステップと、
前記関係性Ｒの適用により前記他の装置へコミットする値を決定するコミットステップと、
前記コミットステップでコミットした値を公開する公開ステップと、
を実行させ、
前記コミットステップと、前記公開ステップとで、前記値ｘ１、・・・、ｘｎから前記コミットする値に対応するそれぞれ異なる値が選択されて前記他の装置へ送信される、コンピュータプログラム。
【請求項１６】
コンピュータに、
異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置がコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記関係性Ｒの適用により前記他の装置がコミットした値に対応する第１の値を受信するコミットステップと、
前記他の装置がコミットした値を公開するための第２の値を受信する公開ステップと、
前記第１の値と前記第２の値とが異なり、かつ前記第１の値及び前記第２の値に前記関数Ｆを適用すると同じ結果になるかどうか判断する関数適用ステップと、
を実行させる、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、情報処理装置、情報処理方法、コンピュータプログラム及び情報処理システムに関する。
【背景技術】
【０００２】
ビットコミットメントプロトコルは、暗号分野の様々な場所で利用されており、様々な問題に基づく効率的な実現方法の提案は非常に有益である。ビットコミットメントの目的は、現在自分が所持しているビット・データの値を知らせることなく、そのビット・データを所持していることを検証者に対して確約すること、及び確約後には、検証者はそのビット・データがそのとき確約されたものであることを検証可能にすることである。
【０００３】
ビットコミットメントプロトコルの安全性は、基にする数学的な問題の困難性に依存する。従って、様々な問題に基づく構成法を提案することで，ダイバーシティが形成できる。ビットコミットメントプロトコルの構成法の既存の結果として，一般の一方向性関数（ｏｎｅ−ｗａｙ  ｆｕｎｃｔｉｏｎ）にもとづくビットコミットメントプロトコルの構成法が知られている（例えば、非特許文献１、２等参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】O. Goldreich and L.A. Levin, A Hard-Core Predicate for all One-WayFunctions, STOC 1989
【非特許文献２】Iftach Haitner, Minh-Huyen Nguyen, Shien Jin Ong, Omer Reingold,Salil Vadhan: Statistically Hiding Commitments and Statistical Zero-KnowledgeArguments from Any One-Way Function, SIAM Journal on Computing 2009
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１、２等で開示されているような、既存のビットコミットメントプロトコルは、最低限の安全性（ｃｏｍｐｕｔａｔｉｏｎａｌｌｙ  ｈｉｄｉｎｇ）しか満たせなかったり、良い効率は望めなかったりしていた。このような事情を鑑みれば、より高い安全性を実現しつつ、高効率なビットコミットメントプロトコルが求められていた。
【０００６】
そこで、本開示は、異なる値に対して同一の結果が得られる関数を用いることで、高い安全性を満たすと共に高効率化を達成するビットコミットメントプロトコルが実現可能な、新規かつ改良された情報処理装置、情報処理方法、コンピュータプログラム及び情報処理システムを提供することにある。
【課題を解決するための手段】
【０００７】
本開示によれば、異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置へコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記関数Ｆを適用すると同じ結果になる値ｘ１、・・・、ｘｎを生成する関数処理部を備え、前記関数処理部は、前記関係性Ｒの適用により前記他の装置へコミットする値を決定するコミット段階と、前記コミット段階でコミットした値を公開する公開段階とを実行し、前記コミット段階と、前記公開段階とで、前記値ｘ１、・・・、ｘｎから前記コミットする値に対応するそれぞれ異なる値を選択して前記他の装置へ送信する、情報処理装置が提供される。
【０００８】
また本開示によれば、異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置がコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記他の装置から送信された前記値に対して前記関数Ｆを適用する関数処理部を備え、前記関数処理部は、前記関係性Ｒの適用により前記他の装置がコミットした値に対応する第１の値を受信するコミット段階と、前記他の装置がコミットした値を公開するための第２の値を受信する公開段階とを実行し、前記関数処理部は、前記公開段階で、前記第１の値と前記第２の値とが異なり、かつ前記第１の値及び前記第２の値に前記関数Ｆを適用すると同じ結果になるかどうか判断する、情報処理装置が提供される。
【０００９】
また本開示によれば、第１の情報処理装置及び第２の情報処理装置を備え、異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに前記第１の情報処理装置が前記第２の情報処理装置へコミットする値との関係性Ｒを前記第１の情報処理装置及び前記第２の情報処理装置の間で共有させ、前記第１の情報処理装置は、前記関数Ｆを適用すると同じ結果になる値ｘ１、・・・、ｘｎを生成する第１の関数処理部を備え、前記第１の関数処理部は、前記関係性Ｒの適用により前記第２の情報処理装置へコミットする値を決定するコミット段階と、前記コミット段階でコミットした値を公開する公開段階とを実行し、前記コミット段階と、前記公開段階とで、前記値ｘ１、・・・、ｘｎから前記コミットする値に対応するそれぞれ異なる値を選択して前記第２の情報処理装置へ送信し、前記第２の情報処理装置は、前記第１の情報処理装置から送信された前記値に対して前記関数Ｆを適用する第２の関数処理部を備え、前記第２の関数処理部は、前記関係性Ｒの適用により前記第１の情報処理装置がコミットした値に対応する第１の値を受信するコミット段階と、前記第１の情報処理装置がコミットした値を公開するための第２の値を受信する公開段階とを実行し、
前記関数処理部は、前記公開段階で、前記第１の値と前記第２の値とが異なり、かつ前記第１の値及び前記第２の値に前記関数Ｆを適用すると同じ結果になるかどうか判断する、情報処理システムが提供される。
【００１０】
また本開示によれば、異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置へコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記関数Ｆを適用すると同じ結果になる値ｘ１、・・・、ｘｎを生成する生成ステップと、前記関係性Ｒの適用により前記他の装置へコミットする値を決定するコミットステップと、前記コミットステップでコミットした値を公開する公開ステップと、を備え、前記コミットステップと、前記公開ステップとで、前記値ｘ１、・・・、ｘｎから前記コミットする値に対応するそれぞれ異なる値が選択されて前記他の装置へ送信される、情報処理方法が提供される。
【００１１】
また本開示によれば、異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置がコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記関係性Ｒの適用により前記他の装置がコミットした値に対応する第１の値を受信するコミットステップと、前記他の装置がコミットした値を公開するための第２の値を受信する公開ステップと、前記第１の値と前記第２の値とが異なり、かつ前記第１の値及び前記第２の値に前記関数Ｆを適用すると同じ結果になるかどうか判断する関数適用ステップと、を備える、情報処理方法が提供される。
【００１２】
また本開示によれば、コンピュータに、異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置へコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記関数Ｆを適用すると同じ結果になる値ｘ１、・・・、ｘｎを生成する生成ステップと、前記関係性Ｒの適用により前記他の装置へコミットする値を決定するコミットステップと、前記コミットステップでコミットした値を公開する公開ステップと、を実行させ、前記コミットステップと、前記公開ステップとで、前記値ｘ１、・・・、ｘｎから前記コミットする値に対応するそれぞれ異なる値が選択されて前記他の装置へ送信される、コンピュータプログラムが提供される。
【００１３】
また本開示によれば、コンピュータに、異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置がコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記関係性Ｒの適用により前記他の装置がコミットした値に対応する第１の値を受信するコミットステップと、前記他の装置がコミットした値を公開するための第２の値を受信する公開ステップと、前記第１の値と前記第２の値とが異なり、かつ前記第１の値及び前記第２の値に前記関数Ｆを適用すると同じ結果になるかどうか判断する関数適用ステップと、実行させる、コンピュータプログラムが提供される。
【発明の効果】
【００１４】
以上説明したように本開示によれば、異なる値に対して同一の結果が得られる関数を用いることで、高い安全性を満たすと共に高効率化を達成するビットコミットメントプロトコルが実現可能な、新規かつ改良された情報処理装置、情報処理方法、コンピュータプログラム及び情報処理システムを提供することができる。
【図面の簡単な説明】
【００１５】
【図１】公開鍵認証方式に係るアルゴリズムの構成について説明するための説明図である。
【図２】電子署名方式に係るアルゴリズムの構成について説明するための説明図である。
【図３】ｎパスの公開鍵認証方式に係るアルゴリズムの構成について説明するための説明図である。
【図４】ビットコミットメントプロトコルのフローを示す流れ図である。
【図５】既存のビットコミットメントプロトコルのフローを示す流れ図である。
【図６】本開示の一実施形態に係る情報処理システム１の構成例を示す説明図である。
【図７】本開示の一実施形態に係る情報処理システム１の動作例を示す流れ図である。
【図８】ｘ１の値によるｘ１とｘ２の大小関係の予測について示す説明図である。
【図９】関係性Ｒ２（ｘ１，ｘ２）を視覚的に示す説明図である。
【図１０】本開示の一実施形態に係る情報処理システム１を用いたストリングコミットメントプロトコルのフローを示す流れ図である。
【図１１】本開示の一実施形態に係る情報処理システム１の動作例を示す流れ図である。
【図１２】情報処理装置のハードウェア構成を示す説明図である。
【発明を実施するための形態】
【００１６】
以下に添付図面を参照しながら、本開示の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００１７】
なお、説明は以下の順序で行うものとする。
＜１．公開鍵認証方式及び秘密鍵の説明＞
＜２．既存のビットコミットメントプロトコルの説明＞
＜３．本開示の一実施形態＞
［システム構成例］
［システム動作例］
［変形例］
＜４．ハードウェア構成例＞
＜５．まとめ＞
【００１８】
＜１．公開鍵認証方式及び秘密鍵の説明＞
本開示の好適な実施の形態について説明する前に、まず、公開鍵認証方式及び電子署名方式の概要を説明し、続いて、後述する本開示の各実施形態で用いられる秘密鍵について説明する。
【００１９】
公開鍵認証方式とは、ある人（証明者）が、公開鍵ｐｋ及び秘密鍵ｓｋを利用して、他の人（検証者）に本人であることを納得させるための認証方式である。例えば、証明者Ａの公開鍵ｐｋＡは、検証者に公開される。一方、証明者Ａの秘密鍵ｓｋＡは、証明者により秘密に管理される。公開鍵認証方式では、公開鍵ｐｋＡに対応する秘密鍵ｓｋＡを知る者が証明者Ａ本人であるとみなされる。
【００２０】
証明者Ａが検証者Ｂに対して本人であることを証明しようとする場合、証明者Ａは、検証者Ｂと対話プロトコルを実行して、自身が公開鍵ｐｋＡに対応する秘密鍵ｓｋＡを知っていることを証明すればよい。そして、対話プロトコルにより証明者Ａが秘密鍵ｓｋＡを知っていることが検証者Ｂにより証明された場合、証明者Ａの正当性（本人であること）が証明される。
【００２１】
なお、公開鍵認証方式の安全性を確保するには、次に示す２つの条件が求められる。
【００２２】
１つ目の条件は、対話プロトコルを実行した際に秘密鍵ｓｋを持たない偽証者により偽証が成立してしまう確率を限りなく小さくすることである。この１つ目の条件が成り立つことを「健全性」と呼ぶ。つまり、健全性を有する対話プロトコルにおいては、秘密鍵ｓｋを持たない偽証者により、無視できない確率で偽証が成立することはないと言い換えられる。２つ目の条件は、対話プロトコルを実行したとしても、証明者Ａが有する秘密鍵ｓｋＡの情報が検証者Ｂに一切漏れることがないようにすることである。この２つ目の条件が成り立つことを「零知識性」と呼ぶ。
【００２３】
上記の健全性と零知識性を有する対話プロトコルを利用することにより、公開鍵認証方式の安全性が確保される。
【００２４】
公開鍵認証方式のモデルには、図１に示すように、証明者と検証者という２つのエンティティが存在する。証明者は、鍵生成アルゴリズムＧｅｎを用いて、証明者固有の秘密鍵ｓｋと公開鍵ｐｋの組を生成する。次いで、証明者は、鍵生成アルゴリズムＧｅｎを用いて生成した秘密鍵ｓｋと公開鍵ｐｋの組を利用して検証者と対話プロトコルを実行する。このとき、証明者は、証明者アルゴリズムＰを利用して対話プロトコルを実行する。上記の通り、対話プロトコルにおいて、証明者は、証明者アルゴリズムＰを利用して、秘密鍵ｓｋを保有していることを検証者に証明する。
【００２５】
一方、検証者は、検証者アルゴリズムＶを利用して対話プロトコルを実行し、証明者が公開している公開鍵に対応する秘密鍵を、その証明者が保有しているか否かを検証する。つまり、検証者は、証明者が公開鍵に対応する秘密鍵を保有しているか否かを検証するエンティティである。このように、公開鍵認証方式のモデルは、証明者と検証者という２つのエンティティ、及び、鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰ、検証者アルゴリズムＶという３つのアルゴリズムにより構成される。
【００２６】
なお、以下の説明において、「証明者」「検証者」という表現を用いるが、これらの表現はあくまでもエンティティを意味するものである。従って、鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰを実行する主体は、「証明者」のエンティティに対応する情報処理装置である。同様に、検証者アルゴリズムＶを実行する主体は、情報処理装置である。
【００２７】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、証明者により利用される。そして、鍵生成アルゴリズムＧｅｎは、証明者に固有の秘密鍵ｓｋと公開鍵ｐｋの組を生成するアルゴリズムである。鍵生成アルゴリズムＧｅｎにより生成された公開鍵ｐｋは公開される。そして、公開された公開鍵ｐｋは、検証者により利用される。一方、鍵生成アルゴリズムＧｅｎにより生成された秘密鍵ｓｋは、証明者が秘密に管理する。そして、秘密に管理される秘密鍵ｓｋは、検証者に対して公開鍵ｐｋに対応する秘密鍵ｓｋを保有していることを証明するために利用される。形式的に、鍵生成アルゴリズムＧｅｎは、セキュリティパラメータ１λ（λは０以上の整数）を入力とし、秘密鍵ｓｋと公開鍵ｐｋを出力するアルゴリズムとして、下記の式（１）のように表現される。
【００２８】
【数１】
2014090235.tif 000003
【００２９】
（証明者アルゴリズムＰ）
証明者アルゴリズムＰは、証明者により利用される。そして、証明者アルゴリズムＰは、公開鍵ｐｋに対応する秘密鍵ｓｋを保有していることを証明するアルゴリズムである。証明者アルゴリズムＰは、証明者の秘密鍵ｓｋと公開鍵ｐｋを入力とし、検証者との対話プロトコルを実行するアルゴリズムとして定義される。
【００３０】
（検証者アルゴリズムＶ）
検証者アルゴリズムＶは、検証者により利用される。そして、検証者アルゴリズムＶは、対話プロトコルの中で、公開鍵ｐｋに対応する秘密鍵ｓｋを証明者が保有しているか否かを検証するアルゴリズムである。検証者アルゴリズムＶは、証明者の公開鍵ｐｋを入力とし、証明者との間で対話プロトコルを実行した後、０又は１（１ｂｉｔ）を出力するアルゴリズムとして定義される。なお、出力０の場合には証明者が不正なものであり、出力１の場合には証明者が正当なものであるとする。形式的に、検証者アルゴリズムＶは、下記の式（２）のように表現される。
【００３１】
【数２】
2014090235.tif 000004
【００３２】
上記の通り、公開鍵認証方式は、安全性を確保するため、健全性と零知識性という２つの条件を満たすことが求められる。しかし、証明者が秘密鍵ｓｋを保有していることを証明者に証明させるためには、証明者が秘密鍵ｓｋに依存した手続きを実行し、その結果を検証者に通知して、その通知内容に基づく検証を検証者に実行させる必要がある。秘密鍵ｓｋに依存した手続きを実行するのは、健全性を担保するために必要である。一方で、この手続きの結果を検証者に通知しても、秘密鍵ｓｋの情報が一切検証者に漏れないようにする必要がある。そのため、これらの要件を満たすように、上記の鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰ、検証者アルゴリズムＶが設計されることが必要になる。
【００３３】
次に、電子署名方式のアルゴリズムについて概要を説明する。図２は、電子署名方式のアルゴリズムについて概要を説明するための説明図である。
【００３４】
紙文書とは異なり、ある電子化されたデータに対して押印したり署名を記載したりすることはできない。そのため、電子化されたデータの作成者を証明するためには、紙文書に押印したり署名を記載したりするのと同等の効果が得られる電子的な仕組みを必要とする。この仕組みが電子署名である。電子署名とは、データの作成者しか知らない署名データをデータに関連付けて受領者に提供し、その署名データを受領者側で検証する仕組みのことを言う。
【００３５】
（モデル）
電子署名方式のモデルには、図２に示すように、署名者及び検証者という２つのエンティティが存在する。そして、電子署名方式のモデルは、鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒという３つのアルゴリズムにより構成される。
【００３６】
署名者は、鍵生成アルゴリズムＧｅｎを利用して署名者固有の署名鍵ｓｋと検証鍵ｐｋとの組を生成する。また、署名者は、署名生成アルゴリズムＳｉｇを利用して文書Ｍに付与する電子署名σを生成する。つまり、署名者は、文書Ｍに電子署名を付与するエンティティである。一方、検証者は、署名検証アルゴリズムＶｅｒを利用して文書Ｍに付与された電子署名σを検証する。つまり、検証者は、文書Ｍの作成者が署名者であるか否かを確認するために、電子署名σを検証するエンティティである。
【００３７】
なお、以下の説明において、「署名者」「検証者」という表現を用いるが、これらの表現はあくまでもエンティティを意味するものである。従って、鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇを実行する主体は、「署名者」のエンティティに対応する情報処理装置である。同様に、署名検証アルゴリズムＶｅｒを実行する主体は、情報処理装置である。
【００３８】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、署名者により利用される。鍵生成アルゴリズムＧｅｎは、署名者固有の署名鍵ｓｋと検証鍵ｐｋとの組を生成するアルゴリズムである。鍵生成アルゴリズムＧｅｎにより生成された検証鍵ｐｋは公開される。一方、鍵生成アルゴリズムＧｅｎにより生成された署名鍵ｓｋは、署名者により秘密に管理される。そして、署名鍵ｓｋは、文書Ｍに付与される電子署名σの生成に利用される。例えば、鍵生成アルゴリズムＧｅｎは、セキュリティパラメータ１λ（λは０以上の整数）を入力とし、署名鍵ｓｋ及び公開鍵ｐｋを出力する。この場合、鍵生成アルゴリズムＧｅｎは、形式的に、下記の式（３）のように表現することができる。
【００３９】
【数３】
2014090235.tif 000005
【００４０】
（署名生成アルゴリズムＳｉｇ）
署名生成アルゴリズムＳｉｇは、署名者により利用される。署名生成アルゴリズムＳｉｇは、文書Ｍに付与される電子署名σを生成するアルゴリズムである。署名生成アルゴリズムＳｉｇは、署名鍵ｓｋと文書Ｍとを入力とし、電子署名σを出力するアルゴリズムである。この署名生成アルゴリズムＳｉｇは、形式的に、下記の式（４）のように表現することができる。
【００４１】
【数４】
2014090235.tif 000006
【００４２】
（署名検証アルゴリズムＶｅｒ）
署名検証アルゴリズムＶｅｒは、検証者により利用される。署名検証アルゴリズムＶｅｒは、電子署名σが文書Ｍに対する正当な電子署名であるか否かを検証するアルゴリズムである。署名検証アルゴリズムＶｅｒは、署名者の検証鍵ｐｋ、文書Ｍ、電子署名σを入力とし、０又は１（１ｂｉｔ）を出力するアルゴリズムである。この署名検証アルゴリズムＶｅｒは、形式的に、下記の式（５）のように表現することができる。なお、検証者は、署名検証アルゴリズムＶｅｒが０を出力した場合（公開鍵ｐｋが文書Ｍと電子署名σを拒否する場合）に電子署名σが不当であると判断し、１を出力した場合（公開鍵ｐｋが文書Ｍと電子署名σを受理する場合）に電子署名σが正当であると判断する。
【００４３】
【数５】
2014090235.tif 000007
【００４４】
（ｎパスの公開鍵認証方式）
次に、図３を参照しながら、ｎパスの公開鍵認証方式について説明する。図３は、ｎパスの公開鍵認証方式について説明するための説明図である。
【００４５】
上記の通り、公開鍵認証方式は、対話プロトコルの中で、証明者が公開鍵ｐｋに対応する秘密鍵ｓｋを保有していることを検証者に証明する認証方式である。また、対話プロトコルは、健全性及び零知識性という２つの条件を満たす必要がある。そのため、対話プロトコルの中では、図３に示すように、証明者及び検証者の双方がそれぞれ処理を実行しながらｎ回の情報交換を行う。
【００４６】
ｎパスの公開鍵認証方式の場合、証明者アルゴリズムＰを用いて証明者により処理（工程＃１）が実行され、情報Ｔ１が検証者に送信される。次いで、検証者アルゴリズムＶを用いて検証者により処理（工程＃２）が実行され、情報Ｔ２が証明者に送信される。さらに、ｋ＝３〜ｎについて処理の実行及び情報Ｔｋの送信が順次行われ、最後に処理（工程＃ｎ＋１）が実行される。このように、情報がｎ回送受信される方式のことを「ｎパス」の公開鍵認証方式と呼ぶ。
【００４７】
以上、ｎパスの公開鍵認証方式について説明した。
【００４８】
上述した、鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰ、検証者アルゴリズムＶの設計の際の要件を満たすものとして、例えば特開２０１２−９８６９０号公報等で開示されている、多次多変数連立方程式に対する求解問題の困難性に安全性の根拠をおく公開鍵認証方式及び電子署名方式がある。上記文献で用いられる関数は、ｍ本のｎ変数の２次多項式（ｍ、ｎはいずれも２以上の整数）で構成される関数であるが、この関数を用いることで、上記文献による公開鍵認証方式は１つの公開鍵から複数の秘密鍵を生成することができる。上記文献で用いられる、ｍ本のｎ変数多次多項式で構成される関数を、ＭＱ（Ｍｕｌｔｉｖａｒｉａｔｅ  Ｑｕａｄｒａｔｉｃ）関数と称する。
【００４９】
まず、上記文献による公開鍵認証方式の鍵生成アルゴリズムを説明する。ここでは、公開鍵ｐｋの一部として２次多項式の組（ｆ１（ｘ），…，ｆｍ（ｘ））を利用する場合について考える。但し、２次多項式ｆｉ（ｘ）は、下記の式（６）のように表現されるものとする。また、ベクトル（ｘ１，…，ｘｎ）をｘと表記し、２次多項式の組（ｆ１（ｘ），…，ｆｍ（ｘ））を多変数多項式Ｆ（ｘ）と表記することにする。
【００５０】
【数３】
2014090235.tif 000008
【００５１】
また、２次多項式の組（ｆ１（ｘ），…，ｆｍ（ｘ））は、下記の式（７）のように表現することができる。また、Ａ１，…，Ａｍは、ｎ×ｎ行列である。さらに、ｂ１，…，ｂｍはそれぞれｎ×１ベクトルである。
【００５２】
【数４】
2014090235.tif 000009
【００５３】
この表現を用いると、多変数多項式Ｆは、下記の式（８）及び式（９）のように表現することができる。この表現が成り立つことは、下記の式（１０）から容易に確認することができる。
【００５４】
【数８】
2014090235.tif 000010
【００５５】
このようにＦ（ｘ＋ｙ）をｘに依存する第１の部分と、ｙに依存する第２の部分と、ｘ及びｙの両方に依存する第３の部分とに分けたとき、第３の部分に対応する項Ｇ（ｘ，ｙ）は、ｘ及びｙについて双線形になる。以下、項Ｇ（ｘ，ｙ）を双線形項と呼ぶ場合がある。この性質を利用すると、効率的なアルゴリズムを構築することが可能になる。
【００５６】
例えば、ベクトルｔ０∈Ｋｎ、ｅ０∈Ｋｍを用いて、多変数多項式Ｆ（ｘ＋ｒ）のマスクに利用する多変数多項式Ｆ１（ｘ）をＦ１（ｘ）＝Ｇ（ｘ，ｔ０）＋ｅ０と表現する。この場合、多変数多項式Ｆ（ｘ＋ｒ０）とＦ１（ｘ）との和は、下記の式（１１）のように表現される。ここで、ｔ１＝ｒ０＋ｔ０、ｅ１＝Ｆ（ｒ０）＋ｅ０とおけば、多変数多項式Ｆ２（ｘ）＝Ｆ（ｘ＋ｒ０）＋Ｆ１（ｘ）は、ベクトルｔ１∈Ｋｎ、ｅ１∈Ｋｍにより表現することができる。そのため、Ｆ１（ｘ）＝Ｇ（ｘ，ｔ０）＋ｅ０に設定すれば、Ｋｎ上のベクトル及びＫｍ上のベクトルを用いてＦ１及びＦ２を表現できるようになり、通信に必要なデータサイズの少ない効率的なアルゴリズムを実現することが可能になる。
【００５７】
【数９】
2014090235.tif 000011
【００５８】
なお、Ｆ２（或いはＦ１）からｒ０に関する情報が一切漏れることはない。例えば、ｅ１及びｔ１（或いはｅ０及びｔ０）を与えられても、ｅ０及びｔ０（或いはｅ１及びｔ１）を知らない限り、ｒ０の情報を一切知ることはできない。従って、零知識性が担保される。
【００５９】
ここでＭＱ関数は、ｍ＝ｎの場合に、Ｆ（ｘ１）＝Ｆ（ｘ２）となるｘ１、ｘ２を求めることができる。具体的な導出方法は以下の通りである。
【００６０】
ｎ＝ｍとした際に、ＭＱ関数に対して、Δ∈ＧＦ（２ｎ）を与えられた時に、ｘ（ｓ．ｔ．  Ｆ（ｘ）＝Ｆ（ｘ＋Δ））を出力するというアルゴリズムが存在する。なぜなら、以下の関係が成り立つからである。
Ｆ（ｘ）＝Ｆ（ｘ＋Δ）⇔Ｆ（Δ）＋Ｇ（ｘ，Δ）＝０
【００６１】
上述の関係は、ｘ＝（ｘ１，…，ｘｎ），ｘｉ＝ＧＦ（２）に関する一次の連立方程式となる。変数ｘｉ（ｉ＝１，２，・・・，ｎ）の個数と、式の本数ｍとが一致しているので、上記の連立一次方程式から解ｘを導出することができる。
【００６２】
また、ｎ＝ｃｍ（ｃは２以上の整数）とした際に、ＭＱ関数に対して、Δ１，・・・，Δｃ∈ＧＦ（２ｎ）を与えられた時に、ｘ（ｓ．ｔ．  Ｆ（ｘ）＝Ｆ（ｘ＋Δ１）＝・・・＝Ｆ（ｘ＋Δｃ））を出力するというアルゴリズムが存在する。なぜなら、以下の関係が成り立つからである。
Ｆ（ｘ）＝Ｆ（ｘ＋Δ１）⇔Ｆ（Δ１）＋Ｇ（ｘ，Δ１）＝０
・・・
Ｆ（ｘ）＝Ｆ（ｘ＋Δｃ）⇔Ｆ（Δｃ）＋Ｇ（ｘ，Δｃ）＝０
【００６３】
上述のそれぞれの方程式は、ｘ＝（ｘ１，…，ｘｎ），ｘｉ＝ＧＦ（２）に関する一次の連立方程式となる。上述のそれぞれの方程式を組み合わせると、変数ｘｉ（ｉ＝１，２，・・・，ｎ）に対して、式の本数がｃｍの連立一次方程式となる。そのため、ｎ＝ｍの場合と同様に、上記の連立一次方程式から解ｘを導出することができる。
【００６４】
このように、１つの公開鍵から複数の秘密鍵を生成することができる公開鍵認証方式で用いられるＭＱ関数を用いることで、高い安全性を満たすと共に高効率化を達成するビットコミットメントプロトコルが実現可能となる。以下では、まず既存のビットコミットメントプロトコルの例及び既存のビットコミットメントプロトコルの問題点を説明し、その後に本開示の一実施形態にかかるビットコミットメントプロトコルについて詳細に説明する。
【００６５】
＜２．既存のビットコミットメントプロトコルの説明＞
まず、既存のビットコミットメントプロトコルについて説明する。図４は、ビットコミットメントプロトコルのフローを示す流れ図である。以下、図４を用いて既存のビットコミットメントプロトコルについて説明する。
【００６６】
ビットコミットメントプロトコルは、図４に示したように、送信者と受信者との間で実行されるプロトコルである。まず送信者は、ビットｂ∈｛０，１｝を選択するとともに、乱数ｒ∈｛０，１｝ｌを選択する。そして送信者は、ビットコミットメント関数ｈを用いて、ｃ＝ｈ（ｂ，ｒ）を計算する。なおビットコミットメントプロトコルにおいて、ビットｂと乱数ｒとからコミットメントｃを生成する関数を、ビットコミットメント関数と呼ぶ。
【００６７】
送信者は、コミットメントｃを生成すると、生成したコミットメントｃを受信者に送信する。このコミットメントｃを送信者から受信者に送信する段階をコミットメントフェーズと呼ぶ。受信者は、送信者から送られてきたコミットメントｃだけでは、送信者が選択したビットｂが０と１のどちらであるかは分からない。
【００６８】
その後、送信者は、ビットｂ’及び値ｒ’を受信者に送り、受信者は、ビットコミットメント関数ｈを用いて、ｃ＝ｈ（ｂ’，ｒ’）となるかを確認する。そして受信者は、ｃ＝ｈ（ｂ’，ｒ’）が成り立つ場合に限り、送信者から送られてきたビットｂ’を出力する。このビットｂ’及び値ｒ’を送信者から受信者に送信する段階をリビールフェーズと呼ぶ。送信者は、コミットメントｃの基になるビットｂ及び乱数ｒと違う値をリビールフェーズで受信者に送信すると、受信者はコミットメントｃの基になるビットｂ及び乱数ｒと違う値がリビールフェーズで送られてきたことを検証することが出来る。
【００６９】
上述してきたように、ビットコミットメントの目的は、現在自分が所持しているビット・データの値を知らせることなく、そのビット・データを所持していることを検証者に対して確約すること、及び確約後には、検証者はそのビット・データがそのとき確約されたものであることを検証可能にすることである。そして、ビットコミットメントプロトコルを用いることで様々なアプリケーションが実現できる。
【００７０】
例えば、ビットコミットメントプロトコルを、他の暗号方式の構成要素の一部として利用することができる。例えば、多次多変数連立方程式に対する求解問題の困難性に安全性の根拠をおく公開鍵認証方式及び電子署名方式ではストリングコミットメントスキームを構成要素の一部として利用しているが、そのストリングコミットメントスキームを実現するための構成要素としても利用することができる。
【００７１】
その他、ビットコミットメントプロトコルを用いてネットワーク上でのじゃんけんを実現することができる。じゃんけんに後出しは厳禁である。しかしネットワーク上でのじゃんけんは、ユーザー同士がお互いの手を見られない状況にあることや、パケットの遅延等が存在するため、後出しの検証は難しい。しかし、ビットコミットメントプロトコルでは、送信者は先に自分の手を送るが、その手は受信者には分からず、また、後で変更することもできないので、両者共お互いの手を知らないまま安全に自分の手を決めることができる。
【００７２】
ビットコミットメントプロトコルに求められる安全性には、ｈｉｄｉｎｇとｂｉｎｄｉｎｇの２つがある。ｈｉｄｉｎｇとは、コミットメントｃからビットｂが特定できないことを言う。ｈｉｄｉｎｇにはｓｔａｔｉｓｔｉｃａｌｌｙ  ｈｉｄｉｎｇとｃｏｍｐｕｔａｔｉｏｎａｌｌｙ  ｈｉｄｉｎｇの２種類が存在し、ｓｔａｔｉｓｔｉｃａｌｌｙ  ｈｉｄｉｎｇの方がより高い安全性を示している。
【００７３】
一方、ｂｉｎｄｉｎｇとは、コミットメントフェーズにて送ったビットｂとは異なるビットを受信者に出力させることができないことを言う。具体的には、ｃ＝ｈ（ｂ，ｒ）＝ｈ（ｂ’，ｒ’）という（ｂ’，ｒ’）  ｓ．ｔ．ｂ’≠ｂを作成できない性質を言う。ビットコミットメントプロトコルは、このｈｉｄｉｎｇとｂｉｎｄｉｎｇの２つの安全性を満たさなければならない。
【００７４】
しかし、従来のビットコミットメントプロトコルには、高度な安全性が満たせなかったり、高度な安全性を満たすために効率が低下したりするものがあった。
【００７５】
図５は、既存のビットコミットメントプロトコルのフローを示す流れ図である。図５に示したのは、一方向性関数に基づいて構成されたビットコミットメントプロトコルのフローであり、非特許文献１、２などで開示されているものである。以下、図５を用いて既存のビットコミットメントプロトコルについて説明する。
【００７６】
まず図５に示したフローにおいて、
ｇ（ｘ，ｒ）：＝ｆ（ｘ）｜｜ｒ
と定義する。また関数ｆは、送信者と受信者との間で共有させておく。送信者は、図４に示したフローと同様に、ビットｂ∈｛０，１｝を選択するとともに、乱数ｒ∈｛０，１｝ｌを選択する。そして送信者は、コミットメントｃ＝ｂ＋＜ｘ，ｒ＞を計算する。なお、＜ｘ，ｒ＞はｘとｒとの内積を計算することを意味し、“＋”は排他的論理和を意味する。
【００７７】
送信者は、コミットメントｃを計算すると、コミットメントフェーズでｇ（ｘ，ｒ）およびコミットメントｃを受信者に送信する。そして送信者は、リビールフェーズで、値ｂ’及びｘ’を送信する。受信者は、ｇ（ｘ，ｒ）＝ｇ（ｘ’，ｒ）となるか確認し、ｇ（ｘ，ｒ）＝ｇ（ｘ’，ｒ）であれば、続いてコミットメントｃがｃ＝ｂ’＋＜ｘ’，ｒ＞となるかを確認する。ｃ＝ｂ’＋＜ｘ’，ｒ＞であれば、受信者は、送信者からリビールフェーズで送信された値ｂ’を出力する。
【００７８】
しかし、非特許文献１に記載されたビットコミットメントプロトコルでは、最低限の安全性（Ｃｏｍｐｕｔａｔｉｏｎａｌｌｙ  ｈｉｄｉｎｇ）しか満たさず、さらに高度な安全性（Ｓｔａｔｉｓｔｉｃａｌｌｙ  ｈｉｄｉｎｇ）は満たせていない。なお、Ｃｏｍｐｕｔａｔｉｏｎａｌｌｙ  ｈｉｄｉｎｇとは、ある程度以下の計算能力しか持たない受信者に対しては、コミットした値が何であるか知られることがないという性質をいう。また、Ｓｔａｔｉｓｔｉｃａｌｌｙ  ｈｉｄｉｎｇとは、どのような計算能力を持つ受信者に対しても、コミットした値が何であるか知られることがないという性質をいう。
【００７９】
また非特許文献２に記載されたビットコミットメントプロトコルでは、Ｓｔａｔｉｓｔｉｃａｌｌｙ  ｈｉｄｉｎｇを達成することができるが、Ｓｔａｔｉｓｔｉｃａｌｌｙ  ｈｉｄｉｎｇを達成するために送信者と受信者との間で必要となる通信回数が増加して、効率が低下してしまうと言う問題が生じる。
【００８０】
そこで本開示の一実施形態では、上述したようなＭＱ関数特有の性質を利用して、効率を低下させること無くＳｔａｔｉｓｔｉｃａｌｌｙ  ｈｉｄｉｎｇを達成できるビットコミットメントプロトコルについて示す。
【００８１】
＜３．本開示の一実施形態＞
［システム構成例］
図６は、本開示の一実施形態に係る情報処理システム１の構成例を示す説明図である。以下、図６を用いて本開示の一実施形態に係る情報処理システム１の構成例について説明する。
【００８２】
図６に示したように、本開示の一実施形態に係る情報処理システム１は、情報処理装置１００、２００を含んで構成される。ここで、情報処理装置１００は、ビットコミットメントプロトコルにおける送信者側の装置であり、情報処理装置２００は、同じくビットコミットメントプロトコルにおける受信者側の装置である。
【００８３】
情報処理装置１００は、ビットコミットメント関数処理部１１０と、通信部１２０と、メモリ１３０と、を含んで構成される。また情報処理装置２００は、ビットコミットメント関数処理部２１０と、通信部２２０と、メモリ２３０と、を含んで構成される。
【００８４】
まず、情報処理装置１００の機能構成について説明する。ビットコミットメント関数処理部１１０は、ビットコミットメントプロトコルで使用する関数を用いた処理を実行する。具体的には後述するが、ビットコミットメント関数処理部１１０は、Ｆ（ｘ１）＝Ｆ（ｘ２）となるｘ１、ｘ２を求めることができるというＭＱ関数の性質を利用して、ＭＱ関数を用いた処理を実行する。
【００８５】
通信部１２０は、ネットワークに対する通信処理を実行するものであり、本実施形態では、情報処理装置２００との間の通信を実行する。通信部１２０が実行する通信処理は、有線による通信であっても無線による通信であってもよい。本実施形態では、通信部１２０は、ビットコミットメント関数処理部１１０による処理内容を情報処理装置２００へ送信する。
【００８６】
メモリ１３０は、情報処理装置１００における各種処理に用いられる情報を格納したり、各種処理時の一時的なワークメモリとして用いられたりする記録媒体である。
【００８７】
次に、情報処理装置２００の機能構成について説明する。ビットコミットメント関数処理部２１０は、ビットコミットメントプロトコルで使用する関数を用いた処理を実行する。具体的には後述するが、ビットコミットメント関数処理部２１０は、ＭＱ関数を用いて、情報処理装置１００で生成されたコミットメントの検証を行なう。
【００８８】
通信部２２０は、ネットワークに対する通信処理を実行するものであり、本実施形態では、情報処理装置１００との間の通信を実行する。通信部２２０が実行する通信処理は、有線による通信であっても無線による通信であってもよい。本実施形態では、通信部２２０は、ビットコミットメントプロトコルの実行に際して、情報処理装置１００から送信された情報を受信し、受信した情報をビットコミットメント関数処理部２１０へ供給する。
【００８９】
メモリ２３０は、情報処理装置２００における各種処理に用いられる情報を格納したり、各種処理時の一時的なワークメモリとして用いられたりする記録媒体である。
【００９０】
本開示の一実施形態に係る情報処理システム１は、情報処理装置１００と情報処理装置２００との間でビットコミットメントプロトコルを実行する。情報処理システム１で実行されるビットコミットメントプロトコルは、Ｆ（ｘ１）＝Ｆ（ｘ２）となるｘ１、ｘ２を求めることができるというＭＱ関数の性質を利用したものであり、ある関係性を用いて、ｘ１、ｘ２に対して｛０，１｝を割り当て、コミットメントフェーズとリビールフェーズとでそれぞれの要素を情報処理装置１００から情報処理装置２００に送信することで実現されるものである。
【００９１】
以上、図６を用いて本開示の一実施形態に係る情報処理システム１の構成例について説明した。次に、本開示の一実施形態に係る情報処理システム１の動作例について説明する。
【００９２】
［システム動作例］
図７は、本開示の一実施形態に係る情報処理システム１の動作例を示す流れ図である。図７に示したのは、情報処理装置１００と情報処理装置２００との間で実行されるビットコミットメントプロトコルである。以下、図７を用いて本開示の一実施形態に係る情報処理システム１の動作例について説明する。
【００９３】
まず、ビットコミットメントプロトコルの実行に先立って、ある関係性Ｒを、情報処理装置１００と情報処理装置２００との間で共有させる。その関係性Ｒを以下のように定義する。
Ｒ：ＧＦ（２ｎ）×ＧＦ（２ｎ）→｛０，１｝
つまり関係性Ｒは、２つのｎビットの値から１ビットの値が決定できるような関係性である。
【００９４】
送信者側の情報処理装置１００は、ＭＱ関数Ｆを用いて、Ｆ（ｘ１）＝Ｆ（ｘ２）となるｘ１、ｘ２をビットコミットメント関数処理部１１０で生成する（ステップＳ１０１）。例えば、Ｒ（ｘ１，ｘ２）は、ｘ１＜ｘ２であれば０を、そうでなければ１を出力するような関係性であるとする。ここでは、関係性Ｒとｘ１、ｘ２との関係は、Ｒ（ｘ１，ｘ２）＝１，Ｒ（ｘ２，ｘ１）＝０とする。
【００９５】
続いて情報処理装置１００は、コミットする値をビットコミットメント関数処理部１１０で決定する（ステップＳ１０２）。本実施形態では、情報処理装置１００は、０をコミットする場合は、コミットメントフェーズで送信する情報ｘｃｏｍはｘｃｏｍ＝ｘ２、リビールフェーズで送信する情報ｘｒｅｖはｘｒｅｖ＝ｘ１とする。また情報処理装置１００は、１をコミットする場合は、コミットメントフェーズで送信する情報ｘｃｏｍはｘｃｏｍ＝ｘ１、リビールフェーズで送信する情報ｘｒｅｖはｘｒｅｖ＝ｘ２とする。
【００９６】
続いて情報処理装置１００は、コミットメントフェーズで情報ｘｃｏｍを情報処理装置２００に送信し（ステップＳ１０３）、続いてリビールフェーズで情報ｘｒｅｖを情報処理装置２００に送信する（ステップＳ１０４）。
【００９７】
情報処理装置２００は、情報処理装置１００からｘｃｏｍ及びｘｒｅｖを受信すると、Ｆ（ｘｃｏｍ）＝Ｆ（ｘｒｅｖ）となるか確認する（ステップＳ１０５）。Ｆ（ｘｃｏｍ）＝Ｆ（ｘｒｅｖ）となれば、情報処理装置１００がコミットした値が正しく情報処理装置２００に送信されたと判断し、情報処理装置２００は、Ｒ（ｘｃｏｍ，ｘｒｅｖ）を出力する。一方、Ｆ（ｘｃｏｍ）＝Ｆ（ｘｒｅｖ）とならなければ、情報処理装置１００がコミットした値ではない値が情報処理装置２００に送信されたと判断し、情報処理装置２００は値の出力を行わない。
【００９８】
本実施形態に係る情報処理システム１は、このように、予め所定の関係性を送信者側と受信者側とで共有させておき、Ｆ（ｘ１）＝Ｆ（ｘ２）となるｘ１、ｘ２を求めることができるというＭＱ関数の性質を利用することで、効率を低下させること無くビットコミットメントプロトコルの安全性を確保することができる。
【００９９】
このようにＭＱ関数を利用することで、安全性を高めたビットコミットメントプロトコルを実現することができるが、関係性Ｒをより複雑なものにすることで、さらにビットコミットメントプロトコルの安全性を高めることができる。
【０１００】
例えば上述した、ｘ１＜ｘ２であれば０を、そうでなければ１を出力するような関係性Ｒ（ｘ１，ｘ２）は、ｎビットのｘ１またはｘ２が明らかになった時点で，その値が０ｎ（４ビットであれば００００）に近いか、または１ｎ（４ビットであれば１１１１）に近いかで，ｘ１とｘ２の大小関係について、確率的に有意性を持った予測が可能となる。図８は、ｘ１の値によるｘ１とｘ２の大小関係の予測について示す説明図である。図８に示したように、ｘ１が０〜２ｎ−１の間にある場合はｘ１＜ｘ２となる確率が高そうであるという予測ができ、ｘ１が２ｎ−１〜２ｎの間にある場合はｘ１＞ｘ２となる確率が高そうであるという予測ができる。もちろんこれは確率上の問題であり、必ずしも上述のような関係が成り立つというわけでは無いが、ビットコミットメントプロトコルの安全性を高めるには、そのような予測すら出来ないような関係性を規定することが、より望ましい。
【０１０１】
そこで、以下においては、より複雑な関係性Ｒを規定することでビットコミットメントプロトコルの安全性を高めた例を説明する。
【０１０２】
上述の関係性Ｒは、ｘ１が明らかになった時点で，その値が固定された値である０ｎに近いか遠いかで、残りの値に関わらずＲ（ｘ１，ｘ２）の値がある程度予測できてしまう。従って、ｘ１が明らかになったとしても、その値に依存した値に近いか遠いかでＲ（ｘ１，ｘ２）の値を決まるようにすることで予測を困難にする場合の例を説明する。
【０１０３】
例えば、関係性Ｒ２（ｘ１，ｘ２）を以下のように規定することで、ビットコミットメントプロトコルにおけるｈｉｄｉｎｇの安全性を高めることが出来る。
【０１０４】
ｉｆ  （ｘ１＜１０ｎ−１）  ｛
ｉｆ  （ｘ１＜ｘ２＜ｘ１＋１０ｎ−１）｛
ｏｕｔｐｕｔ  １
｝  ｅｌｓｅ  ｛
ｏｕｔｐｕｔ  ０
｝
｝  ｅｌｓｅ  ｛
ｉｆ  （ｘ１＋１０ｎ−１＜ｘ２＜ｘ１）｛
ｏｕｔｐｕｔ  ０
｝  ｅｌｓｅ  ｛
ｏｕｔｐｕｔ  １
｝
｝
【０１０５】
つまり関係性Ｒ２（ｘ１，ｘ２）は、ｎビットのｘ１，ｘ２に対し、ｘ１＜１０ｎ−１（ｎが４であれば１０００）であり、さらにｘ１＜ｘ２であり、かつｘ２＜ｘ１＋１０ｎ−１であれば１、そうでなければ０であるとする。また関係性Ｒ（ｘ１，ｘ２）は、ｎビットのｘ１，ｘ２に対し、ｘ１≧１０ｎ−１であり、さらにｘ１＋１０ｎ−１＜ｘ２であり、かつｘ２＜ｘ１であれば０、そうでなければ１であるとする。
【０１０６】
図９は、この関係性Ｒ２（ｘ１，ｘ２）を視覚的に示す説明図である。例えば４ビットのｘ１，ｘ２に対し、ｘ１が“０１１０”である場合、ｘ２が破線の矢印で示した場所にあれば１を出力し、そうでなければ０を出力するような関係性Ｒ２（ｘ１，ｘ２）が規定される。つまり、この関係性Ｒ２（ｘ１，ｘ２）を用いることと、ｘ１に対してＦ（ｘ１）＝Ｆ（ｘ２）を満たすｘ２が｛０，１｝ｎ上でランダムに分布していると仮定することで、ｘ１がどの値であろうとＲ２（ｘ１，ｘ２）の予測は非常に困難になり、ビットコミットメントプロトコルにおけるｈｉｄｉｎｇの安全性を高めることになる。
【０１０７】
このように、ＭＱ関数の特性を生かしてビットコミットメントプロトコルを構成することで、送信者と受信者との間の通信回数が、コミットメントフェーズとリビールフェーズとでそれぞれ１回ずつとなっており、効率的なビットコミットメントプロトコルを実現できる。
【０１０８】
また、ＭＱ関数のパラメータｎ，ｍに対してｎ＞ｍとしたとき，ある値ｙ∈｛０，１｝ｍの逆元の数の期待値は２ｎ−ｍ以上となる。そのことから，ｎをｍに対してある程度大きく設定しておくことで、受信者はリビールフェーズで送られる値を正しく予測できなくなり、安全性を確保できる。この安全性を満たすためのパラメータの設定としては，ｎ≧２ｍとするような設定が考えられる。例えばこの安全性を満たすために、ｎ及びｍを、（ｎ，ｍ）＝（１６０，８０）や（２５６，１２８）のように設定しても良い。
【０１０９】
また、関係性を適切に定義することで（例えば上述のような関係性Ｒ２のように定義することで）、ｓｔａｔｉｓｔｉｃａｌｌｙ  ｈｉｄｉｎｇを達成することができる。
【０１１０】
［変形例］
このように、本開示の一実施形態に係る情報処理システム１は、Ｆ（ｘ１）＝Ｆ（ｘ２）となるｘ１、ｘ２を求めることができるというＭＱ関数の性質を利用することで、効率を低下させること無くビットコミットメントプロトコルの安全性を確保することができる。本開示の一実施形態に係る情報処理システム１は、このビットコミットメントプロトコルをストリングコミットメントプロトコルに拡張しても良い。
【０１１１】
ビットコミットメントプロトコルでは、送信者は｛０，１｝を相手に送信するが、ストリングコミットメントプロトコルでは、送信者は｛０，１｝以上の情報（例えば｛０，１，２｝や、ｚビットの｛０，１｝ｚ）を相手に送信する。
【０１１２】
上述したように、ＭＱ関数は、ｎ＝ｃｍであるｍ，ｎに対して、Ｆ（ｘ１）＝Ｆ（ｘ２）＝…＝Ｆ（ｘｃ＋１）となるようなｘ１，ｘ２，…，ｘｃ＋１が計算できる．そのｘ１，ｘ２，…，ｘｃ＋１に対し，ある関係性を用いてｚビットの｛０，１｝ｚを割り当て，コミットメントフェーズ、リビールフェーズにてそれぞれの要素を送ることで、ストリングコミットメントプロトコルの実現が可能である。
【０１１３】
図１０は、本開示の一実施形態に係る情報処理システム１を用いたストリングコミットメントプロトコルのフローを示す流れ図である。以下、図１０を用いて本開示の一実施形態に係る情報処理システム１を用いたストリングコミットメントプロトコルについて説明する。
【０１１４】
まず、ストリングコミットメントプロトコルの実行に先立って、ある関係性Ｒ３を情報処理装置１００と情報処理装置２００との間で共有させる。その関係性Ｒ３を以下のように定義する。
Ｒ３：ＧＦ（２ｎ）×ＧＦ（２ｎ）×ＧＦ（２ｎ）→｛０，１，２｝
つまり関係性Ｒ３は、３つのｎビットの値から０，１，２のいずれかの値が決定できるような関係性である。
【０１１５】
送信者側の情報処理装置１００は、ＭＱ関数Ｆを用いて、Ｆ（ｘ１）＝Ｆ（ｘ２）＝Ｆ（ｘ３）となるｘ１、ｘ２、ｘ３をビットコミットメント関数処理部１１０で生成する（ステップＳ１１１）。ここでは、関係性Ｒ３とｘ１、ｘ２、ｘ３との関係は、Ｒ３（ｘ１，．，．）＝０、Ｒ３（ｘ２，．，．）＝１，Ｒ３（ｘ３，．，．）＝２であるとする。
【０１１６】
続いて情報処理装置１００は、コミットする値をビットコミットメント関数処理部１１０で決定する（ステップＳ１１２）。この変形例では、情報処理装置１００は、０をコミットする場合は、コミットメントフェーズで送信する情報ｘｃｏｍはｘｃｏｍ＝ｘ１、リビールフェーズで送信する情報ｘｒｅｖはｘｒｅｖ１＝ｘ２、ｘｒｅｖ２＝ｘ３とする。また情報処理装置１００は、１をコミットする場合は、コミットメントフェーズで送信する情報ｘｃｏｍはｘｃｏｍ＝ｘ２、リビールフェーズで送信する情報ｘｒｅｖ１＝ｘ１、ｘｒｅｖ２＝ｘ３とする。また情報処理装置１００は、２をコミットする場合は、コミットメントフェーズで送信する情報ｘｃｏｍはｘｃｏｍ＝ｘ３、リビールフェーズで送信する情報ｘｒｅｖ１＝ｘ１、ｘｒｅｖ２＝ｘ２とする。
【０１１７】
続いて情報処理装置１００は、コミットメントフェーズで情報ｘｃｏｍを情報処理装置２００に送信し（ステップＳ１１３）、続いてリビールフェーズで情報ｘｒｅｖ１、ｘｒｅｖ２を情報処理装置２００に送信する（ステップＳ１１４）。
【０１１８】
情報処理装置２００は、情報処理装置１００からｘｃｏｍ及びｘｒｅｖ１、ｘｒｅｖ２を受信すると、Ｆ（ｘｃｏｍ）＝Ｆ（ｘｒｅｖ１）＝Ｆ（ｘｒｅｖ２）となるか確認する（ステップＳ１１５）。Ｆ（ｘｃｏｍ）＝Ｆ（ｘｒｅｖ１）＝Ｆ（ｘｒｅｖ２）となっていれば、情報処理装置１００がコミットした値が正しく情報処理装置２００に送信されたと判断し、情報処理装置２００は、Ｒ３（ｘｃｏｍ，ｘｒｅｖ１，ｘｒｅｖ２）を出力する。一方、Ｆ（ｘｃｏｍ）＝Ｆ（ｘｒｅｖ１）＝Ｆ（ｘｒｅｖ２）とならなければ、情報処理装置１００がコミットした値ではない値が情報処理装置２００に送信されたと判断し、情報処理装置２００は値の出力を行わない。
【０１１９】
本実施形態に係る情報処理システム１は、このように、予め所定の関係性を送信者側と受信者側とで共有させておき、Ｆ（ｘ１）＝Ｆ（ｘ２）＝Ｆ（ｘ３）となるｘ１、ｘ２、ｘ３を求めることができるというＭＱ関数の性質を利用することでストリングコミットメントプロトコルを実現できる。
【０１２０】
上述したように、本開示の一実施形態に係る情報処理システム１で実行されるビットコミットメントプロトコルは、ＭＱ関数のパラメータｎ，ｍに対して，ｎ≧２ｍとすることで，ｓｔａｔｉｓｔｉｃａｌｌｙ  ｈｉｄｉｎｇを達成することができる。しかし、ｎ≧２ｍの場合はＦ（ｘ１）＝Ｆ（ｘ２）＝Ｆ（ｘ３）となるｘ１、ｘ２、ｘ３が計算できる。
【０１２１】
例えば、Ｆ（ｘ１）＝Ｆ（ｘ２）＝Ｆ（ｘ３）となるｘ１、ｘ２、ｘ３が計算できる場合に、図７に示したビットコミットメントプロトコルにおいて、情報処理装置１００がコミットメントフェーズ時にｘ１を送信した場合、その後のリビールフェーズ時に、情報処理装置１００が残りの２つのｘ２、ｘ３のどちらかを自由に選べるようになる。その場合ｘ２を選択する場合と、ｘ３を選択する場合とで、受信者側の情報処理装置２００の出力に違いが出てくる可能性がある。
【０１２２】
そこで、ｎ≧３ｍとした場合に、ｂｉｎｄｉｎｇを達成するための変形例を説明する。これは、ｎ≧３ｍとした場合に、ｘ１、ｘ２以外の変数の生成法に制限を持たせることで、受信者側で有効な変数かを検証できるようにするものである。
【０１２３】
具体的にはこのように制限を持たせる。ｎ＝ｃｍの場合は、送信者はΔ２，Δ３，…，Δｃをあらかじめプロトコル内で規定された定数ｄ３，ｄ４，…，ｄｃ＋１を用いて、（Δ２，Δ３，…，Δｃ）＝（ｄ３，ｄ４，…，ｄｃ＋１）と設定し、Ｆ（ｘ１）＝…＝Ｆ（ｘｃ＋１）となるｘ１，…，ｘｃ＋１を生成することにする。そして送信者は、リビールフェーズ時に、ｘ１，ｘ２の他にｘ３，…，ｘｃ＋１を全て送信し、受信者はｘ３，…，ｘｃ＋１が、ｘ１（またはｘ２）に対して，それぞれ差分（ｄ３，…，ｄｃ＋１）を持つかを検証する。これにより、送信者側で必要以上の変数はｘ３，…，ｘｃ＋１が利用できないように制限させる。
【０１２４】
図１１は、本開示の一実施形態に係る情報処理システム１の動作例を示す流れ図である。図１１に示したのは、情報処理装置１００と情報処理装置２００との間で実行されるビットコミットメントプロトコルであり。図７に示したビットコミットメントプロトコルの変形例を示したものである。以下、図１を用いて本開示の一実施形態に係る情報処理システム１の動作例について説明する。
【０１２５】
まず、ビットコミットメントプロトコルの実行に先立って、ある関係性Ｒを情報処理装置１００と情報処理装置２００との間で共有させる。その関係性Ｒを以下のように定義する。
Ｒ：ＧＦ（２ｎ）×ＧＦ（２ｎ）→｛０，１｝
つまり関係性Ｒは、２つのｎビットの値から１ビットの値が決定できるような関係性である。
【０１２６】
さらにビットコミットメントプロトコルの実行に先立って、上述した差分（ｄ３，…，ｄｃ＋１）を情報処理装置１００と情報処理装置２００との間で共有させる。
【０１２７】
送信者側の情報処理装置１００は、ＭＱ関数Ｆを用いて、Ｆ（ｘ１）＝…＝Ｆ（ｘｃ＋１）となり、かつｘ３＝ｘ１＋ｄ３，…，ｘｃ＋１＝ｘ１＋ｄｃ＋１となるｘ１，…，ｘｃ＋１をビットコミットメント関数処理部１１０で生成する（ステップＳ１２１）。
【０１２８】
続いて情報処理装置１００は、コミットする値をビットコミットメント関数処理部１１０で決定する（ステップＳ１２２）。この変形例では、図７に示したビットコミットメントプロトコルと同じく、情報処理装置１００は、０をコミットする場合は、コミットメントフェーズで送信する情報ｘｃｏｍはｘｃｏｍ＝ｘ２、リビールフェーズで送信する情報ｘｒｅｖはｘｒｅｖ＝ｘ１とする。また情報処理装置１００は、１をコミットする場合は、コミットメントフェーズで送信する情報ｘｃｏｍはｘｃｏｍ＝ｘ１、リビールフェーズで送信する情報ｘｒｅｖはｘｒｅｖ＝ｘ２とする。
【０１２９】
続いて情報処理装置１００は、コミットメントフェーズで情報ｘｃｏｍを情報処理装置２００に送信し（ステップＳ１２３）、続いてリビールフェーズで情報ｘｒｅｖ及び上記ステップＳ１２１で生成した値の残りであるｘ３，…，ｘｃ＋１を情報処理装置２００に送信する（ステップＳ１２４）。
【０１３０】
情報処理装置２００は、情報処理装置１００からｘｃｏｍ、ｘｒｅｖ及びｘ３，…，ｘｃ＋１を受信すると、ビットコミットメント関数処理部２１０にて、（ｘｃｏｍ＋ｄ３＝ｘ３，…，ｘｃｏｍ＋ｄｃ＋１＝ｘｃ＋１）及び（ｘｒｅｖ＋ｄ３＝ｘ３，…，ｘｒｅｖ＋ｄｃ＋１＝ｘｃ＋１）となるかを確認すると共に、Ｆ（ｘｃｏｍ）＝Ｆ（ｘｒｅｖ）となるか確認する（ステップＳ１２５）。上記の条件をすべて満たせば、情報処理装置１００がコミットした値が正しく情報処理装置２００に送信されたと判断し、情報処理装置２００は、Ｒ（ｘｃｏｍ，ｘｒｅｖ）を出力する。一方、上記の条件をすべて満たしていなければ、情報処理装置１００がコミットした値ではない値が情報処理装置２００に送信されたと判断し、情報処理装置２００は値の出力を行わない。
【０１３１】
このように、送信者側の情報処理装置１００で生成するｘ１、ｘ２以外の変数の生成法に制限を持たせることで、受信者側の情報処理装置２００で有効な変数かを検証でき、安全性が高く、かつ効率も良いビットコミットメントプロトコルを実現することが出来る。
【０１３２】
＜４．ハードウェア構成例＞
上記の各アルゴリズムは、例えば、図１２に示す情報処理装置のハードウェア構成を用いて実行することが可能である。つまり、当該各アルゴリズムの処理は、コンピュータプログラムを用いて図１２に示すハードウェアを制御することにより実現される。なお、このハードウェアの形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、ＰＨＳ、ＰＤＡ等の携帯情報端末、ゲーム機、接触式又は非接触式のＩＣチップ、接触式又は非接触式のＩＣカード、又は種々の情報家電がこれに含まれる。但し、上記のＰＨＳは、Ｐｅｒｓｏｎａｌ  Ｈａｎｄｙ−ｐｈｏｎｅ  Ｓｙｓｔｅｍの略である。また、上記のＰＤＡは、Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔの略である。
【０１３３】
図１２に示すように、このハードウェアは、主に、ＣＰＵ９０２と、ＲＯＭ９０４と、ＲＡＭ９０６と、ホストバス９０８と、ブリッジ９１０と、を有する。さらに、このハードウェアは、外部バス９１２と、インターフェース９１４と、入力部９１６と、出力部９１８と、記憶部９２０と、ドライブ９２２と、接続ポート９２４と、通信部９２６と、を有する。但し、上記のＣＰＵは、Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔの略である。また、上記のＲＯＭは、Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙの略である。そして、上記のＲＡＭは、Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙの略である。
【０１３４】
ＣＰＵ９０２は、例えば、演算処理装置又は制御装置として機能し、ＲＯＭ９０４、ＲＡＭ９０６、記憶部９２０、又はリムーバブル記録媒体９２８に記録された各種プログラムに基づいて各構成要素の動作全般又はその一部を制御する。ＲＯＭ９０４は、ＣＰＵ９０２に読み込まれるプログラムや演算に用いるデータ等を格納する手段である。ＲＡＭ９０６には、例えば、ＣＰＵ９０２に読み込まれるプログラムや、そのプログラムを実行する際に適宜変化する各種パラメータ等が一時的又は永続的に格納される。
【０１３５】
これらの構成要素は、例えば、高速なデータ伝送が可能なホストバス９０８を介して相互に接続される。一方、ホストバス９０８は、例えば、ブリッジ９１０を介して比較的データ伝送速度が低速な外部バス９１２に接続される。また、入力部９１６としては、例えば、マウス、キーボード、タッチパネル、ボタン、スイッチ、及びレバー等が用いられる。さらに、入力部９１６としては、赤外線やその他の電波を利用して制御信号を送信することが可能なリモートコントローラ（以下、リモコン）が用いられることもある。
【０１３６】
出力部９１８としては、例えば、ＣＲＴ、ＬＣＤ、ＰＤＰ、又はＥＬＤ等のディスプレイ装置、スピーカ、ヘッドホン等のオーディオ出力装置、プリンタ、携帯電話、又はファクシミリ等、取得した情報を利用者に対して視覚的又は聴覚的に通知することが可能な装置である。但し、上記のＣＲＴは、Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅの略である。また、上記のＬＣＤは、Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙの略である。そして、上記のＰＤＰは、Ｐｌａｓｍａ  ＤｉｓｐｌａｙＰａｎｅｌの略である。さらに、上記のＥＬＤは、Ｅｌｅｃｔｒｏ−Ｌｕｍｉｎｅｓｃｅｎｃｅ  Ｄｉｓｐｌａｙの略である。
【０１３７】
記憶部９２０は、各種のデータを格納するための装置である。記憶部９２０としては、例えば、ハードディスクドライブ（ＨＤＤ）等の磁気記憶デバイス、半導体記憶デバイス、光記憶デバイス、又は光磁気記憶デバイス等が用いられる。但し、上記のＨＤＤは、Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅの略である。
【０１３８】
ドライブ９２２は、例えば、磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体９２８に記録された情報を読み出し、又はリムーバブル記録媒体９２８に情報を書き込む装置である。リムーバブル記録媒体９２８は、例えば、ＤＶＤメディア、Ｂｌｕ−ｒａｙメディア、ＨＤ  ＤＶＤメディア、各種の半導体記憶メディア等である。もちろん、リムーバブル記録媒体９２８は、例えば、非接触型ＩＣチップを搭載したＩＣカード、又は電子機器等であってもよい。但し、上記のＩＣは、Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔの略である。
【０１３９】
接続ポート９２４は、例えば、ＵＳＢポート、ＩＥＥＥ１３９４ポート、ＳＣＳＩ、ＲＳ−２３２Ｃポート、又は光オーディオ端子等のような外部接続機器９３０を接続するためのポートである。外部接続機器９３０は、例えば、プリンタ、携帯音楽プレーヤ、デジタルカメラ、デジタルビデオカメラ、又はＩＣレコーダ等である。但し、上記のＵＳＢは、Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓの略である。また、上記のＳＣＳＩは、Ｓｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅの略である。
【０１４０】
通信部９２６は、ネットワーク９３２に接続するための通信デバイスであり、例えば、有線又は無線ＬＡＮ、Ｂｌｕｅｔｏｏｔｈ（登録商標）、又はＷＵＳＢ用の通信カード、光通信用のルータ、ＡＤＳＬ用のルータ、又は接触又は非接触通信用のデバイス等である。また、通信部９２６に接続されるネットワーク９３２は、有線又は無線により接続されたネットワークにより構成され、例えば、インターネット、家庭内ＬＡＮ、赤外線通信、可視光通信、放送、又は衛星通信等である。但し、上記のＬＡＮは、Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋの略である。また、上記のＷＵＳＢは、Ｗｉｒｅｌｅｓｓ  ＵＳＢの略である。そして、上記のＡＤＳＬは、Ａｓｙｍｍｅｔｒｉｃ  Ｄｉｇｉｔａｌ  Ｓｕｂｓｃｒｉｂｅｒ  Ｌｉｎｅの略である。
【０１４１】
＜５．まとめ＞
以上説明したように本開示の一実施形態に係る情報処理システム１によれば、予め所定の関係性を送信者側と受信者側とで共有させておき、Ｆ（ｘ１）＝Ｆ（ｘ２）となるｘ１、ｘ２を求めることができるというＭＱ関数の性質を利用したビットコミットメントプロトコルを実行することができる。本開示の一実施形態に係る情報処理システム１は、送信者側の情報処理装置１００と、受信者側の情報処理装置２００との間で上述のビットコミットメントプロトコルを実行することで、ビットコミットメントプロトコルの実行時の効率を低下させること無く、ビットコミットメントプロトコルの安全性を確保することができる。
【０１４２】
また、本開示の一実施形態に係る情報処理システム１は、送信者側と受信者側とで予め共有させる関係性を複雑なものにすることで、ビットコミットメントプロトコルの安全性をより高めることができる。すなわち、予め共有させる関係性を複雑なものにすることで、送信者がどの値をコミットしたかを受信者が推測することが出来ないようなビットコミットメントプロトコルが実現できる。
【０１４３】
なお、上述の説明では、２以上の異なる値から同一の結果が得られる関数ＦとしてＭＱ関数を挙げたが、本開示は係る例に限定されない。ＭＱ関数のように、２以上の異なる値から同一の結果が得られる関数であれば他の関数が用いられても良い。
【０１４４】
以上、添付図面を参照しながら本開示の好適な実施形態について詳細に説明したが、本開示はかかる例に限定されない。本開示の属する技術の分野における通常の知識を有する者であれば、特許請求の範囲に記載された技術的思想の範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、これらについても、当然に本開示の技術的範囲に属するものと了解される。
【０１４５】
なお、本技術は以下のような構成も取ることができる。
（１）
異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置へコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記関数Ｆを適用すると同じ結果になる値ｘ１、・・・、ｘｎを生成する関数処理部を備え、
前記関数処理部は、前記関係性Ｒの適用により前記他の装置へコミットする値を決定するコミット段階と、前記コミット段階でコミットした値を公開する公開段階とを実行し、前記コミット段階と、前記公開段階とで、前記値ｘ１、・・・、ｘｎから前記コミットする値に対応するそれぞれ異なる値を選択して前記他の装置へ送信する、情報処理装置。
（２）
前記関係性Ｒは、前記コミット段階で前記他の装置に送信する値に対して、前記公開段階の前では前記他の装置は前記コミットした値が予測出来ないよう定められている、前記（１）に記載の情報処理装置。
（３）
前記関係性Ｒは、前記値ｘ１、・・・、ｘｎの大小関係によって値が決まるよう定められている、前記（１）に記載の情報処理装置。
（４）
前記ｎの値は２である、前記（１）〜（３）のいずれかに記載の情報処理装置。
（５）
前記ｎの値は３以上であり、
前記関数処理部は、前記関係性Ｒの適用により前記コミット段階で前記値ｘ１、・・・、ｘｎから一の値を選択して前記他の装置へ送信し、前記公開段階で他の前記値を全て前記他の装置へ送信する、前記（１）〜（３）のいずれかに記載の情報処理装置。
（６）
前記ｎの値は３以上であり、
前記関数処理部は、所定の制限に従って前記値ｘ１、・・・、ｘｎを生成して前記所定の制限の情報を前記他の装置との間で共有させ、前記関係性Ｒの適用により前記コミット段階で前記値ｘ１、・・・、ｘｎから一の値を選択して前記他の装置へ送信し、前記公開段階で他の前記値を全て前記他の装置へ送信する、前記（１）〜（３）のいずれかに記載の情報処理装置。
（７）
前記関数Ｆは、ａ本のｂ変数の２次多項式（ａ、ｂはいずれも２以上の整数）で構成される関数である、前記（１）〜（６）のいずれかに記載の情報処理装置。
（８）
異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置がコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記他の装置から送信された前記値に対して前記関数Ｆを適用する関数処理部を備え、
前記関数処理部は、前記関係性Ｒの適用により前記他の装置がコミットした値に対応する第１の値を受信するコミット段階と、前記他の装置がコミットした値を公開するための第２の値を受信する公開段階とを実行し、
前記関数処理部は、前記公開段階で、前記第１の値と前記第２の値とが異なり、かつ前記第１の値及び前記第２の値に前記関数Ｆを適用すると同じ結果になるかどうか判断する、情報処理装置。
（９）
前記関数処理部は、前記第１の値及び前記第２の値に前記関数Ｆを適用して同じ結果になると、前記第１の値及び前記第２の値に対して関係性Ｒを適用した結果を出力する、前記（８）に記載の情報処理装置。
（１０）
前記ｎの値は３以上であり、所定の制限に従って前記他の装置で前記値ｘ１、・・・、ｘｎが生成された場合に前記所定の制限の情報を前記他の装置との間で共有し、
前記関数処理部は、前記公開段階で、前記他の装置から受信した値が前記所定の制限の下で生成されたかどうか判断する、前記（８）に記載の情報処理装置。
（１１）
前記関数Ｆは、ａ本のｂ変数の２次多項式（ａ、ｂはいずれも２以上の整数）で構成される関数である、前記（８）〜（１０）のいずれかに記載の情報処理装置。
（１２）
第１の情報処理装置及び第２の情報処理装置を備え、
異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに前記第１の情報処理装置が前記第２の情報処理装置へコミットする値との関係性Ｒを前記第１の情報処理装置及び前記第２の情報処理装置の間で共有させ、
前記第１の情報処理装置は、
前記関数Ｆを適用すると同じ結果になる値ｘ１、・・・、ｘｎを生成する第１の関数処理部を備え、
前記第１の関数処理部は、前記関係性Ｒの適用により前記第２の情報処理装置へコミットする値を決定するコミット段階と、前記コミット段階でコミットした値を公開する公開段階とを実行し、前記コミット段階と、前記公開段階とで、前記値ｘ１、・・・、ｘｎから前記コミットする値に対応するそれぞれ異なる値を選択して前記第２の情報処理装置へ送信し、
前記第２の情報処理装置は、
前記第１の情報処理装置から送信された前記値に対して前記関数Ｆを適用する第２の関数処理部を備え、
前記第２の関数処理部は、前記関係性Ｒの適用により前記第１の情報処理装置がコミットした値に対応する第１の値を受信するコミット段階と、前記第１の情報処理装置がコミットした値を公開するための第２の値を受信する公開段階とを実行し、
前記関数処理部は、前記公開段階で、前記第１の値と前記第２の値とが異なり、かつ前記第１の値及び前記第２の値に前記関数Ｆを適用すると同じ結果になるかどうか判断する、情報処理システム。
（１３）
異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置へコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記関数Ｆを適用すると同じ結果になる値ｘ１、・・・、ｘｎを生成する生成ステップと、
前記関係性Ｒの適用により前記他の装置へコミットする値を決定するコミットステップと、
前記コミットステップでコミットした値を公開する公開ステップと、
を備え、
前記コミットステップと、前記公開ステップとで、前記値ｘ１、・・・、ｘｎから前記コミットする値に対応するそれぞれ異なる値が選択されて前記他の装置へ送信される、情報処理方法。
（１４）
異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置がコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記関係性Ｒの適用により前記他の装置がコミットした値に対応する第１の値を受信するコミットステップと、
前記他の装置がコミットした値を公開するための第２の値を受信する公開ステップと、
前記第１の値と前記第２の値とが異なり、かつ前記第１の値及び前記第２の値に前記関数Ｆを適用すると同じ結果になるかどうか判断する関数適用ステップと、
を備える、情報処理方法。
（１５）
コンピュータに、
異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置へコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記関数Ｆを適用すると同じ結果になる値ｘ１、・・・、ｘｎを生成する生成ステップと、
前記関係性Ｒの適用により前記他の装置へコミットする値を決定するコミットステップと、
前記コミットステップでコミットした値を公開する公開ステップと、
を実行させ、
前記コミットステップと、前記公開ステップとで、前記値ｘ１、・・・、ｘｎから前記コミットする値に対応するそれぞれ異なる値が選択されて前記他の装置へ送信される、コンピュータプログラム。
（１６）
コンピュータに、
異なる複数の値ｘ１、・・・、ｘｎ（ｎは２以上の整数）に対して同じ結果を算出できる関数Ｆ及び、前記値ｘ１、・・・、ｘｎ並びに他の装置がコミットする値との関係性Ｒを予め該他の装置との間で共有させた状態で、前記関係性Ｒの適用により前記他の装置がコミットした値に対応する第１の値を受信するコミットステップと、
前記他の装置がコミットした値を公開するための第２の値を受信する公開ステップと、
前記第１の値と前記第２の値とが異なり、かつ前記第１の値及び前記第２の値に前記関数Ｆを適用すると同じ結果になるかどうか判断する関数適用ステップと、
を実行させる、コンピュータプログラム。
【符号の説明】
【０１４６】
１    情報処理システム
１００、２００    情報処理装置
１１０、２１０    ビットコミットメント関数処理部
１２０、２２０    通信部
１３０、２３０    メモリ
【図１】
2014090235.tif 000012
【図２】
2014090235.tif 000013
【図３】
2014090235.tif 000014
【図４】
2014090235.tif 000015
【図５】
2014090235.tif 000016
【図６】
2014090235.tif 000017
【図７】
2014090235.tif 000018
【図８】
2014090235.tif 000019
【図９】
2014090235.tif 000020
【図１０】
2014090235.tif 000021
【図１１】
2014090235.tif 000022
【図１２】
2014090235.tif 000023