(57)【特許請求の範囲】
【請求項１】
共通参照情報生成装置と、コミット生成装置と、コミット受信装置とを含むコミットメントシステムであって、
κをセキュリティパラメータ、λｍ（・），λｃ（・）をκの関数、Ｈ：｛０，１｝＊→｛０，１｝λ_ｍを衝突困難ハッシュ関数、Ｋを公開鍵暗号ＰＫＥの鍵生成アルゴリズム、Ｅを公開鍵暗号ＰＫＥの暗号化アルゴリズム、Ｇｅｎｔｃを落し戸付きコミットメントＴＣＯＭの鍵生成アルゴリズム、Ｃｏｍｔｃを落し戸付きコミットメントＴＣＯＭの暗号化アルゴリズム、Ｌｅｎｃ＝｛（ｍ，ＣＴ）｜ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ，ｗ）を満たすｗ∈ＣＯＩＮｐｋ^ｅｎｃが存在する｝を公開鍵暗号ＰＫＥから定義される言語（ただし、ＣＯＩＮｐｋ^ｅｎｃは乱数空間）、ＰΣｃｏｍを言語Ｌｅｎｃ上のシグマプロトコルΣの第一メッセージ生成アルゴリズム、ＰΣａｎｓを言語Ｌｅｎｃ上のシグマプロトコルΣの第二メッセージ生成アルゴリズム、ＶΣｖｒｆｙを言語Ｌｅｎｃ上のシグマプロトコルΣの検証アルゴリズムとして、
前記共通参照情報生成装置は、
１κから、前記鍵生成アルゴリズムＫ、Ｇｅｎｔｃを用いて、２つの公開鍵と秘密鍵の組（ｐｋｅｎｃ，ｓｋｅｎｃ）←Ｋ（１κ）、（ｐｋｔｃ，ｓｋｔｃ）←Ｇｅｎｔｃ（１κ）を生成し、前記秘密鍵ｓｋｅｎｃ、ｓｋｔｃを廃棄する鍵生成部と、
前記公開鍵ｐｋｅｎｃ、ｐｋｔｃ、前記ハッシュ関数Ｈを組にしたｃｒｓ＝（ｐｋｅｎｃ，ｐｋｔｃ，Ｈ）を共通参照情報として生成するＣＲＳ生成部と
を含み、
前記コミット生成装置は、
乱数ｗ←ＣＯＩＮｐｋ^ｅｎｃ（ただし、ＣＯＩＮｐｋ^ｅｎｃは乱数空間）を生成し、前記暗号化アルゴリズムＥと前記公開鍵ｐｋｅｎｃを用いて、秘匿情報ｍ∈ＭＳＰｐｋ^ｅｎｃ（ただし、ＭＳＰｐｋ^ｅｎｃは平文空間）から暗号化済秘匿情報ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ，ｗ）を計算する秘匿情報暗号化部と、
前記第一メッセージ生成アルゴリズムＰΣｃｏｍを用いて、前記秘匿情報ｍと前記暗号化済秘匿情報ＣＴの組（ｍ，ＣＴ）と前記乱数ｗから第一メッセージ（α，ξ）←ＰΣｃｏｍ（（ｍ，ＣＴ），ｗ）を計算する第一メッセージ計算部と、
前記ハッシュ関数Ｈと４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）（ただし、ｓｉｄはセッションＩＤ、ｓｓｉｄはサブセッションＩＤ、Ｃは前記コミット生成装置のＩＤ、Ｒは前記コミット受信装置のＩＤを示す有限のビット列）を用いて、前記秘匿情報ｍ、前記暗号化済秘匿情報ＣＴ、前記第一メッセージの第１要素αからハッシュ値φ＝Ｈ（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ｍ，ＣＴ，α）を計算するハッシュ値計算部と、
乱数ｒｔｃ←ＣＯＩＮｐｋ^ｔｃ（ただし、ＣＯＩＮｐｋ^ｔｃは乱数空間）を生成し、前記暗号化アルゴリズムＣｏｍｔｃと前記公開鍵ｐｋｔｃを用いて、前記ハッシュ値φから暗号化済ハッシュ値Ψ＝Ｃｏｍｔｃｐｋ^ｔｃ （φ；ｒｔｃ） を計算するハッシュ値暗号化部と、
前記４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）、前記暗号化済ハッシュ値Ψを前記コミット受信装置に送信する第一コミット部と、
前記第二メッセージ生成アルゴリズムＰΣａｎｓを用いて、前記秘匿情報ｍと前記暗号化済秘匿情報ＣＴの組（ｍ，ＣＴ）、前記乱数ｗ、前記第一メッセージの第２要素ξ、前記コミット受信装置から受信した乱数εから第二メッセージγ＝ＰΣａｎｓ（（ｍ，ＣＴ），ｗ，ξ，ε）を計算する第二メッセージ計算部と、
前記乱数ｗと前記第一メッセージの第２要素ξを消去する消去部と、
前記暗号化済秘匿情報ＣＴを前記コミット受信装置に送信する第二コミット部と、
前記秘匿情報ｍと前記第一メッセージの第１要素αと前記第二メッセージγと前記乱数ｒｔｃからなる４つ組（ｍ，α，γ，ｒｔｃ）を開示情報として前記コミット受信装置に送信する開示部と
を含み、
前記コミット受信装置は、
前記コミット生成装置から受信した前記４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）を検証し、問題なければ前記乱数ε←｛０，１｝λ_ｃを生成し、前記乱数εを前記コミット生成装置に送信する乱数生成部と、
前記コミット生成装置から受信した前記４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）、前記暗号化済秘匿情報ＣＴ、前記開示情報（ｍ，α，γ，ｒｔｃ）と前記ハッシュ関数Ｈを用いて、ハッシュ値φ’＝Ｈ（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ｍ，ＣＴ，α）を計算するハッシュ値計算部と、
前記暗号化アルゴリズムＣｏｍｔｃと前記検証アルゴリズムＶΣｖｒｆｙを用いて、前記ハッシュ値φ’、前記開示情報（ｍ，α，γ，ｒｔｃ）、前記暗号化済秘匿情報ＣＴ、前記乱数εからＣｏｍｔｃｐｋ^ｔｃ（φ’；ｒｔｃ）とＶΣｖｒｆｙ（（ｍ，ＣＴ），（α，ε，γ））を計算し、前記暗号化済ハッシュ値Ψ＝Ｃｏｍｔｃｐｋ^ｔｃ（φ’；ｒｔｃ）とＶΣｖｒｆｙ（（ｍ，ＣＴ），（α，ε，γ））＝１が成立するか確認する開封部と
を含むコミットメントシステム。
【請求項２】
共通参照情報生成装置と、コミット生成装置と、コミット受信装置とを含むコミットメントシステムであって、
κをセキュリティパラメータ、λｍ（・），λｃ（・）をκの関数、Ｈ：｛０，１｝＊→｛０，１｝λ_ｍを衝突困難ハッシュ関数、Ｋを公開鍵暗号ＰＫＥの鍵生成アルゴリズム、Ｅを公開鍵暗号ＰＫＥの暗号化アルゴリズム、Ｇｅｎｔｃを落し戸付きコミットメントＴＣＯＭの鍵生成アルゴリズム、Ｃｏｍｔｃを落し戸付きコミットメントＴＣＯＭの暗号化アルゴリズム、Ｌｅｎｃ＝｛（ｍ，ＣＴ）｜ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ，ｗ）を満たすｗ∈ＣＯＩＮｐｋ^ｅｎｃが存在する｝を公開鍵暗号ＰＫＥから定義される言語（ただし、ＣＯＩＮｐｋ^ｅｎｃは乱数空間）、ＰΣｃｏｍを言語Ｌｅｎｃ上のシグマプロトコルΣの第一メッセージ生成アルゴリズム、ＰΣａｎｓを言語Ｌｅｎｃ上のシグマプロトコルΣの第二メッセージ生成アルゴリズム、ＶΣｖｒｆｙを言語Ｌｅｎｃ上のシグマプロトコルΣの検証アルゴリズムとして、
前記共通参照情報生成装置は、
１κから、前記鍵生成アルゴリズムＫ、Ｇｅｎｔｃを用いて、２つの公開鍵と秘密鍵の組（ｐｋｅｎｃ，ｓｋｅｎｃ）←Ｋ（１κ）、（ｐｋｔｃ，ｓｋｔｃ）←Ｇｅｎｔｃ（１κ）を生成し、前記秘密鍵ｓｋｅｎｃ、ｓｋｔｃを廃棄する鍵生成部と、
前記公開鍵ｐｋｅｎｃ、ｐｋｔｃ、前記ハッシュ関数Ｈを組にしたｃｒｓ＝（ｐｋｅｎｃ，ｐｋｔｃ，Ｈ）を共通参照情報として生成するＣＲＳ生成部と
を含み、
前記コミット生成装置は、
乱数ｗ←ＣＯＩＮｐｋ^ｅｎｃ（ただし、ＣＯＩＮｐｋ^ｅｎｃは乱数空間）を生成し、前記暗号化アルゴリズムＥと前記公開鍵ｐｋｅｎｃを用いて、秘匿情報ｍ∈ＭＳＰｐｋ^ｅｎｃ（ただし、ＭＳＰｐｋ^ｅｎｃは平文空間）から暗号化済秘匿情報ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ，ｗ）を計算する秘匿情報暗号化部と、
４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）（ただし、ｓｉｄはセッションＩＤ、ｓｓｉｄはサブセッションＩＤ、Ｃは前記コミット生成装置のＩＤ、Ｒは前記コミット受信装置のＩＤを示す有限のビット列）、前記暗号化済秘匿情報ＣＴを前記コミット受信装置に送信する第二コミット部と、
前記第一メッセージ生成アルゴリズムＰΣｃｏｍを用いて、前記秘匿情報ｍと前記暗号化済秘匿情報ＣＴの組（ｍ，ＣＴ）と前記乱数ｗから第一メッセージ（α，ξ）←ＰΣｃｏｍ（（ｍ，ＣＴ），ｗ）を計算する第一メッセージ計算部と、
前記ハッシュ関数Ｈと前記（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）を用いて、前記秘匿情報ｍ、前記暗号化済秘匿情報ＣＴ、前記第一メッセージの第１要素αからハッシュ値φ＝Ｈ（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ｍ，ＣＴ，α）を計算するハッシュ値計算部と、
乱数ｒｔｃ←ＣＯＩＮｐｋ^ｔｃ（ただし、ＣＯＩＮｐｋ^ｔｃは乱数空間）を生成し、前記暗号化アルゴリズムＣｏｍｔｃと前記公開鍵ｐｋｔｃを用いて、前記ハッシュ値φから暗号化済ハッシュ値Ψ＝Ｃｏｍｔｃｐｋ^ｔｃ （φ；ｒｔｃ） を計算するハッシュ値暗号化部と、
前記暗号化済ハッシュ値Ψを前記コミット受信装置に送信する第一開示部と、
前記第二メッセージ生成アルゴリズムＰΣａｎｓを用いて、前記秘匿情報ｍと前記暗号化済秘匿情報ＣＴの組（ｍ，ＣＴ）、前記乱数ｗ、前記第一メッセージの第２要素ξ、前記コミット受信装置から受信した乱数εから第二メッセージγ＝ＰΣａｎｓ（（ｍ，ＣＴ），ｗ，ξ，ε）を計算する第二メッセージ計算部と、
前記秘匿情報ｍと前記第一メッセージの第１要素αと前記第二メッセージγと前記乱数ｒｔｃからなる４つ組（ｍ，α，γ，ｒｔｃ）を第二開示情報として前記コミット受信装置に送信する第二開示部と
を含み、
前記コミット受信装置は、
前記コミット生成装置から受信した前記４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）を検証し、問題なければ前記乱数ε←｛０，１｝λ_ｃを生成し、前記乱数εを前記コミット生成装置に送信する乱数生成部と、
前記コミット生成装置から受信した前記４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）、前記暗号化済秘匿情報ＣＴ、前記開示情報（ｍ，α，γ，ｒｔｃ）と前記ハッシュ関数Ｈを用いて、ハッシュ値φ’＝Ｈ（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ｍ，ＣＴ，α）を計算するハッシュ値計算部と、
前記暗号化アルゴリズムＣｏｍｔｃと前記検証アルゴリズムＶΣｖｒｆｙを用いて、前記ハッシュ値φ’、前記開示情報（ｍ，α，γ，ｒｔｃ）、前記暗号化済秘匿情報ＣＴ、前記乱数εからＣｏｍｔｃｐｋ^ｔｃ（φ’；ｒｔｃ）とＶΣｖｒｆｙ（（ｍ，ＣＴ），（α，ε，γ））を計算し、前記暗号化済ハッシュ値Ψ＝Ｃｏｍｔｃｐｋ^ｔｃ（φ’；ｒｔｃ）とＶΣｖｒｆｙ（（ｍ，ＣＴ），（α，ε，γ））＝１が成立するか確認する開封部と
を含むコミットメントシステム。
【請求項３】
請求項１または請求項２に記載のコミットメントシステムであって、
ｇを位数ｑの巡回群Ｇの生成元、前記κをκ＝ｌｏｇ２（ｑ）、前記ハッシュ関数ＨをＨ’：｛０，１｝＊→Ｚ／ｑＺ（つまり、有限長のビット列ｘ∈｛０，１｝＊をＺ／ｑＺの元にハッシュするハッシュ関数）とし、
前記λｍ，λｃはλｍ，λｃ≦κを満たし、
前記鍵生成アルゴリズムＫは、ｘｅ←Ｚ／ｑＺをランダムに取ってきて、Ｙｅ＝ｇｘ_ｅを計算し、Ｚｅ，Ｚｅ’←Ｇをランダムに取ってきた後、（ｐｋｅｎｃ，ｓｋｅｎｃ）＝（（Ｙｅ，Ｚｅ，Ｚｅ’），ｘｅ）を出力するアルゴリズムであり、
前記暗号化アルゴリズムＥは、乱数ｗ←ＣＯＩＮｐｋ^ｅｎｃを生成し、ｔ＝Ｈ’（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ｇｗ）を計算し、ＣＴ＝（ｇｗ，（ＺｅｔＺｅ’）ｗ，ｍ・Ｙｅｗ）（ただし、ｍ∈Ｇ）を出力するアルゴリズムであり、
前記言語ＬｅｎｃをＬｅｎｃ＝｛（ｍ，ＣＴ）｜ＣＴ＝（ＣＴ１，ＣＴ２，ＣＴ３），ＣＴ１＝ｇｗ，ＣＴ２＝（ＺｅｔＺｅ’）ｗ，ＣＴ３＝ｍ・Ｙｅｗを満たすｗ∈ＣＯＩＮｐｋ^ｅｎｃが存在する。｝（ただし、ｔ＝Ｈ’（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ＣＴ１））とし、
前記第一メッセージ生成アルゴリズムＰΣｃｏｍは、（ｍ，ＣＴ）, ｗ（ただし、ＣＴ＝（ＣＴ１，ＣＴ２，ＣＴ３），ＣＴ１＝ｇｗ，ＣＴ２＝（ＺｅｔＺｅ’）ｗ，ＣＴ３＝ｍ・Ｙｅｗを満たす。なお、ｔ＝Ｈ’（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ＣＴ１））を入力とし、ξ←Ｚ／ｑＺをランダムに選び、α１＝ｇξ,ｔ＝ Ｈ’（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，α１）, α２＝（ＺｅｔＺｅ’）ξ，α３＝Ｙｅξと計算し、α＝（α１，α２，α３）とし、（α，ξ）を出力するアルゴリズムであり、
前記第二メッセージ生成アルゴリズムＰΣａｎｓは、（ｍ，ＣＴ）, ｗ，ξ，ε∈｛０，１｝λ_ｃ（ただし、ＣＴ＝（ＣＴ１，ＣＴ２，ＣＴ３），ＣＴ１＝ｇｗ，ＣＴ２＝（ＺｅｔＺｅ’）ｗ，ＣＴ３＝ｍ・Ｙｅｗを満たす。なお、ｔ＝Ｈ’（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ＣＴ１））を入力とし、γ＝ξ−εｗ  ｍｏｄ ｑを計算し、γを出力するアルゴリズムであり、
前記検証アルゴリズムＶΣｖｒｆｙは、（ｍ，ＣＴ）∈Ｌｅｎｃ，（α，ε，γ）を入力とし、α１＝ｇγＣＴ１ε、α２＝（ＺｅｔＺｅ’）γＣＴ２ε、α３＝Ｙｅγ（ＣＴ３／ｍ）εをすべて満たすなら１を、そうでないなら０を出力するアルゴリズムであり、
前記鍵生成アルゴリズムＧｅｎｔｃは、ｘｔｃ←Ｚ／ｑＺをランダムに取ってきて、ｈ＝ｇｘ_ｔｃを計算し、ｐｋｔｃ＝（Ｇ，ｇ，ｑ，ｈ）、ｓｋｔｃ＝（ｐｋｔｃ，ｘｔｃ）とし、（ｐｋｔｃ，ｓｋｔｃ）を出力するアルゴリズムであり、
前記暗号化アルゴリズムＣｏｍｔｃは、内部乱数ｒｔｃ←Ｚ／ｑＺをランダムにとり、ｃ＝ｇｒ_ｔｃｈｘを計算し、ｃを出力するアルゴリズムである
コミットメントシステム。
【請求項４】
請求項１ないし３のいずれか１項に記載のコミットメントシステムに含まれる共通参照情報生成装置。
【請求項５】
請求項１ないし３のいずれか１項に記載のコミットメントシステムに含まれるコミット生成装置。
【請求項６】
請求項１ないし３のいずれか１項に記載のコミットメントシステムに含まれるコミット受信装置。
【請求項７】
共通参照情報生成装置と、コミット生成装置と、コミット受信装置とを含むコミットメントシステムが実行するコミットメント方法であって、
κをセキュリティパラメータ、λｍ（・），λｃ（・）をκの関数、Ｈ：｛０，１｝＊→｛０，１｝λ_ｍを衝突困難ハッシュ関数、Ｋを公開鍵暗号ＰＫＥの鍵生成アルゴリズム、Ｅを公開鍵暗号ＰＫＥの暗号化アルゴリズム、Ｇｅｎｔｃを落し戸付きコミットメントＴＣＯＭの鍵生成アルゴリズム、Ｃｏｍｔｃを落し戸付きコミットメントＴＣＯＭの暗号化アルゴリズム、Ｌｅｎｃ＝｛（ｍ，ＣＴ）｜ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ，ｗ）を満たすｗ∈ＣＯＩＮｐｋ^ｅｎｃが存在する｝を公開鍵暗号ＰＫＥから定義される言語（ただし、ＣＯＩＮｐｋ^ｅｎｃは乱数空間）、ＰΣｃｏｍを言語Ｌｅｎｃ上のシグマプロトコルΣの第一メッセージ生成アルゴリズム、ＰΣａｎｓを言語Ｌｅｎｃ上のシグマプロトコルΣの第二メッセージ生成アルゴリズム、ＶΣｖｒｆｙを言語Ｌｅｎｃ上のシグマプロトコルΣの検証アルゴリズムとして、
前記共通参照情報生成装置が、１κから、前記鍵生成アルゴリズムＫ、Ｇｅｎｔｃを用いて、２つの公開鍵と秘密鍵の組（ｐｋｅｎｃ，ｓｋｅｎｃ）←Ｋ（１κ）、（ｐｋｔｃ，ｓｋｔｃ）←Ｇｅｎｔｃ（１κ）を生成し、前記秘密鍵ｓｋｅｎｃ、ｓｋｔｃを廃棄する鍵生成ステップと、
前記共通参照情報生成装置が、前記公開鍵ｐｋｅｎｃ、ｐｋｔｃ、前記ハッシュ関数Ｈを組にしたｃｒｓ＝（ｐｋｅｎｃ，ｐｋｔｃ，Ｈ）を共通参照情報として生成するＣＲＳ生成ステップと、
前記コミット生成装置が、乱数ｗ←ＣＯＩＮｐｋ^ｅｎｃ（ただし、ＣＯＩＮｐｋ^ｅｎｃは乱数空間）を生成し、前記暗号化アルゴリズムＥと前記公開鍵ｐｋｅｎｃを用いて、秘匿情報ｍ∈ＭＳＰｐｋ^ｅｎｃ（ただし、ＭＳＰｐｋ^ｅｎｃは平文空間）から暗号化済秘匿情報ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ，ｗ）を計算する秘匿情報暗号化ステップと、
前記コミット生成装置が、前記第一メッセージ生成アルゴリズムＰΣｃｏｍを用いて、前記秘匿情報ｍと前記暗号化済秘匿情報ＣＴの組（ｍ，ＣＴ）と前記乱数ｗから第一メッセージ（α，ξ）←ＰΣｃｏｍ（（ｍ，ＣＴ），ｗ）を計算する第一メッセージ計算ステップと、
前記コミット生成装置が、前記ハッシュ関数Ｈと４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）（ただし、ｓｉｄはセッションＩＤ、ｓｓｉｄはサブセッションＩＤ、Ｃはコミット生成装置のＩＤ、Ｒはコミット受信装置のＩＤを示す有限のビット列）を用いて、前記秘匿情報ｍ、前記暗号化済秘匿情報ＣＴ、前記第一メッセージの第１要素αからハッシュ値φ＝Ｈ（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ｍ，ＣＴ，α）を計算するハッシュ値計算ステップと、
前記コミット生成装置が、乱数ｒｔｃ←ＣＯＩＮｐｋ^ｔｃ（ただし、ＣＯＩＮｐｋ^ｔｃは乱数空間）を生成し、前記暗号化アルゴリズムＣｏｍｔｃと前記公開鍵ｐｋｔｃを用いて、前記ハッシュ値φから暗号化済ハッシュ値Ψ＝Ｃｏｍｔｃｐｋ^ｔｃ （φ；ｒｔｃ） を計算するハッシュ値暗号化ステップと、
前記コミット生成装置が、前記４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）、前記暗号化済ハッシュ値Ψを前記コミット受信装置に送信する第一コミットステップと、
前記コミット受信装置が、前記４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）を検証し、問題なければ乱数ε←｛０，１｝λ_ｃを生成し、前記乱数εを前記コミット生成装置に送信する乱数生成ステップと、
前記コミット生成装置が、前記第二メッセージ生成アルゴリズムＰΣａｎｓを用いて、前記秘匿情報ｍと前記暗号化済秘匿情報ＣＴの組（ｍ，ＣＴ）、前記乱数ｗ、前記第一メッセージの第２要素ξ、前記乱数εから第二メッセージγ＝ＰΣａｎｓ（（ｍ，ＣＴ），ｗ，ξ，ε）を計算する第二メッセージ計算ステップと、
前記コミット生成装置が、前記乱数ｗと前記第一メッセージの第２要素ξを消去する消去ステップと、
前記コミット生成装置が、前記暗号化済秘匿情報ＣＴを前記コミット受信装置に送信する第二コミットステップと、
前記コミット生成装置が、前記秘匿情報ｍと前記第一メッセージの第１要素αと前記第二メッセージγと前記乱数ｒｔｃからなる４つ組（ｍ，α，γ，ｒｔｃ）を開示情報として前記コミット受信装置に送信する開示ステップと、
前記コミット受信装置が、前記４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）、前記暗号化済秘匿情報ＣＴ、前記開示情報（ｍ，α，γ，ｒｔｃ）と前記ハッシュ関数Ｈを用いて、ハッシュ値φ’＝Ｈ（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ｍ，ＣＴ，α）を計算するハッシュ値計算ステップと、
前記コミット受信装置が、前記暗号化アルゴリズムＣｏｍｔｃと前記検証アルゴリズムＶΣｖｒｆｙを用いて、前記ハッシュ値φ’、前記開示情報（ｍ，α，γ，ｒｔｃ）、前記暗号化済秘匿情報ＣＴ、前記乱数εからＣｏｍｔｃｐｋ^ｔｃ（φ’；ｒｔｃ）とＶΣｖｒｆｙ（（ｍ，ＣＴ），（α，ε，γ））を計算し、前記暗号化済ハッシュ値Ψ＝Ｃｏｍｔｃｐｋ^ｔｃ（φ’；ｒｔｃ）とＶΣｖｒｆｙ（（ｍ，ＣＴ），（α，ε，γ））＝１が成立するか確認する開封ステップと
を含むコミットメント方法。
【請求項８】
請求項４に記載の共通参照情報生成装置としてコンピュータを機能させるためのプログラム。
【請求項９】
請求項５に記載のコミット生成装置としてコンピュータを機能させるためのプログラム。
【請求項１０】
請求項６に記載のコミット受信装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術に関するものであり、特に複数の暗号プロトコルの中に組み込まれ同時に動くような環境でもなお高い安全性を保つコミットメントに関する。
【背景技術】
【０００２】
暗号におけるコミットメントとは、電子的に行う「封じ手」のことである。コミットメント方式は、コミットする側の送信者（committer）と、コミットメントを受ける側の受信者（receiver）の間で行われるプロトコルのことである。送信者は、コミット（封じ手）フェーズで、受信者に情報を預託（コミット）する。このとき、受信者は預託された情報の中身を知ることができない（この性質を秘匿性という）。次に、送信者はデコミット（開封）フェーズで秘匿した情報を受信者に納得いく形で開示するが、コミットフェーズで預託した情報と違う情報を開示して受信者を満足させることはできない（この性質を拘束性という）。コミットメントは、基本的にこのような秘匿性と拘束性を満たさなければいけない。
【０００３】
コミットメントのすぐ思いつく応用例は、電子的なジャンケンやコイン投げである。もちろん、将棋や碁に使う封じ手でもよい。簡単に思いつく例をいくつか挙げたが、実際に応用できる範囲はそれより遥かに広い。
【０００４】
コミットメントは、最も基本的な暗号プロトコルであるため、上位の暗号プロトコルの中で頻繁に利用される。近年では、暗号プロトコルをより現実の環境に近づけるため、コミットメントはさらに複雑な組み合わせの中で利用される場合が増えてきた。しかし、複雑な組み合わせの中では、古典的暗号安全性モデルで作られたコミットメントは、秘匿性と拘束性を同時に満たすことができなくなってしまう。
【０００５】
汎用結合可能コミットメントとは、そのような複雑な組み合わせでコミットメントが利用された場合にも、秘匿性と拘束性を満たすよう設計されたコミットメントのことである（汎用結合可能性については非特許文献１を参照）。
【０００６】
コミットメント方式の良し悪しは、計算量、通信量、交信回数に加え、ＣＲＳ再利用型、適応的安全性、情報廃棄型・情報廃棄不要型、対話型・非対話型、離散対数（ＤＬ）型についても考慮する必要がある。以下、それぞれについて説明していく。
【０００７】
＜ＣＲＳ再利用型＞
汎用結合可能コミットメントが構成できるためには、送信者と受信者の双方がアクセスできる（第三者の作った）共通参照情報（common reference string、以下、ＣＲＳと記す）が必要であることが知られている（非特許文献２参照）。技術的な問題により、このＣＲＳは、コミットごとに使い捨てなければいけない場合（すなわち、コミットの回数だけ新しいＣＲＳが必要となる場合）と、使い捨てずに同じＣＲＳを再利用できる場合に分かれる。当然ながら、ＣＲＳをずっと使える「ＣＲＳ再利用型」コミットメント方式の方が、実用性が高い。
【０００８】
＜適応的安全性・静的安全性＞
汎用結合安全性を考えるとき、適応的安全性（adaptive security）を満たしているかというのは重要な目安になる。プロトコルの最中に攻撃者が自由にプロトコルの参加者の装置に侵入しデータを盗み出してしまえるような状況であったとしても（汎用結合）安全性を満たせるとき、そのプロトコルは適応的安全性を満たすという。適応的安全性は通常達成することが大変難しい。
【０００９】
一方、攻撃を受ける参加者が予め決まっている場合の安全性を、静的安全性（static security）という。静的安全性は適応的安全性より低いレベルの安全性である。
＜情報廃棄型・情報廃棄不要型＞
汎用結合可能コミットメントでは、送信者と受信者が、プロトコルの最中もしくは終了後、途中データを廃棄しないと安全性が担保出来ない方式と、廃棄しなくても安全性を担保できる方式が存在する。当然、後者の「情報廃棄不要型」の方が安全性が高く望ましい。
【００１０】
＜対話型・非対話型＞
特に、送信者から受信者に送るだけでコミットメントが完成する方式を「非対話型」という。「非対話型」の方が実用上望ましい。
【００１１】
＜離散対数（ＤＬ）型＞
セキュリティパラメータを小さくできる、または構造が簡単などの理由で、（離散対数（ＤＬ）問題が成立すると思われるような）巡回群上でコミットメントが実装できることが望ましい。実際、現在もっとも効率の良いと思われている非特許文献３や非特許文献４に記載のコミットメントはいずれもＤＬ型である。
【００１２】
効率のよいＣＲＳ再利用型で適応的安全な汎用結合可能コミットメントは、非特許文献３、非特許文献４、非特許文献５、非特許文献６、非特許文献７、非特許文献８などがある。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】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.
【非特許文献２】R. Canetti and M. Fischlin, “Universally composable commitments”, In Joe Kilian, editor, Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19-23, 2001, Proceedings, volume 2139 of Lecture Notes in Computer Science, pages 19-40, Springer, Heidelberg, 2001.
【非特許文献３】Yehuda Lindell, “Highly-efficient universally-composable commitments based on the DDH assumption”, In Kenneth G. Paterson, editor, EUROCRYPT 2011, volume 6632 of Lecture Notes in Computer Science, pages 446-466, Springer, Heidelberg, 2011. The full version is available at Cryptology ePrint Archive http://eprint.iacr.org/2011/180.
【非特許文献４】Olivier Blazy, Celine Chevalier, David Pointcheval and Damien Vergnaud, “Analysis and improvement of lindell's uc-secure commitment schemes”, In Michael J. Jacobson, Jr., Michael E. Locasto, Payman Mohassel and Reihaneh Safavi-Naini, editors, ACNS 2013, volume 7954 of Lecture Notes in Computer Science, pages 534-551, Springer, Heidelberg, 2013.
【非特許文献５】Ivan Damgard and Jesper Buus Nielsen, “Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor”,  In Moti Yung, editor, CRYPTO 2002, volume 2442 of Lecture Notes in Computer Science, pages 581-596, Springer, Heidelberg, 2002. The full version is available at http://www.brics.dk/RS/01/41/.
【非特許文献６】Ivan Damgard and Jens Groth, “Non-interactive and reusable non-malleable commitment schemes”, In STOC 2003, pages 426-437, ACM, 2003.
【非特許文献７】Marc Fischlin, Benoit Libert, and Mark Manulis, “Non-interactive and re-usable universally composable string commitments with adaptive security”, In Dong Hoon Lee and Xiaoyun Wang, editors, ASIACRYPT 2011, volume 7073 of Lecture Notes in Computer Science, pages 468-485, Springer, Heidelberg, 2011.
【非特許文献８】Eiichiro Fujisaki, “All-But-Many encryption - A new framework for fully-equipped UC commitments”, In Palash Sarkar and Tetsu Iwata, editors, ASIACRYPT 2014 (2), volume 8874 of Lecture Notes in Computer Science, pages 426-447, Springer, Heidelberg, 2014.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかし、非特許文献５、非特許文献６、非特許文献８は、素因数分解型問題を安全性の基礎においているため、セキュリティパラメータが大きくなり、ＤＬ型問題に安全性の基礎をおく非特許文献３、非特許文献４より通信量と計算量で劣る。非特許文献７は、ＤＬ型問題に安全性の基礎をおくが、対称ペアリング（参考非特許文献１）上で構成されるため、セキュリティパラメータ長が素因数分解型と同じになりやはり効率で劣る。
（参考非特許文献１：David Freeman, Michael Scott and Edlyn Teske, “A taxonomy of pairing-friendly elliptic curves”, JOC, 23(2), pages 224-280, 2010.）
その他、非特許文献３、非特許文献４、非特許文献７は情報廃棄型であり、非特許文献５、非特許文献６、非特許文献８は情報廃棄不要型である。また、非特許文献４、非特許文献５、非特許文献６はコミットメントで三交信、非特許文献３は五交信が必要であり、非特許文献７、非特許文献８は非対話型である。
【００１５】
このように、非特許文献３、非特許文献４、非特許文献５、非特許文献６、非特許文献７、非特許文献８の各方式を見てみるといずれも一長一短ある。しかし、実装面を考えると、通信量と計算量の点で非特許文献４の方式が最も効率のよい従来方式である。
【００１６】
そこで本発明では、共通パラメータ長、通信量、計算量を削減することが可能となるＣＲＳ再利用型・適応的安全な汎用結合可能コミットメントシステムを提供することを目的とする。
【００１７】
また、場合によっては、汎用結合可能コミットメントシステムに求められる安全性は、適応的安全性でなく、静的安全性で十分なときもある。
【００１８】
そこで本発明では、共通パラメータ長、通信量、計算量を削減することが可能となるＣＲＳ再利用型・静的安全な汎用結合可能コミットメントシステムを提供することを目的とする。
【課題を解決するための手段】
【００１９】
本発明の一態様は、共通参照情報生成装置と、コミット生成装置と、コミット受信装置とを含むコミットメントシステムであって、κをセキュリティパラメータ、λｍ（・），λｃ（・）をκの関数、Ｈ：｛０，１｝＊→｛０，１｝λ_ｍを衝突困難ハッシュ関数、Ｋを公開鍵暗号ＰＫＥの鍵生成アルゴリズム、Ｅを公開鍵暗号ＰＫＥの暗号化アルゴリズム、Ｇｅｎｔｃを落し戸付きコミットメントＴＣＯＭの鍵生成アルゴリズム、Ｃｏｍｔｃを落し戸付きコミットメントＴＣＯＭの暗号化アルゴリズム、Ｌｅｎｃ＝｛（ｍ，ＣＴ）｜ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ，ｗ）を満たすｗ∈ＣＯＩＮｐｋ^ｅｎｃが存在する｝を公開鍵暗号ＰＫＥから定義される言語（ただし、ＣＯＩＮｐｋ^ｅｎｃは乱数空間）、ＰΣｃｏｍを言語Ｌｅｎｃ上のシグマプロトコルΣの第一メッセージ生成アルゴリズム、ＰΣａｎｓを言語Ｌｅｎｃ上のシグマプロトコルΣの第二メッセージ生成アルゴリズム、ＶΣｖｒｆｙを言語Ｌｅｎｃ上のシグマプロトコルΣの検証アルゴリズムとして、前記共通参照情報生成装置は、１κから、前記鍵生成アルゴリズムＫ、Ｇｅｎｔｃを用いて、２つの公開鍵と秘密鍵の組（ｐｋｅｎｃ，ｓｋｅｎｃ）←Ｋ（１κ）、（ｐｋｔｃ，ｓｋｔｃ）←Ｇｅｎｔｃ（１κ）を生成し、前記秘密鍵ｓｋｅｎｃ、ｓｋｔｃを廃棄する鍵生成部と、前記公開鍵ｐｋｅｎｃ、ｐｋｔｃ、前記ハッシュ関数Ｈを組にしたｃｒｓ＝（ｐｋｅｎｃ，ｐｋｔｃ，Ｈ）を共通参照情報として生成するＣＲＳ生成部とを含み、前記コミット生成装置は、乱数ｗ←ＣＯＩＮｐｋ^ｅｎｃ（ただし、ＣＯＩＮｐｋ^ｅｎｃは乱数空間）を生成し、前記暗号化アルゴリズムＥと前記公開鍵ｐｋｅｎｃを用いて、秘匿情報ｍ∈ＭＳＰｐｋ^ｅｎｃ（ただし、ＭＳＰｐｋ^ｅｎｃは平文空間）から暗号化済秘匿情報ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ，ｗ）を計算する秘匿情報暗号化部と、前記第一メッセージ生成アルゴリズムＰΣｃｏｍを用いて、前記秘匿情報ｍと前記暗号化済秘匿情報ＣＴの組（ｍ，ＣＴ）と前記乱数ｗから第一メッセージ（α，ξ）←ＰΣｃｏｍ（（ｍ，ＣＴ），ｗ）を計算する第一メッセージ計算部と、前記ハッシュ関数Ｈと４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）（ただし、ｓｉｄはセッションＩＤ、ｓｓｉｄはサブセッションＩＤ、Ｃは前記コミット生成装置のＩＤ、Ｒは前記コミット受信装置のＩＤを示す有限のビット列）を用いて、前記秘匿情報ｍ、前記暗号化済秘匿情報ＣＴ、前記第一メッセージの第１要素αからハッシュ値φ＝Ｈ（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ｍ，ＣＴ，α）を計算するハッシュ値計算部と、乱数ｒｔｃ←ＣＯＩＮｐｋ^ｔｃ（ただし、ＣＯＩＮｐｋ^ｔｃは乱数空間）を生成し、前記暗号化アルゴリズムＣｏｍｔｃと前記公開鍵ｐｋｔｃを用いて、前記ハッシュ値φから暗号化済ハッシュ値Ψ＝Ｃｏｍｔｃｐｋ^ｔｃ （φ；ｒｔｃ） を計算するハッシュ値暗号化部と、前記４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）、前記暗号化済ハッシュ値Ψを前記コミット受信装置に送信する第一コミット部と、前記第二メッセージ生成アルゴリズムＰΣａｎｓを用いて、前記秘匿情報ｍと前記暗号化済秘匿情報ＣＴの組（ｍ，ＣＴ）、前記乱数ｗ、前記第一メッセージの第２要素ξ、前記コミット受信装置から受信した乱数εから第二メッセージγ＝ＰΣａｎｓ（（ｍ���ＣＴ），ｗ，ξ，ε）を計算する第二メッセージ計算部と、前記乱数ｗと前記第一メッセージの第２要素ξを消去する消去部と、前記暗号化済秘匿情報ＣＴを前記コミット受信装置に送信する第二コミット部と、前記秘匿情報ｍと前記第一メッセージの第１要素αと前記第二メッセージγと前記乱数ｒｔｃからなる４つ組（ｍ，α，γ，ｒｔｃ）を開示情報として前記コミット受信装置に送信する開示部とを含み、前記コミット受信装置は、前記コミット生成装置から受信した前記４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）を検証し、問題なければ前記乱数ε←｛０，１｝λ_ｃを生成し、前記乱数εを前記コミット生成装置に送信する乱数生成部と、前記コミット生成装置から受信した前記４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）、前記暗号化済秘匿情報ＣＴ、前記開示情報（ｍ，α，γ，ｒｔｃ）と前記ハッシュ関数Ｈを用いて、ハッシュ値φ’＝Ｈ（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ｍ，ＣＴ，α）を計算するハッシュ値計算部と、前記暗号化アルゴリズムＣｏｍｔｃと前記検証アルゴリズムＶΣｖｒｆｙを用いて、前記ハッシュ値φ’、前記開示情報（ｍ，α，γ，ｒｔｃ）、前記暗号化済秘匿情報ＣＴ、前記乱数εからＣｏｍｔｃｐｋ^ｔｃ（φ’；ｒｔｃ）とＶΣｖｒｆｙ（（ｍ，ＣＴ），（α，ε，γ））を計算し、前記暗号化済ハッシュ値Ψ＝Ｃｏｍｔｃｐｋ^ｔｃ（φ’；ｒｔｃ）とＶΣｖｒｆｙ（（ｍ，ＣＴ），（α，ε，γ））＝１が成立するか確認する開封部とを含む。
【００２０】
本発明の一態様は、共通参照情報生成装置と、コミット生成装置と、コミット受信装置とを含むコミットメントシステムであって、κをセキュリティパラメータ、λｍ（・），λｃ（・）をκの関数、Ｈ：｛０，１｝＊→｛０，１｝λ_ｍを衝突困難ハッシュ関数、Ｋを公開鍵暗号ＰＫＥの鍵生成アルゴリズム、Ｅを公開鍵暗号ＰＫＥの暗号化アルゴリズム、Ｇｅｎｔｃを落し戸付きコミットメントＴＣＯＭの鍵生成アルゴリズム、Ｃｏｍｔｃを落し戸付きコミットメントＴＣＯＭの暗号化アルゴリズム、Ｌｅｎｃ＝｛（ｍ，ＣＴ）｜ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ，ｗ）を満たすｗ∈ＣＯＩＮｐｋ^ｅｎｃが存在する｝を公開鍵暗号ＰＫＥから定義される言語（ただし、ＣＯＩＮｐｋ^ｅｎｃは乱数空間）、ＰΣｃｏｍを言語Ｌｅｎｃ上のシグマプロトコルΣの第一メッセージ生成アルゴリズム、ＰΣａｎｓを言語Ｌｅｎｃ上のシグマプロトコルΣの第二メッセージ生成アルゴリズム、ＶΣｖｒｆｙを言語Ｌｅｎｃ上のシグマプロトコルΣの検証アルゴリズムとして、前記共通参照情報生成装置は、１κから、前記鍵生成アルゴリズムＫ、Ｇｅｎｔｃを用いて、２つの公開鍵と秘密鍵の組（ｐｋｅｎｃ，ｓｋｅｎｃ）←Ｋ（１κ）、（ｐｋｔｃ，ｓｋｔｃ）←Ｇｅｎｔｃ（１κ）を生成し、前記秘密鍵ｓｋｅｎｃ、ｓｋｔｃを廃棄する鍵生成部と、前記公開鍵ｐｋｅｎｃ、ｐｋｔｃ、前記ハッシュ関数Ｈを組にしたｃｒｓ＝（ｐｋｅｎｃ，ｐｋｔｃ，Ｈ）を共通参照情報として生成するＣＲＳ生成部とを含み、前記コミット生成装置は、乱数ｗ←ＣＯＩＮｐｋ^ｅｎｃ（ただし、ＣＯＩＮｐｋ^ｅｎｃは乱数空間）を生成し、前記暗号化アルゴリズムＥと前記公開鍵ｐｋｅｎｃを用いて、秘匿情報ｍ∈ＭＳＰｐｋ^ｅｎｃ（ただし、ＭＳＰｐｋ^ｅｎｃは平文空間）から暗号化済秘匿情報ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ，ｗ）を計算する秘匿情報暗号化部と、４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）（ただし、ｓｉｄはセッションＩＤ、ｓｓｉｄはサブセッションＩＤ、Ｃは前記コミット生成装置のＩＤ、Ｒは前記コミット受信装置のＩＤを示す有限のビット列）、前記暗号化済秘匿情報ＣＴを前記コミット受信装置に送信する第二コミット部と、前記第一メッセージ生成アルゴリズムＰΣｃｏｍを用いて、前記秘匿情報ｍと前記暗号化済秘匿情報ＣＴの組（ｍ，ＣＴ）と前記乱数ｗから第一メッセージ（α，ξ）←ＰΣｃｏｍ（（ｍ，ＣＴ），ｗ）を計算する第一メッセージ計算部と、前記ハッシュ関数Ｈと前記（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）を用いて、前記秘匿情報ｍ、前記暗号化済秘匿情報ＣＴ、前記第一メッセージの第１要素αからハッシュ値φ＝Ｈ（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ｍ，ＣＴ，α）を計算するハッシュ値計算部と、乱数ｒｔｃ←ＣＯＩＮｐｋ^ｔｃ（ただし、ＣＯＩＮｐｋ^ｔｃは乱数空間）を生成し、前記暗号化アルゴリズムＣｏｍｔｃと前記公開鍵ｐｋｔｃを用いて、前記ハッシュ値φから暗号化済ハッシュ値Ψ＝Ｃｏｍｔｃｐｋ^ｔｃ （φ；ｒｔｃ） を計算するハッシュ値暗号化部と、前記暗号化済ハッシュ値Ψを前記コミット受信装置に送信する第一開示部と、前記第二メッセージ生成アルゴリズムＰΣａｎｓを用いて、前記秘匿情報ｍと前記暗号化済秘匿情報ＣＴの組（ｍ，ＣＴ）、前記乱数ｗ、前記第一メッセージの第２要素ξ、前記コミッ���受信装置から受信した乱数εから第二メッセージγ＝ＰΣａｎｓ（（ｍ，ＣＴ），ｗ，ξ，ε）を計算する第二メッセージ計算部と、前記秘匿情報ｍと前記第一メッセージの第１要素αと前記第二メッセージγと前記乱数ｒｔｃからなる４つ組（ｍ，α，γ，ｒｔｃ）を第二開示情報として前記コミット受信装置に送信する第二開示部とを含み、前記コミット受信装置は、前記コミット生成装置から受信した前記４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）を検証し、問題なければ前記乱数ε←｛０，１｝λ_ｃを生成し、前記乱数εを前記コミット生成装置に送信する乱数生成部と、前記コミット生成装置から受信した前記４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）、前記暗号化済秘匿情報ＣＴ、前記開示情報（ｍ，α，γ，ｒｔｃ）と前記ハッシュ関数Ｈを用いて、ハッシュ値φ’＝Ｈ（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ｍ，ＣＴ，α）を計算するハッシュ値計算部と、前記暗号化アルゴリズムＣｏｍｔｃと前記検証アルゴリズムＶΣｖｒｆｙを用いて、前記ハッシュ値φ’、前記開示情報（ｍ，α，γ，ｒｔｃ）、前記暗号化済秘匿情報ＣＴ、前記乱数εからＣｏｍｔｃｐｋ^ｔｃ（φ’；ｒｔｃ）とＶΣｖｒｆｙ（（ｍ，ＣＴ），（α，ε，γ））を計算し、前記暗号化済ハッシュ値Ψ＝Ｃｏｍｔｃｐｋ^ｔｃ（φ’；ｒｔｃ）とＶΣｖｒｆｙ（（ｍ，ＣＴ），（α，ε，γ））＝１が成立するか確認する開封部とを含む。
【発明の効果】
【００２１】
本発明によれば、ＣＲＳ再利用型・適応的安全な汎用結合可能コミットメント及びＣＲＳ再利用型・静的安全な汎用結合可能コミットメントにおいて、共通パラメータ長、通信量、計算量を削減することが可能となる。
【図面の簡単な説明】
【００２２】
【図１】コミットメントシステム１００の構成を示すブロック図。
【図２】共通参照情報生成装置２００の構成を示すブロック図。
【図３】共通参照情報生成装置２００の動作を示すフローチャート。
【図４】コミット生成装置３００の構成を示すブロック図。
【図５】コミット受信装置４００の構成を示すブロック図。
【図６】コミットフェーズのシークエンス図（実施形態１）。
【図７】デコミットフェーズのシークエンス図（実施形態１）。
【図８】離散対数問題に基づくコミットメント方式の比較表（実施形態２）。
【図９】コミット生成装置５００の構成を示すブロック図。
【図１０】コミット受信装置６００の構成を示すブロック図。
【図１１】コミットフェーズのシークエンス図（実施形態３）。
【図１２】デコミットフェーズのシークエンス図（実施形態３）。
【図１３】離散対数問題に基づくコミットメント方式の比較表（実施形態４）。
【発明を実施するための形態】
【００２３】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２４】
＜本願発明の要点＞
現時点において最も効率がよいと考えられるＣＲＳ再利用型・適応的安全な汎用結合可能コミットメントである非特許文献４は、選択暗号文攻撃に強い公開鍵暗号Cramer-Shoup暗号（参考非特許文献２）とPedersenトラップドアコミットメント（参考非特許文献３）とシグマプロトコル（参考非特許文献４）を組み合わせることで構成される。
（参考非特許文献２：Ronald Cramer and Victor Shoup, “A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack”, In Hugo Krawczyk, editor, CRYPTO '98, volume 1462 of Lecture Notes in Computer Science, pages 13-25, Springer, Heidelberg, 1998.）
（参考非特許文献３：Torben P. Pedersen, “Non-interactive and information-theoretic secure verifiable secret sharing”, In Joan Feigenbaum, editor, CRYPTO '91, volume 576 of Lecture Notes in Computer Science, pages 129-140, Springer, Heidelberg, 1991.）
（参考非特許文献４：R. Cramer, I. Damgard and B. Schoenmakers,“Proofs of partial knowledge and simplified design of witness hiding protocols”, In Yvo G. Desmedt, editor, CRYPTO '94, volume 839 of Lecture Notes in Computer Science, pages 174-187, Springer, Heidelberg, 1994.）
本願発明では、選択暗号文攻撃より弱い公開鍵暗号を使い、さらに２つ使われていたPedersenトラップドアコミットメントを１つにして構成することにより、コミットメントの安全性は落とさずに、共通パラメータ長、通信量、計算量を削減する。
【００２５】
また、別の本願発明では、上記本願発明におけるコミット情報や開示情報の送信順番を換えることにより、コミットメントの安全性を静的安全にしたコミットメントを実現する。当該コミットメントも従来方法に比して共通パラメータ長、通信量、計算量を削減したものとなる。
【００２６】
＜準備＞
実施形態の説明に先立って、この明細書で用いる記法、用語等について説明する。
【００２７】
［記法等］
^（キャレット）は上付き添字を表す。例えば、xy^zはyzがxに対する上付き添字であり、xy^zはyzがxに対する下付き添字であることを表す。また、_（アンダースコア）は下付き添字を表す。例えば、xy_zはyzがxに対する上付き添字であり、xy_zはyzがxに対する下付き添字であることを表す。
【００２８】
アルゴリズムＭが確率的（probablistic）であるとは、Ｍの出力ｙが入力ｘとＭの内部乱数（内部コイン投げ）ｒによって決定されるときにいう。すなわち、Ｍは二入力関数としてＭ（ｘ；ｒ）＝ｙと書ける。確定的（deterministic）なアルゴリズムは、内部コインのない確率的なアルゴリズムの特別な場合として定義できる。以下、ｙ←Ｍ（ｘ）と書くと、確率空間Ｍ（ｘ）から確率変数ｙを選んできた試行を意味する。一方、ｙ＝Ｍ（ｘ；ｒ）と書くときは、Ｍを（確定的な）関数とみている。また、集合Ｘに対して、ｘ←Ｘと書くと、集合Ｘから一様ランダムに確率変数ｘを選んできた試行を意味する。
【００２９】
κをセキュリティパラメータ、λｍ（・），λｃ（・）をκの関数とする。しばしば、λｍ（κ）＝κ，λｃ（κ）＝κである。
Ｈ：｛０，１｝＊→｛０，１｝λ_ｍを衝突困難ハッシュ関数とする。
【００３０】
［公開鍵暗号］
公開鍵暗号ＰＫＥ＝（Ｋ，Ｅ，Ｄ）は、次の３つのアルゴリズムから定義される。
【００３１】
＜Ｋ：鍵生成アルゴリズム＞
入力：セキュリティパラメータ１κ
出力：公開鍵と秘密鍵の組（ｐｋｅｎｃ，ｓｋｅｎｃ）←Ｋ（１κ）
【００３２】
＜Ｅ：暗号化アルゴリズム＞
入力：ｐｋｅｎｃ，平文ｍ∈ＭＳＰｐｋ^ｅｎｃ（ただし、ＭＳＰｐｋ^ｅｎｃは平文生成のための集合（以下、平文空間という））
出力：ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ；ｗ）（ただし、ｗは内部乱数）
【００３３】
＜Ｄ：復号アルゴリズム＞
入力：ｓｋｅｎｃ，ＣＴ
出力：ｍ＝Ｄｓｋ^ｅｎｃ（ＣＴ）
【００３４】
［落し戸付きコミットメント（トラップドアコミットメント）］
落し戸付きコミットメントＴＣＯＭ＝（Ｇｅｎｔｃ，Ｃｏｍｔｃ，ＴＣｏｍｔｃ，ＴＣｏｌｔｃ）とは、次の４つのアルゴリズムからなるコミットメントである（参考非特許文献５）。
（参考非特許文献５：Gilles Brassard, David Chaum and Claude Crepeau, ”Minimum disclosure proofs of knowledge”, Journal of Computer and System Sciences (JCSS), 37(2), pages 156-189, October 1988.）
【００３５】
＜Ｇｅｎｔｃ: 確率的アルゴリズム＞
入力：セキュリティパラメータ１κ
出力：公開鍵と秘密鍵の組（ｐｋｔｃ，ｓｋｔｃ）←Ｇｅｎｔｃ（１κ）
以下では、Ｇｅｎｔｃを鍵生成アルゴリズムともいうことにする。
【００３６】
＜Ｃｏｍｔｃ：確率的アルゴリズム＞
入力：ｐｋｔｃ，平文φ∈｛０，１｝λ_ｍ
出力：ｃ＝Ｃｏｍｔｃｐｋ＾ｔｃ（φ；ｒｔｃ）（ただし、ｒｔｃは内部乱数）
以下では、Ｃｏｍｔｃを暗号化アルゴリズムともいうことにする。
【００３７】
＜ＴＣｏｍｔｃ：確率的アルゴリズム＞
入力：ｓｋｔｃ，１κ
出力：（ｃ，ξ）←ＴＣｏｍｔｃｓｋ＾ｔｃ（１κ）
【００３８】
＜ＴＣｏｌｔｃ：確定的アルゴリズム＞
入力：ｓｋｔｃ，（ｃ，ξ），φ∈｛０，１｝λ_ｍ
出力：ｒ＝ＴＣｏｌｔｃｓｋ＾ｔｃ（ｃ，ξ，φ）
もし、（ｐｋｔｃ，ｓｋｔｃ）∈Ｇｅｎｔｃ，（ｃ，ξ）∈ ＴＣｏｍｔｃｓｋ＾ｔｃ（１κ）であるならば、任意のφ∈｛０，１｝＊に対して、ｒ＝ＴＣｏｌｔｃｓｋ＾ｔｃ（ｃ，ξ，φ）は、ｃ＝Ｃｏｍｔｃｐｋ＾ｔｃ（φ；ｒ）という条件を満たすとする。
【００３９】
落し戸付きコミットメントＴＣＯＭはさらに次のような条件を満たす。
１．  ｐｋｔｃが与えられたとき、Ｃｏｍｔｃｐｋ＾ｔｃ（φ；ｒｔｃ）＝Ｃｏｍｔｃｐｋ＾ｔｃ（φ’；ｒｔｃ’）となる（φ，ｒｔｃ）≠（φ’，ｒｔｃ’）を計算することは難しい。
２．  すべての（ｐｋｔｃ，φ）に対して、（ｃ，φ，ｒｔｃ）を次の二通りのやり方で作っても分布は同じである。ただし、ＣＯＩＮｐｋ＾ｔｃは乱数生成のための集合（以下、乱数空間という）である。
【００４０】
１）rｔｃ←ＣＯＩＮｐｋ＾ｔｃ；ｃ＝Ｃｏｍｔｃｐｋ＾ｔｃ（φ；ｒｔｃ）
２）（ｃ，ξ）←ＴＣｏｍｔｃｓｋ＾ｔｃ（１κ）；ｒｔｃ＝ＴＣｏｌｔｃｓｋ＾ｔｃ（ｃ，ξ，φ）
ＤＬ型の落し戸付きコミットメントの実例としてPedersenのコミットメント（参考非特許文献３）がある。
【００４１】
［シグマプロトコル］
言語Ｌ＝｛ｘ｜（ｘ，ｗ）∈Ｒ｝をＮＰ言語とする（ただし、二項関係ＲはＮＰ関係とする）。言語Ｌ上のシグマプロトコルΣ＝（ＰΣｃｏｍ，ＰΣａｎｓ，ＶΣｖｒｆｙ，ｓｉｍＰΣｃｏｍ）は、次の４つのアルゴリズムから定義される。
【００４２】
＜ＰΣｃｏｍ：確率的アルゴリズム＞
入力：（ｘ，ｗ）∈Ｒ
出力：（α，ξ）←ＰΣｃｏｍ（ｘ，ｗ）
以下では、ＰΣｃｏｍを第一メッセージ生成アルゴリズムともいうことにする。
【００４３】
＜ＰΣａｎｓ：確定的アルゴリズム＞
入力：（ｘ，ｗ）∈Ｒ，ξ，ε∈｛０，１｝λ_ｃ
出力：γ＝ＰΣａｎｓ（ｘ，ｗ，ξ，ε）
以下では、ＰΣａｎｓを第二メッセージ生成アルゴリズムともいうことにする。
【００４４】
＜ＶΣｖｒｆｙ：確定的アルゴリズム＞
入力：ｘ∈Ｌ，（α，ε，γ）
出力：０／１（ただし、１は受理、０は不受理を表す）
以下では、ＶΣｖｒｆｙを検証アルゴリズムともいうことにする。
【００４５】
＜ｓｉｍＰΣｃｏｍ：確率的アルゴリズム＞
入力：ｘ∈Ｌ，ε
出力：（α，γ）←ｓｉｍＰΣｃｏｍ（ｘ，ε）
シグマプロトコルΣは、次のような条件を満たす（詳細は参考非特許文献４を参照）。
１．  すべての（ｘ，ｗ）∈Ｒに対して、
【００４６】
【数１】
0006563857.tif 000002
【００４７】
この式は、（ｘ，ｗ）に対して、（α，ξ）←ＰΣｃｏｍ（ｘ，ｗ）、ε←｛０，１｝λ_ｃ、γ＝ＰΣａｎｓ（ｘ，ｗ，ξ，ε）の順で試行等を進めていくと、（α，ε，γ）がＶΣｖｒｆｙに受理される確率が１になることを示している。
２．  ε≠ε’なる（α，ε，γ）と（α，ε’，γ’）が共にＶΣｖｒｆｙに受理される（すなわち、ＶΣｖｒｆｙ（ｘ，（α，ε，γ））＝１かつＶΣｖｒｆｙ（ｘ，（α，ε’，γ’））＝１が成立する）場合、ｘ∈Ｌである。
３．  すべての（ｘ，ｗ）∈Ｒに対して、（α，ε，γ）を次の二通りのやり方で作っても分布は同じである。
【００４８】
１）（α，ξ）←ＰΣｃｏｍ（ｘ，ｗ）；ε←｛０，１｝λ_ｃ；γ＝ＰΣａｎｓ（ｘ，ｗ，ξ，ε）
２）ε←｛０，１｝λ_ｃ；（α，γ）←ｓｉｍＰΣｃｏｍ（ｘ，ε）
【００４９】
［公開鍵暗号から定義される言語］
公開鍵暗号ＰＫＥ＝（Ｋ，Ｅ，Ｄ）から定義される言語Ｌｅｎｃを以下のように定義する。
Ｌｅｎｃ＝｛（ｍ，ＣＴ）｜ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ，ｗ）を満たすｗ∈ＣＯＩＮｐｋ^ｅｎｃが存在する｝
【００５０】
＜実施形態１＞
以下、図１〜図７を参照してコミットメントシステム１００について説明する。図１は、コミットメントシステム１００の構成を示すブロック図である。図２は、共通参照情報生成装置２００の構成を示すブロック図である。図３は、共通参照情報生成装置２００の動作を示すフローチャートである。図４は、コミット生成装置３００の構成を示すブロック図である。図５は、コミット受信装置４００の構成を示すブロック図である。図６は、コミットフェーズのシークエンス図である。図７は、デコミットフェーズのシークエンス図である。
【００５１】
図１に示すように、コミットメントシステム１００は、共通参照情報生成装置２００と、コミット生成装置３００と、コミット受信装置４００を含む。共通参照情報生成装置２００、コミット生成装置３００、コミット受信装置４００の各装置はネットワーク８００（例：インターネット）に接続しており、相互に通信することが可能である。図２に示すように、共通参照情報生成装置２００は、鍵生成部２１０と、ＣＲＳ生成部２２０と、ハッシュ関数記録部２９０を含む。図４に示すように、コミット生成装置３００は、秘匿情報暗号化部３０５と、第一メッセージ計算部３１０と、ハッシュ値計算部３１５と、ハッシュ値暗号化部３２０と、第一コミット部３２５と、第二メッセージ計算部３３０と、消去部３３５と、第二コミット部３４０と、開示部３５０と、通信部３８０と、開示情報記録部３９０を含む。図５に示すように、コミット受信装置４００は、乱数生成部４０５と、ハッシュ値計算部４５０と、開封部４５５と、通信部４８０と、コミット情報記録部４９０を含む。
【００５２】
［ＣＲＳの生成］
共通参照情報生成装置２００は、セキュリティパラメータ１κから共通参照情報ｃｒｓを生成する。鍵生成部２１０は、セキュリティパラメータ１κから、公開鍵暗号ＰＫＥの鍵生成アルゴリズムＫと落し戸付きコミットメントＴＣＯＭの鍵生成アルゴリズムＧｅｎｔｃを用いて、（ｐｋｅｎｃ，ｓｋｅｎｃ）←Ｋ（１κ）と（ｐｋｔｃ，ｓｋｔｃ）←Ｇｅｎｔｃ（１κ）を生成し、ｓｋｅｎｃとｓｋｔｃを廃棄する（Ｓ２１０）。
【００５３】
ＣＲＳ生成部２２０は、ハッシュ関数記録部２９０に記録してあるハッシュ関数Ｈ：｛０，１｝＊→｛０，１｝λ_ｍを読出し、ｃｒｓ＝（ｐｋｅｎｃ，ｐｋｔｃ，Ｈ）を共通参照情報（ＣＲＳ）として生成し、出力する（Ｓ２２０）。共通参照情報ｃｒｓは、コミット生成装置３００、コミット受信装置４００から取得できるように公開される。あるいは、共通参照情報生成装置２００が、コミット生成装置３００、コミット受信装置４００にｃｒｓを送信するのでもよい。いずれにしてもコミットフェーズ開始時には、コミット生成装置３００、コミット受信装置４００はｃｒｓを保持している。
【００５４】
［コミット（封じ手）フェーズ］
本実施形態のコミットメントはコミット生成装置３００とコミット受信装置４００の３交信からなるプロトコルである。
【００５５】
コミット生成装置３００の秘匿情報暗号化部３０５は、コミットする秘匿情報ｍ∈ＭＳＰｐｋ^ｅｎｃを入力としてとり、乱数ｗ←ＣＯＩＮｐｋ^ｅｎｃを発生させ、公開鍵暗号ＰＫＥの暗号化アルゴリズムＥ、ｃｒｓの第１要素であるｐｋｅｎｃを用いて、暗号化済秘匿情報ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ，ｗ）を計算する（Ｓ３０５）。ただし、ＭＳＰｐｋ^ｅｎｃは平文空間、ＣＯＩＮｐｋ^ｅｎｃは乱数空間である。
【００５６】
なお、秘匿情報ｍとＳ３０５で計算したＣＴの組（ｍ，ＣＴ）はＬｅｎｃ＝｛（ｍ，ＣＴ）｜ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ，ｗ）を満たすｗ∈ＣＯＩＮｐｋ^ｅｎｃが存在する｝で定義される言語Ｌｅｎｃの元となる。
【００５７】
コミット生成装置３００の第一メッセージ計算部３１０は、言語Ｌｅｎｃ上のシグマプロトコルΣの第一メッセージ生成アルゴリズムＰΣｃｏｍを用いて、言語Ｌｅｎｃの元（ｍ，ＣＴ）に対するシグマプロトコルΣの第一メッセージ（α，ξ）←ＰΣｃｏｍ（（ｍ，ＣＴ），ｗ）を計算する（Ｓ３１０）。ここで、ｗは、ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ，ｗ）を満たすＣＯＩＮｐｋ^ｅｎｃの元であり、Ｓ３０５で発生させた乱数ｗである。
【００５８】
コミット生成装置３００のハッシュ値計算部３１５は、ｃｒｓの第３要素であるハッシュ関数Ｈを用いて、ハッシュ値φ＝Ｈ（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ｍ，ＣＴ，α）を計算する（Ｓ３１５）。ｓｉｄはセッションＩＤ、ｓｓｉｄはサブセッションＩＤ、Ｃはコミット生成装置３００のＩＤ、Ｒはコミット受信装置４００のＩＤであり、それぞれ有限のビット列で表される。
【００５９】
コミット生成装置３００のハッシュ値暗号化部３２０は、乱数ｒｔｃ←ＣＯＩＮｐｋ^ｔｃを発生させ、落し戸付きコミットメントＴＣＯＭの暗号化アルゴリズムＣｏｍｔｃ、ｃｒｓの第２要素であるｐｋｔｃを用いて、暗号化済ハッシュ値Ψ＝Ｃｏｍｔｃｐｋ^ｔｃ （φ；ｒｔｃ） を計算する（Ｓ３２０）。ただし、ＣＯＩＮｐｋ^ｔｃは乱数空間である。
【００６０】
コミット生成装置３００の第一コミット部３２５は、ＩＤの４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）と暗号化済ハッシュ値Ψをコミット受信装置４００に送信（Ｓ３２５）、コミット受信装置４００は、通信部４８０を用いて、（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）とΨを受信する（Ｓ４８０−１）。
【００６１】
コミット受信装置４００の乱数生成部４０５は、（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）を検証し、問題なければ乱数ε←｛０，１｝λ_ｃを発生させ、コミット生成装置３００に送信する（Ｓ４０５）。コミット生成装置３００は、通信部３８０を用いて、εを受信する（Ｓ３８０−１）。
【００６２】
コミット生成装置３００の第二メッセージ計算部３３０は、言語Ｌｅｎｃ上のシグマプロトコルΣの第二メッセージ生成アルゴリズムＰΣａｎｓを用いて、言語Ｌｅｎｃの元（ｍ，ＣＴ）に対するシグマプロトコルΣの第二メッセージγ＝ＰΣａｎｓ（（ｍ，ＣＴ），ｗ，ξ，ε）を計算する（Ｓ３３０）。ここで、ξはＳ３１０で計算した第一メッセージの第２要素である。
【００６３】
コミット生成装置３００の消去部３３５は、乱数ｗ，第一メッセージの第２要素ξを消去する（Ｓ３３５）。
【００６４】
コミット生成装置３００の第二コミット部３４０は、暗号化済秘匿情報ＣＴをコミット受信装置４００に送信（Ｓ３４０）、コミット受信装置４００は、通信部４８０を用いて、暗号化済秘匿情報ＣＴを受信し、コミット受信装置４００はデコミットフェーズのための受理状態になる（Ｓ４８０−２）。
【００６５】
コミット生成装置３００は、秘匿情報ｍ、第一メッセージの第１要素α、第二メッセージγ、乱数ｒｔｃからなる４つ組（ｍ，α，γ，ｒｔｃ）を開示情報として開示情報記録部３９０に記録する（Ｓ３９０）。また、コミット受信装置４００は、暗号化済秘匿情報ＣＴ、暗号化済ハッシュ値Ψ、乱数εからなる３つ組（ＣＴ，Ψ，ε）をコミット情報としてコミット情報記録部４９０に記録する（Ｓ４９０）。
【００６６】
［デコミット（開封）フェーズ］
本実施形態のデコミットメントはコミット生成装置３００がコミット受信装置４００に開示情報を送りつけ、コミット受信装置４００がそれを受理するか拒否するかを判定する非対話型プロトコルである。
【００６７】
コミット生成装置３００の開示部３５０は、開示情報記録部３９０に記録しておいた開示情報（ｍ，α，γ，ｒｔｃ）をコミット受信装置４００に送信（Ｓ３５０）、コミット受信装置４００は、通信部４８０を用いて、開示情報（ｍ，α，γ，ｒｔｃ）を受信する（Ｓ４８０−３）。
【００６８】
コミット受信装置４００のハッシュ値計算部４５０は、ｃｒｓの第３要素であるハッシュ関数Ｈを用いて、ハッシュ値φ’＝ Ｈ（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ｍ，ＣＴ，α）を計算し復元する（Ｓ４５０）。なお、（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）はコミットフェーズにおいてコミット生成装置３００から受信し、保持しておいたものである。また、ＣＴはコミット情報記録部４９０に記録したコミット情報（ＣＴ，Ψ，ε）の第１要素である。
【００６９】
コミット受信装置４００の開封部４５５は、落し戸付きコミットメントＴＣＯＭの暗号化アルゴリズムＣｏｍｔｃと言語Ｌｅｎｃ上のシグマプロトコルΣの検証アルゴリズムＶΣｖｒｆｙを用いて、Ｃｏｍｔｃｐｋ^ｔｃ（φ’；ｒｔｃ）とＶΣｖｒｆｙ（（ｍ，ＣＴ），（α，ε，γ））を計算し、Ψ＝Ｃｏｍｔｃｐｋ^ｔｃ（φ’；ｒｔｃ）とＶΣｖｒｆｙ（（ｍ，ＣＴ），（α，ε，γ））＝１が成立するか確認する（Ｓ４５５）。上記２式が成立することが確認されれば開封が正常に行われたと判断し承認する。一方、それ以外の場合、開封を拒絶する。なお、ｍ，α，γ，ｒｔｃはＳ４８０−３で受信した開示情報（ｍ，α，γ，ｒｔｃ）の各要素、ＣＴ，Ψ，εはコミット情報記録部４９０に記録したコミット情報（ＣＴ，Ψ，ε）の各要素である。
【００７０】
なお、（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）をコミット生成装置３００で保持しておき、Ｓ３５０で改めて（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）をコミット生成装置３００からコミット受信装置４００に送信するようにしてもよい。
【００７１】
＜実施形態２＞
実施形態１は、ＣＲＳ再利用型・適応的安全な汎用結合コミットメントの一般的構成法である。そこで、実施形態２では、以下の通り、巡回群Ｇを用いて実施形態１を具体化する。
【００７２】
［記号等］
まず、次のように記号を定義する。
【００７３】
ｇを位数ｑの巡回群Ｇの生成元とする。また、κ＝ｌｏｇ２（ｑ）とする。群演算は、乗法で記述する。ｇがＧの生成元であるので、任意のａ，ｂ∈Ｇに対して、ａ＝ｇｘ，ｂ＝ｇｙとなるｘ，ｙ∈Ｚ／ｑＺが存在し、ａ・ｂ＝ｇｘ＋ｙ∈Ｇである。
【００７４】
また、λｍ，λｃ≦κとする。
【００７５】
さらに、Ｈ’：｛０，１｝＊→Ｚ／ｑＺを有限長のビット列ｘ∈｛０，１｝＊をＺ／ｑＺの元にハッシュするハッシュ関数とする。
【００７６】
［公開鍵暗号］
公開鍵暗号ＰＫＥ＝（Ｋ，Ｅ，Ｄ）は、以下のような暗号である。
【００７７】
＜Ｋ＞ 
入力：１κ（ただし、κ＝ｌｏｇ２（ｑ））
出力：ｘｅ←Ｚ／ｑＺをランダムに取ってきて、Ｙｅ＝ｇｘ_ｅを計算する。Ｚｅ，Ｚｅ’←Ｇをランダムに取ってくる。（ｐｋｅｎｃ，ｓｋｅｎｃ）＝（（Ｙｅ，Ｚｅ，Ｚｅ’），ｘｅ）とし、（ｐｋｅｎｃ，ｓｋｅｎｃ）を出力する。
【００７８】
＜Ｅ＞
入力：ｐｋｅｎｃ，平文ｍ∈Ｇ
出力：乱数ｗ←ＣＯＩＮｐｋ^ｅｎｃを生成し、ｔ＝Ｈ’（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ｇｗ）を計算し、ＣＴ＝（ｇｗ，（ＺｅｔＺｅ’）ｗ，ｍ・Ｙｅｗ）を計算し、ＣＴを出力する。
【００７９】
＜Ｄ＞
入力：ｓｋｅｎｃ，ＣＴ
出力：ＣＴ＝（ＣＴ１，ＣＴ２，ＣＴ３）をＣＴ１，ＣＴ２，ＣＴ３に分解し、ｍ＝ＣＴ３／ＣＴ１ｘ_ｅを計算し、出力する。
【００８０】
［公開鍵暗号から定義される言語］
公開鍵暗号ＰＫＥから定義される言語Ｌｅｎｃ＝｛（ｍ，ＣＴ）｜ＣＴ＝（ＣＴ１，ＣＴ２，ＣＴ３），ＣＴ１＝ｇｗ，ＣＴ２＝（ＺｅｔＺｅ’）ｗ，ＣＴ３＝ｍ・Ｙｅｗを満たすｗ∈ＣＯＩＮｐｋ^ｅｎｃが存在する。｝（ただし、ｔ＝Ｈ’（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ＣＴ１））と定義する。
【００８１】
［シグマプロトコル］
言語Ｌｅｎｃ上のシグマプロトコルΣ＝（ＰΣｃｏｍ，ＰΣａｎｓ，ＶΣｖｒｆｙ，ｓｉｍＰΣｃｏｍ）を次のものとする。
【００８２】
＜ＰΣｃｏｍ＞
入力：（ｍ，ＣＴ）, ｗ（ただし、ＣＴ＝（ＣＴ１，ＣＴ２，ＣＴ３），ＣＴ１＝ｇｗ，ＣＴ２＝（ＺｅｔＺｅ’）ｗ，ＣＴ３＝ｍ・Ｙｅｗを満たす。なお、ｔ＝Ｈ’（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ＣＴ１））
つまり、（ｐｋｅｎｃ，ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）も暗黙に含まれる。
出力：ξ←Ｚ／ｑＺをランダムに選び、α１＝ｇξ,ｔ＝ Ｈ’（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，α１）, α２＝（ＺｅｔＺｅ’）ξ，α３＝Ｙｅξと計算する。α＝（α１，α２，α３）とし、（α，ξ）を出力する。
【００８３】
＜ＰΣａｎｓ＞
入力：（ｍ，ＣＴ）, ｗ，ξ，ε∈｛０，１｝λ_ｃ（ただし、ＣＴ＝（ＣＴ１，ＣＴ２，ＣＴ３），ＣＴ１＝ｇｗ，ＣＴ２＝（ＺｅｔＺｅ’）ｗ，ＣＴ３＝ｍ・Ｙｅｗを満たす。なお、ｔ＝Ｈ’（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ＣＴ１））
出力：γ＝ξ−εｗ  ｍｏｄ ｑを計算し、γを出力する。
【００８４】
＜ＶΣｖｒｆｙ＞
入力：（ｍ，ＣＴ）∈Ｌｅｎｃ，（α，ε，γ）
出力：α１＝ｇγＣＴ１ε、α２＝（ＺｅｔＺｅ’）γＣＴ２ε、α３＝Ｙｅγ（ＣＴ３／ｍ）εをすべて満たすなら１を、そうでないなら０を出力する。
【００８５】
＜ｓｉｍＰΣｃｏｍ＞
入力： （ｍ，ＣＴ）∈Ｌｅｎｃ，ε
出力：γ←Ｚ／ｑＺをランダムに選び、α１＝ｇγＣＴ１ε,α２＝（ＺｅｔＺｅ’）γＣＴ２ε、α３＝Ｙｅγ（ＣＴ３／ｍ）εを計算し、α＝（α１，α２，α３）とし、（α，γ）を出力する。
【００８６】
［落し戸付きコミットメント］
落し戸付きコミットメントＴＣＯＭを次のものとする。
【００８７】
＜Ｇｅｎｔｃ＞
入力：１κ（ただし、κ＝ｌｏｇ２（ｑ））
出力：ｘｔｃ←Ｚ／ｑＺをランダムに取ってきて、ｈ＝ｇｘ_ｔｃを計算する。ｐｋｔｃ＝（Ｇ，ｇ，ｑ，ｈ）、ｓｋｔｃ＝（ｐｋｔｃ，ｘｔｃ）とし、（ｐｋｔｃ，ｓｋｔｃ）を出力する。
【００８８】
＜Ｃｏｍｔｃ＞
入力：ｐｋｔｃ，平文φ∈｛０，１｝λ_ｍ
出力：内部乱数ｒｔｃ←Ｚ／ｑＺをランダムにとり、ｃ＝ｇｒ_ｔｃｈφを計算し、ｃを出力する。
【００８９】
＜ＴＣｏｍｔｃ＞
入力：ｓｋｔｃ，１κ
出力：ξ←Ｚ／ｑＺをランダムに取ってきて、ｃ＝ｇξを計算し、（ｃ，ξ）を出力する。
【００９０】
＜ＴＣｏｌｔｃ＞
入力：ｓｋｔｃ，（ｃ，ξ），φ∈｛０，１｝λ_ｍ
出力：ｒ＝ξ−φ・ｘｔｃ ｍｏｄ ｑを計算し、ｒを出力する（ｃ＝ｇｒｈφを満たすことに注意）。
【００９１】
＜実施形態２の発明の理論的評価（効果）＞
本発明は、共通参照情報ＣＲＳが固定長で再利用でき、適応的安全な汎用結合コミットメントの一般的構成法（実施形態１）とその具体的実現例（実施形態２）である。特に、巡回群を用いて公開鍵暗号、落し戸付きコミットメント、シグマプロトコルの３つを構成することにより、実施形態２はＤＬ型のＣＲＳ再利用型・適応的安全な汎用結合可能コミットメントとなる。
【００９２】
図８に本発明と非特許文献３、非特許文献４の比較表を示す。この表をみると分かるように、実施形態２及び実施形態３は、仮定が非特許文献３や非特許文献４と同等であるにも関わらず、共通パラメータ長、通信量、計算量の点で勝っている。
【００９３】
ただし、κはセキュリティパラメータ、ａ／ｂは交信数（ａはコミットフェーズに必要とされる交信数、ｂはデコミットフェーズに必要とされる交信数）、Ｔｅｘｐ（Ｇ）は巡回群Ｇ上のべき乗剰余演算１回のコストを表す。また、Ｇの表現にもよるが、｜Ｇ｜＝κと考えてよい。ＤＤＨは判定ＤＨ仮定、ＣＲＨは衝突困難ハッシュ関数を意味する。
【００９４】
なお、実施形態２の効率は安全性も考慮に入れて、非特許文献３や非特許文献４と同等になるように、λｍ（κ）＝κ，λｃ（κ）＝κと設定した。つまり、安全性の点では、実施形態２の発明はＤＬ型の非特許文献３や非特許文献４と同程度となっている。
【００９５】
また、非特許文献３、非特許文献４、実施形態２のコミットできる平文ｍは、｜Ｇ｜ビット以下である。
【００９６】
＜実施形態３＞
実施形態１では、ＣＲＳ再利用型・適応的安全な汎用結合コミットメントの一般的構成法を示した。しかし、場合によっては、汎用結合可能コミットメントシステムに求められる安全性として、静的安全性で十分なこともある。また、コミットメントはゼロ知識証明と組み合わさることでしばしば開示することなく利用される。この場合、コミットフェーズの通信量、計算量ができるだけ少なく、コミットフェーズが非対話型であればより望ましい。
【００９７】
そこで、実施形態３では、コミットフェーズが非対話型のＣＲＳ再利用型・静的安全な汎用結合コミットメントの一般的構成法を示す。具体的には、実施形態１での送信手順を一部変更することにより、実現する。
【００９８】
ＣＲＳ再利用型・静的安全な汎用結合コミットメントシステムの構成はコミットメントシステム１００の構成と同じである。また、ＣＲＳ再利用型・静的安全な汎用結合コミットメントシステムに含まれる共通参照情報生成装置の構成もコミットメントシステム１００に含まれる共通参照情報生成装置２００の構成と同一である。そこで、以下では、図９〜図１２を参照してＣＲＳ再利用型・静的安全な汎用結合コミットメントシステムに含まれるコミット生成装置５００とコミット受信装置６００について説明する。図９は、コミット生成装置５００の構成を示すブロック図である。図１０は、コミット受信装置６００の構成を示すブロック図である。図１１は、コミットフェーズのシークエンス図である。図１２は、デコミットフェーズのシークエンス図である。
【００９９】
図９に示すように、コミット生成装置５００は、秘匿情報暗号化部５０５と、第二コミット部５４０と、第一メッセージ計算部５１０と、ハッシュ値計算部５１５と、ハッシュ値暗号化部５２０と、第一開示部５２５と、第二メッセージ計算部５３０と、第二開示部５５０と、通信部５８０と、開示情報生成用情報記録部５９０を含む。図１０に示すように、コミット受信装置６００は、乱数生成部６０５と、ハッシュ値計算部６５０と、開封部６５５と、通信部６８０と、コミット情報記録部６９０を含む。
【０１００】
［コミット（封じ手）フェーズ］
本実施形態のコミットメントはコミット生成装置５００とコミット受信装置６００の非対話型プロトコルである。
【０１０１】
コミット生成装置５００の秘匿情報暗号化部５０５は、コミットする秘匿情報ｍ∈ＭＳＰｐｋ^ｅｎｃを入力としてとり、乱数ｗ←ＣＯＩＮｐｋ^ｅｎｃを発生させ、公開鍵暗号ＰＫＥの暗号化アルゴリズムＥ、ｃｒｓの第１要素であるｐｋｅｎｃを用いて、暗号化済秘匿情報ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ，ｗ）を計算する（Ｓ５０５）。ただし、ＭＳＰｐｋ^ｅｎｃは平文空間、ＣＯＩＮｐｋ^ｅｎｃは乱数空間である。
【０１０２】
なお、秘匿情報ｍとＳ５０５で計算したＣＴの組（ｍ，ＣＴ）はＬｅｎｃ＝｛（ｍ，ＣＴ）｜ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ，ｗ）を満たすｗ∈ＣＯＩＮｐｋ^ｅｎｃが存在する｝で定義される言語Ｌｅｎｃの元となる。
【０１０３】
コミット生成装置５００の第二コミット部５４０は、ＩＤの４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）と暗号化済秘匿情報ＣＴをコミット受信装置６００に送信（Ｓ５４０）、コミット受信装置６００は、通信部６８０を用いて、ＩＤの４つ組（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）と暗号化済秘匿情報ＣＴを受信し、コミット受信装置６００はデコミットフェーズのための受理状態になる（Ｓ６８０−１）。ｓｉｄはセッションＩＤ、ｓｓｉｄはサブセッションＩＤ、Ｃはコミット生成装置５００のＩＤ、Ｒはコミット受信装置６００のＩＤであり、それぞれ有限のビット列で表される。
【０１０４】
コミット生成装置５００は、秘匿情報ｍ、暗号化済秘匿情報ＣＴ、乱数ｗからなる３つ組（ｍ，ＣＴ，ｗ）を開示情報生成用情報として開示情報生成用情報記録部５９０に記録する（Ｓ５９０）。また、コミット受信装置６００は、暗号化済秘匿情報ＣＴをコミット情報としてコミット情報記録部６９０に記録する（Ｓ６９０）。
【０１０５】
［デコミット（開封）フェーズ］
本実施形態のデコミットメントはコミット生成装置５００がコミット受信装置６００に２つの開示情報（第一開示情報と第二開示情報）を送りつけ、コミット受信装置６００がそれを受理するか拒否するかを判定するプロトコルである。第一開示情報は、実施形態１の第一コミット部３２５が送信した情報と同一である。また、第二開示情報は、実施形態１の開示部３５０が送信した情報と同一である。
【０１０６】
コミット生成装置５００の第一メッセージ計算部５１０は、言語Ｌｅｎｃ上のシグマプロトコルΣの第一メッセージ生成アルゴリズムＰΣｃｏｍを用いて、言語Ｌｅｎｃの元（ｍ，ＣＴ）に対するシグマプロトコルΣの第一メッセージ（α，ξ）←ＰΣｃｏｍ（（ｍ，ＣＴ），ｗ）を計算する（Ｓ５１０）。ここで、ｍ，ＣＴ，ｗは、Ｓ５９０で開示情報生成用情報として開示情報生成用情報記録部５９０に記録していたものである。なお、ｗは、ＣＴ＝Ｅｐｋ^ｅｎｃ（ｍ，ｗ）を満たすＣＯＩＮｐｋ^ｅｎｃの元である。
【０１０７】
コミット生成装置５００のハッシュ値計算部５１５は、ｃｒｓの第３要素であるハッシュ関数Ｈを用いて、ハッシュ値φ＝Ｈ（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ｍ，ＣＴ，α）を計算する（Ｓ５１５）。なお、（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）はコミットフェーズにおいてコミット生成装置５００から受信し、保持しておいたものである。
【０１０８】
コミット生成装置５００のハッシュ値暗号化部５２０は、乱数ｒｔｃ←ＣＯＩＮｐｋ^ｔｃを発生させ、落し戸付きコミットメントＴＣＯＭの暗号化アルゴリズムＣｏｍｔｃ、ｃｒｓの第２要素であるｐｋｔｃを用いて、暗号化済ハッシュ値Ψ＝Ｃｏｍｔｃｐｋ^ｔｃ （φ；ｒｔｃ） を計算する（Ｓ５２０）。ただし、ＣＯＩＮｐｋ^ｔｃは乱数空間である。
【０１０９】
コミット生成装置５００の第一開示部５２５は、暗号化済ハッシュ値Ψを第一開示情報としてコミット受信装置６００に送信（Ｓ５２５）、コミット受信装置６００は、通信部６８０を用いて、Ψを受信する（Ｓ６８０−２）。
【０１１０】
コミット受信装置６００の乱数生成部６０５は、（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）を検証し、問題なければ乱数ε←｛０，１｝λ_ｃを発生させ、コミット生成装置５００に送信する（Ｓ６０５）。コミット生成装置５００は、通信部５８０を用いて、εを受信する（Ｓ５８０−１）。
【０１１１】
コミット生成装置５００の第二メッセージ計算部５３０は、言語Ｌｅｎｃ上のシグマプロトコルΣの第二メッセージ生成アルゴリズムＰΣａｎｓを用いて、言語Ｌｅｎｃの元（ｍ，ＣＴ）に対するシグマプロトコルΣの第二メッセージγ＝ＰΣａｎｓ（（ｍ，ＣＴ），ｗ，ξ，ε）を計算する（Ｓ５３０）。ここで、ξはＳ５１０で計算した第一メッセージの第２要素である。
【０１１２】
コミット生成装置５００の第二開示部５５０は、秘匿情報ｍ、第一メッセージの第１要素α、第二メッセージγ、乱数ｒｔｃを４つ組にした第二開示情報（ｍ，α，γ，ｒｔｃ）をコミット受信装置６００に送信（Ｓ５５０）、コミット受信装置６００は、通信部６８０を用いて、第二開示情報（ｍ，α，γ，ｒｔｃ）を受信する（Ｓ６８０−３）。
【０１１３】
コミット受信装置６００のハッシュ値計算部６５０は、ｃｒｓの第３要素であるハッシュ関数Ｈを用いて、ハッシュ値φ’＝ Ｈ（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ，ｍ，ＣＴ，α）を計算し復元する（Ｓ６５０）。なお、（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）はコミットフェーズにおいてコミット生成装置５００から受信し、保持しておいたものである。また、ＣＴはコミット情報記録部６９０に記録したコミット情報である。
【０１１４】
コミット受信装置６００の開封部６５５は、落し戸付きコミットメントＴＣＯＭの暗号化アルゴリズムＣｏｍｔｃと言語Ｌｅｎｃ上のシグマプロトコルΣの検証アルゴリズムＶΣｖｒｆｙを用いて、Ｃｏｍｔｃｐｋ^ｔｃ（φ’；ｒｔｃ）とＶΣｖｒｆｙ（（ｍ，ＣＴ），（α，ε，γ））を計算し、Ψ＝Ｃｏｍｔｃｐｋ^ｔｃ（φ’；ｒｔｃ）とＶΣｖｒｆｙ（（ｍ，ＣＴ），（α，ε，γ））＝１が成立するか確認する（Ｓ６５５）。上記２式が成立することが確認されれば開封が正常に行われたと判断し承認する。一方、それ以外の場合、開封を拒絶する。なお、ｍ，α，γ，ｒｔｃはＳ６８０−３で受信した第二開示情報（ｍ，α，γ，ｒｔｃ）の各要素、ＣＴはコミット情報記録部６９０に記録したコミット情報、ΨはＳ６８０−２で受信した第一開示情報である。
【０１１５】
なお、（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）をコミット生成装置５００で保持しておき、Ｓ５２５・Ｓ５５０で改めて（ｓｉｄ，ｓｓｉｄ，Ｃ，Ｒ）をコミット生成装置５００からコミット受信装置６００に送信するようにしてもよい。
【０１１６】
＜実施形態４＞
実施形態３は、コミットフェーズが非対話型のＣＲＳ再利用型・静的安全な汎用結合コミットメントの一般的構成法である。実施形態４は、実施形態２で用いた公開鍵暗号ＰＫＥ、公開鍵暗号から定義される言語Ｌｅｎｃ、言語Ｌｅｎｃ上のシグマプロトコルΣ、落し戸付きコミットメントＴＣＯＭを実施形態３に適用した汎用結合コミットメントである。
【０１１７】
これにより、ＤＬ型のＣＲＳ再利用型・静的安全な汎用結合コミットメントを構成することができる。
【０１１８】
＜実施形態４の発明の理論的評価（効果）＞
本発明は、コミットフェーズが非対話型であり、共通参照情報ＣＲＳが固定長で再利用でき、静的安全な汎用結合コミットメントの一般的構成法（実施形態３）とその具体的実現例（実施形態４）である。特に、巡回群を用いて公開鍵暗号、落し戸付きコミットメント、シグマプロトコルの３つを構成することにより、実施形態４はＤＬ型のＣＲＳ再利用型・静的安全な汎用結合可能コミットメントとなる。
【０１１９】
図１３に本発明と非特許文献３、非特許文献４の比較表を示す。なお、図１３の非特許文献３（Ｌｉｎ１１）や非特許文献４（ＢＣＰＶ１３）は、図８の非特許文献３（Ｌｉｎ１１）や非特許文献４（ＢＣＰＶ１３）とは異なり、静的安全を満たすように構成された汎用結合コミットメントである。この表をみると分かるように、実施形態２の場合と同様、実施形態４は、仮定が非特許文献３や非特許文献４と同等であるにも関わらず、共通パラメータ長、通信量、計算量の点で勝っている。
【０１２０】
なお、実施形態４の効率も安全性を考慮に入れて、非特許文献３や非特許文献４と同等になるように、λｍ（κ）＝κ，λｃ（κ）＝κと設定したのは実施形態２と同様である。つまり、安全性の点では、実施形態２と同様、実施形態４の発明はＤＬ型の非特許文献３や非特許文献４と同程度となっている。
【０１２１】
また、非特許文献３、非特許文献４、実施形態４のコミットできる平文ｍは、｜Ｇ｜ビット以下である点も実施形態２と同様である。
【０１２２】
＜補記＞
本発明の装置は、例えば単一のハードウェアエンティティとして、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit、キャッシュメモリやレジスタなどを備えていてもよい）、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けることとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【０１２３】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくこととしてもよい）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。
【０１２４】
ハードウェアエンティティでは、外部記憶装置（あるいはＲＯＭなど）に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（上記、…部、…手段などと表した各構成要件）を実現する。
【０１２５】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【０１２６】
既述のように、上記実施形態において説明したハードウェアエンティティ（本発明の装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【０１２７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０１２８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１２９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１３０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
0006563857.tif 000003
【図２】
0006563857.tif 000004
【図３】
0006563857.tif 000005
【図４】
0006563857.tif 000006
【図５】
0006563857.tif 000007
【図６】
0006563857.tif 000008
【図７】
0006563857.tif 000009
【図８】
0006563857.tif 000010
【図９】
0006563857.tif 000011
【図１０】
0006563857.tif 000012
【図１１】
0006563857.tif 000013
【図１２】
0006563857.tif 000014
【図１３】
0006563857.tif 000015