コミットメントシステム、コミットメント生成装置、コミットメント受信装置、その方法及びプログラム
【課題】新しいＳＳＴＣ方式のコミットメントシステム等を提供する。
【解決手段】公開検証可能なタグベース鍵カプセル化メカニズムΠが定める関係Ｒprivpk,tagを
とする。コミットメント受信装置は暗号化アルゴリズムに対し公開鍵とタグ情報を与え、第一暗号文と第一鍵との組を生成する。コミットメント生成装置は第一暗号文を受信し、公開鍵とタグ情報を用いて、第一暗号文が真の暗号文であるか否かを検証し、真の暗号文である場合には、関係Ｒprivpk,tagのΣ−プロトコルに対するｓｉｍΣを計算し、コミットメント情報ａをコミットメント受信装置に送信する。コミットメント受信装置はコミットメント情報を受信し、を格納しておき、秘匿情報を受信すると、関係Ｒprivpk,tagのΣ−プロトコルに対するΣｖｒｆｙを用いて、秘匿情報が変更されていないかを判定する。
【解決手段】公開検証可能なタグベース鍵カプセル化メカニズムΠが定める関係Ｒprivpk,tagを
とする。コミットメント受信装置は暗号化アルゴリズムに対し公開鍵とタグ情報を与え、第一暗号文と第一鍵との組を生成する。コミットメント生成装置は第一暗号文を受信し、公開鍵とタグ情報を用いて、第一暗号文が真の暗号文であるか否かを検証し、真の暗号文である場合には、関係Ｒprivpk,tagのΣ−プロトコルに対するｓｉｍΣを計算し、コミットメント情報ａをコミットメント受信装置に送信する。コミットメント受信装置はコミットメント情報を受信し、を格納しておき、秘匿情報を受信すると、関係Ｒprivpk,tagのΣ−プロトコルに対するΣｖｒｆｙを用いて、秘匿情報が変更されていないかを判定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘匿情報をコミットしコミットメント情報を生成するコミットメント生成装置、コミットメント情報を受信するコミットメント受信装置、コミットメント装置とコミットメント受信装置とからなるコミットメントシステム、その方法及びプログラムに関する。
【背景技術】
【０００２】
暗号におけるコミットメントとは、電子的に行う「封じ手」のことである。コミットメントは、送信者(sender)と、受信者(receiver)に分かれる。送信者は、受信者に情報ｍを秘匿しながらも「委託」(commit)する。委託された情報ｍは、後に開示することになるが、委託する時点で決定した値ｍから変更することは出来ない。この性質を「秘匿性」(hiding)と「拘束性」(binding)と言う。例えばコミットメントを利用して、電子的なジャンケンやコイン投げ（もちろん、将棋や碁の封じ手でも良い）を行うことができる。
【０００３】
コミットメントは、最も基本的な暗号プリミティブであるため、多くの暗号プロトコルの中で頻繁に利用される。近年では、暗号プロトコルをより現実の環境に近づけるため、複雑な組み合わせの中で利用した場合の安全性も求められている。このような複雑な組み合わせの中では、古典的安全性モデルで定義されたコミットメントでは、秘匿性と拘束性を満たせなくなってしまう。
【０００４】
複雑な組み合わせの中で利用するために頑強なコミットメント方式が必要となる。なお、あるコミットメント方式が、頑強(non-malleable)であるとは、そのコミットメント方式を同時にどのように実行しても、秘匿性と拘束性が満たされる場合をいう。
【０００５】
頑強なコミットメント方式よりもさらに強い安全性を持つ汎用結合コミットメントというものもある。汎用結合性とは、コミットメントに限ったものではなく、多くの暗号方式の上で定義できる。暗号方式が汎用結合であると、他の汎用結合な暗号方式と組み合わせて実行しても、お互いの単独で満たされる安全性が確保される。つまり、汎用結合である暗号方式は、いかなる汎用結合な暗号方式と組み合わせても汎用結合な暗号方式になる（非特許文献１及び２参照）。
【０００６】
コミットメント方式の中には、送信者と受信者の双方がアクセス可能な（送信者、受信者の何れでもない第三者により正しく作られた）共通情報(crs: common reference string)を必要とするものもある。技術的な問題により、この共通情報は、コミットメントごとに使い捨てなければいけない場合と、使い捨てずに同じ共通情報をずっと使える場合に分かれる。但し、共通情報をずっと使えるコミットメント方式の方がより実用性が高い。
【０００７】
さらに、落し戸付きコミットメント(trap-door commitment)方式は、落し戸(trap-door) を知っていれば、コミット時点とは異なる秘匿情報でコミットメント情報を開封できる。よって、落し戸付きコミットメント方式において、落し戸は、送信者には秘密である。
【０００８】
落し戸付きコミットメントであり、かつ頑強なコミットメント(non-malleable trap-door com-mitment)方式も存在する。落し戸付きコミットメントの頑強性は、non-malleability with respect to openingという名前で定義される（非特許文献３、４、５、６及び７参照）。
【０００９】
さらに、simulation-sound という定義を満たす落し戸付きコミットメント方式も存在する（非特許文献４及び６参照）。simulation-sound落し戸付きコミットメント(以下「ＳＳＴＣ」という)方式であれば、non-malleability with respect to open コミットメント方式、つまり頑強な落し戸付きコミットメントである。simulation-sound落し戸付きコミットメントは、Σ−プロトコル（非特許文献８参照）と呼ばれる標準的な認証プロトコルの安全性を大幅に上げることができ、さらに、非特許文献９の技術と組み合わせると、汎用結合可能コミットメントを構成できる。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】R. Canetti, "Universally composable security: A new paradigm for cryptographic protocols", In Proceedings of the 42th IEEE Annual Symposium on Foundations of Computer Science (FOCS'01), Oct 2001, p.136-145
【非特許文献２】Ran Canetti, "Universally composable security: A new paradigm for cryptograpic protocols", Technical report, Cryptology ePrint Archive, Report 2000/067, 2005, Preliminary version appeared in FOCS'01
【非特許文献３】Ivan Damgard and Jens Groth, "Non-interactive and reusable non-malleable commitment schemes", In STOC03, 2003, p.426-437
【非特許文献４】J.Groth, "Honest verifier Zero-Knowledge Arguments Applied", PhD thesis, Basic Resarch in Computer Science, University of Aarhus, 2004
【非特許文献５】J. A. Garay, P. Mackenzie, and K. Yang, "Strengthening zero-knowledge protocols using signatures", In Advances in Cryptology-EUROCRYPT 2003, Springer-Verlag, 2003, volume 2656 of Lecture Notes in Computer Science, p.177-194
【非特許文献６】P. D. MacKenzie and K. Yang, "On simulation-sound trapdoor commitments", In C. Cachin and J. Camenisch, editors, Advances in Cryptology - EUROCRYPT 2004, Springer-Verlag, 2004, volume 3027 of Lecture Notes in Computer Science, p.382-400
【非特許文献７】R. Gennaro, "Multi-trapdoor commitments and their applications to proofs of knowledge secure under concurrent man-in-the-middle attacks", In Advances in Cryptology - CRYPTO'04, 2004, volume 3152 of Lecture Notes in Computer Science, p.220-236
【非特許文献８】R. Cramer, I. Damgard, and B. Schoenmakers, "Proofs of partial knowledge and simplied design of witness hiding protocols", In Y. G. Desmedt, editor, Advances in Cryptology - CRYPTO'94, Springer-Verlag, 1994, volume 839 of Lecture Notes in Computer Science, p.174-187
【非特許文献９】I. Damgard and J. Nielsen, "Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor", In Advances in Cryptology - CRYPTO2002, 2002, p.581-596
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、非特許文献３、４、５、６及び７記載の従来技術は、全て使い捨てでない署名から共通の変換方法の基にsimulation-sound落し戸付きコミットメント(ＳＳＴＣ)を構成する。そのため、従来の署名が破られると、同時に従来技術のコミットメント方式も破られる可能性がある。
【００１２】
本発明では、公開検証可能なタグベース鍵カプセル化メカニズムを用いて、新しいＳＳＴＣ方式のコミットメントシステム、コミットメント生成装置、コミットメント受信装置、その方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記の課題を解決するために、本発明の第一の態様によれば、コミットメントシステムはコミットメント生成装置とコミットメント受信装置からなる。公開検証可能なタグベース鍵カプセル化メカニズムをΠ＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）とし、鍵生成アルゴリズムＧｅｎを用いて生成される公開鍵をｐｋとし、コミットメント生成装置とコミットメント受信装置とが共に知っているタグ情報をｔａｇとし、ｒを乱数とし、暗号化アルゴリズムＥｎｃに対し公開鍵ｐｋとタグ情報ｔａｇを与えて得られる第一暗号文をＣとし、第一鍵をＫとし、Πが定める関係Ｒprivpk,tagを
【００１４】
【数１】
【００１５】
とする。コミットメント受信装置は暗号化アルゴリズムＥｎｃに対し公開鍵ｐｋとタグ情報ｔａｇを与え、第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成し、第一暗号文Ｃをコミットメント生成装置に送信する。コミットを開封するときの証拠の一部をｚとし、コミットする秘匿情報をｍとし、コミットメント生成装置は第一暗号文Ｃを受信し、公開鍵ｐｋとタグ情報ｔａｇを用いて、第一暗号文Ｃが真の暗号文であるか否かを検証し、真の暗号文である場合には、関係Ｒprivpk,tagのΣ−プロトコルに対する（ａ，ｚ）←ｓｉｍΣ（Ｃ，ｍ）を計算し、コミットメント情報ａをコミットメント受信装置に送信する。コミットメント受信装置はコミットメント情報ａを受信し、（ｔａｇ，Ｃ，ａ）を格納しておき、（ｔａｇ，ｍ，ｚ）を受信すると、関係Ｒprivpk,tagのΣ−プロトコルに対するΣｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）を用いて、秘匿情報ｍが変更されていないかを判定する。
【００１６】
上記の課題を解決するために、本発明の第二の態様によれば、コミットメント生成装置は秘匿情報ｍをコミットし、コミットメント情報ａを生成する。公開検証可能なタグベース鍵カプセル化メカニズムをΠ＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）とし、鍵生成アルゴリズムＧｅｎを用いて生成される公開鍵をｐｋとし、当該コミットメント生成装置とコミットメント情報ａを受信するコミットメント受信装置とが共に知っているタグ情報をｔａｇとし、ｒを乱数とし、暗号化アルゴリズムＥｎｃに対し公開鍵ｐｋとタグ情報ｔａｇを与えて得られる第一暗号文をＣとし、第一鍵をＫとし、Πが定める関係Ｒprivpk,tagを
【００１７】
【数２】
【００１８】
とし、コミットを開封するときの証拠の一部をｚとする。第一暗号文Ｃを受信し、公開鍵ｐｋとタグ情報ｔａｇとを用いて、受信した第一暗号文Ｃが真の暗号文であるか否かを検証し、真の暗号文である場合には、関係Ｒprivpk,tagのΣ−プロトコルに対する（ａ，ｚ）←ｓｉｍΣ（Ｃ，ｍ）を計算し、コミットメント情報ａをコミットメント受信装置に送信する。
【００１９】
上記の課題を解決するために、本発明の第三の態様によれば、コミットメント受信装置は、コミットメント情報ａを受信する。公開検証可能なタグベース鍵カプセル化メカニズムをΠ＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）とし、鍵生成アルゴリズムＧｅｎを用いて生成される公開鍵をｐｋとし、秘匿情報ｍをコミットし、コミットメント情報ａを生成するコミットメント生成装置と当該コミットメント受信装置とが共に知っているタグ情報をｔａｇとし、ｒを乱数とし、暗号化アルゴリズムＥｎｃに対し公開鍵ｐｋとタグ情報ｔａｇを与えて得られる第一暗号文をＣとし、第一鍵をＫとし、Πが定める関係Ｒprivpk,tagを
【００２０】
【数３】
【００２１】
とする。暗号化アルゴリズムＥｎｃに対し公開鍵ｐｋとタグ情報ｔａｇを与え、第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成し、第一暗号文Ｃをコミットメント受信装置に送信し、コミットを開封するときの証拠の一部をｚとし、コミットメント生成装置からコミットメント情報ａを受信し、（ｔａｇ，Ｃ，ａ）を格納しておき、（ｔａｇ，ｍ，ｚ）を受信すると、Σ−プロトコルに対するΣｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）を用いて、秘匿情報ｍが変更されていないかを判定する。
【００２２】
上記の課題を解決するために、本発明の第四の態様によれば、コミットメント方法は、コミットメント生成装置とコミットメント受信装置を用いる。公開検証可能なタグベース鍵カプセル化メカニズムをΠ＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）とし、鍵生成アルゴリズムＧｅｎを用いて生成される公開鍵をｐｋとし、コミットメント生成装置とコミットメント受信装置とが共に知っているタグ情報をｔａｇとし、ｒを乱数とし、暗号化アルゴリズムＥｎｃに対し公開鍵ｐｋとタグ情報ｔａｇを与えて得られる第一暗号文をＣとし、第一鍵をＫとし、Πが定める関係Ｒprivpk,tagを
【００２３】
【数４】
【００２４】
とする。コミットメント受信装置において、暗号化アルゴリズムＥｎｃに対し公開鍵ｐｋとタグ情報ｔａｇを与え、第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成し、第一暗号文Ｃをコミットメント生成装置に送信する。コミットを開封するときの証拠の一部をｚとし、コミットする秘匿情報をｍとし、コミットメント生成装置が、第一暗号文Ｃを受信し、コミットメント生成装置において、公開鍵ｐｋとタグ情報ｔａｇを用いて、第一暗号文Ｃが真の暗号文であるか否かを検証し、真の暗号文である場合には、関係Ｒprivpk,tagのΣ−プロトコルに対する（ａ，ｚ）←ｓｉｍΣ（Ｃ，ｍ）を計算し、コミットメント情報ａをコミットメント受信装置に送信する。コミットメント受信装置において、コミットメント情報ａを受信し、（ｔａｇ，Ｃ，ａ）を格納しておき、（ｔａｇ，ｍ，ｚ）を受信すると、関係Ｒprivpk,tagのΣ−プロトコルに対するΣｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）を用いて、秘匿情報ｍが変更されていないかを判定する。
【発明の効果】
【００２５】
本発明は、従来の署名のみに基づかずに、公開検証可能なタグベース鍵カプセル化メカニズムを用いて、新しいＳＳＴＣ方式を構成するため、従来の署名が破られた場合にも安全であるという効果を奏する。
【図面の簡単な説明】
【００２６】
【図１】コミットメントシステム１の構成例を示す図。
【図２】コミットメントシステム１の処理フローを示す図。
【図３】第三者装置１１の機能構成例を示すブロック図。
【図４】第三者装置１１の処理フローを示す図。
【図５】コミットメント受信装置１５の機能構成例を示すブロック図。
【図６】コミットメント受信装置１５の処理フローを示す図。
【図７】コミットメント生成装置１３の機能構成例を示すブロック図。
【図８】コミットメント生成装置１３の処理フローを示す図。
【発明を実施するための形態】
【００２７】
以下、本発明の実施形態について、説明する。
【００２８】
＜定義＞
まず、本形態で使用する用語や記号を定義する。
【００２９】
｛０，１｝ｋは、ｋビット長のバイナリ系列（データ）の集合を意味し、｛０，１｝＊は全てのバイナリ系列、つまり、｛０，１｝＊＝∪ｋ≧０｛０，１｝ｋを表す。
確率的アルゴリズムＭは，入力ｘ∈｛０；１｝＊とＭの内部乱数ｒの二入力関数である。
ｙ＝Ｍ（ｘ；ｒ）は、入力ｘ、乱数ｒのときの出力がｙであることを意味する。
ｙ←Ｍ（ｘ）は、Ｍの入力ｘでの確率的試行を表す。例えば、Ｐｒ［ｙ←Ｍ（ｘ）：ｙ＝１］＜１／２とは、乱数ｒに従って出力された確率変数ｙが、１である確率が１／２未満であることを意味する。
【００３０】
「Ａ（Ｘ）の試行の後、Ｂ（Ｙ）の試行が起き、さらに…」のような確率的試行の時系列的並びを、ａ←Ａ（Ｘ）；ｂ←Ｂ（Ｙ）；…のように書く。
【００３１】
Ｐｒ［ａ←Ａ；ｂ←Ｂ：ｅｖｅｎｔ］は、確率的試行ａ←Ａ；ｂ←Ｂの下での事象ｅｖｅｎｔの条件付き生起確率を表す。なお、記述を短くするため、Ｐｒ［ｙ←Ｍ（ｘ）：ｙ＝１］のかわりにＰｒ［Ｍ（ｘ）＝１］と書く場合がある。
【００３２】
なお、確定的（deterministic）なアルゴリズムは、内部コインの無い確率的アルゴリズムと考えてもよい。
【００３３】
［タグベース鍵カプセル化メカニズム（Ｔａｇ−ＫＥＭ: Tag-based Key Encapsulation Mechanisim）］
Π＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）が、Ｔａｇ−ＫＥＭ（参考文献１及び２参照）であるとは、Πが次のような性質１〜性質４を満たすアルゴリズムの集合であるときをいう。
（参考文献１）：V. Shoup, "A proposal for an ISO standard for public key encryption", Technical report, December 2001, Cryptology ePrint Archive, Report 2001/112
(参考文献２)：M. Abe, R. Gennaro, and K. Kurosawa, "Tag-KEM/DEM: A new framework for hybrid encryption", Journal of Cryptology, 2008, Volume 21, Number 1, p.97-130
【００３４】
（性質１）（ｐｋ，ｓｋ）←Ｇｅｎ（１ｎ）：鍵生成アルゴリズムＧｅｎは、セキュリティパラメータｎを入力にとり、公開鍵・秘密鍵の組（ｐｋ，ｓｋ）を出力する確率的アルゴリズムである。
（性質２）（Ｃ，Ｋ）←Ｅｎｃ（ｐｋ，ｔａｇ）。暗号化アルゴリズムＥｎｃは、公開鍵ｐｋとタグ情報ｔａｇ∈｛０；１｝＊を入力とし、乱数ｒ∈Ｇｒを内部発生させ、暗号文Ｃと鍵Ｋを計算し出力する確率的アルゴリズムである。
（性質３）復号アルゴリズムＤｅｃは、秘密鍵ｓｋ、タグ情報ｔａｇ及び暗号文Ｃを入力としてとり、鍵Ｋ＝Ｄｅｃ（ｓｋ，ｔａｇ，Ｃ）を計算する確定的アルゴリズムである。
（性質４）全てのｎ∈Ｎ，全てのｔａｇ∈｛０，１｝＊に対して、
Pr[(pk,sk)←Gen(1n);(C,K)←Enc(pk,tag):Dec(sk,tag,C)=K]=1
である。
【００３５】
［暗号文と鍵との間のＮＰ関係と公開検証可能性］
Ｔａｇ−ＫＥＭ Πに関する以下のようなＮＰ関係を定義する。
【００３６】
【数５】
【００３７】
暗号文Ｃ∈｛０；１｝＊が、対応する鍵Ｋが存在する真の暗号文である（すなわち、あるＫが存在して（Ｃ，Ｋ）∈Ｒｐｒｉｖｐｋ，ｔａｇ）かを、公開鍵ｐｋとｔａｇのみで検証できるとき、Ｔａｇ−ＫＥＭ Πは「公開検証可能」という。
【００３８】
［Σ―プロトコル］
Ｒ＝｛（ｘ，ｗ）｝をＮＰ関係とする。関係Ｒから定義される言語をＬＲ（:=｛ｘ｜∃ｗ ｓ．ｔ．（ｘ，ｗ）∈Ｒ｝）とする。但し、「Ａ:=Ｂ」は「Ａという記号の意味するところをＢと定義する」ことを意味する。関係ＲのΣ−プロトコル（非特許文献８参照）とは、証明者と検証者からなる三交信の次のような認証プロトコルである。なお、（ｘ，ｗ）∈Ｒとする。ｘを証明者と検証者への共通入力として、証明者は、さらにｗを与えられる。
（１）証明者は、乱数ｒａを選び、第一メッセージａ＝Σｃｏｍ（ｘ，ｗ；ｒａ）を計算し、検証者に送る。
（２）検証者は、第二メッセージの乱数ｃ←ＲΣｃｈを選び証明者に送り返す。但し、Ａ←ＲＢは、集合ＢからランダムにＡを選択することを意味する。なお、Σｃｈはチャレンジｃ（例えば、乱数）を生成または選択するアルゴリズムである。
（３）証明者は、第三メッセージｚ＝Σａｎｓ（ｘ，ｗ，ｒａ，ｃ）を計算し、検証者に送る。第三メッセージｚはチャレンジｃに対する証明者の返答であり、返答生成アルゴリズムΣａｎｓを用いて生成する。
【００３９】
検証者は、ｂ＝Σｖｒｆｙ（ｘ，ａ，ｃ，ｚ）を計算して出力する。Σｖｒｆｙは、検証アルゴリズムであり、ｂ＝１であれば、検証者は、証明者の一連の認証行為を受理したという意味でありそれ以外の値であれば、否決したという意味を持っている。第一メッセージａと返答ｚとが、ｗを知っている証明者により、それぞれ第一メッセージ生成アルゴリズムΣｃｏｍと返答生成アルゴリズムΣａｎｓを用いて生成されたものであれば、ｂ＝１となる。Σ−プロトコルは以下の性質を満たす。
［完全性］∀ra,∀c∈Σch[Σvrfy(x,Σcom(x,w;ra),c,Σans(x,w,ra,c))=1]
［特別健全性］
【００４０】
【数６】
【００４１】
つまり、ｘが言語ＬＲに元として含まれないとき、ａに対して、ｚが存在するようなｃは、唯一に決まる。さらに、ｃ≠ｃ’のとき、二つの受理される履歴（ａ，ｃ，ｚ）と（ａ，ｃ’，ｚ’）から、（ｘ，ｗ）∈Ｒを満たすｗが必ず計算できる。
【００４２】
［正直な検証者に対する特別ゼロ知識］∀ｘ∈ＬＲ，∀ｃ∈Σｃｈに対して、検証者に受理される（ａ，ｃ，ｚ）←ｓｉｍΣ（ｘ，ｃ）を作ることができる。さらに、ｃをΣｃｈからランダムに選び、ｓｉｍΣに入力して作った、（ａ，ｃ，ｚ）は、正直な証明者が正直な検証者と実行した履歴と同分布になる。
【００４３】
なお、任意のＮＰ関係に対して、必ずΣ−プロトコルが存在することはすでに知られている（参考文献３参照）。
（参考文献３）：O. Goldreich, S. Micali, and A. Wigderson, "Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems", Journal of the ACM, 1991, 1(38), p.691-729
【００４４】
＜第一実施形態＞
＜コミットメントシステム１＞
図１及び図２を用いて第一実施形態に係るコミットメントシステム１の処理概要を説明する。コミットメントシステム１は、第三者装置１１とコミットメント生成装置１３とコミットメント受信装置１５とからなり、これらの各装置は、例えばインターネットである通信網１２を介して相互に通信可能とされている。
【００４５】
Π＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）を公開検証可能なタグベース鍵カプセル化メカニズムとする。関係Ｒprivpk,tagはΠにより定義される。関係Ｒprivpk,tagはＮＰ関係であり、
【００４６】
【数７】
【００４７】
とする。Πと関係Ｒprivpk,tagに対するΣ−プロトコルからコミットメントシステム１を構成する。
【００４８】
第三者装置１１はセキュリティパラメータｎを入力とし（ｓ１）、鍵生成アルゴリズムＧｅｎを用いて、秘密鍵ｓｋと公開鍵ｐｋを生成する（ｓ２）。この公開鍵ｐｋを共通参照データとする。そして、少なくともコミットメント生成装置１３とコミットメント受信装置１５が共通参照データｃｒｓを利用可能な状態で、第三者装置１１は共通参照データｃｒｓを格納しておく。
【００４９】
コミットメント生成装置１３とコミットメント受信装置１５は、タグ情報ｔａｇを取得する（ｓ３）。ｔａｇ情報とは、コミットメント生成装置１３とコミットメント受信装置１５とが共に知っている情報であり、例えば、プロセスのセッションＩＤ等である。なお、ｔａｇ情報は後述する第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成する前にコミットメント生成装置１３とコミットメント受信装置１５とが共に取得すればよく、どのような取得方法を用いてもよい。
【００５０】
さらに、コミットメント受信装置１５は、共通参照データｃｒｓを取得する（ｓ４）。コミットメント受信装置１５は暗号化アルゴリズムＥｎｃに対し共通参照データｃｒｓとタグ情報ｔａｇを用いて、第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成し（ｓ５）、第一暗号文Ｃをコミットメント生成装置１３に送信する（ｓ６）。
【００５１】
コミットメント生成装置１３はコミットする秘匿情報ｍを入力される（ｓ７）。さらに、コミットメント生成装置１３は第一暗号文Ｃを受信する（ｓ８）。さらに、コミットメント生成装置１３は、共通参照データｃｒｓを取得する（ｓ９）。
【００５２】
コミットメント生成装置１３は共通参照データｃｒｓとタグ情報ｔａｇを用いて、第一暗号文Ｃが真の暗号文であるか否かを検証する（ｓ１０）。真の暗号文である場合には、コミットメント生成装置１３は、関係Ｒprivpk,tagのΣ−プロトコルに対する（ａ，ｚ）←ｓｉｍΣ（Ｃ，ｍ）を計算し（ｓ１１）、コミットメント情報ａをコミットメント受信装置１５に送信する（ｓ１２）。なお、関係Ｒprivpk,tagのΣ−プロトコルに対するｓｉｍΣとは、前述のΣ―プロトコルにおける秘密ｗを知らずに、第一メッセージａ（本実施形態におけるコミットメント情報ａ）を生成し、返答ｚ（本実施形態におけるコミットを開封するときの証拠の一部ｚ）を生成するアルゴリズムである。
【００５３】
コミットメント受信装置１５は、コミットメント情報ａを受信し（ｓ１３）、（ｔａｇ，Ｃ，ａ）を格納しておく（ｓ１４）。
【００５４】
コミットメント開封装置１６は、（ｃｒｓ，ｔａｇ，Ｃ，ｍ，ａ，ｚ）をコミットメント生成装置１３等から受け取り（ｓ１５）、安全に保管しておく。そして、情報ｍを開示するタイミングになると、（ｔａｇ，ｍ，ｚ）をコミットメント受信装置１５に送信する（ｓ１６）。なお、コミットメント生成装置１３とコミットメント開封装置１６との間は安全に通信可能とされている。また、コミットメント開封装置１６を設けず、コミットメント生成装置１３から直接、（ｔａｇ，ｍ，ｚ）をコミットメント受信装置１５に送信する構成としてもよい。
【００５５】
コミットメント受信装置１５は、（ｔａｇ，ｍ，ｚ）を受信すると（ｓ１７）、Σ―プロトコルに対するΣｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）を用いて、コミットメント情報ａを受信した時点から秘匿情報ｍが変更されていないかを判定する（ｓ１８）。なお、前述のΣ―プロトコルにおいて検証アルゴリズムΣｖｒｆｙは証明者がｗを知っているか否かを検証するが、本実施形態においてΣ―プロトコルに対するΣｖｒｆｙはコミットメント情報ａを受信した時点から秘匿情報ｍが変更されていないかを判定する。言い換えると、本実施形態におけるΣ―プロトコルに対するΣｖｒｆｙは、秘匿情報ｍに対するコミットメント情報ａ及びコミットを開封するときの証拠の一部ｚが正しいか否かを検証するアルゴリズムである。
【００５６】
以下、詳細を説明する。まず、第一実施形態において例えば、以下のＴａｇ−ＫＥＭ Π＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）を利用することができる。
【００５７】
＜Ｔａｇ−ＫＥＭ Π＞
ＧとＧＴを素数位数ｑのアーベル群とする。ｅ：Ｇ×Ｇ→ＧＴを非退化な双線形写像とする。ｇをＧの生成元とする。Ｚ／ｑＺを０以上ｑ未満の整数の集合とする。双線形性より、ｘ，ｙ∈Ｇ、ａ，ｂ∈Ｚ／ｑＺに対して、ｅ（ｘａ，ｙｂ）＝ｅ（ｘ，ｙ）ａｂが成り立つ。非退化性より、ｅ（ｇ，ｇ）は、ＧＴの生成元である。Ｈ：｛０，１｝＊→Ｚ／ｑＺのハッシュ関数とする。ｏｔΣ＝（ｏｔＫＧｅｎ，ｏｔＳｉｇｎ，ＯｔＶｒｆｙ）を任意の使い捨て署名とする（参考文献４参照）。
（参考文献４）：Leslie Lamport, "Constructing digital signatures from one-way functions", Technical Report SRI-CSL-98, SRI International Computer Science Laboratory, October 1979
・Ｇｅｎ（１ｎ）：ｘ，ｙ←ＲＺ／ｑＺ；Ｘ:=ｇｘ；Ｙ:=ｇｙ；ｐｋ＝（ｇ，Ｘ，Ｙ，Ｈ）、ｓｋ＝（ｐｋ，ｘ，ｙ）として、（ｐｋ，ｓｋ）を出力する。
・Ｅｎｃ（ｐｋ，ｔａｇ）：（ｏｔｖｋ，ｏｔｓｋ）←ｏｔＫＧｅｎ（１ｋ）；σ←ｏｔＳｉｇｎ（ｏｔｓｋ，ｔａｇ）；ｒ←Ｚ／ｑＺ；ｔ:=Ｈ（ｏｔｖｋ，ｇｒ）；Ｃ:=（σ，ｏｔｖｋ，ｇｒ，（ＸｔＹ）ｒ）；Ｋ:=Ｘｒ；（Ｃ，Ｋ）を出力する。
・Ｄｅｃ（ｓｋ，ｔａｇ，Ｃ）：Ｃ＝（σ，ｏｔｖｋ，ｕ，τ）をσ，ｏｔｖｋ，ｕ，τに分解し、もしｏｔＶｒｆｙ（ｏｔｖｋ，ｔａｇ，σ）≠１ならば、復号を中止し、それ以外の場合、ｔ:=Ｈ（ｏｔｖｋ，ｕ）を計算する。もしｕｘｔ＋ｙ≠τ ならば、復号を中止し、それ以外の場合、Ｋ:=ｕｘ；Ｋを出力する。
【００５８】
なお、第一実施形態において例えば、以下の使い捨て署名ｏｔΣ（ｏｔＫＧｅｎ，ｏｔＳｉｇｎ，ｏｔＶｒｆｙ）を利用することができる。
【００５９】
＜使い捨て署名ｏｔΣ＞
Ｇ２を素数位数ｑ２のアーベル群とする。Ｈ２：｛０，１｝＊→Ｚ／ｑ２Ｚのハッシュ関数とする。ｑ２、Ｇ２、Ｈ２は、Ｔａｇ−ＫＥＭΠで用いるｑ，Ｇ，Ｈと同じであってもよいし、異なっていてもよい。以下において、添え字ｓ１、ｓ２、ｗ１、ｗ２、ｚ１、ｚ２、Ｈ２は、ｓ１、ｓ２、ｗ１、ｗ２、ｚ１、ｚ２、Ｈ２を意味する。
・ｏｔＫＧｅｎ（１ｋ）：ｇ１，ｇ２←ＲＧ２；ｓ１，ｓ２，ｗ１，ｗ２←ＲＺ／ｑ２Ｚ；ｂ:=ｇ１ｗ１ｇ２ｗ２；ｈ:=ｇ１ｓ１ｇ２ｓ２；ｏｔｖｋ:=（ｇ１，ｇ２，ｈ，ｂ）；ｏｔｓｋ:=（ｏｔｖｋ，ｓ１，ｓ２，ｗ１，ｗ２）；（ｏｔｖｋ，ｏｔｓｋ）を出力する。
・ｏｔＳｉｇｎ（ｏｔｓｋ，ｍ）：ｃ:=Ｈ（ｏｔｖｋ，ｍ）；ｚ１:=ｗ１＋ｃ・ｓ１ ｍｏｄ ｑ２；ｚ２:=ｗ２＋ｃ・ｓ２ ｍｏｄ ｑ２；σ:=（ｚ１，ｚ２）を出力する。
・ｏｔＶｒｆｙ（ｏｔｖｋ，ｍ，σ）：ｇ１ｚ１ｇ２ｚ２＝ｂｈＨ２（ｏｔｖｋ，ｍ）のときに限り、１を出力する。
【００６０】
＜共通参照データｃｒｓの生成及び取得＞
図３及び図４を用いて共通参照データｃｒｓの生成について説明する。第三者装置１１は、入力部１１１を介してセキュリティパラメータｎを取得し（ｓ１１１）、鍵生成部１１２において、Ｔａｇ−ＫＥＭの鍵生成アルゴリズムＧｅｎ（１ｎ）により（ｓｋ，ｐｋ）を生成する（ｓ１１２）。例えば、Ｚ／ｑＺからランダムにｘとｙを選択し、Ｘ=ｇｘとＹ=ｇｙを求め、ｇとＸとＹとＨとの組を公開鍵ｐｋとして生成する。この公開鍵ｐｋを共通参照データｃｒｓとする。ｐｋとｘとｙとの組を秘密鍵として生成する。そして、少なくともコミットメント生成装置１３とコミットメント受信装置１５が共通参照データｃｒｓを利用可能な状態で、共通参照データｃｒｓは記憶部１１４に記憶される。また、第三者装置１１は、秘密鍵ｓｋを記憶部１１４に安全に格納してもよいし、破棄してもよい（ｓ１１３）。なお、第三者装置１１は、制御部１１５の制御のもと上記処理を行う。なお、本実施形態では、一つの共通参照データｃｒｓを繰り返し使う。
【００６１】
コミットメント受信装置１５は、制御部１５５（図５）の制御のもと、出力部１５６を介して、第三者装置１１に対し、公開鍵ｐｋを送信するように要求する。第三者装置１１の制御部１１５は、入力部１１１を介して要求を受信し、記憶部１１４から公開鍵ｐｋを取り出し、出力部１１６を介して、コミットメント受信装置１５に送信する。コミットメント受信装置１５は、入力部１５１を介して公開鍵ｐｋを受信し、記憶部１５４に格納する（図６、ｓ１５１）。コミットメント生成装置１３も同様に制御部１３５（図７）の制御のもと、出力部１３６を介して公開鍵ｐｋを要求し、入力部１３１を介して公開鍵ｐｋを受信し、記憶部１３４に格納する（図８、ｓ１３１）。
【００６２】
＜第一暗号文Ｃ及び第一鍵Ｋの生成＞
コミットメント受信装置１５は、入力部１５１を介してセキュリティパラメータｋを取得する（図６、ｓ１５２）。コミットメント受信装置１５は、暗号化部１５２（図５）において、Ｔａｇ−ＫＥＭ Πの暗号化アルゴリズムＥｎｃを実行し、第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成する（ｓ１５３）。
【００６３】
暗号化部１５２内の署名鍵検証鍵生成部１５２ａは、セキュリティパラメータｋを用いて、鍵生成アルゴリズムｏｔＫＧｅｎにより、署名鍵ｏｔｓｋと検証鍵ｏｔｖｋを生成する。例えば、署名鍵検証鍵生成部１５２ａは、Ｇ２からランダムにｇ１、ｇ２を選択し、Ｚ／ｑ２Ｚからランダムにｓ１、ｓ２、ｗ１、ｗ２を選択する。さらに、ｂ＝ｇ１ｗ１ｇ２ｗ２とｈ＝ｇ１ｓ１ｇ２ｓ２を求め、ｇ１とｇ２とｈとｂとの組を検証鍵ｏｔｖｋとし、検証鍵ｏｔｖｋとｓ１とｓ２とｗ１とｗ２との組を署名鍵ｏｔｓｋとして求める。なお、ハッシュ関数ＨとＨ２が異なる場合には、検証鍵ｏｔｖｋがハッシュ関数Ｈ２を含む構成とする。
【００６４】
暗号化部１５２内の署名生成部１５２ｂは、タグ情報ｔａｇと生成した署名鍵ｏｔｓｋを用いて、署名アルゴリズムｏｔＳｉｇｎにより、電子署名σを生成する。例えば、検証鍵ｏｔｖｋとタグ情報ｔａｇをハッシュ関数Ｈ２の入力として、ｃを求める。さらに、（ｚ１＝ｗ１＋ｃ・ｓ１ ｍｏｄ ｑ２）と（ｚ２＝ｗ２＋ｃ・ｓ２ ｍｏｄ ｑ２）とを求め、ｚ１とｚ２との組を電子署名σとする。
【００６５】
暗号化部１５２内の第一鍵第一暗号文生成部１５２ｃは、公開パラメータｐｋ（＝ｇ，Ｘ，Ｙ，Ｈ）と前記検証鍵ｏｔｖｋを用いて、暗号化アルゴリズムＥｎｃにより第一暗号文Ｃと第一鍵Ｋを生成する。例えば、Ｚ／ｑＺからランダムにｒを選択し、Ｋ＝Ｘｒを求める。さらに、ｇｒを求め、検証鍵ｏｔｖｋとｇｒをハッシュ関数Ｈの入力として、ｔを求める。（ＸｔＹ）ｒを計算し、電子署名σと検証鍵ｏｔｖｋとｇｒと（ＸｔＹ）ｒとの組を第一暗号文Ｃとする。
【００６６】
コミットメント受信装置１５は、第一暗号文Ｃとタグ情報ｔａｇを関連付けて記憶部１５４に記憶し、さらに、第一暗号文Ｃを出力部１５６を介してコミットメント生成装置１３に送信する（ｓ１５４）。コミットメント受信装置１５は、署名鍵ｏｔｓｋを記憶部１５４に安全に格納してもよいし、破棄してもよい。
【００６７】
＜第一暗号文Ｃの検証＞
コミットメント生成装置１３は、入力部１３１（図７）を介して、第一暗号文Ｃ＝（σ，ｏｔｖｋ，ｕ，τ）を受信する（ｓ１３２）。
【００６８】
暗号文検証部１３２において、まず、電子署名σと検証鍵ｏｔｖｋとタグ情報ｔａｇを用いて、ｏｔＶｒｆｙ（ｏｔｖｋ，ｔａｇ，σ）により、電子署名σが正当か否かを検証する（ｓ１３３）。例えば、電子署名σ＝（ｚ１，ｚ２）とｏｔｖｋ＝（ｇ１，ｇ２，ｈ，ｂ）を用いて、ｇ１ｚ１ｇ２ｚ２を求める。さらに、検証鍵ｏｔｖｋとタグ情報ｔａｇを入力とし、Ｈ２（ｏｔｖｋ，ｔａｇ）を求め、検証鍵に含まれるｂを用いて、ｂｈＨ２（ｏｔｖｋ，ｔａｇ）を求める。求めたｇ１ｚ１ｇ２ｚ２とｂｈＨ２（ｏｔｖｋ，ｔａｇ）とが同一の場合に電子署名σが正当であると判断する。つまり、ｏｔＶｒｆｙは１を返す。ｇ１ｚ１ｇ２ｚ２とｂｈＨ２（ｏｔｖｋ，ｔａｇ）とが異なる場合には、電子署名が正当ではないと判断し、否決する（ｓ１３７）。つまり、ｏｔＶｒｆｙは１以外の値を返す。コミットメント受信装置１５以外の生成した電子署名を否決することができる。
【００６９】
電子署名σが正当である場合には、暗号文検証部１３２は、記憶部１５４から公開パラメータｐｋ＝（ｇ，Ｘ，Ｙ，Ｈ）を取り出し、ハッシュ関数Ｈと第一暗号文Ｃに含まれるｕと検証鍵ｏｔｖｋを用いて、ｔ＝Ｈ（ｏｔｖｋ，ｕ）を求める。さらに、公開パラメータｐｋ＝（ｇ，Ｘ，Ｙ，Ｈ）と第一暗号文Ｃに含まれるτを用いて、ｅ（ｕ，ＸｔＹ）＝ｅ（ｇ，τ）が成り立つか否か検証する（ｓ１３４）。受信した第一暗号文Ｃに含まれるｕとτが、それぞれ、コミットメント受信装置１５で生成されるｇｒ、（ＸｔＹ）ｒと同一であれば、前記式が成り立つ。ｅ（ｕ，ＸｔＹ）＝ｅ（ｇ，τ）が成り立つ場合には、受信した第一暗号文Ｃが真の暗号文であると判定する。ｅ（ｕ，ＸｔＹ）＝ｅ（ｇ，τ）が成り立たない場合には、第一暗号文Ｃが真の暗号文ではないと判断し、否決する（ｓ１３７）。この処理により、
【００７０】
【数８】
【００７１】
第一暗号文Ｃが言語ＬＲに元として含まれない場合（Ｃが真の暗号文でない場合）に処理を中止することができる。
【００７２】
＜コミットメント情報の生成＞
第一暗号文Ｃが真の暗号文であると判定した場合、コミットメント情報生成部１３８は、第一暗号文Ｃと秘匿情報ｍを用いて、関係Ｒprivpk,tagのΣ−プロトコルに対する（ａ，ｚ）←ｓｉｍΣ（Ｃ，ｍ）を計算する（ｓ１３５）。例えばコミットメント情報生成部１３８は、Ｇから単位元を除いた群Ｇ＊からランダムにＫ＾を選択し、Ｚ／ｑＺからランダムにｚを選択する。さらに、ａ＾＝ｅ（ｇ，Ｋ＾）ｚ・ｅ（ｕ，Ｘ）−ｍを計算し、Ｋ＾とａ＾との組をコミットメント情報ａとして生成する。コミットメント生成装置１３は、出力部１３６を介して、生成したコミットメント情報ａをコミットメント受信装置１５に送信する（ｓ１３６）。
【００７３】
コミットメント生成装置１３とコミットメント開封装置１６が同一装置の場合、（ｃｒｓ，ｔａｇ，Ｃ，ｍ，ａ，ｚ）を記憶部１３４に安全に記憶しておく。別装置の場合には、コミットメント生成装置１３は上記情報をコミットメント開封装置１６に出力部１３６を介して送信する。
【００７４】
＜コミットメント情報の受信及び開封処理＞
コミットメント受信装置１５は、入力部１５１（図５）を介して、コミットメント情報ａを受信し（図６、ｓ１５５）、記憶部１５４に（ｔａｇ，Ｃ）と関連付けて記憶しておく（ｓ１５６）。
【００７５】
さらに、コミットメント受信装置１５は、入力部１５１を介して、コミットメント生成装置１３またはコミットメント開封装置１６から（ｔａｇ，ｍ，ｚ）を受信する（ｓ１５７）。コミットメント受信装置１５の開封部１５９において、Σｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）を用いて、ｅ（ｇ，Ｋ＾）ｚ＝ａ＾・ｅ（ｕ，Ｘ）ｍが成り立つか否か判定する（ｓ１５８）。例えば、公開パラメータｐｋに含まれるｇとＸ、ａ＝（Ｋ＾，ａ＾）、第一暗号文Ｃに含まれるｕ，ｚ及びｍを用いて、ｅ（ｇ，Ｋ＾）ｚ＝ａ＾・ｅ（ｕ，Ｘ）ｍが成り立つか否か判定する。成り立つ場合には、Σｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）は１を返し、受信した秘匿情報ｍは、コミットメント情報ａ受信時点から変更されていないと判定し、受理する（ｓ１５９）。ｅ（ｇ，Ｋ＾）ｚ＝ａ＾・ｅ（ｕ，Ｘ）ｍが成り立たない場合、Σｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）は１以外の値を返し、少なくともｍかｚかの何れかに変更があったものとし、否決する（ｓ１６０）。
【００７６】
＜効果＞
このような構成とすることで、従来の署名が破られた場合にも安全なコミットメント方式とすることができる。
【００７７】
さらに、本実施形態では、公開検証可能なＴａｇ−ＫＥＭに加え、電子署名を組合せているため、より安全性の高いコミットメント方式を実現している。
【００７８】
さらに、電子署名を使い捨て署名とすることで、従来（非特許文献３、４、５、６及び７参照）より効率のよいコミットメント方式を実現している。従来技術では、使い捨てでない電子署名から共通の変換法の基にＳＳＴＣを構成していた。これらの方式は署名方式から変換するので、コミットメントの効率は署名方式に依存する。現在知られている限りでは、安全な使い捨てでない署名方式は、安全な使い捨て署名や安全な暗号方式と比べてより強い家庭または大きなパラメータを使わなくてはならない。例えば、参考文献５記載の署名方式では、公開パラメータｐｋとして（ｇ、ｇ１，ｇ２，ｕ’，Ｈ，ｕ１，…，ｕｎ）を必要とする（例えばｎ＝１６０や２５６等）。一方、本実施形態では、公開検証可能なＴａｇ−ＫＥＭと使い捨て署名を組み合わせて用いることで、公開パラメータを（ｇ，Ｘ，Ｙ，Ｈ）とし、小さいパラメータで十分な安全性を実現することができる。
（参考文献５）：Brent Waters, "Efficient Identity-Based Encryption Without Random Oracles", EUROCRYPT 2005, LNCS, Springer, Heidelberg, 2005, vol. 3494, p.114-127.
【００７９】
また、本実施形態は、ＣＤＨ仮定に対しタイトであり、従来技術に比べ、セキュリティパラメータを短くすることができ、情報量、計算量を共に削減することができ、効率のよいコミットメントシステムを構成することができる。例えば、ＣＤＨ仮定がｋビットの場合、本実施形態ではｋ’（≒ｋ）ビットのセキュリティパラメータを用いることができる。一方、参考文献５記載の署名方式ではｋ”（≒１０２ｋ）ビットのセキュリティパラメータを用いなければ同程度の安全性を得ることはできない。
【００８０】
＜プログラム及び記憶媒体＞
上述した第三者装置、コミットメント生成装置及びコミットメント受信装置は、コンピュータにより機能させることもできる。この場合はコンピュータに、目的とする装置（各種実施例で図に示した機能構成をもつ装置）として機能させるためのプログラム、またはその処理手順（各実施例で示したもの）の各過程をコンピュータに実行させるためのプログラムを、ＣＤ−ＲＯＭ、磁気ディスク、半導体記憶装置などの記録媒体から、あるいは通信回線を介してそのコンピュータ内にダウンロードし、そのプログラムを実行させればよい。
【００８１】
＜その他の変形例＞
他の公開検証可能なＴａｇ−ＫＥＭや使い捨て署名を用いてもよい。Πと関係Ｒprivpk,tagに対するΣ−プロトコルからコミットメントシステムを構成すればよく、第一暗号文Ｃは必ずしも署名を含まなくともよい。また、使い捨てではない署名を用いてもよく、その場合も、従来技術と比べ安全なコミットメント方式となる。
【００８２】
本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【産業上の利用可能性】
【００８３】
本発明は、様々な暗号プロトコルに利用することができる。例えば、ゼロ知識証明、マルチパーティ計算、電子マネーまたは電子投票等に利用することができる。
【符号の説明】
【００８４】
１ コミットメントシステム
１１ 第三者装置
１２ 通信網
１３ コミットメント生成装置
１５ コミットメント受信装置
１６ コミットメント開封装置
１１１ 入力部
１１２ 鍵生成部
１１４ 記憶部
１１５ 制御部
１１６ 出力部
１３１ 入力部
１３２ 暗号検証部
１３４ 記憶部
１３５ 制御部
１３６ 出力部
１３８ コミットメント情報生成部
１５１ 入力部
１５２ 暗号化部
１５２ａ 署名鍵検証鍵生成部
１５２ｂ 署名生成部
１５２ｃ 第一鍵第一暗号文生成部
１５４ 記憶部
１５５ 制御部
１５６ 出力部
１５９ 開封部
【技術分野】
【０００１】
本発明は、秘匿情報をコミットしコミットメント情報を生成するコミットメント生成装置、コミットメント情報を受信するコミットメント受信装置、コミットメント装置とコミットメント受信装置とからなるコミットメントシステム、その方法及びプログラムに関する。
【背景技術】
【０００２】
暗号におけるコミットメントとは、電子的に行う「封じ手」のことである。コミットメントは、送信者(sender)と、受信者(receiver)に分かれる。送信者は、受信者に情報ｍを秘匿しながらも「委託」(commit)する。委託された情報ｍは、後に開示することになるが、委託する時点で決定した値ｍから変更することは出来ない。この性質を「秘匿性」(hiding)と「拘束性」(binding)と言う。例えばコミットメントを利用して、電子的なジャンケンやコイン投げ（もちろん、将棋や碁の封じ手でも良い）を行うことができる。
【０００３】
コミットメントは、最も基本的な暗号プリミティブであるため、多くの暗号プロトコルの中で頻繁に利用される。近年では、暗号プロトコルをより現実の環境に近づけるため、複雑な組み合わせの中で利用した場合の安全性も求められている。このような複雑な組み合わせの中では、古典的安全性モデルで定義されたコミットメントでは、秘匿性と拘束性を満たせなくなってしまう。
【０００４】
複雑な組み合わせの中で利用するために頑強なコミットメント方式が必要となる。なお、あるコミットメント方式が、頑強(non-malleable)であるとは、そのコミットメント方式を同時にどのように実行しても、秘匿性と拘束性が満たされる場合をいう。
【０００５】
頑強なコミットメント方式よりもさらに強い安全性を持つ汎用結合コミットメントというものもある。汎用結合性とは、コミットメントに限ったものではなく、多くの暗号方式の上で定義できる。暗号方式が汎用結合であると、他の汎用結合な暗号方式と組み合わせて実行しても、お互いの単独で満たされる安全性が確保される。つまり、汎用結合である暗号方式は、いかなる汎用結合な暗号方式と組み合わせても汎用結合な暗号方式になる（非特許文献１及び２参照）。
【０００６】
コミットメント方式の中には、送信者と受信者の双方がアクセス可能な（送信者、受信者の何れでもない第三者により正しく作られた）共通情報(crs: common reference string)を必要とするものもある。技術的な問題により、この共通情報は、コミットメントごとに使い捨てなければいけない場合と、使い捨てずに同じ共通情報をずっと使える場合に分かれる。但し、共通情報をずっと使えるコミットメント方式の方がより実用性が高い。
【０００７】
さらに、落し戸付きコミットメント(trap-door commitment)方式は、落し戸(trap-door) を知っていれば、コミット時点とは異なる秘匿情報でコミットメント情報を開封できる。よって、落し戸付きコミットメント方式において、落し戸は、送信者には秘密である。
【０００８】
落し戸付きコミットメントであり、かつ頑強なコミットメント(non-malleable trap-door com-mitment)方式も存在する。落し戸付きコミットメントの頑強性は、non-malleability with respect to openingという名前で定義される（非特許文献３、４、５、６及び７参照）。
【０００９】
さらに、simulation-sound という定義を満たす落し戸付きコミットメント方式も存在する（非特許文献４及び６参照）。simulation-sound落し戸付きコミットメント(以下「ＳＳＴＣ」という)方式であれば、non-malleability with respect to open コミットメント方式、つまり頑強な落し戸付きコミットメントである。simulation-sound落し戸付きコミットメントは、Σ−プロトコル（非特許文献８参照）と呼ばれる標準的な認証プロトコルの安全性を大幅に上げることができ、さらに、非特許文献９の技術と組み合わせると、汎用結合可能コミットメントを構成できる。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】R. Canetti, "Universally composable security: A new paradigm for cryptographic protocols", In Proceedings of the 42th IEEE Annual Symposium on Foundations of Computer Science (FOCS'01), Oct 2001, p.136-145
【非特許文献２】Ran Canetti, "Universally composable security: A new paradigm for cryptograpic protocols", Technical report, Cryptology ePrint Archive, Report 2000/067, 2005, Preliminary version appeared in FOCS'01
【非特許文献３】Ivan Damgard and Jens Groth, "Non-interactive and reusable non-malleable commitment schemes", In STOC03, 2003, p.426-437
【非特許文献４】J.Groth, "Honest verifier Zero-Knowledge Arguments Applied", PhD thesis, Basic Resarch in Computer Science, University of Aarhus, 2004
【非特許文献５】J. A. Garay, P. Mackenzie, and K. Yang, "Strengthening zero-knowledge protocols using signatures", In Advances in Cryptology-EUROCRYPT 2003, Springer-Verlag, 2003, volume 2656 of Lecture Notes in Computer Science, p.177-194
【非特許文献６】P. D. MacKenzie and K. Yang, "On simulation-sound trapdoor commitments", In C. Cachin and J. Camenisch, editors, Advances in Cryptology - EUROCRYPT 2004, Springer-Verlag, 2004, volume 3027 of Lecture Notes in Computer Science, p.382-400
【非特許文献７】R. Gennaro, "Multi-trapdoor commitments and their applications to proofs of knowledge secure under concurrent man-in-the-middle attacks", In Advances in Cryptology - CRYPTO'04, 2004, volume 3152 of Lecture Notes in Computer Science, p.220-236
【非特許文献８】R. Cramer, I. Damgard, and B. Schoenmakers, "Proofs of partial knowledge and simplied design of witness hiding protocols", In Y. G. Desmedt, editor, Advances in Cryptology - CRYPTO'94, Springer-Verlag, 1994, volume 839 of Lecture Notes in Computer Science, p.174-187
【非特許文献９】I. Damgard and J. Nielsen, "Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor", In Advances in Cryptology - CRYPTO2002, 2002, p.581-596
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、非特許文献３、４、５、６及び７記載の従来技術は、全て使い捨てでない署名から共通の変換方法の基にsimulation-sound落し戸付きコミットメント(ＳＳＴＣ)を構成する。そのため、従来の署名が破られると、同時に従来技術のコミットメント方式も破られる可能性がある。
【００１２】
本発明では、公開検証可能なタグベース鍵カプセル化メカニズムを用いて、新しいＳＳＴＣ方式のコミットメントシステム、コミットメント生成装置、コミットメント受信装置、その方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記の課題を解決するために、本発明の第一の態様によれば、コミットメントシステムはコミットメント生成装置とコミットメント受信装置からなる。公開検証可能なタグベース鍵カプセル化メカニズムをΠ＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）とし、鍵生成アルゴリズムＧｅｎを用いて生成される公開鍵をｐｋとし、コミットメント生成装置とコミットメント受信装置とが共に知っているタグ情報をｔａｇとし、ｒを乱数とし、暗号化アルゴリズムＥｎｃに対し公開鍵ｐｋとタグ情報ｔａｇを与えて得られる第一暗号文をＣとし、第一鍵をＫとし、Πが定める関係Ｒprivpk,tagを
【００１４】
【数１】
【００１５】
とする。コミットメント受信装置は暗号化アルゴリズムＥｎｃに対し公開鍵ｐｋとタグ情報ｔａｇを与え、第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成し、第一暗号文Ｃをコミットメント生成装置に送信する。コミットを開封するときの証拠の一部をｚとし、コミットする秘匿情報をｍとし、コミットメント生成装置は第一暗号文Ｃを受信し、公開鍵ｐｋとタグ情報ｔａｇを用いて、第一暗号文Ｃが真の暗号文であるか否かを検証し、真の暗号文である場合には、関係Ｒprivpk,tagのΣ−プロトコルに対する（ａ，ｚ）←ｓｉｍΣ（Ｃ，ｍ）を計算し、コミットメント情報ａをコミットメント受信装置に送信する。コミットメント受信装置はコミットメント情報ａを受信し、（ｔａｇ，Ｃ，ａ）を格納しておき、（ｔａｇ，ｍ，ｚ）を受信すると、関係Ｒprivpk,tagのΣ−プロトコルに対するΣｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）を用いて、秘匿情報ｍが変更されていないかを判定する。
【００１６】
上記の課題を解決するために、本発明の第二の態様によれば、コミットメント生成装置は秘匿情報ｍをコミットし、コミットメント情報ａを生成する。公開検証可能なタグベース鍵カプセル化メカニズムをΠ＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）とし、鍵生成アルゴリズムＧｅｎを用いて生成される公開鍵をｐｋとし、当該コミットメント生成装置とコミットメント情報ａを受信するコミットメント受信装置とが共に知っているタグ情報をｔａｇとし、ｒを乱数とし、暗号化アルゴリズムＥｎｃに対し公開鍵ｐｋとタグ情報ｔａｇを与えて得られる第一暗号文をＣとし、第一鍵をＫとし、Πが定める関係Ｒprivpk,tagを
【００１７】
【数２】
【００１８】
とし、コミットを開封するときの証拠の一部をｚとする。第一暗号文Ｃを受信し、公開鍵ｐｋとタグ情報ｔａｇとを用いて、受信した第一暗号文Ｃが真の暗号文であるか否かを検証し、真の暗号文である場合には、関係Ｒprivpk,tagのΣ−プロトコルに対する（ａ，ｚ）←ｓｉｍΣ（Ｃ，ｍ）を計算し、コミットメント情報ａをコミットメント受信装置に送信する。
【００１９】
上記の課題を解決するために、本発明の第三の態様によれば、コミットメント受信装置は、コミットメント情報ａを受信する。公開検証可能なタグベース鍵カプセル化メカニズムをΠ＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）とし、鍵生成アルゴリズムＧｅｎを用いて生成される公開鍵をｐｋとし、秘匿情報ｍをコミットし、コミットメント情報ａを生成するコミットメント生成装置と当該コミットメント受信装置とが共に知っているタグ情報をｔａｇとし、ｒを乱数とし、暗号化アルゴリズムＥｎｃに対し公開鍵ｐｋとタグ情報ｔａｇを与えて得られる第一暗号文をＣとし、第一鍵をＫとし、Πが定める関係Ｒprivpk,tagを
【００２０】
【数３】
【００２１】
とする。暗号化アルゴリズムＥｎｃに対し公開鍵ｐｋとタグ情報ｔａｇを与え、第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成し、第一暗号文Ｃをコミットメント受信装置に送信し、コミットを開封するときの証拠の一部をｚとし、コミットメント生成装置からコミットメント情報ａを受信し、（ｔａｇ，Ｃ，ａ）を格納しておき、（ｔａｇ，ｍ，ｚ）を受信すると、Σ−プロトコルに対するΣｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）を用いて、秘匿情報ｍが変更されていないかを判定する。
【００２２】
上記の課題を解決するために、本発明の第四の態様によれば、コミットメント方法は、コミットメント生成装置とコミットメント受信装置を用いる。公開検証可能なタグベース鍵カプセル化メカニズムをΠ＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）とし、鍵生成アルゴリズムＧｅｎを用いて生成される公開鍵をｐｋとし、コミットメント生成装置とコミットメント受信装置とが共に知っているタグ情報をｔａｇとし、ｒを乱数とし、暗号化アルゴリズムＥｎｃに対し公開鍵ｐｋとタグ情報ｔａｇを与えて得られる第一暗号文をＣとし、第一鍵をＫとし、Πが定める関係Ｒprivpk,tagを
【００２３】
【数４】
【００２４】
とする。コミットメント受信装置において、暗号化アルゴリズムＥｎｃに対し公開鍵ｐｋとタグ情報ｔａｇを与え、第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成し、第一暗号文Ｃをコミットメント生成装置に送信する。コミットを開封するときの証拠の一部をｚとし、コミットする秘匿情報をｍとし、コミットメント生成装置が、第一暗号文Ｃを受信し、コミットメント生成装置において、公開鍵ｐｋとタグ情報ｔａｇを用いて、第一暗号文Ｃが真の暗号文であるか否かを検証し、真の暗号文である場合には、関係Ｒprivpk,tagのΣ−プロトコルに対する（ａ，ｚ）←ｓｉｍΣ（Ｃ，ｍ）を計算し、コミットメント情報ａをコミットメント受信装置に送信する。コミットメント受信装置において、コミットメント情報ａを受信し、（ｔａｇ，Ｃ，ａ）を格納しておき、（ｔａｇ，ｍ，ｚ）を受信すると、関係Ｒprivpk,tagのΣ−プロトコルに対するΣｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）を用いて、秘匿情報ｍが変更されていないかを判定する。
【発明の効果】
【００２５】
本発明は、従来の署名のみに基づかずに、公開検証可能なタグベース鍵カプセル化メカニズムを用いて、新しいＳＳＴＣ方式を構成するため、従来の署名が破られた場合にも安全であるという効果を奏する。
【図面の簡単な説明】
【００２６】
【図１】コミットメントシステム１の構成例を示す図。
【図２】コミットメントシステム１の処理フローを示す図。
【図３】第三者装置１１の機能構成例を示すブロック図。
【図４】第三者装置１１の処理フローを示す図。
【図５】コミットメント受信装置１５の機能構成例を示すブロック図。
【図６】コミットメント受信装置１５の処理フローを示す図。
【図７】コミットメント生成装置１３の機能構成例を示すブロック図。
【図８】コミットメント生成装置１３の処理フローを示す図。
【発明を実施するための形態】
【００２７】
以下、本発明の実施形態について、説明する。
【００２８】
＜定義＞
まず、本形態で使用する用語や記号を定義する。
【００２９】
｛０，１｝ｋは、ｋビット長のバイナリ系列（データ）の集合を意味し、｛０，１｝＊は全てのバイナリ系列、つまり、｛０，１｝＊＝∪ｋ≧０｛０，１｝ｋを表す。
確率的アルゴリズムＭは，入力ｘ∈｛０；１｝＊とＭの内部乱数ｒの二入力関数である。
ｙ＝Ｍ（ｘ；ｒ）は、入力ｘ、乱数ｒのときの出力がｙであることを意味する。
ｙ←Ｍ（ｘ）は、Ｍの入力ｘでの確率的試行を表す。例えば、Ｐｒ［ｙ←Ｍ（ｘ）：ｙ＝１］＜１／２とは、乱数ｒに従って出力された確率変数ｙが、１である確率が１／２未満であることを意味する。
【００３０】
「Ａ（Ｘ）の試行の後、Ｂ（Ｙ）の試行が起き、さらに…」のような確率的試行の時系列的並びを、ａ←Ａ（Ｘ）；ｂ←Ｂ（Ｙ）；…のように書く。
【００３１】
Ｐｒ［ａ←Ａ；ｂ←Ｂ：ｅｖｅｎｔ］は、確率的試行ａ←Ａ；ｂ←Ｂの下での事象ｅｖｅｎｔの条件付き生起確率を表す。なお、記述を短くするため、Ｐｒ［ｙ←Ｍ（ｘ）：ｙ＝１］のかわりにＰｒ［Ｍ（ｘ）＝１］と書く場合がある。
【００３２】
なお、確定的（deterministic）なアルゴリズムは、内部コインの無い確率的アルゴリズムと考えてもよい。
【００３３】
［タグベース鍵カプセル化メカニズム（Ｔａｇ−ＫＥＭ: Tag-based Key Encapsulation Mechanisim）］
Π＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）が、Ｔａｇ−ＫＥＭ（参考文献１及び２参照）であるとは、Πが次のような性質１〜性質４を満たすアルゴリズムの集合であるときをいう。
（参考文献１）：V. Shoup, "A proposal for an ISO standard for public key encryption", Technical report, December 2001, Cryptology ePrint Archive, Report 2001/112
(参考文献２)：M. Abe, R. Gennaro, and K. Kurosawa, "Tag-KEM/DEM: A new framework for hybrid encryption", Journal of Cryptology, 2008, Volume 21, Number 1, p.97-130
【００３４】
（性質１）（ｐｋ，ｓｋ）←Ｇｅｎ（１ｎ）：鍵生成アルゴリズムＧｅｎは、セキュリティパラメータｎを入力にとり、公開鍵・秘密鍵の組（ｐｋ，ｓｋ）を出力する確率的アルゴリズムである。
（性質２）（Ｃ，Ｋ）←Ｅｎｃ（ｐｋ，ｔａｇ）。暗号化アルゴリズムＥｎｃは、公開鍵ｐｋとタグ情報ｔａｇ∈｛０；１｝＊を入力とし、乱数ｒ∈Ｇｒを内部発生させ、暗号文Ｃと鍵Ｋを計算し出力する確率的アルゴリズムである。
（性質３）復号アルゴリズムＤｅｃは、秘密鍵ｓｋ、タグ情報ｔａｇ及び暗号文Ｃを入力としてとり、鍵Ｋ＝Ｄｅｃ（ｓｋ，ｔａｇ，Ｃ）を計算する確定的アルゴリズムである。
（性質４）全てのｎ∈Ｎ，全てのｔａｇ∈｛０，１｝＊に対して、
Pr[(pk,sk)←Gen(1n);(C,K)←Enc(pk,tag):Dec(sk,tag,C)=K]=1
である。
【００３５】
［暗号文と鍵との間のＮＰ関係と公開検証可能性］
Ｔａｇ−ＫＥＭ Πに関する以下のようなＮＰ関係を定義する。
【００３６】
【数５】
【００３７】
暗号文Ｃ∈｛０；１｝＊が、対応する鍵Ｋが存在する真の暗号文である（すなわち、あるＫが存在して（Ｃ，Ｋ）∈Ｒｐｒｉｖｐｋ，ｔａｇ）かを、公開鍵ｐｋとｔａｇのみで検証できるとき、Ｔａｇ−ＫＥＭ Πは「公開検証可能」という。
【００３８】
［Σ―プロトコル］
Ｒ＝｛（ｘ，ｗ）｝をＮＰ関係とする。関係Ｒから定義される言語をＬＲ（:=｛ｘ｜∃ｗ ｓ．ｔ．（ｘ，ｗ）∈Ｒ｝）とする。但し、「Ａ:=Ｂ」は「Ａという記号の意味するところをＢと定義する」ことを意味する。関係ＲのΣ−プロトコル（非特許文献８参照）とは、証明者と検証者からなる三交信の次のような認証プロトコルである。なお、（ｘ，ｗ）∈Ｒとする。ｘを証明者と検証者への共通入力として、証明者は、さらにｗを与えられる。
（１）証明者は、乱数ｒａを選び、第一メッセージａ＝Σｃｏｍ（ｘ，ｗ；ｒａ）を計算し、検証者に送る。
（２）検証者は、第二メッセージの乱数ｃ←ＲΣｃｈを選び証明者に送り返す。但し、Ａ←ＲＢは、集合ＢからランダムにＡを選択することを意味する。なお、Σｃｈはチャレンジｃ（例えば、乱数）を生成または選択するアルゴリズムである。
（３）証明者は、第三メッセージｚ＝Σａｎｓ（ｘ，ｗ，ｒａ，ｃ）を計算し、検証者に送る。第三メッセージｚはチャレンジｃに対する証明者の返答であり、返答生成アルゴリズムΣａｎｓを用いて生成する。
【００３９】
検証者は、ｂ＝Σｖｒｆｙ（ｘ，ａ，ｃ，ｚ）を計算して出力する。Σｖｒｆｙは、検証アルゴリズムであり、ｂ＝１であれば、検証者は、証明者の一連の認証行為を受理したという意味でありそれ以外の値であれば、否決したという意味を持っている。第一メッセージａと返答ｚとが、ｗを知っている証明者により、それぞれ第一メッセージ生成アルゴリズムΣｃｏｍと返答生成アルゴリズムΣａｎｓを用いて生成されたものであれば、ｂ＝１となる。Σ−プロトコルは以下の性質を満たす。
［完全性］∀ra,∀c∈Σch[Σvrfy(x,Σcom(x,w;ra),c,Σans(x,w,ra,c))=1]
［特別健全性］
【００４０】
【数６】
【００４１】
つまり、ｘが言語ＬＲに元として含まれないとき、ａに対して、ｚが存在するようなｃは、唯一に決まる。さらに、ｃ≠ｃ’のとき、二つの受理される履歴（ａ，ｃ，ｚ）と（ａ，ｃ’，ｚ’）から、（ｘ，ｗ）∈Ｒを満たすｗが必ず計算できる。
【００４２】
［正直な検証者に対する特別ゼロ知識］∀ｘ∈ＬＲ，∀ｃ∈Σｃｈに対して、検証者に受理される（ａ，ｃ，ｚ）←ｓｉｍΣ（ｘ，ｃ）を作ることができる。さらに、ｃをΣｃｈからランダムに選び、ｓｉｍΣに入力して作った、（ａ，ｃ，ｚ）は、正直な証明者が正直な検証者と実行した履歴と同分布になる。
【００４３】
なお、任意のＮＰ関係に対して、必ずΣ−プロトコルが存在することはすでに知られている（参考文献３参照）。
（参考文献３）：O. Goldreich, S. Micali, and A. Wigderson, "Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems", Journal of the ACM, 1991, 1(38), p.691-729
【００４４】
＜第一実施形態＞
＜コミットメントシステム１＞
図１及び図２を用いて第一実施形態に係るコミットメントシステム１の処理概要を説明する。コミットメントシステム１は、第三者装置１１とコミットメント生成装置１３とコミットメント受信装置１５とからなり、これらの各装置は、例えばインターネットである通信網１２を介して相互に通信可能とされている。
【００４５】
Π＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）を公開検証可能なタグベース鍵カプセル化メカニズムとする。関係Ｒprivpk,tagはΠにより定義される。関係Ｒprivpk,tagはＮＰ関係であり、
【００４６】
【数７】
【００４７】
とする。Πと関係Ｒprivpk,tagに対するΣ−プロトコルからコミットメントシステム１を構成する。
【００４８】
第三者装置１１はセキュリティパラメータｎを入力とし（ｓ１）、鍵生成アルゴリズムＧｅｎを用いて、秘密鍵ｓｋと公開鍵ｐｋを生成する（ｓ２）。この公開鍵ｐｋを共通参照データとする。そして、少なくともコミットメント生成装置１３とコミットメント受信装置１５が共通参照データｃｒｓを利用可能な状態で、第三者装置１１は共通参照データｃｒｓを格納しておく。
【００４９】
コミットメント生成装置１３とコミットメント受信装置１５は、タグ情報ｔａｇを取得する（ｓ３）。ｔａｇ情報とは、コミットメント生成装置１３とコミットメント受信装置１５とが共に知っている情報であり、例えば、プロセスのセッションＩＤ等である。なお、ｔａｇ情報は後述する第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成する前にコミットメント生成装置１３とコミットメント受信装置１５とが共に取得すればよく、どのような取得方法を用いてもよい。
【００５０】
さらに、コミットメント受信装置１５は、共通参照データｃｒｓを取得する（ｓ４）。コミットメント受信装置１５は暗号化アルゴリズムＥｎｃに対し共通参照データｃｒｓとタグ情報ｔａｇを用いて、第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成し（ｓ５）、第一暗号文Ｃをコミットメント生成装置１３に送信する（ｓ６）。
【００５１】
コミットメント生成装置１３はコミットする秘匿情報ｍを入力される（ｓ７）。さらに、コミットメント生成装置１３は第一暗号文Ｃを受信する（ｓ８）。さらに、コミットメント生成装置１３は、共通参照データｃｒｓを取得する（ｓ９）。
【００５２】
コミットメント生成装置１３は共通参照データｃｒｓとタグ情報ｔａｇを用いて、第一暗号文Ｃが真の暗号文であるか否かを検証する（ｓ１０）。真の暗号文である場合には、コミットメント生成装置１３は、関係Ｒprivpk,tagのΣ−プロトコルに対する（ａ，ｚ）←ｓｉｍΣ（Ｃ，ｍ）を計算し（ｓ１１）、コミットメント情報ａをコミットメント受信装置１５に送信する（ｓ１２）。なお、関係Ｒprivpk,tagのΣ−プロトコルに対するｓｉｍΣとは、前述のΣ―プロトコルにおける秘密ｗを知らずに、第一メッセージａ（本実施形態におけるコミットメント情報ａ）を生成し、返答ｚ（本実施形態におけるコミットを開封するときの証拠の一部ｚ）を生成するアルゴリズムである。
【００５３】
コミットメント受信装置１５は、コミットメント情報ａを受信し（ｓ１３）、（ｔａｇ，Ｃ，ａ）を格納しておく（ｓ１４）。
【００５４】
コミットメント開封装置１６は、（ｃｒｓ，ｔａｇ，Ｃ，ｍ，ａ，ｚ）をコミットメント生成装置１３等から受け取り（ｓ１５）、安全に保管しておく。そして、情報ｍを開示するタイミングになると、（ｔａｇ，ｍ，ｚ）をコミットメント受信装置１５に送信する（ｓ１６）。なお、コミットメント生成装置１３とコミットメント開封装置１６との間は安全に通信可能とされている。また、コミットメント開封装置１６を設けず、コミットメント生成装置１３から直接、（ｔａｇ，ｍ，ｚ）をコミットメント受信装置１５に送信する構成としてもよい。
【００５５】
コミットメント受信装置１５は、（ｔａｇ，ｍ，ｚ）を受信すると（ｓ１７）、Σ―プロトコルに対するΣｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）を用いて、コミットメント情報ａを受信した時点から秘匿情報ｍが変更されていないかを判定する（ｓ１８）。なお、前述のΣ―プロトコルにおいて検証アルゴリズムΣｖｒｆｙは証明者がｗを知っているか否かを検証するが、本実施形態においてΣ―プロトコルに対するΣｖｒｆｙはコミットメント情報ａを受信した時点から秘匿情報ｍが変更されていないかを判定する。言い換えると、本実施形態におけるΣ―プロトコルに対するΣｖｒｆｙは、秘匿情報ｍに対するコミットメント情報ａ及びコミットを開封するときの証拠の一部ｚが正しいか否かを検証するアルゴリズムである。
【００５６】
以下、詳細を説明する。まず、第一実施形態において例えば、以下のＴａｇ−ＫＥＭ Π＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）を利用することができる。
【００５７】
＜Ｔａｇ−ＫＥＭ Π＞
ＧとＧＴを素数位数ｑのアーベル群とする。ｅ：Ｇ×Ｇ→ＧＴを非退化な双線形写像とする。ｇをＧの生成元とする。Ｚ／ｑＺを０以上ｑ未満の整数の集合とする。双線形性より、ｘ，ｙ∈Ｇ、ａ，ｂ∈Ｚ／ｑＺに対して、ｅ（ｘａ，ｙｂ）＝ｅ（ｘ，ｙ）ａｂが成り立つ。非退化性より、ｅ（ｇ，ｇ）は、ＧＴの生成元である。Ｈ：｛０，１｝＊→Ｚ／ｑＺのハッシュ関数とする。ｏｔΣ＝（ｏｔＫＧｅｎ，ｏｔＳｉｇｎ，ＯｔＶｒｆｙ）を任意の使い捨て署名とする（参考文献４参照）。
（参考文献４）：Leslie Lamport, "Constructing digital signatures from one-way functions", Technical Report SRI-CSL-98, SRI International Computer Science Laboratory, October 1979
・Ｇｅｎ（１ｎ）：ｘ，ｙ←ＲＺ／ｑＺ；Ｘ:=ｇｘ；Ｙ:=ｇｙ；ｐｋ＝（ｇ，Ｘ，Ｙ，Ｈ）、ｓｋ＝（ｐｋ，ｘ，ｙ）として、（ｐｋ，ｓｋ）を出力する。
・Ｅｎｃ（ｐｋ，ｔａｇ）：（ｏｔｖｋ，ｏｔｓｋ）←ｏｔＫＧｅｎ（１ｋ）；σ←ｏｔＳｉｇｎ（ｏｔｓｋ，ｔａｇ）；ｒ←Ｚ／ｑＺ；ｔ:=Ｈ（ｏｔｖｋ，ｇｒ）；Ｃ:=（σ，ｏｔｖｋ，ｇｒ，（ＸｔＹ）ｒ）；Ｋ:=Ｘｒ；（Ｃ，Ｋ）を出力する。
・Ｄｅｃ（ｓｋ，ｔａｇ，Ｃ）：Ｃ＝（σ，ｏｔｖｋ，ｕ，τ）をσ，ｏｔｖｋ，ｕ，τに分解し、もしｏｔＶｒｆｙ（ｏｔｖｋ，ｔａｇ，σ）≠１ならば、復号を中止し、それ以外の場合、ｔ:=Ｈ（ｏｔｖｋ，ｕ）を計算する。もしｕｘｔ＋ｙ≠τ ならば、復号を中止し、それ以外の場合、Ｋ:=ｕｘ；Ｋを出力する。
【００５８】
なお、第一実施形態において例えば、以下の使い捨て署名ｏｔΣ（ｏｔＫＧｅｎ，ｏｔＳｉｇｎ，ｏｔＶｒｆｙ）を利用することができる。
【００５９】
＜使い捨て署名ｏｔΣ＞
Ｇ２を素数位数ｑ２のアーベル群とする。Ｈ２：｛０，１｝＊→Ｚ／ｑ２Ｚのハッシュ関数とする。ｑ２、Ｇ２、Ｈ２は、Ｔａｇ−ＫＥＭΠで用いるｑ，Ｇ，Ｈと同じであってもよいし、異なっていてもよい。以下において、添え字ｓ１、ｓ２、ｗ１、ｗ２、ｚ１、ｚ２、Ｈ２は、ｓ１、ｓ２、ｗ１、ｗ２、ｚ１、ｚ２、Ｈ２を意味する。
・ｏｔＫＧｅｎ（１ｋ）：ｇ１，ｇ２←ＲＧ２；ｓ１，ｓ２，ｗ１，ｗ２←ＲＺ／ｑ２Ｚ；ｂ:=ｇ１ｗ１ｇ２ｗ２；ｈ:=ｇ１ｓ１ｇ２ｓ２；ｏｔｖｋ:=（ｇ１，ｇ２，ｈ，ｂ）；ｏｔｓｋ:=（ｏｔｖｋ，ｓ１，ｓ２，ｗ１，ｗ２）；（ｏｔｖｋ，ｏｔｓｋ）を出力する。
・ｏｔＳｉｇｎ（ｏｔｓｋ，ｍ）：ｃ:=Ｈ（ｏｔｖｋ，ｍ）；ｚ１:=ｗ１＋ｃ・ｓ１ ｍｏｄ ｑ２；ｚ２:=ｗ２＋ｃ・ｓ２ ｍｏｄ ｑ２；σ:=（ｚ１，ｚ２）を出力する。
・ｏｔＶｒｆｙ（ｏｔｖｋ，ｍ，σ）：ｇ１ｚ１ｇ２ｚ２＝ｂｈＨ２（ｏｔｖｋ，ｍ）のときに限り、１を出力する。
【００６０】
＜共通参照データｃｒｓの生成及び取得＞
図３及び図４を用いて共通参照データｃｒｓの生成について説明する。第三者装置１１は、入力部１１１を介してセキュリティパラメータｎを取得し（ｓ１１１）、鍵生成部１１２において、Ｔａｇ−ＫＥＭの鍵生成アルゴリズムＧｅｎ（１ｎ）により（ｓｋ，ｐｋ）を生成する（ｓ１１２）。例えば、Ｚ／ｑＺからランダムにｘとｙを選択し、Ｘ=ｇｘとＹ=ｇｙを求め、ｇとＸとＹとＨとの組を公開鍵ｐｋとして生成する。この公開鍵ｐｋを共通参照データｃｒｓとする。ｐｋとｘとｙとの組を秘密鍵として生成する。そして、少なくともコミットメント生成装置１３とコミットメント受信装置１５が共通参照データｃｒｓを利用可能な状態で、共通参照データｃｒｓは記憶部１１４に記憶される。また、第三者装置１１は、秘密鍵ｓｋを記憶部１１４に安全に格納してもよいし、破棄してもよい（ｓ１１３）。なお、第三者装置１１は、制御部１１５の制御のもと上記処理を行う。なお、本実施形態では、一つの共通参照データｃｒｓを繰り返し使う。
【００６１】
コミットメント受信装置１５は、制御部１５５（図５）の制御のもと、出力部１５６を介して、第三者装置１１に対し、公開鍵ｐｋを送信するように要求する。第三者装置１１の制御部１１５は、入力部１１１を介して要求を受信し、記憶部１１４から公開鍵ｐｋを取り出し、出力部１１６を介して、コミットメント受信装置１５に送信する。コミットメント受信装置１５は、入力部１５１を介して公開鍵ｐｋを受信し、記憶部１５４に格納する（図６、ｓ１５１）。コミットメント生成装置１３も同様に制御部１３５（図７）の制御のもと、出力部１３６を介して公開鍵ｐｋを要求し、入力部１３１を介して公開鍵ｐｋを受信し、記憶部１３４に格納する（図８、ｓ１３１）。
【００６２】
＜第一暗号文Ｃ及び第一鍵Ｋの生成＞
コミットメント受信装置１５は、入力部１５１を介してセキュリティパラメータｋを取得する（図６、ｓ１５２）。コミットメント受信装置１５は、暗号化部１５２（図５）において、Ｔａｇ−ＫＥＭ Πの暗号化アルゴリズムＥｎｃを実行し、第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成する（ｓ１５３）。
【００６３】
暗号化部１５２内の署名鍵検証鍵生成部１５２ａは、セキュリティパラメータｋを用いて、鍵生成アルゴリズムｏｔＫＧｅｎにより、署名鍵ｏｔｓｋと検証鍵ｏｔｖｋを生成する。例えば、署名鍵検証鍵生成部１５２ａは、Ｇ２からランダムにｇ１、ｇ２を選択し、Ｚ／ｑ２Ｚからランダムにｓ１、ｓ２、ｗ１、ｗ２を選択する。さらに、ｂ＝ｇ１ｗ１ｇ２ｗ２とｈ＝ｇ１ｓ１ｇ２ｓ２を求め、ｇ１とｇ２とｈとｂとの組を検証鍵ｏｔｖｋとし、検証鍵ｏｔｖｋとｓ１とｓ２とｗ１とｗ２との組を署名鍵ｏｔｓｋとして求める。なお、ハッシュ関数ＨとＨ２が異なる場合には、検証鍵ｏｔｖｋがハッシュ関数Ｈ２を含む構成とする。
【００６４】
暗号化部１５２内の署名生成部１５２ｂは、タグ情報ｔａｇと生成した署名鍵ｏｔｓｋを用いて、署名アルゴリズムｏｔＳｉｇｎにより、電子署名σを生成する。例えば、検証鍵ｏｔｖｋとタグ情報ｔａｇをハッシュ関数Ｈ２の入力として、ｃを求める。さらに、（ｚ１＝ｗ１＋ｃ・ｓ１ ｍｏｄ ｑ２）と（ｚ２＝ｗ２＋ｃ・ｓ２ ｍｏｄ ｑ２）とを求め、ｚ１とｚ２との組を電子署名σとする。
【００６５】
暗号化部１５２内の第一鍵第一暗号文生成部１５２ｃは、公開パラメータｐｋ（＝ｇ，Ｘ，Ｙ，Ｈ）と前記検証鍵ｏｔｖｋを用いて、暗号化アルゴリズムＥｎｃにより第一暗号文Ｃと第一鍵Ｋを生成する。例えば、Ｚ／ｑＺからランダムにｒを選択し、Ｋ＝Ｘｒを求める。さらに、ｇｒを求め、検証鍵ｏｔｖｋとｇｒをハッシュ関数Ｈの入力として、ｔを求める。（ＸｔＹ）ｒを計算し、電子署名σと検証鍵ｏｔｖｋとｇｒと（ＸｔＹ）ｒとの組を第一暗号文Ｃとする。
【００６６】
コミットメント受信装置１５は、第一暗号文Ｃとタグ情報ｔａｇを関連付けて記憶部１５４に記憶し、さらに、第一暗号文Ｃを出力部１５６を介してコミットメント生成装置１３に送信する（ｓ１５４）。コミットメント受信装置１５は、署名鍵ｏｔｓｋを記憶部１５４に安全に格納してもよいし、破棄してもよい。
【００６７】
＜第一暗号文Ｃの検証＞
コミットメント生成装置１３は、入力部１３１（図７）を介して、第一暗号文Ｃ＝（σ，ｏｔｖｋ，ｕ，τ）を受信する（ｓ１３２）。
【００６８】
暗号文検証部１３２において、まず、電子署名σと検証鍵ｏｔｖｋとタグ情報ｔａｇを用いて、ｏｔＶｒｆｙ（ｏｔｖｋ，ｔａｇ，σ）により、電子署名σが正当か否かを検証する（ｓ１３３）。例えば、電子署名σ＝（ｚ１，ｚ２）とｏｔｖｋ＝（ｇ１，ｇ２，ｈ，ｂ）を用いて、ｇ１ｚ１ｇ２ｚ２を求める。さらに、検証鍵ｏｔｖｋとタグ情報ｔａｇを入力とし、Ｈ２（ｏｔｖｋ，ｔａｇ）を求め、検証鍵に含まれるｂを用いて、ｂｈＨ２（ｏｔｖｋ，ｔａｇ）を求める。求めたｇ１ｚ１ｇ２ｚ２とｂｈＨ２（ｏｔｖｋ，ｔａｇ）とが同一の場合に電子署名σが正当であると判断する。つまり、ｏｔＶｒｆｙは１を返す。ｇ１ｚ１ｇ２ｚ２とｂｈＨ２（ｏｔｖｋ，ｔａｇ）とが異なる場合には、電子署名が正当ではないと判断し、否決する（ｓ１３７）。つまり、ｏｔＶｒｆｙは１以外の値を返す。コミットメント受信装置１５以外の生成した電子署名を否決することができる。
【００６９】
電子署名σが正当である場合には、暗号文検証部１３２は、記憶部１５４から公開パラメータｐｋ＝（ｇ，Ｘ，Ｙ，Ｈ）を取り出し、ハッシュ関数Ｈと第一暗号文Ｃに含まれるｕと検証鍵ｏｔｖｋを用いて、ｔ＝Ｈ（ｏｔｖｋ，ｕ）を求める。さらに、公開パラメータｐｋ＝（ｇ，Ｘ，Ｙ，Ｈ）と第一暗号文Ｃに含まれるτを用いて、ｅ（ｕ，ＸｔＹ）＝ｅ（ｇ，τ）が成り立つか否か検証する（ｓ１３４）。受信した第一暗号文Ｃに含まれるｕとτが、それぞれ、コミットメント受信装置１５で生成されるｇｒ、（ＸｔＹ）ｒと同一であれば、前記式が成り立つ。ｅ（ｕ，ＸｔＹ）＝ｅ（ｇ，τ）が成り立つ場合には、受信した第一暗号文Ｃが真の暗号文であると判定する。ｅ（ｕ，ＸｔＹ）＝ｅ（ｇ，τ）が成り立たない場合には、第一暗号文Ｃが真の暗号文ではないと判断し、否決する（ｓ１３７）。この処理により、
【００７０】
【数８】
【００７１】
第一暗号文Ｃが言語ＬＲに元として含まれない場合（Ｃが真の暗号文でない場合）に処理を中止することができる。
【００７２】
＜コミットメント情報の生成＞
第一暗号文Ｃが真の暗号文であると判定した場合、コミットメント情報生成部１３８は、第一暗号文Ｃと秘匿情報ｍを用いて、関係Ｒprivpk,tagのΣ−プロトコルに対する（ａ，ｚ）←ｓｉｍΣ（Ｃ，ｍ）を計算する（ｓ１３５）。例えばコミットメント情報生成部１３８は、Ｇから単位元を除いた群Ｇ＊からランダムにＫ＾を選択し、Ｚ／ｑＺからランダムにｚを選択する。さらに、ａ＾＝ｅ（ｇ，Ｋ＾）ｚ・ｅ（ｕ，Ｘ）−ｍを計算し、Ｋ＾とａ＾との組をコミットメント情報ａとして生成する。コミットメント生成装置１３は、出力部１３６を介して、生成したコミットメント情報ａをコミットメント受信装置１５に送信する（ｓ１３６）。
【００７３】
コミットメント生成装置１３とコミットメント開封装置１６が同一装置の場合、（ｃｒｓ，ｔａｇ，Ｃ，ｍ，ａ，ｚ）を記憶部１３４に安全に記憶しておく。別装置の場合には、コミットメント生成装置１３は上記情報をコミットメント開封装置１６に出力部１３６を介して送信する。
【００７４】
＜コミットメント情報の受信及び開封処理＞
コミットメント受信装置１５は、入力部１５１（図５）を介して、コミットメント情報ａを受信し（図６、ｓ１５５）、記憶部１５４に（ｔａｇ，Ｃ）と関連付けて記憶しておく（ｓ１５６）。
【００７５】
さらに、コミットメント受信装置１５は、入力部１５１を介して、コミットメント生成装置１３またはコミットメント開封装置１６から（ｔａｇ，ｍ，ｚ）を受信する（ｓ１５７）。コミットメント受信装置１５の開封部１５９において、Σｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）を用いて、ｅ（ｇ，Ｋ＾）ｚ＝ａ＾・ｅ（ｕ，Ｘ）ｍが成り立つか否か判定する（ｓ１５８）。例えば、公開パラメータｐｋに含まれるｇとＸ、ａ＝（Ｋ＾，ａ＾）、第一暗号文Ｃに含まれるｕ，ｚ及びｍを用いて、ｅ（ｇ，Ｋ＾）ｚ＝ａ＾・ｅ（ｕ，Ｘ）ｍが成り立つか否か判定する。成り立つ場合には、Σｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）は１を返し、受信した秘匿情報ｍは、コミットメント情報ａ受信時点から変更されていないと判定し、受理する（ｓ１５９）。ｅ（ｇ，Ｋ＾）ｚ＝ａ＾・ｅ（ｕ，Ｘ）ｍが成り立たない場合、Σｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）は１以外の値を返し、少なくともｍかｚかの何れかに変更があったものとし、否決する（ｓ１６０）。
【００７６】
＜効果＞
このような構成とすることで、従来の署名が破られた場合にも安全なコミットメント方式とすることができる。
【００７７】
さらに、本実施形態では、公開検証可能なＴａｇ−ＫＥＭに加え、電子署名を組合せているため、より安全性の高いコミットメント方式を実現している。
【００７８】
さらに、電子署名を使い捨て署名とすることで、従来（非特許文献３、４、５、６及び７参照）より効率のよいコミットメント方式を実現している。従来技術では、使い捨てでない電子署名から共通の変換法の基にＳＳＴＣを構成していた。これらの方式は署名方式から変換するので、コミットメントの効率は署名方式に依存する。現在知られている限りでは、安全な使い捨てでない署名方式は、安全な使い捨て署名や安全な暗号方式と比べてより強い家庭または大きなパラメータを使わなくてはならない。例えば、参考文献５記載の署名方式では、公開パラメータｐｋとして（ｇ、ｇ１，ｇ２，ｕ’，Ｈ，ｕ１，…，ｕｎ）を必要とする（例えばｎ＝１６０や２５６等）。一方、本実施形態では、公開検証可能なＴａｇ−ＫＥＭと使い捨て署名を組み合わせて用いることで、公開パラメータを（ｇ，Ｘ，Ｙ，Ｈ）とし、小さいパラメータで十分な安全性を実現することができる。
（参考文献５）：Brent Waters, "Efficient Identity-Based Encryption Without Random Oracles", EUROCRYPT 2005, LNCS, Springer, Heidelberg, 2005, vol. 3494, p.114-127.
【００７９】
また、本実施形態は、ＣＤＨ仮定に対しタイトであり、従来技術に比べ、セキュリティパラメータを短くすることができ、情報量、計算量を共に削減することができ、効率のよいコミットメントシステムを構成することができる。例えば、ＣＤＨ仮定がｋビットの場合、本実施形態ではｋ’（≒ｋ）ビットのセキュリティパラメータを用いることができる。一方、参考文献５記載の署名方式ではｋ”（≒１０２ｋ）ビットのセキュリティパラメータを用いなければ同程度の安全性を得ることはできない。
【００８０】
＜プログラム及び記憶媒体＞
上述した第三者装置、コミットメント生成装置及びコミットメント受信装置は、コンピュータにより機能させることもできる。この場合はコンピュータに、目的とする装置（各種実施例で図に示した機能構成をもつ装置）として機能させるためのプログラム、またはその処理手順（各実施例で示したもの）の各過程をコンピュータに実行させるためのプログラムを、ＣＤ−ＲＯＭ、磁気ディスク、半導体記憶装置などの記録媒体から、あるいは通信回線を介してそのコンピュータ内にダウンロードし、そのプログラムを実行させればよい。
【００８１】
＜その他の変形例＞
他の公開検証可能なＴａｇ−ＫＥＭや使い捨て署名を用いてもよい。Πと関係Ｒprivpk,tagに対するΣ−プロトコルからコミットメントシステムを構成すればよく、第一暗号文Ｃは必ずしも署名を含まなくともよい。また、使い捨てではない署名を用いてもよく、その場合も、従来技術と比べ安全なコミットメント方式となる。
【００８２】
本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【産業上の利用可能性】
【００８３】
本発明は、様々な暗号プロトコルに利用することができる。例えば、ゼロ知識証明、マルチパーティ計算、電子マネーまたは電子投票等に利用することができる。
【符号の説明】
【００８４】
１ コミットメントシステム
１１ 第三者装置
１２ 通信網
１３ コミットメント生成装置
１５ コミットメント受信装置
１６ コミットメント開封装置
１１１ 入力部
１１２ 鍵生成部
１１４ 記憶部
１１５ 制御部
１１６ 出力部
１３１ 入力部
１３２ 暗号検証部
１３４ 記憶部
１３５ 制御部
１３６ 出力部
１３８ コミットメント情報生成部
１５１ 入力部
１５２ 暗号化部
１５２ａ 署名鍵検証鍵生成部
１５２ｂ 署名生成部
１５２ｃ 第一鍵第一暗号文生成部
１５４ 記憶部
１５５ 制御部
１５６ 出力部
１５９ 開封部
【特許請求の範囲】
【請求項１】
コミットメント生成装置とコミットメント受信装置からなるコミットメントシステムであって、
公開検証可能なタグベース鍵カプセル化メカニズムをΠ＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）とし、鍵生成アルゴリズムＧｅｎを用いて生成される公開鍵をｐｋとし、前記コミットメント生成装置と前記コミットメント受信装置とが共に知っているタグ情報をｔａｇとし、ｒを乱数とし、暗号化アルゴリズムＥｎｃに対し前記公開鍵ｐｋと前記タグ情報ｔａｇを与えて得られる第一暗号文をＣとし、第一鍵をＫとし、前記Πが定める関係Ｒprivpk,tagを
【数９】
とし、
前記コミットメント受信装置は暗号化アルゴリズムＥｎｃに対し前記公開鍵ｐｋと前記タグ情報ｔａｇを与え、第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成し、前記第一暗号文Ｃを前記コミットメント生成装置に送信し、
コミットを開封するときの証拠の一部をｚとし、コミットする秘匿情報をｍとし、前記コミットメント生成装置は前記第一暗号文Ｃを受信し、前記公開鍵ｐｋと前記タグ情報ｔａｇを用いて、前記第一暗号文Ｃが真の暗号文であるか否かを検証し、真の暗号文である場合には、前記関係Ｒprivpk,tagのΣ−プロトコルに対する（ａ，ｚ）←ｓｉｍΣ（Ｃ，ｍ）を計算し、コミットメント情報ａを前記コミットメント受信装置に送信し、
前記コミットメント受信装置はコミットメント情報ａを受信し、（ｔａｇ，Ｃ，ａ）を格納しておき、（ｔａｇ，ｍ，ｚ）を受信すると、前記関係Ｒprivpk,tagのΣ−プロトコルに対するΣｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）を用いて、秘匿情報ｍが変更されていないかを判定する、
コミットメントシステム。
【請求項２】
請求項１記載のコミットメントシステムであって、
Ｚ／ｑＺを０以上ｑ未満の整数の集合とし、ｘ，ｙ←ＲＺ／ｑＺとし、ＧとＧＴを素数位数ｑのアーベル群とし、ｅ：Ｇ×Ｇ→ＧＴを非退化な双線形写像とし、ｇをＧの生成元とし、Ｈをハッシュ関数とし、Ｘ:=ｇｘとし、Ｙ:=ｇｙとし、前記公開鍵ｐｋ＝（ｇ，Ｘ，Ｙ，Ｈ，）とし、
前記コミットメント受信装置は、署名鍵ｏｔｓｋと検証鍵ｏｔｖｋを生成し、前記署名鍵ｏｔｓｋと前記タグ情報ｔａｇを用いて電子署名σを生成し、さらに、ｒ←Ｚ／ｑＺと前記検証鍵ｏｔｖｋを用いてｔ:=Ｈ（ｏｔｖｋ，ｇｒ）を計算し、前記電子署名σ及び検証鍵ｏｔｖｋを含む前記第一暗号文Ｃ:=（σ，ｏｔｖｋ，ｇｒ，（ＸｔＹ）ｒ）を生成し、
前記コミットメント生成装置は、第一暗号文Ｃ＝（σ，ｏｔｖｋ，ｕ，τ）を受信し、前記公開鍵ｐｋと前記タグ情報ｔａｇを用いて、電子署名σが正当か否かを検証し、前記電子署名σが正当であって、ｅ（ｕ，ＸｔＹ）＝ｅ（ｇ，τ）が成り立つ場合には、前記第一暗号文Ｃが真の暗号文であると判定し、Ｋ＾←Ｇ＊＝（Ｇ−｛１Ｇ｝）とｚ←Ｚ／ｑＺを用いて、ａ＾＝ｅ（ｇ，Ｋ＾）ｚ・ｅ（ｕ，Ｘ）−ｍを計算し、コミットメント情報ａ＝（Ｋ＾，ａ＾）を前記コミットメント受信装置に送信し、
前記コミットメント受信装置は、コミットメント情報ａを受信し、（ｔａｇ，Ｃ，ａ）を格納しておき、（ｔａｇ，ｍ，ｚ）を受信すると、ｅ（ｇ，Ｋ＾）ｚ＝ａ＾・ｅ（ｕ，Ｘ）ｍが成り立つか否か判定し、成り立つ場合には、秘匿情報ｍが変更されていないと判定する、
コミットメントシステム。
【請求項３】
請求項２記載のコミットメントシステムであって、
Ｚ／ｑ２Ｚを０以上ｑ２未満の整数の集合とし、Ｇ２を素数位数ｑ２のアーベル群とし、Ｈ２をハッシュ関数とし、
添え字のｓ１、ｓ２、ｗ１及びｗ２はそれぞれｓ１、ｓ２、ｗ１及びｗ２を意味し、前記署名鍵ｏｔｓｋ及び前記検証鍵ｏｔｖｋは使い捨て署名であり、前記コミットメント受信装置はｇ１，ｇ２←ＲＧ２、ｓ１，ｓ２，ｗ１，ｗ２←ＲＺ／ｑ２Ｚを用いて、ｂ:=ｇ１ｗ１ｇ２ｗ２及びｈ:=ｇ１ｓ１ｇ２ｓ２を求め、前記検証鍵ｏｔｖｋ:=（ｇ１，ｇ２，ｈ，ｂ）、前記署名鍵ｏｔｓｋ＝（ｏｔｖｋ，ｓ１，ｓ２，ｗ１，ｗ２）を生成し、ｃ:=Ｈ２（ｏｔｖｋ，ｔａｇ）を求め、ｚ１:=ｘ１＋ｃ・ｓ１ ｍｏｄ ｑ２、ｚ２:=ｘ２＋ｃ・ｓ２ ｍｏｄ ｑ２を求め、前記電子署名σ＝（ｚ１，ｚ２）を生成し、
添え字のＨ２、ｚ１及びｚ２はそれぞれＨ２、ｚ１及びｚ２を意味し、前記コミットメント生成装置は、前記検証鍵ｏｔｖｋ:=（ｇ１，ｇ２，ｈ，ｂ）と前記電子署名σ＝（ｚ１，ｚ２）を用いて、ｇ１ｚ１g２ｚ２＝ｂｈＨ２（ｏｔｖｋ，ｔａｇ）が成り立つか否かを判定し、成り立つ場合には、前記電子署名σが正当であると判定する、
コミットメントシステム。
【請求項４】
秘匿情報ｍをコミットし、コミットメント情報ａを生成するコミットメント生成装置であって、
公開検証可能なタグベース鍵カプセル化メカニズムをΠ＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）とし、鍵生成アルゴリズムＧｅｎを用いて生成される公開鍵をｐｋとし、当該コミットメント生成装置とコミットメント情報ａを受信するコミットメント受信装置とが共に知っているタグ情報をｔａｇとし、ｒを乱数とし、暗号化アルゴリズムＥｎｃに対し前記公開鍵ｐｋと前記タグ情報ｔａｇを与えて得られる第一暗号文をＣとし、第一鍵をＫとし、前記Πが定める関係Ｒprivpk,tagを
【数１０】
とし、コミットを開封するときの証拠の一部をｚとし、
第一暗号文Ｃを受信し、公開鍵ｐｋとタグ情報ｔａｇとを用いて、受信した前記第一暗号文Ｃが真の暗号文であるか否かを検証し、真の暗号文である場合には、前記関係Ｒprivpk,tagのΣ−プロトコルに対する（ａ，ｚ）←ｓｉｍΣ（Ｃ，ｍ）を計算し、コミットメント情報ａを前記コミットメント受信装置に送信する、
コミットメント生成装置。
【請求項５】
コミットメント情報ａを受信するコミットメント受信装置であって、
公開検証可能なタグベース鍵カプセル化メカニズムをΠ＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）とし、鍵生成アルゴリズムＧｅｎを用いて生成される公開鍵をｐｋとし、秘匿情報ｍをコミットし、コミットメント情報ａを生成するコミットメント生成装置と当該コミットメント受信装置とが共に知っているタグ情報をｔａｇとし、ｒを乱数とし、暗号化アルゴリズムＥｎｃに対し前記公開鍵ｐｋと前記タグ情報ｔａｇを与えて得られる第一暗号文をＣとし、第一鍵をＫとし、前記Πが定める関係Ｒprivpk,tagを
【数１１】
とし、
暗号化アルゴリズムＥｎｃに対し前記公開鍵ｐｋと前記タグ情報ｔａｇを与え、第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成し、前記第一暗号文Ｃを前記コミットメント受信装置に送信し、
コミットを開封するときの証拠の一部をｚとし、前記コミットメント生成装置からコミットメント情報ａを受信し、（ｔａｇ，Ｃ，ａ）を格納しておき、（ｔａｇ，ｍ，ｚ）を受信すると、Σ−プロトコルに対するΣｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）を用いて、秘匿情報ｍが変更されていないかを判定する、
コミットメント受信装置。
【請求項６】
コミットメント生成装置とコミットメント受信装置を用いたコミットメント方法であって、
公開検証可能なタグベース鍵カプセル化メカニズムをΠ＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）とし、鍵生成アルゴリズムＧｅｎを用いて生成される公開鍵をｐｋとし、前記コミットメント生成装置と前記コミットメント受信装置とが共に知っているタグ情報をｔａｇとし、ｒを乱数とし、暗号化アルゴリズムＥｎｃに対し前記公開鍵ｐｋと前記タグ情報ｔａｇを与えて得られる第一暗号文をＣとし、第一鍵をＫとし、前記Πが定める関係Ｒprivpk,tagを
【数１２】
とし、
前記コミットメント受信装置において、暗号化アルゴリズムＥｎｃに対し前記公開鍵ｐｋと前記タグ情報ｔａｇを与え、第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成し、前記第一暗号文Ｃを前記コミットメント生成装置に送信する第一暗号文生成ステップと、
コミットを開封するときの証拠の一部をｚとし、コミットする秘匿情報をｍとし、前記コミットメント生成装置が、前記第一暗号文Ｃを受信し、コミットメント生成装置において、前記公開鍵ｐｋと前記タグ情報ｔａｇを用いて、前記第一暗号文Ｃが真の暗号文であるか否かを検証し、真の暗号文である場合には、前記関係Ｒprivpk,tagのΣ−プロトコルに対する（ａ，ｚ）←ｓｉｍΣ（Ｃ，ｍ）を計算し、コミットメント情報ａを前記コミットメント受信装置に送信するコミットメント情報生成ステップと、
前記コミットメント受信装置において、コミットメント情報ａを受信し、（ｔａｇ，Ｃ，ａ）を格納しておき、（ｔａｇ，ｍ，ｚ）を受信すると、前記関係Ｒprivpk,tagのΣ−プロトコルに対するΣｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）を用いて、秘匿情報ｍが変更されていないかを判定する開封ステップと、を含む、
コミットメント方法。
【請求項７】
請求項６記載のコミットメント方法であって、
Ｚ／ｑＺを０以上ｑ未満の整数の集合とし、ｘ，ｙ←ＲＺ／ｑＺとし、ＧとＧＴを素数位数ｑのアーベル群とし、ｅ：Ｇ×Ｇ→ＧＴを非退化な双線形写像とし、ｇをＧの生成元とし、Ｈをハッシュ関数とし、Ｘ:=ｇｘとし、Ｙ:=ｇｙとし、前記公開鍵ｐｋ＝（ｇ，Ｘ，Ｙ，Ｈ，）とし、
前記第一暗号文生成ステップにおいて、前記コミットメント受信装置は、署名鍵ｏｔｓｋと検証鍵ｏｔｖｋを生成し、前記署名鍵ｏｔｓｋと前記タグ情報ｔａｇを用いて電子署名σを生成し、さらに、ｒ←Ｚ／ｑＺと前記検証鍵ｏｔｖｋを用いてｔ:=Ｈ（ｏｔｖｋ，ｇｒ）を計算し、前記電子署名σ及び検証鍵ｏｔｖｋを含む前記第一暗号文Ｃ:=（σ，ｏｔｖｋ，ｇｒ，（ＸｔＹ）ｒ）を生成し、
前記コミットメント情報生成ステップにおいて、前記コミットメント生成装置は、第一暗号文Ｃ＝（σ，ｏｔｖｋ，ｕ，τ）を受信し、前記公開鍵ｐｋと前記タグ情報ｔａｇを用いて、電子署名σが正当か否かを検証し、前記電子署名σが正当であって、ｅ（ｕ，ＸｔＹ）＝ｅ（ｇ，τ）が成り立つ場合には、前記第一暗号文Ｃが真の暗号文であると判定し、Ｋ＾←Ｇ＊＝（Ｇ−｛１Ｇ｝）とｚ←Ｚ／ｑＺを用いて、ａ＾＝ｅ（ｇ，Ｋ＾）ｚ・ｅ（ｕ，Ｘ）−ｍを計算し、コミットメント情報ａ＝（Ｋ＾，ａ＾）を前記コミットメント受信装置に送信し、
前記開封ステップにおいて、前記コミットメント受信装置は、コミットメント情報ａを受信し、（ｔａｇ，Ｃ，ａ）を格納しておき、（ｔａｇ，ｍ，ｚ）を受信すると、ｅ（ｇ，Ｋ＾）ｚ＝ａ＾・ｅ（ｕ，Ｘ）ｍが成り立つか否か判定し、成り立つ場合には、秘匿情報ｍが変更されていないと判定する、
コミットメント方法。
【請求項８】
請求項７記載のコミットメント方法であって、
Ｚ／ｑ２Ｚを０以上ｑ２未満の整数の集合とし、Ｇ２を素数位数ｑ２のアーベル群とし、Ｈ２をハッシュ関数とし、
添え字のｓ１、ｓ２、ｗ１及びｗ２はそれぞれｓ１、ｓ２、ｗ１及びｗ２を意味し、前記署名鍵ｏｔｓｋ及び前記検証鍵ｏｔｖｋは使い捨て署名であり、前記第一暗号文生成ステップにおいて、前記コミットメント受信装置はｇ１，ｇ２←ＲＧ２、ｓ１，ｓ２，ｗ１，ｗ２←ＲＺ／ｑ２Ｚを用いて、ｂ:=ｇ１ｗ１ｇ２ｗ２及びｈ:=ｇ１ｓ１ｇ２ｓ２を求め、前記検証鍵ｏｔｖｋ:=（ｇ１，ｇ２，ｈ，ｂ）、前記署名鍵ｏｔｓｋ＝（ｏｔｖｋ，ｓ１，ｓ２，ｗ１，ｗ２）を生成し、ｃ:=Ｈ２（ｏｔｖｋ，ｔａｇ）を求め、ｚ１:=ｘ１＋ｃ・ｓ１ ｍｏｄ ｑ２、ｚ２:=ｘ２＋ｃ・ｓ２ ｍｏｄ ｑ２を求め、前記電子署名σ＝（ｚ１，ｚ２）を生成し、
添え字のＨ２、ｚ１及びｚ２はそれぞれＨ２、ｚ１及びｚ２を意味し、前記第一暗号文検証ステップにおいて、前記コミットメント生成装置は、前記検証鍵ｏｔｖｋ:=（ｇ１，ｇ２，ｈ，ｂ）と前記電子署名σ＝（ｚ１，ｚ２）を用いて、ｇ１ｚ１g２ｚ２＝ｂｈＨ２（ｏｔｖｋ，ｔａｇ）が成り立つか否かを判定し、成り立つ場合には、前記電子署名σが正当であると判定する、
コミットメント方法。
【請求項９】
請求項４または５記載のコミットメント生成装置またはコミットメント受信装置として、コンピュータを機能させるためのプログラム。
【請求項１】
コミットメント生成装置とコミットメント受信装置からなるコミットメントシステムであって、
公開検証可能なタグベース鍵カプセル化メカニズムをΠ＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）とし、鍵生成アルゴリズムＧｅｎを用いて生成される公開鍵をｐｋとし、前記コミットメント生成装置と前記コミットメント受信装置とが共に知っているタグ情報をｔａｇとし、ｒを乱数とし、暗号化アルゴリズムＥｎｃに対し前記公開鍵ｐｋと前記タグ情報ｔａｇを与えて得られる第一暗号文をＣとし、第一鍵をＫとし、前記Πが定める関係Ｒprivpk,tagを
【数９】
とし、
前記コミットメント受信装置は暗号化アルゴリズムＥｎｃに対し前記公開鍵ｐｋと前記タグ情報ｔａｇを与え、第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成し、前記第一暗号文Ｃを前記コミットメント生成装置に送信し、
コミットを開封するときの証拠の一部をｚとし、コミットする秘匿情報をｍとし、前記コミットメント生成装置は前記第一暗号文Ｃを受信し、前記公開鍵ｐｋと前記タグ情報ｔａｇを用いて、前記第一暗号文Ｃが真の暗号文であるか否かを検証し、真の暗号文である場合には、前記関係Ｒprivpk,tagのΣ−プロトコルに対する（ａ，ｚ）←ｓｉｍΣ（Ｃ，ｍ）を計算し、コミットメント情報ａを前記コミットメント受信装置に送信し、
前記コミットメント受信装置はコミットメント情報ａを受信し、（ｔａｇ，Ｃ，ａ）を格納しておき、（ｔａｇ，ｍ，ｚ）を受信すると、前記関係Ｒprivpk,tagのΣ−プロトコルに対するΣｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）を用いて、秘匿情報ｍが変更されていないかを判定する、
コミットメントシステム。
【請求項２】
請求項１記載のコミットメントシステムであって、
Ｚ／ｑＺを０以上ｑ未満の整数の集合とし、ｘ，ｙ←ＲＺ／ｑＺとし、ＧとＧＴを素数位数ｑのアーベル群とし、ｅ：Ｇ×Ｇ→ＧＴを非退化な双線形写像とし、ｇをＧの生成元とし、Ｈをハッシュ関数とし、Ｘ:=ｇｘとし、Ｙ:=ｇｙとし、前記公開鍵ｐｋ＝（ｇ，Ｘ，Ｙ，Ｈ，）とし、
前記コミットメント受信装置は、署名鍵ｏｔｓｋと検証鍵ｏｔｖｋを生成し、前記署名鍵ｏｔｓｋと前記タグ情報ｔａｇを用いて電子署名σを生成し、さらに、ｒ←Ｚ／ｑＺと前記検証鍵ｏｔｖｋを用いてｔ:=Ｈ（ｏｔｖｋ，ｇｒ）を計算し、前記電子署名σ及び検証鍵ｏｔｖｋを含む前記第一暗号文Ｃ:=（σ，ｏｔｖｋ，ｇｒ，（ＸｔＹ）ｒ）を生成し、
前記コミットメント生成装置は、第一暗号文Ｃ＝（σ，ｏｔｖｋ，ｕ，τ）を受信し、前記公開鍵ｐｋと前記タグ情報ｔａｇを用いて、電子署名σが正当か否かを検証し、前記電子署名σが正当であって、ｅ（ｕ，ＸｔＹ）＝ｅ（ｇ，τ）が成り立つ場合には、前記第一暗号文Ｃが真の暗号文であると判定し、Ｋ＾←Ｇ＊＝（Ｇ−｛１Ｇ｝）とｚ←Ｚ／ｑＺを用いて、ａ＾＝ｅ（ｇ，Ｋ＾）ｚ・ｅ（ｕ，Ｘ）−ｍを計算し、コミットメント情報ａ＝（Ｋ＾，ａ＾）を前記コミットメント受信装置に送信し、
前記コミットメント受信装置は、コミットメント情報ａを受信し、（ｔａｇ，Ｃ，ａ）を格納しておき、（ｔａｇ，ｍ，ｚ）を受信すると、ｅ（ｇ，Ｋ＾）ｚ＝ａ＾・ｅ（ｕ，Ｘ）ｍが成り立つか否か判定し、成り立つ場合には、秘匿情報ｍが変更されていないと判定する、
コミットメントシステム。
【請求項３】
請求項２記載のコミットメントシステムであって、
Ｚ／ｑ２Ｚを０以上ｑ２未満の整数の集合とし、Ｇ２を素数位数ｑ２のアーベル群とし、Ｈ２をハッシュ関数とし、
添え字のｓ１、ｓ２、ｗ１及びｗ２はそれぞれｓ１、ｓ２、ｗ１及びｗ２を意味し、前記署名鍵ｏｔｓｋ及び前記検証鍵ｏｔｖｋは使い捨て署名であり、前記コミットメント受信装置はｇ１，ｇ２←ＲＧ２、ｓ１，ｓ２，ｗ１，ｗ２←ＲＺ／ｑ２Ｚを用いて、ｂ:=ｇ１ｗ１ｇ２ｗ２及びｈ:=ｇ１ｓ１ｇ２ｓ２を求め、前記検証鍵ｏｔｖｋ:=（ｇ１，ｇ２，ｈ，ｂ）、前記署名鍵ｏｔｓｋ＝（ｏｔｖｋ，ｓ１，ｓ２，ｗ１，ｗ２）を生成し、ｃ:=Ｈ２（ｏｔｖｋ，ｔａｇ）を求め、ｚ１:=ｘ１＋ｃ・ｓ１ ｍｏｄ ｑ２、ｚ２:=ｘ２＋ｃ・ｓ２ ｍｏｄ ｑ２を求め、前記電子署名σ＝（ｚ１，ｚ２）を生成し、
添え字のＨ２、ｚ１及びｚ２はそれぞれＨ２、ｚ１及びｚ２を意味し、前記コミットメント生成装置は、前記検証鍵ｏｔｖｋ:=（ｇ１，ｇ２，ｈ，ｂ）と前記電子署名σ＝（ｚ１，ｚ２）を用いて、ｇ１ｚ１g２ｚ２＝ｂｈＨ２（ｏｔｖｋ，ｔａｇ）が成り立つか否かを判定し、成り立つ場合には、前記電子署名σが正当であると判定する、
コミットメントシステム。
【請求項４】
秘匿情報ｍをコミットし、コミットメント情報ａを生成するコミットメント生成装置であって、
公開検証可能なタグベース鍵カプセル化メカニズムをΠ＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）とし、鍵生成アルゴリズムＧｅｎを用いて生成される公開鍵をｐｋとし、当該コミットメント生成装置とコミットメント情報ａを受信するコミットメント受信装置とが共に知っているタグ情報をｔａｇとし、ｒを乱数とし、暗号化アルゴリズムＥｎｃに対し前記公開鍵ｐｋと前記タグ情報ｔａｇを与えて得られる第一暗号文をＣとし、第一鍵をＫとし、前記Πが定める関係Ｒprivpk,tagを
【数１０】
とし、コミットを開封するときの証拠の一部をｚとし、
第一暗号文Ｃを受信し、公開鍵ｐｋとタグ情報ｔａｇとを用いて、受信した前記第一暗号文Ｃが真の暗号文であるか否かを検証し、真の暗号文である場合には、前記関係Ｒprivpk,tagのΣ−プロトコルに対する（ａ，ｚ）←ｓｉｍΣ（Ｃ，ｍ）を計算し、コミットメント情報ａを前記コミットメント受信装置に送信する、
コミットメント生成装置。
【請求項５】
コミットメント情報ａを受信するコミットメント受信装置であって、
公開検証可能なタグベース鍵カプセル化メカニズムをΠ＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）とし、鍵生成アルゴリズムＧｅｎを用いて生成される公開鍵をｐｋとし、秘匿情報ｍをコミットし、コミットメント情報ａを生成するコミットメント生成装置と当該コミットメント受信装置とが共に知っているタグ情報をｔａｇとし、ｒを乱数とし、暗号化アルゴリズムＥｎｃに対し前記公開鍵ｐｋと前記タグ情報ｔａｇを与えて得られる第一暗号文をＣとし、第一鍵をＫとし、前記Πが定める関係Ｒprivpk,tagを
【数１１】
とし、
暗号化アルゴリズムＥｎｃに対し前記公開鍵ｐｋと前記タグ情報ｔａｇを与え、第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成し、前記第一暗号文Ｃを前記コミットメント受信装置に送信し、
コミットを開封するときの証拠の一部をｚとし、前記コミットメント生成装置からコミットメント情報ａを受信し、（ｔａｇ，Ｃ，ａ）を格納しておき、（ｔａｇ，ｍ，ｚ）を受信すると、Σ−プロトコルに対するΣｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）を用いて、秘匿情報ｍが変更されていないかを判定する、
コミットメント受信装置。
【請求項６】
コミットメント生成装置とコミットメント受信装置を用いたコミットメント方法であって、
公開検証可能なタグベース鍵カプセル化メカニズムをΠ＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）とし、鍵生成アルゴリズムＧｅｎを用いて生成される公開鍵をｐｋとし、前記コミットメント生成装置と前記コミットメント受信装置とが共に知っているタグ情報をｔａｇとし、ｒを乱数とし、暗号化アルゴリズムＥｎｃに対し前記公開鍵ｐｋと前記タグ情報ｔａｇを与えて得られる第一暗号文をＣとし、第一鍵をＫとし、前記Πが定める関係Ｒprivpk,tagを
【数１２】
とし、
前記コミットメント受信装置において、暗号化アルゴリズムＥｎｃに対し前記公開鍵ｐｋと前記タグ情報ｔａｇを与え、第一暗号文Ｃと第一鍵Ｋとの組（Ｃ，Ｋ）を生成し、前記第一暗号文Ｃを前記コミットメント生成装置に送信する第一暗号文生成ステップと、
コミットを開封するときの証拠の一部をｚとし、コミットする秘匿情報をｍとし、前記コミットメント生成装置が、前記第一暗号文Ｃを受信し、コミットメント生成装置において、前記公開鍵ｐｋと前記タグ情報ｔａｇを用いて、前記第一暗号文Ｃが真の暗号文であるか否かを検証し、真の暗号文である場合には、前記関係Ｒprivpk,tagのΣ−プロトコルに対する（ａ，ｚ）←ｓｉｍΣ（Ｃ，ｍ）を計算し、コミットメント情報ａを前記コミットメント受信装置に送信するコミットメント情報生成ステップと、
前記コミットメント受信装置において、コミットメント情報ａを受信し、（ｔａｇ，Ｃ，ａ）を格納しておき、（ｔａｇ，ｍ，ｚ）を受信すると、前記関係Ｒprivpk,tagのΣ−プロトコルに対するΣｖｒｆｙ（Ｃ，ａ，ｍ，ｚ）を用いて、秘匿情報ｍが変更されていないかを判定する開封ステップと、を含む、
コミットメント方法。
【請求項７】
請求項６記載のコミットメント方法であって、
Ｚ／ｑＺを０以上ｑ未満の整数の集合とし、ｘ，ｙ←ＲＺ／ｑＺとし、ＧとＧＴを素数位数ｑのアーベル群とし、ｅ：Ｇ×Ｇ→ＧＴを非退化な双線形写像とし、ｇをＧの生成元とし、Ｈをハッシュ関数とし、Ｘ:=ｇｘとし、Ｙ:=ｇｙとし、前記公開鍵ｐｋ＝（ｇ，Ｘ，Ｙ，Ｈ，）とし、
前記第一暗号文生成ステップにおいて、前記コミットメント受信装置は、署名鍵ｏｔｓｋと検証鍵ｏｔｖｋを生成し、前記署名鍵ｏｔｓｋと前記タグ情報ｔａｇを用いて電子署名σを生成し、さらに、ｒ←Ｚ／ｑＺと前記検証鍵ｏｔｖｋを用いてｔ:=Ｈ（ｏｔｖｋ，ｇｒ）を計算し、前記電子署名σ及び検証鍵ｏｔｖｋを含む前記第一暗号文Ｃ:=（σ，ｏｔｖｋ，ｇｒ，（ＸｔＹ）ｒ）を生成し、
前記コミットメント情報生成ステップにおいて、前記コミットメント生成装置は、第一暗号文Ｃ＝（σ，ｏｔｖｋ，ｕ，τ）を受信し、前記公開鍵ｐｋと前記タグ情報ｔａｇを用いて、電子署名σが正当か否かを検証し、前記電子署名σが正当であって、ｅ（ｕ，ＸｔＹ）＝ｅ（ｇ，τ）が成り立つ場合には、前記第一暗号文Ｃが真の暗号文であると判定し、Ｋ＾←Ｇ＊＝（Ｇ−｛１Ｇ｝）とｚ←Ｚ／ｑＺを用いて、ａ＾＝ｅ（ｇ，Ｋ＾）ｚ・ｅ（ｕ，Ｘ）−ｍを計算し、コミットメント情報ａ＝（Ｋ＾，ａ＾）を前記コミットメント受信装置に送信し、
前記開封ステップにおいて、前記コミットメント受信装置は、コミットメント情報ａを受信し、（ｔａｇ，Ｃ，ａ）を格納しておき、（ｔａｇ，ｍ，ｚ）を受信すると、ｅ（ｇ，Ｋ＾）ｚ＝ａ＾・ｅ（ｕ，Ｘ）ｍが成り立つか否か判定し、成り立つ場合には、秘匿情報ｍが変更されていないと判定する、
コミットメント方法。
【請求項８】
請求項７記載のコミットメント方法であって、
Ｚ／ｑ２Ｚを０以上ｑ２未満の整数の集合とし、Ｇ２を素数位数ｑ２のアーベル群とし、Ｈ２をハッシュ関数とし、
添え字のｓ１、ｓ２、ｗ１及びｗ２はそれぞれｓ１、ｓ２、ｗ１及びｗ２を意味し、前記署名鍵ｏｔｓｋ及び前記検証鍵ｏｔｖｋは使い捨て署名であり、前記第一暗号文生成ステップにおいて、前記コミットメント受信装置はｇ１，ｇ２←ＲＧ２、ｓ１，ｓ２，ｗ１，ｗ２←ＲＺ／ｑ２Ｚを用いて、ｂ:=ｇ１ｗ１ｇ２ｗ２及びｈ:=ｇ１ｓ１ｇ２ｓ２を求め、前記検証鍵ｏｔｖｋ:=（ｇ１，ｇ２，ｈ，ｂ）、前記署名鍵ｏｔｓｋ＝（ｏｔｖｋ，ｓ１，ｓ２，ｗ１，ｗ２）を生成し、ｃ:=Ｈ２（ｏｔｖｋ，ｔａｇ）を求め、ｚ１:=ｘ１＋ｃ・ｓ１ ｍｏｄ ｑ２、ｚ２:=ｘ２＋ｃ・ｓ２ ｍｏｄ ｑ２を求め、前記電子署名σ＝（ｚ１，ｚ２）を生成し、
添え字のＨ２、ｚ１及びｚ２はそれぞれＨ２、ｚ１及びｚ２を意味し、前記第一暗号文検証ステップにおいて、前記コミットメント生成装置は、前記検証鍵ｏｔｖｋ:=（ｇ１，ｇ２，ｈ，ｂ）と前記電子署名σ＝（ｚ１，ｚ２）を用いて、ｇ１ｚ１g２ｚ２＝ｂｈＨ２（ｏｔｖｋ，ｔａｇ）が成り立つか否かを判定し、成り立つ場合には、前記電子署名σが正当であると判定する、
コミットメント方法。
【請求項９】
請求項４または５記載のコミットメント生成装置またはコミットメント受信装置として、コンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１２−１５６５９０（Ｐ２０１２−１５６５９０Ａ）
【公開日】平成２４年８月１６日（２０１２．８．１６）
【国際特許分類】
【出願番号】特願２０１１−１１２１８（Ｐ２０１１−１１２１８）
【出願日】平成２３年１月２１日（２０１１．１．２１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年８月１６日（２０１２．８．１６）
【国際特許分類】
【出願日】平成２３年１月２１日（２０１１．１．２１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]