ビットコミットメント検証システム、ビットコミットメント装置、検証装置、ビットコミットメント検証方法、ビットコミットメント方法、検証方法、ビットコミットメントプログラム、検証プログラム
【課題】本発明は、開封情報をＧの元とし、他の暗号プロトコル中において、効率的に利用可能なビットコメント方法及びその装置を提供することを目的とする。
【解決手段】本発明のビットコミットメント検証システムは登録装置と、ビットコミットメント装置と、検証装置からなる。ビットコメント装置は、二つの群の生成元を用いて、コミットメント鍵ｃｋを生成する。ｇ，ｈ１及びｒｉとコミットする情報ｍｉからＣ＝Πｎｉ＝１ｇｍｉｈ１ｒｉを計算し、これをコミットメントとして出力する。開封情報Ｈ＝Πｎｉ＝１ｈ２ｒｉを算出する。検証装置は、等式ｅ（Ｃ／Πｎｉ＝１ｇｍｉ，ｈ２）＝ｅ（ｈ１，Ｈ）が成立するか否かを判定し、成立する場合には合格とし、成立しない場合には不合格とする。
【解決手段】本発明のビットコミットメント検証システムは登録装置と、ビットコミットメント装置と、検証装置からなる。ビットコメント装置は、二つの群の生成元を用いて、コミットメント鍵ｃｋを生成する。ｇ，ｈ１及びｒｉとコミットする情報ｍｉからＣ＝Πｎｉ＝１ｇｍｉｈ１ｒｉを計算し、これをコミットメントとして出力する。開封情報Ｈ＝Πｎｉ＝１ｈ２ｒｉを算出する。検証装置は、等式ｅ（Ｃ／Πｎｉ＝１ｇｍｉ，ｈ２）＝ｅ（ｈ１，Ｈ）が成立するか否かを判定し、成立する場合には合格とし、成立しない場合には不合格とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電気通信システムである情報をコミット（確約）し、検証するビットコミットメント検証システム、ビットコミットメント装置、検証装置、及びその方法に関する。
【背景技術】
【０００２】
ビットコミットメントは、ある時点で送信者がメッセージｍを保持していたことを、後々、受信者に納得させる方法である。例えば、Ａ，Ｂの二者が後出しを許さない公平なじゃんけんを行う方法を考える。Ａはまず紙に書いた自分の選択（「グー」、「チョキ」または「パー」）を金庫に入れて、鍵をかけ、金庫のみをＢに渡す。次に、Ｂは自分の選択をＡに告げる。ＡはＢの選択を確認した後に、鍵をＢに渡す。Ｂは受け取った鍵で金庫を開け、Ａの選択を確認し、じゃんけんの勝敗を確認する。この「金庫」や「鍵」に相当する機能を電子的に提供する方法がビットコミットメントである。
【０００３】
非特許文献１記載のビットコミットメント方法（いわゆる「Ｐｅｄｅｒｓｅｎのコミットメント」）について説明する。
【０００４】
ｑを大きな素数とし、Ｇを位数ｑの（乗法）群であって、離散対数問題が困難である群とする。
【０００５】
コミットメントする者Ａは、Ｇの異なる２つの生成元ｇ、ｈを無作為に選び、（Ｇ，ｑ，ｇ，ｈ）をコミットメント鍵とする。以下、Ｚｑを０以上ｑ−１以下の整数の集合とし、Ｚｑ＊をＺｑから０を除いた集合とする。コミットする情報をｍ∈Ｚｑとする。
【０００６】
コミットメントする者は、Ｚｑからｒを無作為に選択し、開封情報とする。
Ｃ＝ｇｍｈｒ∈Ｇ （１）
を計算し、Ｃをコミットメントとして検証者Ｂへ送る。また、情報ｍと開封情報ｒを秘密に保存する。
【０００７】
その後、Ａは、情報ｍ及び開封情報ｒを公開する。
Ｂは、コミットメント鍵（Ｇ，ｑ，ｇ，ｈ）と情報ｍと開封情報ｒから
ｇｍｈｒ＝Ｃ （２）
式（２）が成り立つか否か検証する。成り立つ場合には、Ｃを検証者Ｂへ送った時点から情報ｍに変更が加えられていないことが確認できる。成り立たない場合には、改竄等の可能性が考えられる。
【０００８】
コミットメントＣ＝ｇｍｈｒから情報ｍを知ることは情報理論的に不可能である。つまり、検証者Ｂは、コミットメントＣを受け取った時点では、情報ｍを知ることはできない。一方、コミットメントＣを二通りの（ｍ，ｒ）と（ｍ’，ｒ’）により生成することは離散対数ｌｏｇｇｈ∈Ｚｑを求めることと等価であり、離散対数問題の困難性を仮定すれば、一旦コミットされたＣは１通りの情報ｍ及び開封情報ｒを持ってのみ開封することができる。よって、Ａは、コミットメントＣを検証者Ｂへ送った後に、情報ｍを改竄することはできない。
【０００９】
ビットコミットメントは暗号プロトコルと密接な関係を持っている。例えば、ゼロ知識証明、マルチパーティ計算、電子マネー、電子投票、グループ署名等に用いられている。
【非特許文献１】Torben P. Pedersen, "Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing", Advances in Cryptology - CRYPTO ’91, Springer Berlin / Heidelberg, 1992, Volume 576/1992, p.129-140
【発明の開示】
【発明が解決しようとする課題】
【００１０】
暗号プロトコル中でビットコミットメントが使われる場合、コミットメント作成者が、開封情報ｒを実際に公開することなく、正しい開封情報を保持している事実のみを証明する必要が生じることがある。例えば、コミットされたメッセージ間の様々な関係を示す非対話ゼロ知識証明を用いると、開封情報ｒを秘匿したまま、ｒを保持している、つまり、コミットメントＣを開封できるという事実を第三者に納得させることができる。例えば、Jens Groth, Amit Sahai, "Efficient Non-interactive Proof Systems for Bilinear Groups", Advances in Cryptology - EUROCRYPT 2008, Springer Berlin / Heidelberg, June 3,2008, Volume 4965/2008, p415-432（以下「参考文献１」という）には、開封情報ｒがＧの元であれば、ペアリングを利用して効率的な非対話ゼロ知識証明が構成できることが記載されている。参考文献１のように、開封情報ｒがＺｑの元である場合についての非対話ゼロ知識証明は理想的なランダムオラクルモデルにおいては効率的な構成が知られているが、理想化された関数を仮定しないモデルにおいては、非効率的な構成しか知られていない。非特許文献１記載のビットコメント方法は、開封情報（ｍ，ｒ）がＧの元となっていないため、Ｇの元を利用して効率的にゼロ知識証明や、グループ署名等を構成することができない。
【００１１】
本発明は、開封情報をＧの元とし、他の暗号プロトコル中において、効率的に利用可能なビットコメント方法及びその装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明のビットコミットメント検証システムは登録装置と、ビットコミットメント装置と、検証装置からなる。ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、公開パラメータｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）とする。ビットコメント装置は、Ｇ１から生成元ｇ及びｈ１を、Ｇ２から生成元ｈ２を、無作為に選択し、これらの生成元を用いてコミットメント鍵ｃｋを生成する。Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、情報ｍの個数を表す）を生成する。公開パラメータｖ及び乱数ｒｉを記憶し、特に乱数ｒｉは秘密に記憶する。ｇ，ｈ１及びｒｉとコミットする情報ｍｉからＣ＝Πｎｉ＝１ｇｍｉｈ１ｒｉを計算し、これをコミットメントとして出力する。開封情報Ｈ＝Πｎｉ＝１ｈ２ｒｉを算出する。検証装置は、コミットメント鍵ｃｋ、情報Ｍ、開封情報Ｈ及びＣを記憶する。等式ｅ（Ｃ／Πｎｉ＝１ｇｍｉ，ｈ２）＝ｅ（ｈ１，Ｈ）が成立するか否かを判定し、成立する場合には合格とし、成立しない場合には不合格とする。登録装置は、公開パラメータｖ及びコミットメント鍵ｃｋを記憶する記憶部を有する。ビットコミットメント装置は、登録装置から公開パラメータｖを受け取り、コミットメント鍵ｃｋを登録装置へ、コミットメントＣを検証装置へ、送り、コミットメントＣを送ると同時または送った後に、情報ｍを含む情報Ｍ及び開封情報Ｈを検証装置へ送る。検証装置は、登録装置からコミットメント鍵ｃｋを、ビットコミットメント装置からコミットメントＣ、情報Ｍ及び開封情報Ｈを、受け取る。
【発明の効果】
【００１３】
本発明のビットコミットメント検証方法及び装置によれば、ビットコミットメント方法を、効率的に様々な他の暗号プロトコルの構成要素として利用できる。
【００１４】
例えば、本発明のビットコミットメント方法を用いた場合、開封情報がＧの元であるため、ペアリングを利用した効率的な非対話ゼロ知識証明を構成することができる。
【発明を実施するための最良の形態】
【００１５】
ここで、本発明の実施例について説明する。
【実施例１】
【００１６】
［ビットコミットメント検証システム１］
図１は、ビットコミットメント検証システム１の構成例を示す図である。図２は、ビットコミットメント検証システム１のシーケンス図の一例を示す図である。ビットコミットメント検証システム１は、登録装置３００と、ビットコミットメント装置１００と、検証装置２００からなる。
【００１７】
ｑを大きな素数とし、Ｇ１，Ｇ２，ＧＴを位数ｑの群とし、ｅを効率的に計算可能なバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、ｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）を公開パラメータとする。ここで、Ｇ１，Ｇ２は、任意のｈ１ｒからｈ２ｒを計算できるのはｒを知っている場合に限られるという性質を有する群である。なお、ｇａとは、ｇ∈Ｇに対し、群Ｇで定義される演算をａ回行うことを意味する。バイリニアマップとしては、例えば、ＷｅｉｌペアリングやＴａｔｅペアリング等が考えられる。
【００１８】
ビットコミットメント装置１００は、コミットメントＣを生成するために、登録装置３００に対して、公開パラメータｖを要求する（ｓ１０）。登録装置３００は、ｖをビットコミットメント装置１００へ送る（ｓ１２）。ビットコミットメント装置１００は、公開パラメータｖからコミットメント鍵ｃｋを生成し、登録装置３００へ送る（ｓ１４）。登録装置３００は、コミットメント鍵ｃｋを登録及び公開する（ｓ１６）。なお、送るたびに公開パラメータを要求しなくとも、記憶している公開パラメータを利用してコミットメント鍵を生成してもよい。さらに、情報ｍ、コミットメント鍵ｃｋ及び乱数ｒを用いて、コミットメントＣを生成する。ビットコミットメント装置１００は、コミットメントＣを検証装置へ送る（ｓ１８）。送ると同時または送った後に、乱数ｒを用いて算出した開封情報Ｈと、情報ｍを含む情報Ｍを前記検証装置へ送る（ｓ１９）。
【００１９】
検証装置２００は、コミットメントＣに対応するコミットメント鍵ｃｋを登録装置３００へ要求する（ｓ２０）。登録装置３００は、コミットメント鍵ｃｋを検証装置２００へ送る（ｓ２２）。検証装置２００は、コミットメントＣ、情報ｍ、コミットメント鍵ｃｋを用いて、改竄及び成りすまし等が行われていないか検証し（ｓ２４）、確かにコミットメントＣが送られてきた時点から情報ｍが改竄等されていないことを確認する。以下、各装置及び各処理について詳細を説明する。
【００２０】
［登録装置３００］
登録装置３００は、公開パラメータｖを登録及び公開している。例えば、登録装置３００は、信頼できる第三者等が管理し、通信部３０１と、記憶部３０３と、制御部３０５を有する。登録装置３００は、通信部３０１を介して、ビットコミットメント装置及び検証装置と通信する。以下、特に記述しなくとも、ビットコメント装置１００及び検証装置２００と通信する際には、通信部３０１を介して行われるものとする。通信部３０１は、例えば、ＬＡＮアダプタ等により構成され、ＬＡＮやインターネット等からなる通信回線と接続される。但し、必ずしも通信部を有さずともよく、例えば、キーボード等の入力装置から公開パラメータを入力してもよいし、また、ＵＳＢメモリ等の可搬媒体に公開パラメータを記憶し、それを入力してもよい。以下、同様に各装置（ビットコメント装置及び検証装置）は送信部１０１、２０１を有さずともよく、装置間のデータの入出力は、通信以外の方法であってもよい。記憶部３０３は、公開パラメータ、コミットメント鍵等を記憶する。なお、上記「登録」とは、記憶部３０３に記憶することを意味してもよい。また、「公開」とは、利用者の求めに応じて、情報（例えば、公開パラメータ）を閲覧可能、または、取得可能とすることを意味する。制御部３０５は、各処理を制御する。
【００２１】
［ビットコミットメント装置１００］
図３は、ビットコミットメント装置１００の構成例を示す図である。図４は、ビットコミットメント装置１００の処理フローの一例を示す図である。ビットコミットメント装置１００は、通信部１０１と、記憶部１０３と、制御部１０５と、コミットメント鍵生成部１２０と、乱数生成部１３０と、開封情報生成部１４０と、コミットメント生成部１５０を有する。
【００２２】
＜制御部１０５、通信部１０１及び記憶部１０３＞
本実施例のビットコミットメント装置１００は、制御部１０５の制御のもと各処理を実行する。ビットコミットメント装置１００は、登録装置３００から公開パラメータｖを受け取る。例えば、通信部１０１は、登録装置３００及び検証装置２００と通信を行い、登録装置３００から公開パラメータｖを受信する（ｓ１０１）。以下、特に記述しなくとも、登録装置３００及び検証装置２００と通信する際には、通信部１０１を介して行われるものとする。
【００２３】
受信した公開パラメータｖを記憶部１０３に記憶する（ｓ１０３）。また、特に示さない限り、入出力される各データや演算過程の各データは、逐一、記憶部１０３に格納・読み出され、各演算処理が進められる。但し、必ずしも記憶部１０３に記憶しなければならないわけではなく、各部間で直接データを受け渡してもよい。
【００２４】
＜コミットメント鍵生成部１２０＞
コミットメント鍵生成部１２０は、Ｇ１から生成元ｇ及びｈ１を、Ｇ２から生成元ｈ２を、無作為に選択し、これらの生成元を用いてコミットメント鍵ｃｋを生成する（ｓ１２０）。例えば、コミットメント鍵ｃｋ＝（ｖ，ｇ，ｈ１，ｈ２）として生成する。コミットメント鍵生成部１２０は、通信部１０１を介して、または、通信部１０１及び記憶部１０３を介して公開パラメータｖが入力され、生成元ｈ２を開封情報算出部１４０へ、生成元ｇ及びｈ１をコミットメント生成部１５０へ出力する。また、通信部１０１を介して、コミットメント鍵ｃｋを登録装置３００へ送る。なお、コミットメント鍵ｃｋには、利用した公開パラメータを表示する情報ｉ等を含めｐｋ＝（ｉ，ｇ，ｈ１，ｈ２）としてもよい。この場合には、以下で説明する検証装置２００は、情報ｉに基づいて、登録装置３００に対応する公開パラメータｖｉを要求する。また、登録装置３００の記憶している公開パラメータの中から対応する公開パラメータを特定することができる場合には、コミットメント鍵ｃｋに公開パラメータｖや、公開パラメータを表示する情報ｉ等を含まなくともよく、検証装置２００は、情報Ｍ及び開封情報Ｈを受け付けた際に、登録装置３００に公開パラメータｖを要求する。
【００２５】
＜乱数生成部１３０及び開封情報算出部１４０＞
乱数生成部１３０は、Ｚｑに属する乱数ｒを生成する（ｓ１３０）。乱数ｒを開封情報算出部１４０及びコミットメント生成部１５０へ出力する。記憶部１０３は、乱数ｒが秘密に記憶される（ｓ１３５）。開封情報算出部１４０は、開封情報Ｈ＝ｈ２ｒを算出する（ｓ１４０）。これにより開封情報Ｈが離散対数問題が困難な元となる。開放情報算出部１４０は、Ｇ２の生成元ｈ２及び乱数ｒが入力され、開封情報Ｈ＝ｈ２ｒを出力する。
【００２６】
＜コミットメント生成部１５０＞
コミットメント生成部１５０は、ｇ，ｈ１及びｒとコミットする情報ｍからＣ＝ｇｍｈ１ｒを計算し、これをコミットメントとして出力する（ｓ１５０）。コミットメント生成部１５０は、乱数生成部１３０から乱数ｒを、コミットメント鍵生成部１２０からＧ１の生成元ｇ、ｈ１を、さらに情報ｍを入力され、コミットメントＣを出力する。なお、情報ｍ∈Ｚｑであり、補助記憶装置やメモリ上のデータ等、もしくは、入力インターフェース、キーボード、マウス等から入力されるデータである。
【００２７】
ビットコミットメント装置１００は、コミットメント鍵ｃｋを登録装置３００へ、コミットメントＣを検証装置２００へ、送る（ｓ１５３）。送ると同時または送った後に、情報ｍを含む情報Ｍ及び開封情報Ｈを検証装置２００へ送る（ｓ１５５）。なお、情報ｍを含む情報Ｍとは、例えば、情報ｍ自体（つまり、Ｍ＝ｍ）であってもよいし、ｇｍであってもよい（つまり、Ｍ＝ｇｍ）。情報Ｍ＝ｇｍとする場合には、図示しない情報変更部を設け、情報変更部は生成元ｇ及び情報ｍを入力され、Ｍ＝ｇｍを算出し、Ｍを出力する構成としてもよい。なお、Ｍ＝ｇｍの場合には、離散対数問題の困難性により、検証装置２００は、Ｍを受け取った場合にも、ｍについて知ることはできない。このとき、ビットコメント装置１００は、情報ｍを秘匿したまま、コミットメントを開封できることを検証装置２００に納得させることができる。非特許文献１同様、一旦コミットされたＣは１通りの情報Ｍ及び開封情報Ｈを持ってのみ開封することができる。よって、ビットコミットメント装置１００は、コミットメントＣを検証装置２００へ送ってから（ｓ１５３）、情報Ｍ及び開封情報Ｈを検証装置２００へ送る（ｓ１５５）までの間に、情報Ｍを改竄することはできない。なお、開封情報の算出（ｓ１４０）とコミットメントの生成（ｓ１５０）は、どちらが先に行われてもよいが、コミットメントＣを先に送らなければ、ある時点で送信者がメッセージｍを保持していたことを、後々、受信者に納得させるという効果を得ることはできない。
【００２８】
［検証装置２００］
図５は、検証装置２００の構成例を示す。図６は、検証装置１００の処理フローの一例を示す図である。検証装置２００は、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２０を有する。
【００２９】
＜制御部２０５、通信部２０１及び記憶部２０３＞
本実施例の検証装置２００は、制御部２０５の制御のもと各処理を実行する。検証装置２００は、登録装置３００からコミットメント鍵ｃｋを、ビットコミットメント装置からコミットメントＣ、情報Ｍ及び開封情報Ｈを、受け取る。例えば、通信部２０１は、登録装置３００及び検証装置１００と通信を行う。登録装置３００からコミットメント鍵ｃｋを受信する（ｓ２０１）。ビットコミットメント装置１００からコミットメントＣを受信し（ｓ２０２ａ）、それと同時またはその後、ビットコミットメント装置１００から情報Ｍ及び開封情報Ｈを受信する（ｓ２０２ｂ）。記憶部２０３は、コミットメントＣ、コミットメント鍵ｃｋ、情報Ｍ及び開封情報Ｈが記憶される（ｓ２０３）。
【００３０】
＜判定部２２０＞
判定部２２０は、以下の等式（１１）が成立するか否かを判定する（ｓ２２０）。
ｅ（Ｃ／ｇｍ，ｈ２）＝ｅ（ｈ１，Ｈ） （１１）
成立する場合には合格とし（ｓ２２３）、成立しない場合には不合格とする（ｓ２２５）。判定部２２０は、通信部２０１を介して、または、通信部２０１及び記憶部２０３を介して、コミットメント鍵ｃｋ、コミットメントＣ、開封情報Ｈ及び情報Ｍ（ｍまたはｇｍ）が入力される。
【００３１】
以下、検証方法を説明する。式（１１）は、Ｃ＝ｇｍｈ１ｒ、Ｈ＝ｈ２ｒより、
ｅ（ｇｍｈ１ｒ／ｇｍ，ｈ２）＝ｅ（ｈ１，ｈ２ｒ） （１１）’
と表すことができる。ペアリングの性質により、ｍ及びｒが正しいときのみ、等式が成り立ち、従来技術同様、検証装置２００は、コミットメントＣを受け取った時点では、情報ｍを知ることはできない。一方、ビットコミットメント装置１００は、コミットメントＣを検証装置２００へ送った後に、情報ｍを改竄することはできない。また、情報Ｍをｇｍとした場合には、乱数ｒだけではなく、情報ｍを秘匿したまま、コミットメントＣを開封できることを第三者に納得させることできる。
【００３２】
このような構成とすることによって、ビットコミットメント方法を、効率的に様々な他の暗号プロトコルの構成要素として利用できる。例えば、本発明のビットコミットメント方法を用いた場合、開封情報Ｈ＝ｈ２ｒが、離散対数問題が困難な群Ｇの元であるため、ペアリングを利用した効率的な非対話ゼロ知識証明を構成することができる。なお、群Ｇとして、例えば、楕円曲線が作る群等を用いることができる。
【００３３】
＜ハードウェア構成＞
図７は、本実施例におけるビットコミットメント装置１００のハードウェア構成を例示したブロック図である。検証装置２００及び登録装置３００も同様の構成を有する。
【００３４】
図７に例示するように、この例のビットコミットメント装置１００、検証装置２００、登録装置３００は、それぞれＣＰＵ（Central Processing Unit）１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ（Read Only Memory）１５、ＲＡＭ（Random Access Memory）１６及びバス１７を有している。
【００３５】
この例のＣＰＵ１１は、制御部１１ａ、演算部１１ｂ及びレジスタ１１ｃを有し、レジスタ１１ｃに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１２は、データが入力される入力インターフェース、キーボード、マウス等であり、出力部１３は、データが出力される出力インターフェース等である。補助記憶装置１４は、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、ビットコミットメント装置１００、検証装置２００及び登録装置３００としてコンピュータを機能させるためのプログラムが格納されるプログラム領域１４ａ及び各種データが格納されるデータ領域１４ｂを有している。また、ＲＡＭ１６は、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等であり、上記のプログラムが格納されるプログラム領域１６ａ及び各種データが格納されるデータ領域１６ｂを有している。また、バス１７は、ＣＰＵ１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ１５及びＲＡＭ１６を通信可能に接続する。
【００３６】
なお、このようなハードウェアの具体例としては、例えば、パーソナルコンピュータの他、サーバ装置やワークステーション等を例示できる。
【００３７】
＜プログラム構成＞
上述のように、プログラム領域１４ａ，１６ａには、本実施例のビットコミットメント装置１００、検証装置２００、登録装置３００の各処理を実行するための各プログラムが格納される。ビットコミットメントプログラム、検証プログラム及び登録プログラムを構成する各プログラムは、単一のプログラム列として記載されていてもよく、また、少なくとも一部のプログラムが別個のモジュールとしてライブラリに格納されていてもよい。また、各プログラムが単体でそれぞれの機能を実現してもよいし、各プログラムがさらに他のライブラリを読み出して各機能を実現するものでもよい。
【００３８】
＜ハードウェアとプログラムとの協働＞
ＣＰＵ１１（図７）は、読み込まれたＯＳ（Operating System）プログラムに従い、補助記憶装置１４のプログラム領域１４ａに格納されている上述のプログラムをＲＡＭ１６のプログラム領域１６ａに書き込む。同様にＣＰＵ１１は、補助記憶装置１４のデータ領域１４ｂに格納されている各種データを、ＲＡＭ１６のデータ領域１６ｂに書き込む。そして、このプログラムやデータが書き込まれたＲＡＭ１６上のアドレスがＣＰＵ１１のレジスタ１１ｃに格納される。ＣＰＵ１１の制御部１１ａは、レジスタ１１ｃに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１６上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１１ｂに順次実行させ、その演算結果をレジスタ１１ｃに格納していく。
【００３９】
図３、５は、このようにＣＰＵ１１に上述のプログラムが読み込まれて実行されることにより構成されるビットコミットメント装置１００、検証装置２００の機能構成を例示したブロック図である。
【００４０】
ここで、記憶部１０３及び２０３は、補助記憶装置１４、ＲＡＭ１６、レジスタ１１ｃ、その他のバッファメモリやキャッシュメモリ等の何れか、あるいはこれらを併用した記憶領域に相当する。また、通信部１０１と、記憶部１０３と、制御部１０５と、コミットメント鍵生成部１２０と、乱数生成部１３０と、開封情報生成部１４０と、コミットメント生成部１５０は、ＣＰＵ１１にビットコミットメントプログラムを実行させることにより構成されるものである。また、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２０は、ＣＰＵ１１に検証プログラムを実行させることにより構成されるものである。
【００４１】
また、本形態のビットコミットメント装置１００、検証装置２００及び登録装置３００は、各制御部１０５、２０５及び３０５の制御のもと各処理を実行する。
【実施例２】
【００４２】
実施例１と異なる部分についてのみ説明する。実施例２記載のビットコミットメント検証システム１０００は、実施例１で示した構成を複数並列に処理し、等式の両辺を乗算にてまとめることにより、複数の情報ｍｉ（但し、１≦ｉ≦ｎであり、ｎは情報の個数を表す）に対するビットコミットメントＣにも対応することができる。また、各情報ｍ１，ｍ２，…，ｍｎのビット長は同一であっても、異なってもよい。
【００４３】
［ビットコミットメント検証システム１０００］
ビットコミットメント検証システム１０００は、登録装置３００と、ビットコミットメント装置１１００と、検証装置１２００からなる。
【００４４】
ビットコミットメント装置１１００は、複数の情報ｍｉに対するコミットメントＣを生成するために、登録装置３００に対して、公開パラメータｖを要求する。登録装置３００は、ｖをビットコミットメント装置１１００へ送る。ビットコミットメント装置１１００は、公開パラメータｖからコミットメント鍵ｃｋを生成し、登録装置３００へ送る。登録装置３００は、コミットメント鍵ｃｋを登録及び公開する。さらに、複数の情報ｍｉ、コミットメント鍵ｃｋ及び複数の乱数ｒｉを用いて、コミットメントＣを生成する。ビットコミットメント装置１１００は、コミットメントＣを検証装置１２００へ送る。送ると同時または送った後に、乱数ｒｉを用いて、開封情報Ｈを生成し、情報ｍｉを含む情報Ｍ及び開封情報Ｈを検証装置１２００へ送る。
【００４５】
検証装置１２００は、コミットメントＣに対応するコミットメント鍵ｃｋを登録装置３００へ要求する。登録装置３００は、コミットメント鍵ｃｋを検証装置１２００へ送る。検証装置１２００は、コミットメントＣ、情報Ｍ、コミットメント鍵ｃｋを用いて、改竄及び成りすまし等が行われていないか検証し、確かにコミットメントＣが送られてきた時点から情報ｍｉが改竄等されていないことを確認する。以下、各装置及び各処理について詳細を説明する。
【００４６】
［ビットコミットメント装置１１００］
ビットコミットメント装置１１００は、通信部１０１と、記憶部１１０３と、制御部１０５と、コミットメント鍵生成部１２０と、乱数生成部１１３０と、開封情報生成部１１４０と、コミットメント生成部１１５０を有する。
【００４７】
＜乱数生成部１１３０、記憶部１１０３及び開封情報算出部１１４０＞
乱数生成部１１３０は、Ｚｑに属する複数の乱数ｒｉを生成する。乱数ｒｉは、開封情報算出部１１４０及びコミットメント生成部１１５０へ出力される。記憶部１１０３は、乱数ｒｉは秘密に記憶される。開封情報算出部１１４０は、開封情報Ｈ＝Πｎｉ＝１ｈ２ｒｉを算出する（但し、ｒｉとは、上記乱数ｒｉのことを意味する）。開封情報算出部１１４０は、コミットメント鍵生成部１２０から生成元ｈ２を、乱数生成部１３０から乱数ｒｉを入力され、開封情報Ｈ＝Πｎｉ＝１ｈ２ｒｉを出力する。
【００４８】
＜コミットメント生成部１１５０＞
コミットメント生成部１１５０は、ｇ，ｈ１及びｒｉとコミットする情報ｍｉからＣ＝Πｎｉ＝１ｇｍｉｈ１ｒｉを計算し、これをコミットメントとして出力する（ｓ１５０）。コミットメント生成部１１５０は、コミットメント鍵生成部１２０からＧ１の生成元ｇ、ｈ１を、乱数生成部１３０から乱数ｒｉを、及び情報ｍｉを入力され、コミットメントＣを出力する。なお、情報ｍｉ∈Ｚｑである。
【００４９】
ビットコミットメント装置１０００は、コミットメント鍵ｃｋを登録装置３００へ、コミットメントＣを検証装置１２００へ、送る。送ると同時または送った後に、情報ｍｉを含む情報Ｍ及び開封情報Ｈを検証装置１２００へ送る。なお、情報ｍｉを含む情報Ｍとは、例えば、情報ｍｉ自体（つまり、Ｍ＝（ｍ１，ｍ２，…，ｍｎ）であってもよいし、ｇｍｉであってもよい（つまり、Ｍ＝（ｇｍ１，ｇｍ２，…，ｇｍｎ）。また、ｇｍｉの総積であってもよい（つまり、Ｍ＝Πｎｉ＝１ｇｍｉ）。
【００５０】
このような構成とすることによって、実施例１と同様の効果を得ることができる。さらに、複数の情報ｍｉ（１≦ｉ≦ｎ）に対してビットコミットメントＣを生成することができるため、実施例１の方法により複数の情報に対し、複数のビットコミットメントを作成するのに比べ、処理を軽減することができる。また、ビットコミットメントの情報量、通信量を小さくすることができる。
【００５１】
［検証装置１２００］
検証装置１２００は、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２０を有する。
【００５２】
＜判定部２２０＞
判定部２２０は、以下の等式（２１）が成立するか否かを判定する（ｓ２２０）。
ｅ（Ｃ／Πｎｉ＝１ｇｍｉ，ｈ２）＝ｅ（ｈ１，Ｈ） （２１）
成立する場合には合格とし（ｓ２２３）、成立しない場合には不合格とする（ｓ２２５）。
【００５３】
以下、検証方法を説明する。式（１１）は、Ｃ＝Πｇｍｉｈ１ｒｉ、Ｈ＝Πｎｉ＝１ｈ２ｒｉより、
ｅ（Πｎｉ＝１ｇｍｉｈ１ｒｉ／Πｎｉ＝１ｇｍｉ，ｈ２）＝ｅ（ｈ１，Πｎｉ＝１ｈ２ｒｉ） (21)'
と表すことができる。ペアリングの性質により、ｍｉ及びｒｉの全てが正しいときのみ、等式が成り立ち、実施例１と同様の効果をえることができる。さらに、等式の両辺を乗算にてまとめることにより、実施例１の方法により複数のコミットメントを検証するのに比べ、処理を軽減することができる。
【図面の簡単な説明】
【００５４】
【図１】ビットコミットメント検証システム１の構成例を示す図。
【図２】ビットコミットメント検証システム１のシーケンス図の一例を示す図。
【図３】ビットコミットメント装置１００の構成例を示す図。
【図４】ビットコミットメント装置１００の処理フローの一例を示す図。
【図５】検証装置２００の構成例を示す図。
【図６】検証装置２００の処理フローの一例を示す図。
【図７】実施例１におけるビットコミットメント装置１００のハードウェア構成を例示したブロック図。
【符号の説明】
【００５５】
１ ビットコミットメント検証システム
１００ ビットコミットメント装置 ２００ 検証装置
３００ 登録装置
１０１、２０１ 通信部 １０３、２０３ 記憶部
１０５、２０５ 制御部 １２０ コミットメント鍵生成部
１３０ 乱数生成部 １４０ 開封情報算出部
１５０ ビットコミットメント生成部 ２２０ 判定部
【技術分野】
【０００１】
本発明は、電気通信システムである情報をコミット（確約）し、検証するビットコミットメント検証システム、ビットコミットメント装置、検証装置、及びその方法に関する。
【背景技術】
【０００２】
ビットコミットメントは、ある時点で送信者がメッセージｍを保持していたことを、後々、受信者に納得させる方法である。例えば、Ａ，Ｂの二者が後出しを許さない公平なじゃんけんを行う方法を考える。Ａはまず紙に書いた自分の選択（「グー」、「チョキ」または「パー」）を金庫に入れて、鍵をかけ、金庫のみをＢに渡す。次に、Ｂは自分の選択をＡに告げる。ＡはＢの選択を確認した後に、鍵をＢに渡す。Ｂは受け取った鍵で金庫を開け、Ａの選択を確認し、じゃんけんの勝敗を確認する。この「金庫」や「鍵」に相当する機能を電子的に提供する方法がビットコミットメントである。
【０００３】
非特許文献１記載のビットコミットメント方法（いわゆる「Ｐｅｄｅｒｓｅｎのコミットメント」）について説明する。
【０００４】
ｑを大きな素数とし、Ｇを位数ｑの（乗法）群であって、離散対数問題が困難である群とする。
【０００５】
コミットメントする者Ａは、Ｇの異なる２つの生成元ｇ、ｈを無作為に選び、（Ｇ，ｑ，ｇ，ｈ）をコミットメント鍵とする。以下、Ｚｑを０以上ｑ−１以下の整数の集合とし、Ｚｑ＊をＺｑから０を除いた集合とする。コミットする情報をｍ∈Ｚｑとする。
【０００６】
コミットメントする者は、Ｚｑからｒを無作為に選択し、開封情報とする。
Ｃ＝ｇｍｈｒ∈Ｇ （１）
を計算し、Ｃをコミットメントとして検証者Ｂへ送る。また、情報ｍと開封情報ｒを秘密に保存する。
【０００７】
その後、Ａは、情報ｍ及び開封情報ｒを公開する。
Ｂは、コミットメント鍵（Ｇ，ｑ，ｇ，ｈ）と情報ｍと開封情報ｒから
ｇｍｈｒ＝Ｃ （２）
式（２）が成り立つか否か検証する。成り立つ場合には、Ｃを検証者Ｂへ送った時点から情報ｍに変更が加えられていないことが確認できる。成り立たない場合には、改竄等の可能性が考えられる。
【０００８】
コミットメントＣ＝ｇｍｈｒから情報ｍを知ることは情報理論的に不可能である。つまり、検証者Ｂは、コミットメントＣを受け取った時点では、情報ｍを知ることはできない。一方、コミットメントＣを二通りの（ｍ，ｒ）と（ｍ’，ｒ’）により生成することは離散対数ｌｏｇｇｈ∈Ｚｑを求めることと等価であり、離散対数問題の困難性を仮定すれば、一旦コミットされたＣは１通りの情報ｍ及び開封情報ｒを持ってのみ開封することができる。よって、Ａは、コミットメントＣを検証者Ｂへ送った後に、情報ｍを改竄することはできない。
【０００９】
ビットコミットメントは暗号プロトコルと密接な関係を持っている。例えば、ゼロ知識証明、マルチパーティ計算、電子マネー、電子投票、グループ署名等に用いられている。
【非特許文献１】Torben P. Pedersen, "Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing", Advances in Cryptology - CRYPTO ’91, Springer Berlin / Heidelberg, 1992, Volume 576/1992, p.129-140
【発明の開示】
【発明が解決しようとする課題】
【００１０】
暗号プロトコル中でビットコミットメントが使われる場合、コミットメント作成者が、開封情報ｒを実際に公開することなく、正しい開封情報を保持している事実のみを証明する必要が生じることがある。例えば、コミットされたメッセージ間の様々な関係を示す非対話ゼロ知識証明を用いると、開封情報ｒを秘匿したまま、ｒを保持している、つまり、コミットメントＣを開封できるという事実を第三者に納得させることができる。例えば、Jens Groth, Amit Sahai, "Efficient Non-interactive Proof Systems for Bilinear Groups", Advances in Cryptology - EUROCRYPT 2008, Springer Berlin / Heidelberg, June 3,2008, Volume 4965/2008, p415-432（以下「参考文献１」という）には、開封情報ｒがＧの元であれば、ペアリングを利用して効率的な非対話ゼロ知識証明が構成できることが記載されている。参考文献１のように、開封情報ｒがＺｑの元である場合についての非対話ゼロ知識証明は理想的なランダムオラクルモデルにおいては効率的な構成が知られているが、理想化された関数を仮定しないモデルにおいては、非効率的な構成しか知られていない。非特許文献１記載のビットコメント方法は、開封情報（ｍ，ｒ）がＧの元となっていないため、Ｇの元を利用して効率的にゼロ知識証明や、グループ署名等を構成することができない。
【００１１】
本発明は、開封情報をＧの元とし、他の暗号プロトコル中において、効率的に利用可能なビットコメント方法及びその装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明のビットコミットメント検証システムは登録装置と、ビットコミットメント装置と、検証装置からなる。ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、公開パラメータｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）とする。ビットコメント装置は、Ｇ１から生成元ｇ及びｈ１を、Ｇ２から生成元ｈ２を、無作為に選択し、これらの生成元を用いてコミットメント鍵ｃｋを生成する。Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、情報ｍの個数を表す）を生成する。公開パラメータｖ及び乱数ｒｉを記憶し、特に乱数ｒｉは秘密に記憶する。ｇ，ｈ１及びｒｉとコミットする情報ｍｉからＣ＝Πｎｉ＝１ｇｍｉｈ１ｒｉを計算し、これをコミットメントとして出力する。開封情報Ｈ＝Πｎｉ＝１ｈ２ｒｉを算出する。検証装置は、コミットメント鍵ｃｋ、情報Ｍ、開封情報Ｈ及びＣを記憶する。等式ｅ（Ｃ／Πｎｉ＝１ｇｍｉ，ｈ２）＝ｅ（ｈ１，Ｈ）が成立するか否かを判定し、成立する場合には合格とし、成立しない場合には不合格とする。登録装置は、公開パラメータｖ及びコミットメント鍵ｃｋを記憶する記憶部を有する。ビットコミットメント装置は、登録装置から公開パラメータｖを受け取り、コミットメント鍵ｃｋを登録装置へ、コミットメントＣを検証装置へ、送り、コミットメントＣを送ると同時または送った後に、情報ｍを含む情報Ｍ及び開封情報Ｈを検証装置へ送る。検証装置は、登録装置からコミットメント鍵ｃｋを、ビットコミットメント装置からコミットメントＣ、情報Ｍ及び開封情報Ｈを、受け取る。
【発明の効果】
【００１３】
本発明のビットコミットメント検証方法及び装置によれば、ビットコミットメント方法を、効率的に様々な他の暗号プロトコルの構成要素として利用できる。
【００１４】
例えば、本発明のビットコミットメント方法を用いた場合、開封情報がＧの元であるため、ペアリングを利用した効率的な非対話ゼロ知識証明を構成することができる。
【発明を実施するための最良の形態】
【００１５】
ここで、本発明の実施例について説明する。
【実施例１】
【００１６】
［ビットコミットメント検証システム１］
図１は、ビットコミットメント検証システム１の構成例を示す図である。図２は、ビットコミットメント検証システム１のシーケンス図の一例を示す図である。ビットコミットメント検証システム１は、登録装置３００と、ビットコミットメント装置１００と、検証装置２００からなる。
【００１７】
ｑを大きな素数とし、Ｇ１，Ｇ２，ＧＴを位数ｑの群とし、ｅを効率的に計算可能なバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、ｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）を公開パラメータとする。ここで、Ｇ１，Ｇ２は、任意のｈ１ｒからｈ２ｒを計算できるのはｒを知っている場合に限られるという性質を有する群である。なお、ｇａとは、ｇ∈Ｇに対し、群Ｇで定義される演算をａ回行うことを意味する。バイリニアマップとしては、例えば、ＷｅｉｌペアリングやＴａｔｅペアリング等が考えられる。
【００１８】
ビットコミットメント装置１００は、コミットメントＣを生成するために、登録装置３００に対して、公開パラメータｖを要求する（ｓ１０）。登録装置３００は、ｖをビットコミットメント装置１００へ送る（ｓ１２）。ビットコミットメント装置１００は、公開パラメータｖからコミットメント鍵ｃｋを生成し、登録装置３００へ送る（ｓ１４）。登録装置３００は、コミットメント鍵ｃｋを登録及び公開する（ｓ１６）。なお、送るたびに公開パラメータを要求しなくとも、記憶している公開パラメータを利用してコミットメント鍵を生成してもよい。さらに、情報ｍ、コミットメント鍵ｃｋ及び乱数ｒを用いて、コミットメントＣを生成する。ビットコミットメント装置１００は、コミットメントＣを検証装置へ送る（ｓ１８）。送ると同時または送った後に、乱数ｒを用いて算出した開封情報Ｈと、情報ｍを含む情報Ｍを前記検証装置へ送る（ｓ１９）。
【００１９】
検証装置２００は、コミットメントＣに対応するコミットメント鍵ｃｋを登録装置３００へ要求する（ｓ２０）。登録装置３００は、コミットメント鍵ｃｋを検証装置２００へ送る（ｓ２２）。検証装置２００は、コミットメントＣ、情報ｍ、コミットメント鍵ｃｋを用いて、改竄及び成りすまし等が行われていないか検証し（ｓ２４）、確かにコミットメントＣが送られてきた時点から情報ｍが改竄等されていないことを確認する。以下、各装置及び各処理について詳細を説明する。
【００２０】
［登録装置３００］
登録装置３００は、公開パラメータｖを登録及び公開している。例えば、登録装置３００は、信頼できる第三者等が管理し、通信部３０１と、記憶部３０３と、制御部３０５を有する。登録装置３００は、通信部３０１を介して、ビットコミットメント装置及び検証装置と通信する。以下、特に記述しなくとも、ビットコメント装置１００及び検証装置２００と通信する際には、通信部３０１を介して行われるものとする。通信部３０１は、例えば、ＬＡＮアダプタ等により構成され、ＬＡＮやインターネット等からなる通信回線と接続される。但し、必ずしも通信部を有さずともよく、例えば、キーボード等の入力装置から公開パラメータを入力してもよいし、また、ＵＳＢメモリ等の可搬媒体に公開パラメータを記憶し、それを入力してもよい。以下、同様に各装置（ビットコメント装置及び検証装置）は送信部１０１、２０１を有さずともよく、装置間のデータの入出力は、通信以外の方法であってもよい。記憶部３０３は、公開パラメータ、コミットメント鍵等を記憶する。なお、上記「登録」とは、記憶部３０３に記憶することを意味してもよい。また、「公開」とは、利用者の求めに応じて、情報（例えば、公開パラメータ）を閲覧可能、または、取得可能とすることを意味する。制御部３０５は、各処理を制御する。
【００２１】
［ビットコミットメント装置１００］
図３は、ビットコミットメント装置１００の構成例を示す図である。図４は、ビットコミットメント装置１００の処理フローの一例を示す図である。ビットコミットメント装置１００は、通信部１０１と、記憶部１０３と、制御部１０５と、コミットメント鍵生成部１２０と、乱数生成部１３０と、開封情報生成部１４０と、コミットメント生成部１５０を有する。
【００２２】
＜制御部１０５、通信部１０１及び記憶部１０３＞
本実施例のビットコミットメント装置１００は、制御部１０５の制御のもと各処理を実行する。ビットコミットメント装置１００は、登録装置３００から公開パラメータｖを受け取る。例えば、通信部１０１は、登録装置３００及び検証装置２００と通信を行い、登録装置３００から公開パラメータｖを受信する（ｓ１０１）。以下、特に記述しなくとも、登録装置３００及び検証装置２００と通信する際には、通信部１０１を介して行われるものとする。
【００２３】
受信した公開パラメータｖを記憶部１０３に記憶する（ｓ１０３）。また、特に示さない限り、入出力される各データや演算過程の各データは、逐一、記憶部１０３に格納・読み出され、各演算処理が進められる。但し、必ずしも記憶部１０３に記憶しなければならないわけではなく、各部間で直接データを受け渡してもよい。
【００２４】
＜コミットメント鍵生成部１２０＞
コミットメント鍵生成部１２０は、Ｇ１から生成元ｇ及びｈ１を、Ｇ２から生成元ｈ２を、無作為に選択し、これらの生成元を用いてコミットメント鍵ｃｋを生成する（ｓ１２０）。例えば、コミットメント鍵ｃｋ＝（ｖ，ｇ，ｈ１，ｈ２）として生成する。コミットメント鍵生成部１２０は、通信部１０１を介して、または、通信部１０１及び記憶部１０３を介して公開パラメータｖが入力され、生成元ｈ２を開封情報算出部１４０へ、生成元ｇ及びｈ１をコミットメント生成部１５０へ出力する。また、通信部１０１を介して、コミットメント鍵ｃｋを登録装置３００へ送る。なお、コミットメント鍵ｃｋには、利用した公開パラメータを表示する情報ｉ等を含めｐｋ＝（ｉ，ｇ，ｈ１，ｈ２）としてもよい。この場合には、以下で説明する検証装置２００は、情報ｉに基づいて、登録装置３００に対応する公開パラメータｖｉを要求する。また、登録装置３００の記憶している公開パラメータの中から対応する公開パラメータを特定することができる場合には、コミットメント鍵ｃｋに公開パラメータｖや、公開パラメータを表示する情報ｉ等を含まなくともよく、検証装置２００は、情報Ｍ及び開封情報Ｈを受け付けた際に、登録装置３００に公開パラメータｖを要求する。
【００２５】
＜乱数生成部１３０及び開封情報算出部１４０＞
乱数生成部１３０は、Ｚｑに属する乱数ｒを生成する（ｓ１３０）。乱数ｒを開封情報算出部１４０及びコミットメント生成部１５０へ出力する。記憶部１０３は、乱数ｒが秘密に記憶される（ｓ１３５）。開封情報算出部１４０は、開封情報Ｈ＝ｈ２ｒを算出する（ｓ１４０）。これにより開封情報Ｈが離散対数問題が困難な元となる。開放情報算出部１４０は、Ｇ２の生成元ｈ２及び乱数ｒが入力され、開封情報Ｈ＝ｈ２ｒを出力する。
【００２６】
＜コミットメント生成部１５０＞
コミットメント生成部１５０は、ｇ，ｈ１及びｒとコミットする情報ｍからＣ＝ｇｍｈ１ｒを計算し、これをコミットメントとして出力する（ｓ１５０）。コミットメント生成部１５０は、乱数生成部１３０から乱数ｒを、コミットメント鍵生成部１２０からＧ１の生成元ｇ、ｈ１を、さらに情報ｍを入力され、コミットメントＣを出力する。なお、情報ｍ∈Ｚｑであり、補助記憶装置やメモリ上のデータ等、もしくは、入力インターフェース、キーボード、マウス等から入力されるデータである。
【００２７】
ビットコミットメント装置１００は、コミットメント鍵ｃｋを登録装置３００へ、コミットメントＣを検証装置２００へ、送る（ｓ１５３）。送ると同時または送った後に、情報ｍを含む情報Ｍ及び開封情報Ｈを検証装置２００へ送る（ｓ１５５）。なお、情報ｍを含む情報Ｍとは、例えば、情報ｍ自体（つまり、Ｍ＝ｍ）であってもよいし、ｇｍであってもよい（つまり、Ｍ＝ｇｍ）。情報Ｍ＝ｇｍとする場合には、図示しない情報変更部を設け、情報変更部は生成元ｇ及び情報ｍを入力され、Ｍ＝ｇｍを算出し、Ｍを出力する構成としてもよい。なお、Ｍ＝ｇｍの場合には、離散対数問題の困難性により、検証装置２００は、Ｍを受け取った場合にも、ｍについて知ることはできない。このとき、ビットコメント装置１００は、情報ｍを秘匿したまま、コミットメントを開封できることを検証装置２００に納得させることができる。非特許文献１同様、一旦コミットされたＣは１通りの情報Ｍ及び開封情報Ｈを持ってのみ開封することができる。よって、ビットコミットメント装置１００は、コミットメントＣを検証装置２００へ送ってから（ｓ１５３）、情報Ｍ及び開封情報Ｈを検証装置２００へ送る（ｓ１５５）までの間に、情報Ｍを改竄することはできない。なお、開封情報の算出（ｓ１４０）とコミットメントの生成（ｓ１５０）は、どちらが先に行われてもよいが、コミットメントＣを先に送らなければ、ある時点で送信者がメッセージｍを保持していたことを、後々、受信者に納得させるという効果を得ることはできない。
【００２８】
［検証装置２００］
図５は、検証装置２００の構成例を示す。図６は、検証装置１００の処理フローの一例を示す図である。検証装置２００は、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２０を有する。
【００２９】
＜制御部２０５、通信部２０１及び記憶部２０３＞
本実施例の検証装置２００は、制御部２０５の制御のもと各処理を実行する。検証装置２００は、登録装置３００からコミットメント鍵ｃｋを、ビットコミットメント装置からコミットメントＣ、情報Ｍ及び開封情報Ｈを、受け取る。例えば、通信部２０１は、登録装置３００及び検証装置１００と通信を行う。登録装置３００からコミットメント鍵ｃｋを受信する（ｓ２０１）。ビットコミットメント装置１００からコミットメントＣを受信し（ｓ２０２ａ）、それと同時またはその後、ビットコミットメント装置１００から情報Ｍ及び開封情報Ｈを受信する（ｓ２０２ｂ）。記憶部２０３は、コミットメントＣ、コミットメント鍵ｃｋ、情報Ｍ及び開封情報Ｈが記憶される（ｓ２０３）。
【００３０】
＜判定部２２０＞
判定部２２０は、以下の等式（１１）が成立するか否かを判定する（ｓ２２０）。
ｅ（Ｃ／ｇｍ，ｈ２）＝ｅ（ｈ１，Ｈ） （１１）
成立する場合には合格とし（ｓ２２３）、成立しない場合には不合格とする（ｓ２２５）。判定部２２０は、通信部２０１を介して、または、通信部２０１及び記憶部２０３を介して、コミットメント鍵ｃｋ、コミットメントＣ、開封情報Ｈ及び情報Ｍ（ｍまたはｇｍ）が入力される。
【００３１】
以下、検証方法を説明する。式（１１）は、Ｃ＝ｇｍｈ１ｒ、Ｈ＝ｈ２ｒより、
ｅ（ｇｍｈ１ｒ／ｇｍ，ｈ２）＝ｅ（ｈ１，ｈ２ｒ） （１１）’
と表すことができる。ペアリングの性質により、ｍ及びｒが正しいときのみ、等式が成り立ち、従来技術同様、検証装置２００は、コミットメントＣを受け取った時点では、情報ｍを知ることはできない。一方、ビットコミットメント装置１００は、コミットメントＣを検証装置２００へ送った後に、情報ｍを改竄することはできない。また、情報Ｍをｇｍとした場合には、乱数ｒだけではなく、情報ｍを秘匿したまま、コミットメントＣを開封できることを第三者に納得させることできる。
【００３２】
このような構成とすることによって、ビットコミットメント方法を、効率的に様々な他の暗号プロトコルの構成要素として利用できる。例えば、本発明のビットコミットメント方法を用いた場合、開封情報Ｈ＝ｈ２ｒが、離散対数問題が困難な群Ｇの元であるため、ペアリングを利用した効率的な非対話ゼロ知識証明を構成することができる。なお、群Ｇとして、例えば、楕円曲線が作る群等を用いることができる。
【００３３】
＜ハードウェア構成＞
図７は、本実施例におけるビットコミットメント装置１００のハードウェア構成を例示したブロック図である。検証装置２００及び登録装置３００も同様の構成を有する。
【００３４】
図７に例示するように、この例のビットコミットメント装置１００、検証装置２００、登録装置３００は、それぞれＣＰＵ（Central Processing Unit）１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ（Read Only Memory）１５、ＲＡＭ（Random Access Memory）１６及びバス１７を有している。
【００３５】
この例のＣＰＵ１１は、制御部１１ａ、演算部１１ｂ及びレジスタ１１ｃを有し、レジスタ１１ｃに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１２は、データが入力される入力インターフェース、キーボード、マウス等であり、出力部１３は、データが出力される出力インターフェース等である。補助記憶装置１４は、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、ビットコミットメント装置１００、検証装置２００及び登録装置３００としてコンピュータを機能させるためのプログラムが格納されるプログラム領域１４ａ及び各種データが格納されるデータ領域１４ｂを有している。また、ＲＡＭ１６は、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等であり、上記のプログラムが格納されるプログラム領域１６ａ及び各種データが格納されるデータ領域１６ｂを有している。また、バス１７は、ＣＰＵ１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ１５及びＲＡＭ１６を通信可能に接続する。
【００３６】
なお、このようなハードウェアの具体例としては、例えば、パーソナルコンピュータの他、サーバ装置やワークステーション等を例示できる。
【００３７】
＜プログラム構成＞
上述のように、プログラム領域１４ａ，１６ａには、本実施例のビットコミットメント装置１００、検証装置２００、登録装置３００の各処理を実行するための各プログラムが格納される。ビットコミットメントプログラム、検証プログラム及び登録プログラムを構成する各プログラムは、単一のプログラム列として記載されていてもよく、また、少なくとも一部のプログラムが別個のモジュールとしてライブラリに格納されていてもよい。また、各プログラムが単体でそれぞれの機能を実現してもよいし、各プログラムがさらに他のライブラリを読み出して各機能を実現するものでもよい。
【００３８】
＜ハードウェアとプログラムとの協働＞
ＣＰＵ１１（図７）は、読み込まれたＯＳ（Operating System）プログラムに従い、補助記憶装置１４のプログラム領域１４ａに格納されている上述のプログラムをＲＡＭ１６のプログラム領域１６ａに書き込む。同様にＣＰＵ１１は、補助記憶装置１４のデータ領域１４ｂに格納されている各種データを、ＲＡＭ１６のデータ領域１６ｂに書き込む。そして、このプログラムやデータが書き込まれたＲＡＭ１６上のアドレスがＣＰＵ１１のレジスタ１１ｃに格納される。ＣＰＵ１１の制御部１１ａは、レジスタ１１ｃに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１６上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１１ｂに順次実行させ、その演算結果をレジスタ１１ｃに格納していく。
【００３９】
図３、５は、このようにＣＰＵ１１に上述のプログラムが読み込まれて実行されることにより構成されるビットコミットメント装置１００、検証装置２００の機能構成を例示したブロック図である。
【００４０】
ここで、記憶部１０３及び２０３は、補助記憶装置１４、ＲＡＭ１６、レジスタ１１ｃ、その他のバッファメモリやキャッシュメモリ等の何れか、あるいはこれらを併用した記憶領域に相当する。また、通信部１０１と、記憶部１０３と、制御部１０５と、コミットメント鍵生成部１２０と、乱数生成部１３０と、開封情報生成部１４０と、コミットメント生成部１５０は、ＣＰＵ１１にビットコミットメントプログラムを実行させることにより構成されるものである。また、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２０は、ＣＰＵ１１に検証プログラムを実行させることにより構成されるものである。
【００４１】
また、本形態のビットコミットメント装置１００、検証装置２００及び登録装置３００は、各制御部１０５、２０５及び３０５の制御のもと各処理を実行する。
【実施例２】
【００４２】
実施例１と異なる部分についてのみ説明する。実施例２記載のビットコミットメント検証システム１０００は、実施例１で示した構成を複数並列に処理し、等式の両辺を乗算にてまとめることにより、複数の情報ｍｉ（但し、１≦ｉ≦ｎであり、ｎは情報の個数を表す）に対するビットコミットメントＣにも対応することができる。また、各情報ｍ１，ｍ２，…，ｍｎのビット長は同一であっても、異なってもよい。
【００４３】
［ビットコミットメント検証システム１０００］
ビットコミットメント検証システム１０００は、登録装置３００と、ビットコミットメント装置１１００と、検証装置１２００からなる。
【００４４】
ビットコミットメント装置１１００は、複数の情報ｍｉに対するコミットメントＣを生成するために、登録装置３００に対して、公開パラメータｖを要求する。登録装置３００は、ｖをビットコミットメント装置１１００へ送る。ビットコミットメント装置１１００は、公開パラメータｖからコミットメント鍵ｃｋを生成し、登録装置３００へ送る。登録装置３００は、コミットメント鍵ｃｋを登録及び公開する。さらに、複数の情報ｍｉ、コミットメント鍵ｃｋ及び複数の乱数ｒｉを用いて、コミットメントＣを生成する。ビットコミットメント装置１１００は、コミットメントＣを検証装置１２００へ送る。送ると同時または送った後に、乱数ｒｉを用いて、開封情報Ｈを生成し、情報ｍｉを含む情報Ｍ及び開封情報Ｈを検証装置１２００へ送る。
【００４５】
検証装置１２００は、コミットメントＣに対応するコミットメント鍵ｃｋを登録装置３００へ要求する。登録装置３００は、コミットメント鍵ｃｋを検証装置１２００へ送る。検証装置１２００は、コミットメントＣ、情報Ｍ、コミットメント鍵ｃｋを用いて、改竄及び成りすまし等が行われていないか検証し、確かにコミットメントＣが送られてきた時点から情報ｍｉが改竄等されていないことを確認する。以下、各装置及び各処理について詳細を説明する。
【００４６】
［ビットコミットメント装置１１００］
ビットコミットメント装置１１００は、通信部１０１と、記憶部１１０３と、制御部１０５と、コミットメント鍵生成部１２０と、乱数生成部１１３０と、開封情報生成部１１４０と、コミットメント生成部１１５０を有する。
【００４７】
＜乱数生成部１１３０、記憶部１１０３及び開封情報算出部１１４０＞
乱数生成部１１３０は、Ｚｑに属する複数の乱数ｒｉを生成する。乱数ｒｉは、開封情報算出部１１４０及びコミットメント生成部１１５０へ出力される。記憶部１１０３は、乱数ｒｉは秘密に記憶される。開封情報算出部１１４０は、開封情報Ｈ＝Πｎｉ＝１ｈ２ｒｉを算出する（但し、ｒｉとは、上記乱数ｒｉのことを意味する）。開封情報算出部１１４０は、コミットメント鍵生成部１２０から生成元ｈ２を、乱数生成部１３０から乱数ｒｉを入力され、開封情報Ｈ＝Πｎｉ＝１ｈ２ｒｉを出力する。
【００４８】
＜コミットメント生成部１１５０＞
コミットメント生成部１１５０は、ｇ，ｈ１及びｒｉとコミットする情報ｍｉからＣ＝Πｎｉ＝１ｇｍｉｈ１ｒｉを計算し、これをコミットメントとして出力する（ｓ１５０）。コミットメント生成部１１５０は、コミットメント鍵生成部１２０からＧ１の生成元ｇ、ｈ１を、乱数生成部１３０から乱数ｒｉを、及び情報ｍｉを入力され、コミットメントＣを出力する。なお、情報ｍｉ∈Ｚｑである。
【００４９】
ビットコミットメント装置１０００は、コミットメント鍵ｃｋを登録装置３００へ、コミットメントＣを検証装置１２００へ、送る。送ると同時または送った後に、情報ｍｉを含む情報Ｍ及び開封情報Ｈを検証装置１２００へ送る。なお、情報ｍｉを含む情報Ｍとは、例えば、情報ｍｉ自体（つまり、Ｍ＝（ｍ１，ｍ２，…，ｍｎ）であってもよいし、ｇｍｉであってもよい（つまり、Ｍ＝（ｇｍ１，ｇｍ２，…，ｇｍｎ）。また、ｇｍｉの総積であってもよい（つまり、Ｍ＝Πｎｉ＝１ｇｍｉ）。
【００５０】
このような構成とすることによって、実施例１と同様の効果を得ることができる。さらに、複数の情報ｍｉ（１≦ｉ≦ｎ）に対してビットコミットメントＣを生成することができるため、実施例１の方法により複数の情報に対し、複数のビットコミットメントを作成するのに比べ、処理を軽減することができる。また、ビットコミットメントの情報量、通信量を小さくすることができる。
【００５１】
［検証装置１２００］
検証装置１２００は、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２０を有する。
【００５２】
＜判定部２２０＞
判定部２２０は、以下の等式（２１）が成立するか否かを判定する（ｓ２２０）。
ｅ（Ｃ／Πｎｉ＝１ｇｍｉ，ｈ２）＝ｅ（ｈ１，Ｈ） （２１）
成立する場合には合格とし（ｓ２２３）、成立しない場合には不合格とする（ｓ２２５）。
【００５３】
以下、検証方法を説明する。式（１１）は、Ｃ＝Πｇｍｉｈ１ｒｉ、Ｈ＝Πｎｉ＝１ｈ２ｒｉより、
ｅ（Πｎｉ＝１ｇｍｉｈ１ｒｉ／Πｎｉ＝１ｇｍｉ，ｈ２）＝ｅ（ｈ１，Πｎｉ＝１ｈ２ｒｉ） (21)'
と表すことができる。ペアリングの性質により、ｍｉ及びｒｉの全てが正しいときのみ、等式が成り立ち、実施例１と同様の効果をえることができる。さらに、等式の両辺を乗算にてまとめることにより、実施例１の方法により複数のコミットメントを検証するのに比べ、処理を軽減することができる。
【図面の簡単な説明】
【００５４】
【図１】ビットコミットメント検証システム１の構成例を示す図。
【図２】ビットコミットメント検証システム１のシーケンス図の一例を示す図。
【図３】ビットコミットメント装置１００の構成例を示す図。
【図４】ビットコミットメント装置１００の処理フローの一例を示す図。
【図５】検証装置２００の構成例を示す図。
【図６】検証装置２００の処理フローの一例を示す図。
【図７】実施例１におけるビットコミットメント装置１００のハードウェア構成を例示したブロック図。
【符号の説明】
【００５５】
１ ビットコミットメント検証システム
１００ ビットコミットメント装置 ２００ 検証装置
３００ 登録装置
１０１、２０１ 通信部 １０３、２０３ 記憶部
１０５、２０５ 制御部 １２０ コミットメント鍵生成部
１３０ 乱数生成部 １４０ 開封情報算出部
１５０ ビットコミットメント生成部 ２２０ 判定部
【特許請求の範囲】
【請求項１】
登録装置と、ビットコミットメント装置と、検証装置からなるビットコミットメント検証システムであって、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、公開パラメータｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）とし、
前記ビットコメント装置は、Ｇ１から生成元ｇ及びｈ１を、Ｇ２から生成元ｈ２を、無作為に選択し、これらの生成元を用いてコミットメント鍵ｃｋを生成するコミットメント鍵生成部と、
Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、情報ｍの個数を表す）を生成する乱数生成部と、
前記公開パラメータｖ及び乱数ｒｉが記憶され、特に乱数ｒｉは秘密に記憶される記憶部と、
前記ｇ，ｈ１及びｒｉとコミットする情報ｍｉからＣ＝Πｎｉ＝１ｇｍｉｈ１ｒｉを計算し、これをコミットメントとして出力するコミットメント生成部と、
開封情報Ｈ＝Πｎｉ＝１ｈ２ｒｉを算出する開封情報算出部と、を有し、
前記検証装置は、前記コミットメント鍵ｃｋ、前記情報ｍｉを含む情報Ｍ、前記開封情報Ｈ及びコミットメントＣが記憶される記憶部と、
等式ｅ（Ｃ／Πｎｉ＝１ｇｍｉ，ｈ２）＝ｅ（ｈ１，Ｈ）が成立するか否かを判定し、成立する場合には合格とし、成立しない場合には不合格とする判定部を有し、
前記登録装置は、前記公開パラメータｖ及び前記コミットメント鍵ｃｋを記憶する記憶部を有し、
前記ビットコミットメント装置は、前記登録装置から前記公開パラメータｖを受け取り、前記コミットメント鍵ｃｋを前記登録装置へ、前記コミットメントＣを検証装置へ、送り、コミットメントＣを送ると同時または送った後に、前記情報Ｍ及び開封情報Ｈを前記検証装置へ送り、
前記検証装置は、前記登録装置から前記コミットメント鍵ｃｋを、前記ビットコミットメント装置から前記コミットメントＣ、前記情報Ｍ及び開封情報Ｈを、受け取る、
ことを特徴とするビットコミットメント検証システム。
【請求項２】
請求項１記載のビットコミットメント検証システムであって、
ｎ＝１であること、
を特徴とするビットコミットメント検証システム。
【請求項３】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、公開パラメータｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）とし、
Ｇ１から生成元ｇ及びｈ１を、Ｇ２から生成元ｈ２を、無作為に選択し、これらの生成元を用いてコミットメント鍵ｃｋを生成するコミットメント鍵生成部と、
Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、情報ｍの個数を表す）を生成する乱数生成部と、
前記公開パラメータｖ及び乱数ｒｉが記憶され、特に乱数ｒｉは秘密に記憶される記憶部と、
前記ｇ，ｈ１及びｒｉとコミットする情報ｍｉからＣ＝Πｎｉ＝１ｇｍｉｈ１ｒｉを計算し、これをコミットメントとして出力するコミットメント生成部と、
開封情報Ｈ＝Πｎｉ＝１ｈ２ｒｉを算出する開封情報算出部と、を有し、
登録装置から前記公開パラメータｖを受け取り、前記コミットメント鍵ｃｋを登録装置へ、前記コミットメントＣを検証装置へ、送り、コミットメントＣを送ると同時または送った後に、前記情報ｍｉを含む情報Ｍ及び開封情報Ｈを前記検証装置へ送る、
ことを特徴とするビットコミットメント装置。
【請求項４】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、
コミットメント鍵ｃｋ、情報ｍｉを含む情報Ｍ、開封情報Ｈ及びコミットメントＣが記憶される記憶部と、
等式ｅ（Ｃ／Πｎｉ＝１ｇｍｉ，ｈ２）＝ｅ（ｈ１，Ｈ）が成立するか否かを判定し、成立する場合には合格とし、成立しない場合には不合格とする判定部を有し、
登録装置から前記コミットメント鍵ｃｋを、ビットコミットメント装置から前記コミットメントＣ、前記情報Ｍ及び開封情報Ｈを、受け取る、
ことを特徴とする検証装置。
【請求項５】
登録装置と、ビットコミットメント装置と、検証装置を用いるビットコミットメント検証方法であって、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、公開パラメータｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）とし、
前記ビットコミットメント装置が、前記登録装置から前記公開パラメータｖを受け取るステップと、
前記ビットコメント装置が、Ｇ１から生成元ｇ及びｈ１を、Ｇ２から生成元ｈ２を、無作為に選択し、これらの生成元を用いてコミットメント鍵ｃｋを生成するコミットメント鍵生成ステップと、
前記ビットコメント装置が、前記コミットメント鍵ｃｋを前記登録装置へ送るステップと、
前記登録装置が、前記コミットメント鍵ｃｋを登録及び公開するステップと、
前記ビットコメント装置が、Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、情報ｍの個数を表す）を生成する乱数生成ステップと、
前記ビットコメント装置が、前記公開パラメータｖ及び乱数ｒｉを記憶し、特に乱数ｒｉは秘密に記憶する記憶ステップと、
前記ビットコメント装置が、前記ｇ，ｈ１及びｒｉとコミットする情報ｍｉからＣ＝Πｎｉ＝１ｇｍｉｈ１ｒｉを計算し、これをコミットメントとして出力するコミットメント生成ステップと、
前記ビットコメント装置が、前記コミットメントＣを検証装置へ送るステップと、
前記ビットコメント装置が、開封情報Ｈ＝Πｎｉ＝１ｈ２ｒｉを算出する開封情報算出ステップと、
前記ビットコメント装置が、前記コミットメントＣを送ると同時または送った後に、前記情報ｍｉを含む情報Ｍ及び開封情報Ｈを前記検証装置へ送るステップと、
前記検証装置が、前記ビットコミットメント装置から前記コミットメントＣを受け取るステップと、
前記検証装置が、前記登録装置から前記コミットメント鍵ｃｋを受け取るステップと、
前記検証装置が、前記ビットコミットメント装置から前記情報Ｍ及び開封情報Ｈを、受け取るステップと、
前記検証装置が、前記コミットメント鍵ｃｋ、前記情報Ｍ、前記開封情報Ｈ及びコミットメントＣを記憶する記憶ステップと、
前記検証装置が、等式ｅ（Ｃ／Πｎｉ＝１ｇｍｉ，ｈ２）＝ｅ（ｈ１，Ｈ）が成立するか否かを判定し、成立する場合には合格とし、成立しない場合には不合格とする判定ステップとを有する、
ことを特徴とするビットコミットメント検証方法。
【請求項６】
請求項５記載のビットコミットメント検証方法であって、
ｎ＝１であること、
を特徴とするビットコミットメント検証方法。
【請求項７】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、公開パラメータｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）とし、
ビットコミットメント装置が、登録装置から前記公開パラメータｖを受け取るステップと、
前記ビットコメント装置が、Ｇ１から生成元ｇ及びｈ１を、Ｇ２から生成元ｈ２を、無作為に選択し、これらの生成元を用いてコミットメント鍵ｃｋを生成するコミットメント鍵生成ステップと、
前記ビットコメント装置が、前記コミットメント鍵ｃｋを前記登録装置へ送るステップと、
前記ビットコメント装置が、Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、情報ｍの個数を表す）を生成する乱数生成ステップと、
前記ビットコメント装置が、前記公開パラメータｖ及び乱数ｒｉを記憶し、特に乱数ｒｉは秘密に記憶する記憶ステップと、
前記ビットコメント装置が、前記ｇ，ｈ１及びｒｉとコミットする情報ｍｉからＣ＝Πｎｉ＝１ｇｍｉｈ１ｒｉを計算し、これをコミットメントとして出力するコミットメント生成ステップと、
前記ビットコメント装置が、前記コミットメントＣを検証装置へ送るステップと、
前記ビットコメント装置が、開封情報Ｈ＝Πｎｉ＝１ｈ２ｒｉを算出する開封情報算出ステップと、
前記ビットコメント装置が、前記コミットメントＣを送ると同時または送った後に、前記情報ｍｉを含む情報Ｍ及び開封情報Ｈを前記検証装置へ送るステップと、
を有する、
ことを特徴とするビットコミットメント方法。
【請求項８】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、公開パラメータｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）とし、
検証装置が、ビットコミットメント装置からコミットメントＣを受け取るステップと、
前記検証装置が、登録装置からコミットメント鍵ｃｋを受け取るステップと、
前記検証装置が、前記ビットコミットメント装置から情報Ｍ及び開封情報Ｈを、受け取るステップと、
前記検証装置が、前記コミットメント鍵ｃｋ、前記情報Ｍ、前記開封情報Ｈ及びコミットメントＣを記憶する記憶ステップと、
前記検証装置が、等式ｅ（Ｃ／Πｎｉ＝１ｇｍｉ，ｈ２）＝ｅ（ｈ１，Ｈ）が成立するか否かを判定し、成立する場合には合格とし、成立しない場合には不合格とする判定ステップとを有する、
ことを特徴とする検証方法。
【請求項９】
請求項３記載のビットコミットメント装置としてコンピュータを機能させるためのビットコミットメントプログラム。
【請求項１０】
請求項４記載の検証装置としてコンピュータを機能させるための検証プログラム。
【請求項１】
登録装置と、ビットコミットメント装置と、検証装置からなるビットコミットメント検証システムであって、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、公開パラメータｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）とし、
前記ビットコメント装置は、Ｇ１から生成元ｇ及びｈ１を、Ｇ２から生成元ｈ２を、無作為に選択し、これらの生成元を用いてコミットメント鍵ｃｋを生成するコミットメント鍵生成部と、
Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、情報ｍの個数を表す）を生成する乱数生成部と、
前記公開パラメータｖ及び乱数ｒｉが記憶され、特に乱数ｒｉは秘密に記憶される記憶部と、
前記ｇ，ｈ１及びｒｉとコミットする情報ｍｉからＣ＝Πｎｉ＝１ｇｍｉｈ１ｒｉを計算し、これをコミットメントとして出力するコミットメント生成部と、
開封情報Ｈ＝Πｎｉ＝１ｈ２ｒｉを算出する開封情報算出部と、を有し、
前記検証装置は、前記コミットメント鍵ｃｋ、前記情報ｍｉを含む情報Ｍ、前記開封情報Ｈ及びコミットメントＣが記憶される記憶部と、
等式ｅ（Ｃ／Πｎｉ＝１ｇｍｉ，ｈ２）＝ｅ（ｈ１，Ｈ）が成立するか否かを判定し、成立する場合には合格とし、成立しない場合には不合格とする判定部を有し、
前記登録装置は、前記公開パラメータｖ及び前記コミットメント鍵ｃｋを記憶する記憶部を有し、
前記ビットコミットメント装置は、前記登録装置から前記公開パラメータｖを受け取り、前記コミットメント鍵ｃｋを前記登録装置へ、前記コミットメントＣを検証装置へ、送り、コミットメントＣを送ると同時または送った後に、前記情報Ｍ及び開封情報Ｈを前記検証装置へ送り、
前記検証装置は、前記登録装置から前記コミットメント鍵ｃｋを、前記ビットコミットメント装置から前記コミットメントＣ、前記情報Ｍ及び開封情報Ｈを、受け取る、
ことを特徴とするビットコミットメント検証システム。
【請求項２】
請求項１記載のビットコミットメント検証システムであって、
ｎ＝１であること、
を特徴とするビットコミットメント検証システム。
【請求項３】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、公開パラメータｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）とし、
Ｇ１から生成元ｇ及びｈ１を、Ｇ２から生成元ｈ２を、無作為に選択し、これらの生成元を用いてコミットメント鍵ｃｋを生成するコミットメント鍵生成部と、
Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、情報ｍの個数を表す）を生成する乱数生成部と、
前記公開パラメータｖ及び乱数ｒｉが記憶され、特に乱数ｒｉは秘密に記憶される記憶部と、
前記ｇ，ｈ１及びｒｉとコミットする情報ｍｉからＣ＝Πｎｉ＝１ｇｍｉｈ１ｒｉを計算し、これをコミットメントとして出力するコミットメント生成部と、
開封情報Ｈ＝Πｎｉ＝１ｈ２ｒｉを算出する開封情報算出部と、を有し、
登録装置から前記公開パラメータｖを受け取り、前記コミットメント鍵ｃｋを登録装置へ、前記コミットメントＣを検証装置へ、送り、コミットメントＣを送ると同時または送った後に、前記情報ｍｉを含む情報Ｍ及び開封情報Ｈを前記検証装置へ送る、
ことを特徴とするビットコミットメント装置。
【請求項４】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、
コミットメント鍵ｃｋ、情報ｍｉを含む情報Ｍ、開封情報Ｈ及びコミットメントＣが記憶される記憶部と、
等式ｅ（Ｃ／Πｎｉ＝１ｇｍｉ，ｈ２）＝ｅ（ｈ１，Ｈ）が成立するか否かを判定し、成立する場合には合格とし、成立しない場合には不合格とする判定部を有し、
登録装置から前記コミットメント鍵ｃｋを、ビットコミットメント装置から前記コミットメントＣ、前記情報Ｍ及び開封情報Ｈを、受け取る、
ことを特徴とする検証装置。
【請求項５】
登録装置と、ビットコミットメント装置と、検証装置を用いるビットコミットメント検証方法であって、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、公開パラメータｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）とし、
前記ビットコミットメント装置が、前記登録装置から前記公開パラメータｖを受け取るステップと、
前記ビットコメント装置が、Ｇ１から生成元ｇ及びｈ１を、Ｇ２から生成元ｈ２を、無作為に選択し、これらの生成元を用いてコミットメント鍵ｃｋを生成するコミットメント鍵生成ステップと、
前記ビットコメント装置が、前記コミットメント鍵ｃｋを前記登録装置へ送るステップと、
前記登録装置が、前記コミットメント鍵ｃｋを登録及び公開するステップと、
前記ビットコメント装置が、Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、情報ｍの個数を表す）を生成する乱数生成ステップと、
前記ビットコメント装置が、前記公開パラメータｖ及び乱数ｒｉを記憶し、特に乱数ｒｉは秘密に記憶する記憶ステップと、
前記ビットコメント装置が、前記ｇ，ｈ１及びｒｉとコミットする情報ｍｉからＣ＝Πｎｉ＝１ｇｍｉｈ１ｒｉを計算し、これをコミットメントとして出力するコミットメント生成ステップと、
前記ビットコメント装置が、前記コミットメントＣを検証装置へ送るステップと、
前記ビットコメント装置が、開封情報Ｈ＝Πｎｉ＝１ｈ２ｒｉを算出する開封情報算出ステップと、
前記ビットコメント装置が、前記コミットメントＣを送ると同時または送った後に、前記情報ｍｉを含む情報Ｍ及び開封情報Ｈを前記検証装置へ送るステップと、
前記検証装置が、前記ビットコミットメント装置から前記コミットメントＣを受け取るステップと、
前記検証装置が、前記登録装置から前記コミットメント鍵ｃｋを受け取るステップと、
前記検証装置が、前記ビットコミットメント装置から前記情報Ｍ及び開封情報Ｈを、受け取るステップと、
前記検証装置が、前記コミットメント鍵ｃｋ、前記情報Ｍ、前記開封情報Ｈ及びコミットメントＣを記憶する記憶ステップと、
前記検証装置が、等式ｅ（Ｃ／Πｎｉ＝１ｇｍｉ，ｈ２）＝ｅ（ｈ１，Ｈ）が成立するか否かを判定し、成立する場合には合格とし、成立しない場合には不合格とする判定ステップとを有する、
ことを特徴とするビットコミットメント検証方法。
【請求項６】
請求項５記載のビットコミットメント検証方法であって、
ｎ＝１であること、
を特徴とするビットコミットメント検証方法。
【請求項７】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、公開パラメータｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）とし、
ビットコミットメント装置が、登録装置から前記公開パラメータｖを受け取るステップと、
前記ビットコメント装置が、Ｇ１から生成元ｇ及びｈ１を、Ｇ２から生成元ｈ２を、無作為に選択し、これらの生成元を用いてコミットメント鍵ｃｋを生成するコミットメント鍵生成ステップと、
前記ビットコメント装置が、前記コミットメント鍵ｃｋを前記登録装置へ送るステップと、
前記ビットコメント装置が、Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、情報ｍの個数を表す）を生成する乱数生成ステップと、
前記ビットコメント装置が、前記公開パラメータｖ及び乱数ｒｉを記憶し、特に乱数ｒｉは秘密に記憶する記憶ステップと、
前記ビットコメント装置が、前記ｇ，ｈ１及びｒｉとコミットする情報ｍｉからＣ＝Πｎｉ＝１ｇｍｉｈ１ｒｉを計算し、これをコミットメントとして出力するコミットメント生成ステップと、
前記ビットコメント装置が、前記コミットメントＣを検証装置へ送るステップと、
前記ビットコメント装置が、開封情報Ｈ＝Πｎｉ＝１ｈ２ｒｉを算出する開封情報算出ステップと、
前記ビットコメント装置が、前記コミットメントＣを送ると同時または送った後に、前記情報ｍｉを含む情報Ｍ及び開封情報Ｈを前記検証装置へ送るステップと、
を有する、
ことを特徴とするビットコミットメント方法。
【請求項８】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、公開パラメータｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）とし、
検証装置が、ビットコミットメント装置からコミットメントＣを受け取るステップと、
前記検証装置が、登録装置からコミットメント鍵ｃｋを受け取るステップと、
前記検証装置が、前記ビットコミットメント装置から情報Ｍ及び開封情報Ｈを、受け取るステップと、
前記検証装置が、前記コミットメント鍵ｃｋ、前記情報Ｍ、前記開封情報Ｈ及びコミットメントＣを記憶する記憶ステップと、
前記検証装置が、等式ｅ（Ｃ／Πｎｉ＝１ｇｍｉ，ｈ２）＝ｅ（ｈ１，Ｈ）が成立するか否かを判定し、成立する場合には合格とし、成立しない場合には不合格とする判定ステップとを有する、
ことを特徴とする検証方法。
【請求項９】
請求項３記載のビットコミットメント装置としてコンピュータを機能させるためのビットコミットメントプログラム。
【請求項１０】
請求項４記載の検証装置としてコンピュータを機能させるための検証プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１０−１３５９２８（Ｐ２０１０−１３５９２８Ａ）
【公開日】平成２２年６月１７日（２０１０．６．１７）
【国際特許分類】
【出願番号】特願２００８−３０７９０２（Ｐ２００８−３０７９０２）
【出願日】平成２０年１２月２日（２００８．１２．２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２２年６月１７日（２０１０．６．１７）
【国際特許分類】
【出願日】平成２０年１２月２日（２００８．１２．２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]