"コミットメント生成装置とコミットメント受信装置からなるコミットメントシステムであって、公開検証可能なタグベース鍵カプセル化メカニズムをΠ=Gen,Enc,Decとし、鍵生成アルゴリズムGenを用いて生成される公開鍵をpkとし、前記コミットメント生成装置と前記コミットメント受信装置とが共に知っているタグ情報をtagとし、rを乱数とし、暗号化アルゴリズムEncに対し前記公開鍵pkと前記タグ情報tagを与えて得られる第一暗号文をCとし、第一鍵をKとし、前記Πが定める関係Rprivpktagをとし、前記コミットメント受信装置は暗号化アルゴリズムEncに対し前記公開鍵pkと前記タグ情報tagを与え、第一暗号文Cと第一鍵Kとの組C,Kを生成し、前記第一暗号文Cを前記コミットメント生成装置に送信し、コミットを開封するときの証拠の一部をzとし、コミットする秘匿情報をmとし、前記コミットメント生成装置は前記第一暗号文Cを受信し、前記公開鍵pkと前記タグ情報tagを用いて、前記第一暗号文Cが真の暗号文であるか否かを検証し、真の暗号文である場合には、前記関係RprivpktagのΣ-プロトコルに対するa,z←simΣC,mを計算し、コミットメント情報aを前記コミットメント受信装置に送信し、前記コミットメント受信装置はコミットメント情報aを受信し、tag,C,aを格納しておき、tag,m,zを受信すると、前記関係RprivpktagのΣ-プロトコルに対するΣvrfyC,a,m,zを用いて、秘匿情報mが変更されていないかを判定する、コミットメントシステム。請求項1記載のコミットメントシステムであって、Z/qZを0以上q未満の整数の集合とし、x,y←RZ/qZとし、GとGTを素数位数qのアーベル群とし、e:G×G→GTを非退化な双線形写像とし、gをGの生成元とし、Hをハッシュ関数とし、Xgxとし、Ygyとし、前記公開鍵pk=g,X,Y,H,とし、前記コミットメント受信装置は、署名鍵otskと検証鍵otvkを生成し、前記署名鍵otskと前記タグ情報tagを用いて電子署名σを生成し、さらに、r←Z/qZと前記検証鍵otvkを用いてtHotvk,grを計算し、前記電子署名σ及び検証鍵otvkを含む前記第一暗号文Cσ,otvk,gr,XtYrを生成し、前記コミットメント生成装置は、第一暗号文C=σ,otvk,u,τを受信し、前記公開鍵pkと前記タグ情報tagを用いて、電子署名σが正当か否かを検証し、前記電子署名σが正当であって、eu,XtY=eg,τが成り立つ場合には、前記第一暗号文Cが真の暗号文であると判定し、K^←G=G-{1G}とz←Z/qZを用いて、a^=eg,K^zeu,X-mを計算し、コミットメント情報a=K^,a^を前記コミットメント受信装置に送信し、前記コミットメント受信装置は、コミットメント情報aを受信し、tag,C,aを格納しておき、tag,m,zを受信すると、eg,K^z=a^eu,Xmが成り立つか否か判定し、成り立つ場合には、秘匿情報mが変更されていないと判定する、コミットメントシステム。請求項2記載のコミットメントシステムであって、Z/q2Zを0以上q2未満の整数の集合とし、G2を素数位数q2のアーベル群とし、H2をハッシュ関数とし、添え字のs1、s2、w1及びw2はそれぞれs1、s2、w1及びw2を意味し、前記署名鍵otsk及び前記検証鍵otvkは使い捨て署名であり、前記コミットメント受信装置はg1,g2←RG2、s1,s2,w1,w2←RZ/q2Zを用いて、bg1w1g2w2及びhg1s1g2s2を求め、前記検証鍵otvkg1,g2,h,b、前記署名鍵otsk=otvk,s1,s2,w1,w2を生成し、cH2otvk,tagを求め、z1x1cs1modq2、z2x2cs2modq2を求め、前記電子署名σ=z1,z2を生成し、添え字のH2、z1及びz2はそれぞれH2、z1及びz2を意味し、前記コミットメント生成装置は、前記検証鍵otvkg1,g2,h,bと前記電子署名σ=z1,z2を用いて、g1z1g2z2=bhH2otvk,tagが成り立つか否かを判定し、成り立つ場合には、前記電子署名σが正当であると判定する、コミットメントシステム。秘匿情報mをコミットし、コミットメント情報aを生成するコミットメント生成装置であって、公開検証可能なタグベース鍵カプセル化メカニズムをΠ=Gen,Enc,Decとし、鍵生成アルゴリズムGenを用いて生成される公開鍵をpkとし、当該コミットメント生成装置とコミットメント情報aを受信するコミットメント受信装置とが共に知っているタグ情報をtagとし、rを乱数とし、暗号化アルゴリズムEncに対し前記公開鍵pkと前記タグ情報tagを与えて得られる第一暗号文をCとし、第一鍵をKとし、前記Πが定める関係Rprivpktagをとし、コミットを開封するときの証拠の一部をzとし、第一暗号文Cを受信し、公開鍵pkとタグ情報tagとを用いて、受信した前記第一暗号文Cが真の暗号文であるか否かを検証し、真の暗号文である場合には、前記関係RprivpktagのΣ-プロトコルに対するa,z←simΣC,mを計算し、コミットメント情報aを前記コミットメント受信装置に送信する、コミットメント生成装置。コミットメント情報aを受信するコミットメント受信装置であって、公開検証可能なタグベース鍵カプセル化メカニズムをΠ=Gen,Enc,Decとし、鍵生成アルゴリズムGenを用いて生成される公開鍵をpkとし、秘匿情報mをコミットし、コミットメント情報aを生成するコミットメント生成装置と当該コミットメント受信装置とが共に知っているタグ情報をtagとし、rを乱数とし、暗号化アルゴリズムEncに対し前記公開鍵pkと前記タグ情報tagを与えて得られる第一暗号文をCとし、第一鍵をKとし、前記Πが定める関係Rprivpktagをとし、暗号化アルゴリズムEncに対し前記公開鍵pkと前記タグ情報tagを与え、第一暗号文Cと第一鍵Kとの組C,Kを生成し、前記第一暗号文Cを前記コミットメント受信装置に送信し、コミットを開封するときの証拠の一部をzとし、前記コミットメント生成装置からコミットメント情報aを受信し、tag,C,aを格納しておき、tag,m,zを受信すると、Σ-プロトコルに対するΣvrfyC,a,m,zを用いて、秘匿情報mが変更されていないかを判定する、コミットメント受信装置。コミットメント生成装置とコミットメント受信装置を用いたコミットメント方法であって、公開検証可能なタグベース鍵カプセル化メカニズムをΠ=Gen,Enc,Decとし、鍵生成アルゴリズムGenを用いて生成される公開鍵をpkとし、前記コミットメント生成装置と前記コミットメント受信装置とが共に知っているタグ情報をtagとし、rを乱数とし、暗号化アルゴリズムEncに対し前記公開鍵pkと前記タグ情報tagを与えて得られる第一暗号文をCとし、第一鍵をKとし、前記Πが定める関係Rprivpktagをとし、前記コミットメント受信装置において、暗号化アルゴリズムEncに対し前記公開鍵pkと前記タグ情報tagを与え、第一暗号文Cと第一鍵Kとの組C,Kを生成し、前記第一暗号文Cを前記コミットメント生成装置に送信する第一暗号文生成ステップと、コミットを開封するときの証拠の一部をzとし、コミットする秘匿情報をmとし、前記コミットメント生成装置が、前記第一暗号文Cを受信し、コミットメント生成装置において、前記公開鍵pkと前記タグ情報tagを用いて、前記第一暗号文Cが真の暗号文であるか否かを検証し、真の暗号文である場合には、前記関係RprivpktagのΣ-プロトコルに対するa,z←simΣC,mを計算し、コミットメント情報aを前記コミットメント受信装置に送信するコミットメント情報生成ステップと、前記コミットメント受信装置において、コミットメント情報aを受信し、tag,C,aを格納しておき、tag,m,zを受信すると、前記関係RprivpktagのΣ-プロトコルに対するΣvrfyC,a,m,zを用いて、秘匿情報mが変更されていないかを判定する開封ステップと、を含む、コミットメント方法。請求項6記載のコミットメント方法であって、Z/qZを0以上q未満の整数の集合とし、x,y←RZ/qZとし、GとGTを素数位数qのアーベル群とし、e:G×G→GTを非退化な双線形写像とし、gをGの生成元とし、Hをハッシュ関数とし、Xgxとし、Ygyとし、前記公開鍵pk=g,X,Y,H,とし、前記第一暗号文生成ステップにおいて、前記コミットメント受信装置は、署名鍵otskと検証鍵otvkを生成し、前記署名鍵otskと前記タグ情報tagを用いて電子署名σを生成し、さらに、r←Z/qZと前記検証鍵otvkを用いてtHotvk,grを計算し、前記電子署名σ及び検証鍵otvkを含む前記第一暗号文Cσ,otvk,gr,XtYrを生成し、前記コミットメント情報生成ステップにおいて、前記コミットメント生成装置は、第一暗号文C=σ,otvk,u,τを受信し、前記公開鍵pkと前記タグ情報tagを用いて、電子署名σが正当か否かを検証し、前記電子署名σが正当であって、eu,XtY=eg,τが成り立つ場合には、前記第一暗号文Cが真の暗号文であると判定し、K^←G=G-{1G}とz←Z/qZを用いて、a^=eg,K^zeu,X-mを計算し、コミットメント情報a=K^,a^を前記コミットメント受信装置に送信し、前記開封ステップにおいて、前記コミットメント受信装置は、コミットメント情報aを受信し、tag,C,aを格納しておき、tag,m,zを受信すると、eg,K^z=a^eu,Xmが成り立つか否か判定し、成り立つ場合には、秘匿情報mが変更されていないと判定する、コミットメント方法。請求項7記載のコミットメント方法であって、Z/q2Zを0以上q2未満の整数の集合とし、G2を素数位数q2のアーベル群とし、H2をハッシュ関数とし、添え字のs1、s2、w1及びw2はそれぞれs1、s2、w1及びw2を意味し、前記署名鍵otsk及び前記検証鍵otvkは使い捨て署名であり、前記第一暗号文生成ステップにおいて、前記コミットメント受信装置はg1,g2←RG2、s1,s2,w1,w2←RZ/q2Zを用いて、bg1w1g2w2及びhg1s1g2s2を求め、前記検証鍵otvkg1,g2,h,b、前記署名鍵otsk=otvk,s1,s2,w1,w2を生成し、cH2otvk,tagを求め、z1x1cs1modq2、z2x2cs2modq2を求め、前記電子署名σ=z1,z2を生成し、添え字のH2、z1及びz2はそれぞれH2、z1及びz2を意味し、前記第一暗号文検証ステップにおいて、前記コミットメント生成装置は、前記検証鍵otvkg1,g2,h,bと前記電子署名σ=z1,z2を用いて、g1z1g2z2=bhH2otvk,tagが成り立つか否かを判定し、成り立つ場合には、前記電子署名σが正当であると判定する、コミットメント方法。請求項4または5記載のコミットメント生成装置またはコミットメント受信装置として、コンピュータを機能させるためのプログラム。しかしながら、非特許文献3、4、5、6及び7記載の従来技術は、全て使い捨てでない署名から共通の変換方法の基にsimulationsound落し戸付きコミットメントを構成する。そのため、従来の署名が破られると、同時に従来技術のコミットメント方式も破られる可能性がある。本発明では、公開検証可能なタグベース鍵カプセル化メカニズムを用いて、新しいSSTC方式のコミットメントシステム、コミットメント生成装置、コミットメント受信装置、その方法及びプログラムを提供することを目的とする。上記の課題を解決するために、本発明の第一の態様によれば、コミットメントシステムはコミットメント生成装置とコミットメント受信装置からなる。公開検証可能なタグベース鍵カプセル化メカニズムをΠ=Gen,Enc,Decとし、鍵生成アルゴリズムGenを用いて生成される公開鍵をpkとし、コミットメント生成装置とコミットメント受信装置とが共に知っているタグ情報をtagとし、rを乱数とし、暗号化アルゴリズムEncに対し公開鍵pkとタグ情報tagを与えて得られる第一暗号文をCとし、第一鍵をKとし、Πが定める関係Rprivpktagをとする。コミットメント受信装置は暗号化アルゴリズムEncに対し公開鍵pkとタグ情報tagを与え、第一暗号文Cと第一鍵Kとの組C,Kを生成し、第一暗号文Cをコミットメント生成装置に送信する。コミットを開封するときの証拠の一部をzとし、コミットする秘匿情報をmとし、コミットメント生成装置は第一暗号文Cを受信し、公開鍵pkとタグ情報tagを用いて、第一暗号文Cが真の暗号文であるか否かを検証し、真の暗号文である場合には、関係RprivpktagのΣ-プロトコルに対するa,z←simΣC,mを計算し、コミットメント情報aをコミットメント受信装置に送信する。コミットメント受信装置はコミットメント情報aを受信し、tag,C,aを格納しておき、tag,m,zを受信すると、関係RprivpktagのΣ-プロトコルに対するΣvrfyC,a,m,zを用いて、秘匿情報mが変更されていないかを判定する。上記の課題を解決するために、本発明の第二の態様によれば、コミットメント生成装置は秘匿情報mをコミットし、コミットメント情報aを生成する。公開検証可能なタグベース鍵カプセル化メカニズムをΠ=Gen,Enc,Decとし、鍵生成アルゴリズムGenを用いて生成される公開鍵をpkとし、当該コミットメント生成装置とコミットメント情報aを受信するコミットメント受信装置とが共に知っているタグ情報をtagとし、rを乱数とし、暗号化アルゴリズムEncに対し公開鍵pkとタグ情報tagを与えて得られる第一暗号文をCとし、第一鍵をKとし、Πが定める関係Rprivpktagをとし、コミットを開封するときの証拠の一部をzとする。第一暗号文Cを受信し、公開鍵pkとタグ情報tagとを用いて、受信した第一暗号文Cが真の暗号文であるか否かを検証し、真の暗号文である場合には、関係RprivpktagのΣ-プロトコルに対するa,z←simΣC,mを計算し、コミットメント情報aをコミットメント受信装置に送信する。上記の課題を解決するために、本発明の第三の態様によれば、コミットメント受信装置は、コミットメント情報aを受信する。公開検証可能なタグベース鍵カプセル化メカニズムをΠ=Gen,Enc,Decとし、鍵生成アルゴリズムGenを用いて生成される公開鍵をpkとし、秘匿情報mをコミットし、コミットメント情報aを生成するコミットメント生成装置と当該コミットメント受信装置とが共に知っているタグ情報をtagとし、rを乱数とし、暗号化アルゴリズムEncに対し公開鍵pkとタグ情報tagを与えて得られる第一暗号文をCとし、第一鍵をKとし、Πが定める関係Rprivpktagをとする。暗号化アルゴリズムEncに対し公開鍵pkとタグ情報tagを与え、第一暗号文Cと第一鍵Kとの組C,Kを生成し、第一暗号文Cをコミットメント受信装置に送信し、コミットを開封するときの証拠の一部をzとし、コミットメント生成装置からコミットメント情報aを受信し、tag,C,aを格納しておき、tag,m,zを受信すると、Σ-プロトコルに対するΣvrfyC,a,m,zを用いて、秘匿情報mが変更されていないかを判定する。上記の課題を解決するために、本発明の第四の態様によれば、コミットメント方法は、コミットメント生成装置とコミットメント受信装置を用いる。公開検証可能なタグベース鍵カプセル化メカニズムをΠ=Gen,Enc,Decとし、鍵生成アルゴリズムGenを用いて生成される公開鍵をpkとし、コミットメント生成装置とコミットメント受信装置とが共に知っているタグ情報をtagとし、rを乱数とし、暗号化アルゴリズムEncに対し公開鍵pkとタグ情報tagを与えて得られる第一暗号文をCとし、第一鍵をKとし、Πが定める関係Rprivpktagをとする。コミットメント受信装置において、暗号化アルゴリズムEncに対し公開鍵pkとタグ情報tagを与え、第一暗号文Cと第一鍵Kとの組C,Kを生成し、第一暗号文Cをコミットメント生成装置に送信する。コミットを開封するときの証拠の一部をzとし、コミットする秘匿情報をmとし、コミットメント生成装置が、第一暗号文Cを受信し、コミットメント生成装置において、公開鍵pkとタグ情報tagを用いて、第一暗号文Cが真の暗号文であるか否かを検証し、真の暗号文である場合には、関係RprivpktagのΣ-プロトコルに対するa,z←simΣC,mを計算し、コミットメント情報aをコミットメント受信装置に送信する。コミットメント受信装置において、コミットメント情報aを受信し、tag,C,aを格納しておき、tag,m,zを受信すると、関係RprivpktagのΣ-プロトコルに対するΣvrfyC,a,m,zを用いて、秘匿情報mが変更されていないかを判定する。本発明は、従来の署名のみに基づかずに、公開検証可能なタグベース鍵カプセル化メカニズムを用いて、新しいSSTC方式を構成するため、従来の署名が破られた場合にも安全であるという効果を奏する。以下、本発明の実施形態について、説明する。<定義>まず、本形態で使用する用語や記号を定義する。{0,1}kは、kビット長のバイナリ系列データの集合を意味し、{0,1}は全てのバイナリ系列、つまり、{0,1}=∪k≧0{0,1}kを表す。確率的アルゴリズムMは,入力x∈{0;1}とMの内部乱数rの二入力関数である。y=Mx;rは、入力x、乱数rのときの出力がyであることを意味する。y←Mxは、Mの入力xでの確率的試行を表す。例えば、Pr[y←Mx:y=1]<1/2とは、乱数rに従って出力された確率変数yが、1である確率が1/2未満であることを意味する。AXの試行の後、BYの試行が起き、さらに...のような確率的試行の時系列的並びを、a←AX;b←BY;...のように書く。Pr[a←A;b←B:event]は、確率的試行a←A;b←Bの下での事象eventの条件付き生起確率を表す。なお、記述を短くするため、Pr[y←Mx:y=1]のかわりにPr[Mx=1]と書く場合がある。なお、確定的deterministicなアルゴリズムは、内部コインの無い確率的アルゴリズムと考えてもよい。[タグベース鍵カプセル化メカニズムTag-KEMTagbasedKeyEncapsulationMechanisim]Π=Gen,Enc,Decが、Tag-KEM参考文献1及び2参照であるとは、Πが次のような性質1~性質4を満たすアルゴリズムの集合であるときをいう。参考文献1:VShoupAproposalforanISOstandardforpublickeyencryptionTechnicalreportDecember2001CryptologyePrintArchiveReport2001112:MAbeRGennaroandKKurosawaTagKEMDEMAnewframeworkforhybridencryptionJournalofCryptology2008Volume21Number1p97130性質1pk,sk←Gen1n:鍵生成アルゴリズムGenは、セキュリティパラメータnを入力にとり、公開鍵秘密鍵の組pk,skを出力する確率的アルゴリズムである。性質2C,K←Encpk,tag。暗号化アルゴリズムEncは、公開鍵pkとタグ情報tag∈{0;1}を入力とし、乱数r∈Grを内部発生させ、暗号文Cと鍵Kを計算し出力する確率的アルゴリズムである。性質3復号アルゴリズムDecは、秘密鍵sk、タグ情報tag及び暗号文Cを入力としてとり、鍵K=Decsk,tag,Cを計算する確定的アルゴリズムである。性質4全てのn∈N,全てのtag∈{0,1}に対して、Pr←Gen←EncDecK1である。[暗号文と鍵との間のNP関係と公開検証可能性]Tag-KEMΠに関する以下のようなNP関係を定義する。暗号文C∈{0;1}が、対応する鍵Kが存在する真の暗号文であるすなわち、あるKが存在してC,K∈Rprivpk,tagかを、公開鍵pkとtagのみで検証できるとき、Tag-KEMΠは公開検証可能という。[Σ―プロトコル]R={x,w}をNP関係とする。関係Rから定義される言語をLR{x|∃ws.t.x,w∈R}とする。但し、ABはAという記号の意味するところをBと定義することを意味する。関係RのΣ-プロトコル非特許文献8参照とは、証明者と検証者からなる三交信の次のような認証プロトコルである。なお、x,w∈Rとする。xを証明者と検証者への共通入力として、証明者は、さらにwを与えられる。1証明者は、乱数raを選び、第一メッセージa=Σcomx,w;raを計算し、検証者に送る。2検証者は、第二メッセージの乱数c←RΣchを選び証明者に送り返す。但し、A←RBは、集合BからランダムにAを選択することを意味する。なお、Σchはチャレンジc例えば、乱数を生成または選択するアルゴリズムである。3証明者は、第三メッセージz=Σansx,w,ra,cを計算し、検証者に送る。第三メッセージzはチャレンジcに対する証明者の返答であり、返答生成アルゴリズムΣansを用いて生成する。検証者は、b=Σvrfyx,a,c,zを計算して出力する。Σvrfyは、検証アルゴリズムであり、b=1であれば、検証者は、証明者の一連の認証行為を受理したという意味でありそれ以外の値であれば、否決したという意味を持っている。第一メッセージaと返答zとが、wを知っている証明者により、それぞれ第一メッセージ生成アルゴリズムΣcomと返答生成アルゴリズムΣansを用いて生成されたものであれば、b=1となる。Σ-プロトコルは以下の性質を満たす。[完全性]∀ra∀c∈ΣchΣvrfycΣans1[特別健全性]つまり、xが言語LRに元として含まれないとき、aに対して、zが存在するようなcは、唯一に決まる。さらに、c≠c’のとき、二つの受理される履歴a,c,zとa,c’,z’から、x,w∈Rを満たすwが必ず計算できる。[正直な検証者に対する特別ゼロ知識]∀x∈LR,∀c∈Σchに対して、検証者に受理されるa,c,z←simΣx,cを作ることができる。さらに、cをΣchからランダムに選び、simΣに入力して作った、a,c,zは、正直な証明者が正直な検証者と実行した履歴と同分布になる。なお、任意のNP関係に対して、必ずΣ-プロトコルが存在することはすでに知られている参考文献3参照。参考文献3:OGoldreichSMicaliandAWigdersonProofsthatyieldnothingbuttheirvalidityoralllanguagesinnphavezeroknowledgeproofsystemsJournaloftheACM19911p691729<第一実施形態><コミットメントシステム1>図1及び図2を用いて第一実施形態に係るコミットメントシステム1の処理概要を説明する。コミットメントシステム1は、第三者装置11とコミットメント生成装置13とコミットメント受信装置15とからなり、これらの各装置は、例えばインターネットである通信網12を介して相互に通信可能とされている。Π=Gen,Enc,Decを公開検証可能なタグベース鍵カプセル化メカニズムとする。関係RprivpktagはΠにより定義される。関係RprivpktagはNP関係であり、とする。Πと関係Rprivpktagに対するΣ-プロトコルからコミットメントシステム1を構成する。第三者装置11はセキュリティパラメータnを入力としs1、鍵生成アルゴリズムGenを用いて、秘密鍵skと公開鍵pkを生成するs2。この公開鍵pkを共通参照データとする。そして、少なくともコミットメント生成装置13とコミットメント受信装置15が共通参照データcrsを利用可能な状態で、第三者装置11は共通参照データcrsを格納しておく。コミットメント生成装置13とコミットメント受信装置15は、タグ情報tagを取得するs3。tag情報とは、コミットメント生成装置13とコミットメント受信装置15とが共に知っている情報であり、例えば、プロセスのセッションID等である。なお、tag情報は後述する第一暗号文Cと第一鍵Kとの組C,Kを生成する前にコミットメント生成装置13とコミットメント受信装置15とが共に取得すればよく、どのような取得方法を用いてもよい。さらに、コミットメント受信装置15は、共通参照データcrsを取得するs4。コミットメント受信装置15は暗号化アルゴリズムEncに対し共通参照データcrsとタグ情報tagを用いて、第一暗号文Cと第一鍵Kとの組C,Kを生成しs5、第一暗号文Cをコミットメント生成装置13に送信するs6。コミットメント生成装置13はコミットする秘匿情報mを入力されるs7。さらに、コミットメント生成装置13は第一暗号文Cを受信するs8。さらに、コミットメント生成装置13は、共通参照データcrsを取得するs9。コミットメント生成装置13は共通参照データcrsとタグ情報tagを用いて、第一暗号文Cが真の暗号文であるか否かを検証するs10。真の暗号文である場合には、コミットメント生成装置13は、関係RprivpktagのΣ-プロトコルに対するa,z←simΣC,mを計算しs11、コミットメント情報aをコミットメント受信装置15に送信するs12。なお、関係RprivpktagのΣ-プロトコルに対するsimΣとは、前述のΣ―プロトコルにおける秘密wを知らずに、第一メッセージa本実施形態におけるコミットメント情報aを生成し、返答z本実施形態におけるコミットを開封するときの証拠の一部zを生成するアルゴリズムである。コミットメント受信装置15は、コミットメント情報aを受信しs13、tag,C,aを格納しておくs14。コミットメント開封装置16は、crs,tag,C,m,a,zをコミットメント生成装置13等から受け取りs15、安全に保管しておく。そして、情報mを開示するタイミングになると、tag,m,zをコミットメント受信装置15に送信するs16。なお、コミットメント生成装置13とコミットメント開封装置16との間は安全に通信可能とされている。また、コミットメント開封装置16を設けず、コミットメント生成装置13から直接、tag,m,zをコミットメント受信装置15に送信する構成としてもよい。コミットメント受信装置15は、tag,m,zを受信するとs17、Σ―プロトコルに対するΣvrfyC,a,m,zを用いて、コミットメント情報aを受信した時点から秘匿情報mが変更されていないかを判定するs18。なお、前述のΣ―プロトコルにおいて検証アルゴリズムΣvrfyは証明者がwを知っているか否かを検証するが、本実施形態においてΣ―プロトコルに対するΣvrfyはコミットメント情報aを受信した時点から秘匿情報mが変更されていないかを判定する。言い換えると、本実施形態におけるΣ―プロトコルに対するΣvrfyは、秘匿情報mに対するコミットメント情報a及びコミットを開封するときの証拠の一部zが正しいか否かを検証するアルゴリズムである。以下、詳細を説明する。まず、第一実施形態において例えば、以下のTag-KEMΠ=Gen,Enc,Decを利用することができる。<Tag-KEMΠ>GとGTを素数位数qのアーベル群とする。e:G×G→GTを非退化な双線形写像とする。gをGの生成元とする。Z/qZを0以上q未満の整数の集合とする。双線形性より、x,y∈G、a,b∈Z/qZに対して、exa,yb=ex,yabが成り立つ。非退化性より、eg,gは、GTの生成元である。H:{0,1}→Z/qZのハッシュ関数とする。otΣ=otKGen,otSign,OtVrfyを任意の使い捨て署名とする参考文献4参照。参考文献4:LeslieLamportConstructingdigitalsignaturesfromonewayfunctionsTechnicalReportSRICSL98SRIInternationalComputerScienceLaboratoryOctober1979Gen1n:x,y←RZ/qZ;Xgx;Ygy;pk=g,X,Y,H、sk=pk,x,yとして、pk,skを出力する。Encpk,tag:otvk,otsk←otKGen1k;σ←otSignotsk,tag;r←Z/qZ;tHotvk,gr;Cσ,otvk,gr,XtYr;KXr;C,Kを出力する。Decsk,tag,C:C=σ,otvk,u,τをσ,otvk,u,τに分解し、もしotVrfyotvk,tag,σ≠1ならば、復号を中止し、それ以外の場合、tHotvk,uを計算する。もしuxty≠τならば、復号を中止し、それ以外の場合、Kux;Kを出力する。なお、第一実施形態において例えば、以下の使い捨て署名otΣotKGen,otSign,otVrfyを利用することができる。<使い捨て署名otΣ>G2を素数位数q2のアーベル群とする。H2:{0,1}→Z/q2Zのハッシュ関数とする。q2、G2、H2は、Tag-KEMΠで用いるq,G,Hと同じであってもよいし、異なっていてもよい。以下において、添え字s1、s2、w1、w2、z1、z2、H2は、s1、s2、w1、w2、z1、z2、H2を意味する。otKGen1k:g1,g2←RG2;s1,s2,w1,w2←RZ/q2Z;bg1w1g2w2;hg1s1g2s2;otvkg1,g2,h,b;otskotvk,s1,s2,w1,w2;otvk,otskを出力する。otSignotsk,m:cHotvk,m;z1w1cs1modq2;z2w2cs2modq2;σz1,z2を出力する。otVrfyotvk,m,σ:g1z1g2z2=bhH2otvk,mのときに限り、1を出力する。<共通参照データcrsの生成及び取得>図3及び図4を用いて共通参照データcrsの生成について説明する。第三者装置11は、入力部111を介してセキュリティパラメータnを取得しs111、鍵生成部112において、Tag-KEMの鍵生成アルゴリズムGen1nによりsk,pkを生成するs112。例えば、Z/qZからランダムにxとyを選択し、XgxとYgyを求め、gとXとYとHとの組を公開鍵pkとして生成する。この公開鍵pkを共通参照データcrsとする。pkとxとyとの組を秘密鍵として生成する。そして、少なくともコミットメント生成装置13とコミットメント受信装置15が共通参照データcrsを利用可能な状態で、共通参照データcrsは記憶部114に記憶される。また、第三者装置11は、秘密鍵skを記憶部114に安全に格納してもよいし、破棄してもよいs113。なお、第三者装置11は、制御部115の制御のもと上記処理を行う。なお、本実施形態では、一つの共通参照データcrsを繰り返し使う。コミットメント受信装置15は、制御部155図5の制御のもと、出力部156を介して、第三者装置11に対し、公開鍵pkを送信するように要求する。第三者装置11の制御部115は、入力部111を介して要求を受信し、記憶部114から公開鍵pkを取り出し、出力部116を介して、コミットメント受信装置15に送信する。コミットメント受信装置15は、入力部151を介して公開鍵pkを受信し、記憶部154に格納する図6、s151。コミットメント生成装置13も同様に制御部135図7の制御のもと、出力部136を介して公開鍵pkを要求し、入力部131を介して公開鍵pkを受信し、記憶部134に格納する図8、s131。<第一暗号文C及び第一鍵Kの生成>コミットメント受信装置15は、入力部151を介してセキュリティパラメータkを取得する図6、s152。コミットメント受信装置15は、暗号化部152図5において、Tag-KEMΠの暗号化アルゴリズムEncを実行し、第一暗号文Cと第一鍵Kとの組C,Kを生成するs153。暗号化部152内の署名鍵検証鍵生成部152aは、セキュリティパラメータkを用いて、鍵生成アルゴリズムotKGenにより、署名鍵otskと検証鍵otvkを生成する。例えば、署名鍵検証鍵生成部152aは、G2からランダムにg1、g2を選択し、Z/q2Zからランダムにs1、s2、w1、w2を選択する。さらに、b=g1w1g2w2とh=g1s1g2s2を求め、g1とg2とhとbとの組を検証鍵otvkとし、検証鍵otvkとs1とs2とw1とw2との組を署名鍵otskとして求める。なお、ハッシュ関数HとH2が異なる場合には、検証鍵otvkがハッシュ関数H2を含む構成とする。暗号化部152内の署名生成部152bは、タグ情報tagと生成した署名鍵otskを用いて、署名アルゴリズムotSignにより、電子署名σを生成する。例えば、検証鍵otvkとタグ情報tagをハッシュ関数H2の入力として、cを求める。さらに、z1=w1cs1modq2とz2=w2cs2modq2とを求め、z1とz2との組を電子署名σとする。暗号化部152内の第一鍵第一暗号文生成部152cは、公開パラメータpk=g,X,Y,Hと前記検証鍵otvkを用いて、暗号化アルゴリズムEncにより第一暗号文Cと第一鍵Kを生成する。例えば、Z/qZからランダムにrを選択し、K=Xrを求める。さらに、grを求め、検証鍵otvkとgrをハッシュ関数Hの入力として、tを求める。XtYrを計算し、電子署名σと検証鍵otvkとgrとXtYrとの組を第一暗号文Cとする。コミットメント受信装置15は、第一暗号文Cとタグ情報tagを関連付けて記憶部154に記憶し、さらに、第一暗号文Cを出力部156を介してコミットメント生成装置13に送信するs154。コミットメント受信装置15は、署名鍵otskを記憶部154に安全に格納してもよいし、破棄してもよい。<第一暗号文Cの検証>コミットメント生成装置13は、入力部131図7を介して、第一暗号文C=σ,otvk,u,τを受信するs132。暗号文検証部132において、まず、電子署名σと検証鍵otvkとタグ情報tagを用いて、otVrfyotvk,tag,σにより、電子署名σが正当か否かを検証するs133。例えば、電子署名σ=z1,z2とotvk=g1,g2,h,bを用いて、g1z1g2z2を求める。さらに、検証鍵otvkとタグ情報tagを入力とし、H2otvk,tagを求め、検証鍵に含まれるbを用いて、bhH2otvk,tagを求める。求めたg1z1g2z2とbhH2otvk,tagとが同一の場合に電子署名σが正当であると判断する。つまり、otVrfyは1を返す。g1z1g2z2とbhH2otvk,tagとが異なる場合には、電子署名が正当ではないと判断し、否決するs137。つまり、otVrfyは1以外の値を返す。コミットメント受信装置15以外の生成した電子署名を否決することができる。電子署名σが正当である場合には、暗号文検証部132は、記憶部154から公開パラメータpk=g,X,Y,Hを取り出し、ハッシュ関数Hと第一暗号文Cに含まれるuと検証鍵otvkを用いて、t=Hotvk,uを求める。さらに、公開パラメータpk=g,X,Y,Hと第一暗号文Cに含まれるτを用いて、eu,XtY=eg,τが成り立つか否か検証するs134。受信した第一暗号文Cに含まれるuとτが、それぞれ、コミットメント受信装置15で生成されるgr、XtYrと同一であれば、前記式が成り立つ。eu,XtY=eg,τが成り立つ場合には、受信した第一暗号文Cが真の暗号文であると判定する。eu,XtY=eg,τが成り立たない場合には、第一暗号文Cが真の暗号文ではないと判断し、否決するs137。この処理により、第一暗号文Cが言語LRに元として含まれない場合Cが真の暗号文でない場合に処理を中止することができる。<コミットメント情報の生成>第一暗号文Cが真の暗号文であると判定した場合、コミットメント情報生成部138は、第一暗号文Cと秘匿情報mを用いて、関係RprivpktagのΣ-プロトコルに対するa,z←simΣC,mを計算するs135。例えばコミットメント情報生成部138は、Gから単位元を除いた群GからランダムにK^を選択し、Z/qZからランダムにzを選択する。さらに、a^=eg,K^zeu,X-mを計算し、K^とa^との組をコミットメント情報aとして生成する。コミットメント生成装置13は、出力部136を介して、生成したコミットメント情報aをコミットメント受信装置15に送信するs136。コミットメント生成装置13とコミットメント開封装置16が同一装置の場合、crs,tag,C,m,a,zを記憶部134に安全に記憶しておく。別装置の場合には、コミットメント生成装置13は上記情報をコミットメント開封装置16に出力部136を介して送信する。<コミットメント情報の受信及び開封処理>コミットメント受信装置15は、入力部151図5を介して、コミットメント情報aを受信し図6、s155、記憶部154にtag,Cと関連付けて記憶しておくs156。さらに、コミットメント受信装置15は、入力部151を介して、コミットメント生成装置13またはコミットメント開封装置16からtag,m,zを受信するs157。コミットメント受信装置15の開封部159において、ΣvrfyC,a,m,zを用いて、eg,K^z=a^eu,Xmが成り立つか否か判定するs158。例えば、公開パラメータpkに含まれるgとX、a=K^,a^、第一暗号文Cに含まれるu,z及びmを用いて、eg,K^z=a^eu,Xmが成り立つか否か判定する。成り立つ場合には、ΣvrfyC,a,m,zは1を返し、受信した秘匿情報mは、コミットメント情報a受信時点から変更されていないと判定し、受理するs159。eg,K^z=a^eu,Xmが成り立たない場合、ΣvrfyC,a,m,zは1以外の値を返し、少なくともmかzかの何れかに変更があったものとし、否決するs160。<効果>このような構成とすることで、従来の署名が破られた場合にも安全なコミットメント方式とすることができる。さらに、本実施形態では、公開検証可能なTag-KEMに加え、電子署名を組合せているため、より安全性の高いコミットメント方式を実現している。さらに、電子署名を使い捨て署名とすることで、従来非特許文献3、4、5、6及び7参照より効率のよいコミットメント方式を実現している。従来技術では、使い捨てでない電子署名から共通の変換法の基にSSTCを構成していた。これらの方式は署名方式から変換するので、コミットメントの効率は署名方式に依存する。現在知られている限りでは、安全な使い捨てでない署名方式は、安全な使い捨て署名や安全な暗号方式と比べてより強い家庭または大きなパラメータを使わなくてはならない。例えば、参考文献5記載の署名方式では、公開パラメータpkとしてg、g1,g2,u’,H,u1,...,unを必要とする例えばn=160や256等。一方、本実施形態では、公開検証可能なTag-KEMと使い捨て署名を組み合わせて用いることで、公開パラメータをg,X,Y,Hとし、小さいパラメータで十分な安全性を実現することができる。参考文献5:BrentWatersEfficientIdentityBasedEncryptionWithoutRandomOraclesEUROCRYPT2005LNCSSpringerHeidelberg2005vol3494p114127また、本実施形態は、CDH仮定に対しタイトであり、従来技術に比べ、セキュリティパラメータを短くすることができ、情報量、計算量を共に削減することができ、効率のよいコミットメントシステムを構成することができる。例えば、CDH仮定がkビットの場合、本実施形態ではk’≒kビットのセキュリティパラメータを用いることができる。一方、参考文献5記載の署名方式ではk≒102kビットのセキュリティパラメータを用いなければ同程度の安全性を得ることはできない。<プログラム及び記憶媒体>上述した第三者装置、コミットメント生成装置及びコミットメント受信装置は、コンピュータにより機能させることもできる。この場合はコンピュータに、目的とする装置各種実施例で図に示した機能構成をもつ装置として機能させるためのプログラム、またはその処理手順各実施例で示したものの各過程をコンピュータに実行させるためのプログラムを、CD-ROM、磁気ディスク、半導体記憶装置などの記録媒体から、あるいは通信回線を介してそのコンピュータ内にダウンロードし、そのプログラムを実行させればよい。<その他の変形例>他の公開検証可能なTag-KEMや使い捨て署名を用いてもよい。Πと関係Rprivpktagに対するΣ-プロトコルからコミットメントシステムを構成すればよく、第一暗号文Cは必ずしも署名を含まなくともよい。また、使い捨てではない署名を用いてもよく、その場合も、従来技術と比べ安全なコミットメント方式となる。本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。"