(57)【特許請求の範囲】
【請求項１】
共通参照情報生成装置とコミット生成装置とコミット受信装置とを備えるコミットメントシステムであって、
正の整数κをセキュリティパラメータ、Ｓ１ｕをあらかじめ定めた集合、Ｓ２ｕをあらかじめ定めた集合、Ｓ１をκビットの値と集合Ｓ１ｕの組み合わせで表現される集合、Ｓ２をκビットの値と集合Ｓ２ｕの組み合わせで表現される集合、Ｌｕ１を集合Ｓ１ｕの部分集合、Ｌｕ２を集合Ｓ２ｕの部分集合、Ｌ１をκビットの値と集合Ｌｕ１の組み合わせで表現される集合、Ｌ２をκビットの値と集合Ｌｕ２の組み合わせで表現される集合、ｐｋ１を集合の組（Ｓ１，Ｌ１）の記述を含んだ公開鍵、ｐｋ２を集合の組（Ｓ２，Ｌ２）の記述を含んだ公開鍵、ｓｋ１を公開鍵ｐｋ１に対する秘密鍵、ｓｋ２を公開鍵ｐｋ２に対する秘密鍵とし、
前記共通参照情報生成装置は、
前記セキュリティパラメータκに基づいて（ｐｋ１，ｓｋ１）、（ｐｋ２，ｓｋ２）を生成する鍵生成部と、
前記秘密鍵ｓｋ１，ｓｋ２を廃棄する秘密鍵廃棄部と、
公開鍵の組ｐｋ＝（ｐｋ１，ｐｋ２）を共通参照情報として公開するＣＲＳ公開部と、
を備え、
前記コミット生成装置は、
前記公開鍵の組ｐｋとκビットの値であるタグｔとコミットする対象である平文ｘを取得する入力情報取得部と、
前記集合Ｓ１ｕの元の中からサンプル値ｕ１をランダムに選択し、前記集合Ｓ２ｕの元の中からサンプル値ｕ２をランダムに選択するサンプル値選択部と、
前記公開鍵ｐｋ１と前記平文ｘからあらかじめ定めた方法で一意に決まる内部乱数空間ＣＯＩＮ１の元の中から内部乱数ｒ１をランダムに選択し、前記公開鍵ｐｋ２と前記平文ｘからあらかじめ定めた方法で一意に決まる内部乱数空間ＣＯＩＮ２の元の中から内部乱数ｒ２をランダムに選択する乱数生成部と、
前記平文ｘを前記公開鍵ｐｋ１と前記タグｔと前記サンプル値ｕ１と前記内部乱数ｒ１を用いて暗号化して暗号文ｃ１を求め、前記平文ｘを前記公開鍵ｐｋ２と前記タグｔと前記サンプル値ｕ２と前記内部乱数ｒ２を用いて暗号化して暗号文ｃ２を求め、コミットメントをｃ＝（ｃ１，ｃ２）とする暗号化部と、
前記コミットメントｃと前記タグｔと前記サンプル値ｕ１，ｕ２を前記コミット受信装置に送信するコミット送信部と、
前記内部乱数ｒ１，ｒ２と前記平文ｘを前記コミット受信装置に送信するデコミット送信部と
を備え、
前記コミット受信装置は、
前記公開鍵の組ｐｋを取得する公開情報取得部と、
コミットメントｃ’＝（ｃ１’，ｃ２’）とタグｔ’とサンプル値ｕ１’，ｕ２’を受信するコミット受信部と、
内部乱数ｒ１’，ｒ２’と平文ｘ’を受信するデコミット受信部と、
前記内部乱数ｒ１’が前記公開鍵ｐｋ１と前記平文ｘ’から前記あらかじめ定めた方法で一意に決まる内部乱数空間ＣＯＩＮ１の元であるかを確認し、前記内部乱数ｒ２’が前記公開鍵ｐｋ２と前記平文ｘ’から前記あらかじめ定めた方法で一意に決まる内部乱数空間ＣＯＩＮ２の元であるかを確認し、前記平文ｘ’を前記公開鍵ｐｋ１と前記タグｔ’と前記サンプル値ｕ１’と前記内部乱数ｒ１’を用いて暗号化して得た暗号文ｃ１”が、ｃ１”＝ｃ１’であることを確認し、前記平文ｘ’を前記公開鍵ｐｋ２と前記タグｔ’と前記サンプル値ｕ２’と前記内部乱数ｒ２’を用いて暗号化して得た暗号文ｃ２”が、ｃ２”＝ｃ２’であることを確認する確認部と
を備える
ことを特徴とするコミットメントシステム。
【請求項２】
請求項１記載のコミットメントシステムであって、
ｑ１，ｑ２を素数、ｇ１を位数ｑ１の群Ｇ１の生成元、ｇ２を位数ｑ２の群Ｇ２の生成元、ｘ１１，ｘ１２，ｙ１０，ｙ１１，…，ｙ１κを０以上ｑ１−１以下の整数、ｘ２１，ｘ２２，ｙ２０，ｙ２１，…，ｙ２κを０以上ｑ２−１以下の整数、ｉを１または２、ｊを１以上κ以下の整数、ｍを１または２、＾をべき乗を示す記号、ｔｎをｔのｎビット目、λをＯ（ｌｏｇκ）の秘密情報長、集合Ｓ１ｕを群Ｇ１の２つの元の組み合わせの集合、集合Ｓ２ｕを群Ｇ２の２つの元の組み合わせの集合、Ｈｍ（ｔ）を
【数５】
0005755600.tif 000006
とし、
前記鍵生成部は、ｇ１，ｘ１１，ｘ１２，ｙ１０，ｙ１１，…，ｙ１κをランダムに選び、ｇ１１，ｇ１２，ｈ１０，ｈ１１，…，ｈ１κをｇ１ｉ＝ｇ１＾ｘ１ｉ、ｈ１ｊ＝ｇ１＾ｙ１ｊのように計算し、ｐｋ１＝（Ｇ１，ｇ１，ｑ１，λ，（Ｓ１，Ｌ１），ｇ１１，ｇ１２，ｈ１０，ｈ１１，…，ｈ１κ）とｓｋ１＝（ｐｋ１，ｘ１２，ｙ１０，ｙ１１，…，ｙ１κ）のように（ｐｋ１，ｓｋ１）を生成し、ｇ２，ｘ２１，ｘ２２，ｙ２０，ｙ２１，…，ｙ２κをランダムに選び、ｇ２１，ｇ２２，ｈ２０，ｈ２１，…，ｈ２κをｇ２ｉ＝ｇ２＾ｘ２ｉ、ｈ２ｊ＝ｇ２＾ｙ２ｊのように計算し、ｐｋ２＝（Ｇ２，ｇ２，ｑ２，λ，（Ｓ２，Ｌ２），ｇ２１，ｇ２２，ｈ２０，ｈ２１，…，ｈ２κ）とｓｋ２＝（ｐｋ２，ｘ２２，ｙ２０，ｙ２１，…，ｙ２κ）のように（ｐｋ２，ｓｋ２）を生成し、
前記サンプル値選択部は、サンプル値ｕ１として、群Ｇ１の中の２つの元の組（ｕ１ｒ，ｕ１ｔ）をランダムに選定し、サンプル値ｕ２として、群Ｇ２の中の２つの元の組（ｕ２ｒ，ｕ２ｔ）をランダムに選定し、
前記乱数生成部は、内部乱数ｒ１として、０以上ｑ−１以下の整数である乱数ｚ１と乱数ｓ１を生成し、内部乱数ｒ２として、０以上ｑ−１以下の整数である乱数ｚ２と乱数ｓ２を生成し、
前記暗号化部は、
Ａ１＝（ｇ１１＾ｚ１）（Ｈ１（ｔ）＾ｓ１）（ｕ１ｔ＾ｘ１）
ａ１＝（ｇ１＾ｚ１）（ｇ１２＾ｘ１）
ｂ１＝（ｇ１＾ｓ１）（ｕ１ｒ＾ｘ１）
を計算してｃ１＝（Ａ１，ａ１，ｂ１）とし、
Ａ２＝（ｇ２１＾ｚ１）（Ｈ２（ｔ）＾ｓ２）（ｕ２ｔ＾ｘ２）
ａ２＝（ｇ２＾ｚ２）（ｇ２２＾ｘ２）
ｂ２＝（ｇ２＾ｓ２）（ｕ２ｒ＾ｘ２）
を計算してｃ２＝（Ａ２，ａ２，ｂ２）として、（ｃ１，ｃ２）をコミットメントｃとする
ことを特徴とするコミットメントシステム。
【請求項３】
請求項１記載のコミットメントシステムであって、
Ｐ１，Ｑ１，Ｐ２，Ｑ２を整数、Ｎ１＝Ｐ１Ｑ１、Ｎ２＝Ｐ２Ｑ２、ｖ１，ｖ２を正の整数、ｉを１または２、ｊを１以上κ以下の整数、ｍを１または２、＾をべき乗を示す記号、ｘ１ｉとｙ１ｊを０以上Ｎ１＾ｖ１−１以下の整数、ｘ２ｉとｙ２ｊを０以上Ｎ２＾ｖ２−１以下の整数、Ｓ１ｕを０以上Ｎ１＾（ｖ１＋１）−１以下の整数の中の２つの整数の組み合わせの集合、Ｓ２ｕを０以上Ｎ２＾（ｖ２＋１）−１以下の整数の中の２つの整数の組み合わせの集合、ｇ１＝１＋Ｎ１、ｇ２＝１＋Ｎ２、平文ｘを０以上Ｎ１＾ｖ１−１以下の整数かつ０以上Ｎ２＾ｖ２−１以下の整数、Ｈｍ（ｔ）を
【数６】
0005755600.tif 000007
とし、
前記鍵生成部は、ｘ１１，ｘ１２，ｙ１０，ｙ１１，…，ｙ１κをランダムに選び、０以上Ｎ１＾（ｖ１＋１）−１の整数である乱数Ｒ１１，Ｒ１２を生成し、ｇ１１，ｇ１２，ｈ１０，ｈ１１，…，ｈ１κを
ｇ１ｉ＝（ｇ１＾ｘ１ｉ）Ｒ１ｉ＾Ｎ１＾ｖ１  ｍｏｄＮ１＾（ｖ１＋１）
ｈ１ｊ＝ｇ１＾ｙ１ｊ  ｍｏｄＮ１＾（ｖ１＋１） 
のように計算し、ｐｋ１＝（Ｎ１，ｖ１，（Ｓ１，Ｌ１），ｇ１１，ｇ１２，ｈ１０，ｈ１１，…，ｈ１κ）とｓｋ１＝（ｘ１２，ｙ１０，ｙ１１，…，ｙ１κ）のように（ｐｋ１，ｓｋ１）を生成し、ｘ２１，ｘ２２，ｙ２０，ｙ２１，…，ｙ２κをランダムに選び、０以上Ｎ２＾（ｖ２＋１）−１の整数である乱数Ｒ２１，Ｒ２２を生成し、ｇ２１，ｇ２２，ｈ２０，ｈ２１，…，ｈ２κを
ｇ２ｉ＝（ｇ２＾ｘ２ｉ）Ｒ２ｉ＾Ｎ２＾ｖ２  ｍｏｄＮ２＾（ｖ２＋１）
ｈ２ｊ＝ｇ２＾ｙ２ｊ  ｍｏｄＮ２＾（ｖ２＋１）
のように計算し、ｐｋ２＝（Ｎ２，ｖ２，（Ｓ２，Ｌ２），ｇ２１，ｇ２２，ｈ２０，ｈ２１，…，ｈ２κ）とｓｋ２＝（ｘ２２，ｙ２０，ｙ２１，…，ｙ２κ）のように（ｐｋ２，ｓｋ２）を生成し、
前記サンプル値選択部は、前記サンプル値ｕ１として、０以上Ｎ１＾（ｖ１＋１）−１以下の整数の中の２つの整数の組み合わせ（ｕ１ｒ，ｕ１ｔ）をランダムに選定し、前記サンプル値ｕ２として、０以上Ｎ２＾（ｖ２＋１）−１以下の整数の中の２つの整数の組み合わせ（ｕ２ｒ，ｕ２ｔ）をランダムに選定し、
前記乱数生成部は、内部乱数ｒ１として０以上Ｎ１＾ｖ１−１以下の整数である乱数ｚ１と乱数ｓ１を生成し、０以上Ｎ１＾（ｖ１＋１）−１以下の整数である乱数Ｒ１Ａ，Ｒ１ａ，Ｒ１ｂを生成し、内部乱数ｒ２として０以上Ｎ２＾ｖ２−１以下の整数である乱数ｚ２と乱数ｓ２を生成し、０以上Ｎ２＾（ｖ２＋１）−１以下の整数である乱数Ｒ２Ａ，Ｒ２ａ，Ｒ２ｂを生成し、
前記暗号化部は、
Ａ１＝（ｇ１１＾ｚ１）（Ｈ１（ｔ）＾ｓ１）（ｕ１ｔ＾ｘ１）（Ｒ１Ａ＾Ｎ１＾ｖ１）
ｍｏｄＮ１＾（ｖ１＋１）
ａ１＝（（ｇ１＾ｚ１）（Ｒ１ａ＾Ｎ１＾ｖ１）  ｍｏｄＮ１＾（ｖ１＋１））（ｇ１２＾ｘ１）
ｂ１＝（（ｇ１＾ｓ１）（Ｒ１ｂ＾Ｎ１＾ｖ１）  ｍｏｄＮ１＾（ｖ１＋１））（ｕ１ｒ＾ｘ１）
を計算してｃ１＝（Ａ１，ａ１，ｂ１）とし、
Ａ２＝（ｇ２１＾ｚ２）（Ｈ２（ｔ）＾ｓ２）（ｕ２ｔ＾ｘ２）（Ｒ２Ａ＾Ｎ２＾ｖ２）
ｍｏｄＮ２＾（ｖ２＋１）
ａ２＝（（ｇ２＾ｚ２）（Ｒ２ａ＾Ｎ２＾ｖ２）  ｍｏｄＮ２＾（ｖ２＋１））（ｇ２２＾ｘ２）
ｂ２＝（（ｇ２＾ｓ２）（Ｒ２ｂ＾Ｎ２＾ｖ２）  ｍｏｄＮ２＾（ｖ２＋１））（ｕ２ｒ＾ｘ２）
を計算してｃ２＝（Ａ２，ａ２，ｂ２）として、（ｃ１，ｃ２）をコミットメントｃとする  ことを特徴とするコミットメントシステム。
【請求項４】
請求項１〜３のいずれかに記載のコミットメントシステムが備える前記共通参照情報生成装置であることを特徴とする共通参照情報生成装置。
【請求項５】
請求項１〜３のいずれかに記載のコミットメントシステムが備える前記コミット生成装置であることを特徴とするコミット生成装置。
【請求項６】
請求項１〜３のいずれかに記載のコミットメントシステムが備える前記コミット受信装置であることを特徴とするコミット受信装置。
【請求項７】
共通参照情報生成装置とコミット生成装置とコミット受信装置とを用いたコミットメント方法であって、
正の整数κをセキュリティパラメータ、Ｓ１ｕをあらかじめ定めた集合、Ｓ２ｕをあらかじめ定めた集合、Ｓ１をκビットの値と集合Ｓ１ｕの組み合わせで表現される集合、Ｓ２をκビットの値と集合Ｓ２ｕの組み合わせで表現される集合、Ｌｕ１を集合Ｓ１ｕの部分集合、Ｌｕ２を集合Ｓ２ｕの部分集合、Ｌ１をκビットの値と集合Ｌｕ１の組み合わせで表現される集合、Ｌ２をκビットの値と集合Ｌｕ２の組み合わせで表現される集合、ｐｋ１を集合の組（Ｓ１，Ｌ１）の記述を含んだ公開鍵、ｐｋ２を集合の組（Ｓ２，Ｌ２）の記述を含んだ公開鍵、ｓｋ１を公開鍵ｐｋ１に対する秘密鍵、ｓｋ２を公開鍵ｐｋ２に対する秘密鍵とし、
前記共通参照情報生成装置が、前記セキュリティパラメータκに基づいて（ｐｋ１，ｓｋ１）、（ｐｋ２，ｓｋ２）を生成する鍵生成ステップと、
前記共通参照情報生成装置が、前記秘密鍵ｓｋ１，ｓｋ２を廃棄する秘密鍵廃棄ステップと、
前記共通参照情報生成装置が、公開鍵の組ｐｋ＝（ｐｋ１，ｐｋ２）を共通参照情報として公開するＣＲＳ公開ステップと、
前記コミット生成装置が、前記公開鍵の組ｐｋとκビットの値であるタグｔとコミットする対象である平文ｘを取得する入力情報取得ステップと、
前記コミット受信装置が、前記公開鍵の組ｐｋを取得する公開情報取得ステップと、
前記コミット生成装置が、前記集合Ｓ１ｕの元の中からサンプル値ｕ１をランダムに選択し、前記集合Ｓ２ｕの元の中からサンプル値ｕ２をランダムに選択するサンプル値選択ステップと、
前記コミット生成装置が、前記公開鍵ｐｋ１と前記平文ｘからあらかじめ定めた方法で一意に決まる内部乱数空間ＣＯＩＮ１の元の中から内部乱数ｒ１をランダムに選択し、前記公開鍵ｐｋ２と前記平文ｘからあらかじめ定めた方法で一意に決まる内部乱数空間ＣＯＩＮ２の元の中から内部乱数ｒ２をランダムに選択する乱数生成ステップと、
前記コミット生成装置が、前記平文ｘを前記公開鍵ｐｋ１と前記タグｔと前記サンプル値ｕ１と前記内部乱数ｒ１を用いて暗号化して暗号文ｃ１を求め、前記平文ｘを前記公開鍵ｐｋ２と前記タグｔと前記サンプル値ｕ２と前記内部乱数ｒ２を用いて暗号化して暗号文ｃ２を求め、コミットメントをｃ＝（ｃ１，ｃ２）とする暗号化ステップと、
前記コミット生成装置が、前記コミットメントｃと前記タグｔと前記サンプル値ｕ１，ｕ２を前記コミット受信装置に送信するコミット送信ステップと、
前記コミット受信装置が、コミットメントｃ’＝（ｃ１’，ｃ２’）とタグｔ’とサンプル値ｕ１’，ｕ２’を受信するコミット受信ステップと、
前記コミット生成装置が、前記内部乱数ｒ１，ｒ２と前記平文ｘを前記コミット受信装置に送信するデコミット送信ステップと、
前記コミット受信装置が、内部乱数ｒ１’，ｒ２’と平文ｘ’を受信するデコミット受信ステップと、
前記コミット受信装置が、前記内部乱数ｒ１’が前記公開鍵ｐｋ１と前記平文ｘ’から前記あらかじめ定めた方法で一意に決まる内部乱数空間ＣＯＩＮ１の元であるかを確認し、前記内部乱数ｒ２’が前記公開鍵ｐｋ２と前記平文ｘ’から前記あらかじめ定めた方法で一意に決まる内部乱数空間ＣＯＩＮ２の元であるかを確認し、前記平文ｘ’を前記公開鍵ｐｋ１と前記タグｔ’と前記サンプル値ｕ１’と前記内部乱数ｒ１’を用いて暗号化して得た暗号文ｃ１”が、ｃ１”＝ｃ１’であることを確認し、前記平文ｘ’を前記公開鍵ｐｋ２と前記タグｔ’と前記サンプル値ｕ２’と前記内部乱数ｒ２’を用いて暗号化して得た暗号文ｃ２”が、ｃ２”＝ｃ２’であることを確認する確認ステップと
を有するコミットメント方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術に関し、複数の暗号プロトコルの中に組み込まれ、同時に動くような環境でも高い安全性を保つコミットメントに関する。
【背景技術】
【０００２】
暗号におけるコミットメントとは、電子的に行う「封じ手」のことである。コミットメント方式は、コミットする側の送信者(committer)と、コミットメントを受ける側の受信者(receiver)の間で行われるプロトコルのことである。送信者は、コミットフェーズで、受信者に情報を預託（コミット）する。この時、受信者は預託された情報の中身を知ることができない（秘匿性）。次に、送信者は開示フェーズで秘匿した情報を受信者に納得いく形で開示するが、コミットフェーズで預託した情報と違う情報を開示して受信者を満足させることはできない（拘束性）。コミットメントは、基本的にこのような秘匿性と拘束性を満たさなければいけない。コミットメントのすぐ思いつく応用例は、電子的なジャンケンやコイン投げ（もちろん、将棋や碁に使う封じ手でも良い）であるが、実際に応用できる範囲はそれより遥かに広い。
【０００３】
コミットメントは最も基本的な暗号プロトコルであるため、上位の暗号プロトコルの中で頻繁に利用される。近年では、暗号プロトコルをより現実の環境に近づけるため、コミットメントはさらに複雑な組み合わせの中で利用される場合が増えてきた。このような複雑な組み合わせの中では、古典的暗号安全性モデルで作られたコミットメントでは、秘匿性と拘束性を同時に満たすことができなくなってしまう。汎用結合可能コミットメントとは、そのような複雑な組み合わせでコミットメントが利用された場合にも、秘匿性と拘束性を満たすよう設計されたコミットメントのことである（汎用結合可能性については非特許文献１，２参照）。
【０００４】
汎用結合可能コミットメントが構成できるためには、送信者と受信者の双方がアクセスできる（第三者の作った）共通参照情報(common reference string、以下ＣＲＳと記載)が必要であることが知られている（非特許文献３参照）。技術的な問題により、このＣＲＳは、コミットごとに使い捨てなければならない場合（すなわち、コミットの回数だけ新しいＣＲＳが必要となる）と、使い捨てずに同じＣＲＳを再利用できる場合に分かれる。当然ながら、ＣＲＳをずっと使える「ＣＲＳ再利用型」コミットメント方式の方が、実用性が高い。ＣＲＳ再利用型汎用結合可能コミットメントには、従来、非特許文献１，４，５の技術があった。
【０００５】
汎用結合可能コミットメントでは、送信者と受信者が、プロトコルの最中、もしくは終了後、途中データを廃棄しないと安全性が担保できない方式と、廃棄しなくても安全性を担保できる方式が存在する。当然、後者の「情報廃棄不要型」の方が、安全性が高く望ましい。さらに、計算量、通信量、交信回数なども、汎用結合コミットメントの良し悪しを判断する指標となる。当然、計算量、通信量、交信回数が少ないほど実用性が高い。特に、送信者から受信者に送るだけでコミットメントが完成する方式を「非対話型」という。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】R. Canetti. Universally composable security, “A new paradigm for cryptographic protocols”, In 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2001), pages 136-145, IEEE Computer Society, 2001.
【非特許文献２】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-Verlag, 2001.
【非特許文献４】Ivan Damgard and Jens Groth, “Non-interactive and reusable non-malleable commitment schemes”, In STOC 2003, pages 426-437, ACM, 2003.
【非特許文献５】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-Verlag, 2002.
【非特許文献６】Ryo Nishimaki, Eiichiro Fujisaki, and Keisuke Tanaka, “ Efficient non-interactive universally composable string-commitment schemes”, In Josef Pieprzyk and Fangguo Zhang, editors, ProvSec 2009, volume 5848 of Lecture Notes in Computer Science, pages 3-18, Springer-Verlag, 2009.
【非特許文献７】Yehuda Lindell,“Highly-efficient universally-composable commitments based on the DDH assumption”,Cryptology ePrint Archive, Report 2011/180, 2011, To appear EUROCRYPT 2011.
【非特許文献８】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-Verlag, 2011.
【非特許文献９】R. Canetti, Y. Lindell, R. Ostrovsky, and A. Sahai,“Universally composable two-party and multiparty secure computation”, In STOC 2002, pages 494-503. ACM, 2002.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献２，９以外の方式は、１ビットの秘密情報をコミットするのにＯ（ｋ）ビットの平文空間を持つ選択暗号文攻撃に対して安全な公開鍵暗号が最低２つ必要であった。なお、ｋはセキュリティパラメータであり、例えばｋは2048や160などである。また、Ｏ（ｘ）はｘと同じオーダーの大きさの値を示す記号である。すなわち、１ビットの秘密情報をコミットするのに、Ｏ（ｋ）ビットの情報量が必要であり効率が悪い。非特許文献４，５では、ｋビットの秘密情報をコミットするのにＯ（ｋ）ビットで済むので効率は改善されている。しかし、これらのプロトコルは送信者と受信者間の交信回数を３回必要としている。また、非特許文献４の方式は、ＣＲＳのサイズが、参加者の数に比例して増える（コミットメント方式をサブプロトコルに使う上位のプロトコルの参加者数が増えると、それに応じてＣＲＳのサイズが伸びる）。一方、非特許文献５の方式は、ＣＲＳのサイズは固定だが、途中データを適切な時に廃棄しないと安全性が担保されない可能性がある。いずれにせよ、両方式とも送信者と受信者の間に３交信が必要であるという欠点がある。
【０００８】
また、非特許文献６の方式は、非対話型だが、ＣＲＳ再利用型ではない。非特許文献７の方式は、通信量は少ないが５交信対話型であり、途中データを適切に廃棄できなければいけない。非特許文献８の方式は、非対話型だが、やはり途中データを廃棄できなければいけない。
【０００９】
本発明は、ＣＲＳが再利用可能であり、非対話、情報廃棄不要型の汎用結合可能コミットメントの構成方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明のコミットメントシステムは、共通参照情報生成装置とコミット生成装置とコミット受信装置とを備える。ここで、正の整数κをセキュリティパラメータ、Ｓ１ｕをあらかじめ定めた集合、Ｓ２ｕをあらかじめ定めた集合、Ｓ１をκビットの値と集合Ｓ１ｕの組み合わせで表現される集合、Ｓ２をκビットの値と集合Ｓ２ｕの組み合わせで表現される集合、Ｌｕ１を集合Ｓ１ｕの部分集合、Ｌｕ２を集合Ｓ２ｕの部分集合、Ｌ１をκビットの値と集合Ｌｕ１の組み合わせで表現される集合、Ｌ２をκビットの値と集合Ｌｕ２の組み合わせで表現される集合、ｐｋ１を集合の組（Ｓ１，Ｌ１）の記述を含んだ公開鍵、ｐｋ２を集合の組（Ｓ２，Ｌ２）の記述を含んだ公開鍵、ｓｋ１を公開鍵ｐｋ１に対する秘密鍵、ｓｋ２を公開鍵ｐｋ２に対する秘密鍵とする。また、平文ｘは、公開鍵ｐｋ１から定まるメッセージ空間と公開鍵ｐｋ２から定まるメッセージ空間の両方に属する元とする。共通参照情報生成装置は、セキュリティパラメータκに基づいて（ｐｋ１，ｓｋ１）と（ｐｋ２，ｓｋ２）を生成する鍵生成部と、秘密鍵ｓｋ１と秘密鍵ｓｋ２を廃棄する秘密鍵廃棄部と、公開鍵の組ｐｋ＝（ｐｋ１，ｐｋ２）を共通参照情報として公開するＣＲＳ公開部とを備える。コミット生成装置は、入力情報取得部、サンプル値選択部、乱数生成部、暗号化部、コミット送信部、デコミット送信部を備える。入力情報取得部は、公開鍵の組ｐｋ＝（ｐｋ１，ｐｋ２）とκビットの値であるタグｔとコミットする対象である平文ｘを取得する。サンプル値選択部は、集合Ｓ１ｕの元の中からサンプル値ｕ１をランダムに選択し、集合Ｓ２ｕの元の中からサンプル値ｕ２をランダムに選択する。乱数生成部は、公開鍵ｐｋ１と平文ｘからあらかじめ定めた方法で一意に決まる内部乱数空間ＣＯＩＮ１の元の中から内部乱数ｒ１をランダムに選択し、公開鍵ｐｋ２と平文ｘからあらかじめ定めた方法で一意に決まる内部乱数空間ＣＯＩＮ２の元の中から内部乱数ｒ２をランダムに選択する。暗号化部は、平文ｘを公開鍵ｐｋ１とタグｔとサンプル値ｕ１と内部乱数ｒ１を用いて暗号化して得た暗号文ｃ１と、平文ｘを公開鍵ｐｋ２とタグｔとサンプル値ｕ２と内部乱数ｒ２を用いて暗号化して得た暗号文ｃ２との組（ｃ１，ｃ２）を、コミットメントｃとする。コミット送信部は、コミットメントｃ＝（ｃ１，ｃ２）とタグｔとサンプル値ｕ１，ｕ２をコミット受信装置に送信する。デコミット送信部は、内部乱数ｒ１，ｒ２と平文ｘをコミット受信装置に送信する。コミット受信装置は、公開情報取得部、コミット受信部、デコミット受信部、確認部を備える。公開情報取得部は、公開鍵の組ｐｋを取得する。コミット受信部は、コミットメントｃ’＝（ｃ１’，ｃ２’）とタグｔ’とサンプル値ｕ１’，ｕ２’を受信する。デコミット受信部は、内部乱数ｒ１’，ｒ２’と平文ｘ’を受信する。確認部は、内部乱数ｒ１’が公開鍵ｐｋ１と平文ｘ’からあらかじめ定めた方法で一意に決まる内部乱数空間ＣＯＩＮ１の元であるかを確認し、内部乱数ｒ２’が公開鍵ｐｋ２と平文ｘ’からあらかじめ定めた方法で一意に決まる内部乱数空間ＣＯＩＮ２の元であるかを確認し、平文ｘ’を公開鍵ｐｋ１とタグｔ’とサンプル値ｕ１’と内部乱数ｒ���’を用いて暗号化して得た暗号文ｃ１”が、ｃ１”＝ｃ１’であることを確認し、平文ｘ’を公開鍵ｐｋ２とタグｔ’とサンプル値ｕ２’と内部乱数ｒ２’を用いて暗号化して得た暗号文ｃ２”が、ｃ２”＝ｃ２’であることを確認する。
【発明の効果】
【００１１】
本発明のコミットメントシステムはＡＢＭ暗号を利用しているので、ＣＲＳが再利用可能であり、非対話、情報廃棄不要型の汎用結合可能コミットメントを提供できる。
【図面の簡単な説明】
【００１２】
【図１】本発明のコミットメントシステムの構成例を示す図。
【図２】本発明の共通参照情報生成装置の機能構成例を示す図。
【図３】本発明のコミット生成装置の機能構成例を示す図。
【図４】本発明のコミット受信装置の機能構成例を示す図。
【図５】本発明のコミットメントシステムの処理フローを示す図。
【図６】ＡＢＭ暗号の構成を示す図。
【図７】４つの安全性条件を具体的に示す図。
【図８】ＡＢＭ暗号が４つの安全性条件を満たすことを証明するための第１の図。
【図９】ＡＢＭ暗号が４つの安全性条件を満たすことを証明するための第２の図。
【図１０】ＡＢＭ暗号が４つの安全性条件を満たすことを証明するための第３の図。
【図１１】ＡＢＭ暗号が４つの安全性条件を満たすことを証明するための第４の図。
【図１２】実施例２，３の方式と従来技術の比較を示す図。
【図１３】実施例２の方式と従来技術との効率に関する比較を示す図。
【発明を実施するための形態】
【００１３】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１４】
＜具体的なシステム＞
図１に本発明のコミットメントシステムの構成例を示す。本発明のコミットメントシステムは、例えばネットワーク１０００を介してつながった共通参照情報生成装置１００、コミット生成装置２００、コミット受信装置３００を備える。なお、ネットワーク１０００を介すのではなく、ＣＤなどの記録媒体を介して情報の授受を行ってもよい。ここで、正の整数κをセキュリティパラメータ、Ｓ１ｕをあらかじめ定めた集合、Ｓ２ｕをあらかじめ定めた集合、Ｓ１をκビットの値と集合Ｓ１ｕの組み合わせで表現される集合、Ｓ２をκビットの値と集合Ｓ２ｕの組み合わせで表現される集合、Ｌｕ１を集合Ｓ１ｕの部分集合、Ｌｕ２を集合Ｓ２ｕの部分集合、Ｌ１をκビットの値と集合Ｌｕ１の組み合わせで表現される集合、Ｌ２をκビットの値と集合Ｌｕ２の組み合わせで表現される集合、ｐｋ１を集合の組（Ｓ１，Ｌ１）の記述を含んだ公開鍵、ｐｋ２を集合の組（Ｓ２，Ｌ２）の記述を含んだ公開鍵、ｓｋ１を公開鍵ｐｋ１に対する秘密鍵、ｓｋ２を公開鍵ｐｋ２に対する秘密鍵とする。また、平文ｘは、公開鍵ｐｋ１から定まるメッセージ空間と公開鍵ｐｋ２から定まるメッセージ空間の両方に属する元とする。
【００１５】
図２は共通参照情報生成装置１００の機能構成例、図３はコミット生成装置２００の機能構成例、図４はコミット受信装置３００の機能構成例を示す図である。また、図５はコミットメントシステムの処理フローを示す図である。共通参照情報生成装置１００は、鍵生成部１１０、秘密鍵廃棄部１２０、ＣＲＳ公開部１３０、記録部１９０を備える。コミット生成装置２００は、入力情報取得部２１０、サンプル値選択部２２０、乱数生成部２３０、暗号化部２４０、コミット送信部２５０、デコミット送信部２６０、記録部２９０を備える。コミット受信装置３００は、公開情報取得部３１０、コミット受信部３２０、デコミット受信部３３０、確認部３４０、記録部３９０を備える。
【００１６】
まず、共通参照情報生成装置１００が以下の処理を行う。記録部１９０はセキュリティパラメータκなどのデータを記録しておく。鍵生成部１１０が、セキュリティパラメータκに基づいて（ｐｋ１，ｓｋ１）と（ｐｋ２，ｓｋ２）を生成する（Ｓ１１０）。秘密鍵廃棄部１２０が、秘密鍵ｓｋ１と秘密鍵ｓｋ２を廃棄する（Ｓ１２０）。ＣＲＳ公開部１３０が、公開鍵の組ｐｋ＝（ｐｋ１，ｐｋ２）を共通参照情報として公開する（Ｓ１３０）。
【００１７】
次にコミットフェーズとして、以下の処理を行う。コミット生成装置２００の入力情報取得部２１０が、公開鍵の組ｐｋ＝（ｐｋ１，ｐｋ２）とκビットの値であるタグｔとコミットする対象である平文ｘを取得し、記録部２９０に記録する（Ｓ２１０）。サンプル値選択部２２０が、集合Ｓ１ｕの元の中からサンプル値ｕ１をランダムに選択し、集合Ｓ２ｕの元の中からサンプル値ｕ２をランダムに選択し、記録部２９０に記録する（Ｓ２２０）。なお、集合Ｓ１ｕ，Ｓ２ｕが数値を元とする集合であり、サンプル値ｕ１，ｕ２はその集合の中の１つの数値でもよいし、集合Ｓ１ｕ，Ｓ２ｕが複数の数値の組み合わせを元とする集合であり、サンプル値ｕ１，ｕ２は複数の数値の組み合わせでもよい。乱数生成部２３０は、公開鍵ｐｋ１と平文ｘからあらかじめ定めた方法で一意に決まる内部乱数空間ＣＯＩＮ１の元の中から内部乱数ｒ１をランダムに選択し、公開鍵ｐｋ２と平文ｘからあらかじめ定めた方法で一意に決まる内部乱数空間ＣＯＩＮ２の元の中から内部乱数ｒ２をランダムに選択し、記録部２９０に記録する（Ｓ２３０）。なお、内部乱数空間ＣＯＩＮ１，ＣＯＩＮ２が数値を元とする空間であり、内部乱数ｒ１，ｒ２はその集合の中の１つの数値でもよいし、内部乱数空間ＣＯＩＮ１，ＣＯＩＮ２が複数の数値の組み合わせを元とする空間であり、内部乱数ｒ１，ｒ２は複数の数値の組み合わせでもよい。暗号化部２４０は、平文ｘを公開鍵ｐｋ１とタグｔとサンプル値ｕ１と内部乱数ｒ１を用いて暗号化して得た暗号文ｃ１と、平文ｘを公開鍵ｐｋ２とタグｔとサンプル値ｕ２と内部乱数ｒ２を用いて暗号化して得た暗号文ｃ２との組（ｃ１，ｃ２）を、コミットメントｃとし、記録部２９０に記録する（Ｓ２４０）。コミット送信部２５０は、コミットメントｃ＝（ｃ１，ｃ２）とタグｔとサンプル値ｕ１，ｕ２をコミット受信装置３００に送信する（Ｓ２５０）。コミット受信装置３００の公開情報取得部３１０は、公開鍵の組ｐｋ＝（ｐｋ１，ｐｋ２）を取得し、記録部３９０に記録する（Ｓ３１０）。なお、ステップＳ３１０は、後述の確認ステップ（Ｓ３４０）よりも前に行えばいつ実行してもよいので、デコミットフェーズで行ってもよい。コミット受信部３２０は、コミットメントｃ’＝（ｃ１’，ｃ２’）とタグｔ’とサンプル値ｕ１’，ｕ２’を受信し、記録部３９０に記録する（Ｓ３２０）。なお、図４に示した処理フローを前提にすれば、コミット受信装置３００が受信するのはコミット生成装置２００が送信した正しいコミットメントｃとタグｔとサンプル値ｕ１，ｕ２のはずである。しかし、コミット受信装置３００は受信したコミットメントが正しいことを確認するので、ここでは正しいか否かが分からないことを示すためにコミットメントｃ’とタグｔ’とサンプル値ｕ１’，ｕ２’のように記載している。
【００１８】
次にデコミットフェーズについて説明する。コミット生成装置２００のデコミット送信部２６０は、記録部２９０に記録された内部乱数ｒ１，ｒ２と平文ｘをコミット受信装置３００に送信する（Ｓ２６０）。コミット受信装置３００のデコミット受信部３３０は、内部乱数ｒ１’，ｒ２’と平文ｘ’を受信する（Ｓ３３０）。なお、図４に示した処理フローを前提にすれば、コミット受信装置３００が受信するのはコミット生成装置２００が送信した正しい内部乱数ｒ１，ｒ２と平文ｘのはずである。しかし、コミット受信装置３００は受信したコミットメントが正しいことを確認するので、ここでは正しいか否かが分からないことを示すために内部乱数ｒ１’，ｒ２’と平文ｘ’のように記載している。確認部３４０は、次のような確認を行う（Ｓ３４０）。
【００１９】
・サンプル値ｕ１’が集合Ｓ１ｕの元かを確認する。
【００２０】
・サンプル値ｕ２’が集合Ｓ２ｕの元かを確認する。
【００２１】
・内部乱数ｒ１’が公開鍵ｐｋ１と平文ｘ’からあらかじめ定めた方法で一意に決まる内部乱数空間ＣＯＩＮ１の元であるかを確認する。
【００２２】
・内部乱数ｒ２’が公開鍵ｐｋ２と平文ｘ’からあらかじめ定めた方法で一意に決まる内部乱数空間ＣＯＩＮ２の元であるかを確認する。
【００２３】
・平文ｘ’を公開鍵ｐｋ１とタグｔ’とサンプル値ｕ１’と内部乱数ｒ１’を用いて暗号化して得た暗号文ｃ１”が、ｃ１”＝ｃ１’であることを確認する。
【００２４】
・平文ｘ’を公開鍵ｐｋ２とタグｔ’とサンプル値ｕ２’と内部乱数ｒ２’を用いて暗号化して得た暗号文ｃ２”が、ｃ２”＝ｃ２’であることを確認する。
そして、コミット受信装置３００は、上記のすべての確認で正しいと判断された場合には開封などの処理を継続することを承認し、いずれかの確認で不正と判断された場合には処理を中断する。
【００２５】
＜理論的な裏づけ＞
本発明のコミットメントシステムは、以下に示すAll-but-many暗号（以下、「ＡＢＭ暗号」と呼ぶ）を作成した上で、ＡＢＭ暗号を利用することで実現している。ＡＢＭ暗号は、鍵生成アルゴリズム（ABM.gen）、サンプリングアルゴリズム（ABM.spl）、暗号化アルゴリズム（ABM.enc）、復号アルゴリズム（ABM.dec）、コリジョンアルゴリズム（ABM.col）からなる暗号方式である。
【００２６】
鍵生成アルゴリズム（ABM.gen）は、入力をセキュリティパラメータκ、出力を（公開鍵ｐｋ，秘密鍵ｓｋ）とする確率的アルゴリズムである。公開鍵ｐｋは、集合の組（Ｓ，Ｌ）の記述を含んでいる。なお、秘密鍵ｓｋは、記述の簡素化のために公開鍵ｐｋを含んでもよい。
【００２７】
サンプリングアルゴリズム（ABM.spl）は、入力を秘密鍵ｓｋとタグｔ、出力をサンプル値ｕとする確率的アルゴリズムである。ただし、サンプリングアルゴリズムではサンプル値ｕは集合Ｌｕの元であり、組（ｔ，ｕ）は集合Ｌの元である。また、サンプリングアルゴリズムの内部乱数空間ＣＯＩＮｓｐｌは公開鍵ｐｋから一意に定まるものとし、サンプリングアルゴリズムでサンプル値ｕを求めるときに使用する内部乱数ｒｓｐｌは内部乱数空間ＣＯＩＮｓｐｌからランダムに選択された元である。
【００２８】
暗号化アルゴリズム（ABM.enc）は、入力を公開鍵ｐｋとタグｔとサンプル値ｕと平文ｘ、出力を暗号文ｃとする確率的アルゴリズムである。暗号化アルゴリズムではサンプル値ｕは集合Ｓｕの元であり、組（ｔ，ｕ）は集合Ｓの元である。また、暗号化アルゴリズムの内部乱数空間ＣＯＩＮは公開鍵ｐｋと平文ｘから一意に定まるものとし、暗号化アルゴリズムで暗号文ｃを求めるときに使用する内部乱数ｒは内部乱数空間ＣＯＩＮからランダムに選択された元である。
【００２９】
復号アルゴリズム（ABM.dec）は、入力を秘密鍵ｓｋとタグｔとサンプル値ｕと暗号文ｃ、出力を平文ｘとする確定的アルゴリズムである。復号アルゴリズムではサンプル値ｕは集合Ｓｕの元であり、組（ｔ，ｕ）は集合Ｓの元である。
【００３０】
コリジョンアルゴリズム（ABM.col）は、２つの確率的アルゴリズムで構成される。第１のアルゴリズム（ABM.col1）は、入力を秘密鍵ｓｋと乱数ｒ’とタグｔ、出力を暗号文ｃと数値ξとする。ここで、乱数ｒ’は内部乱数空間ＣＯＩＮｓｐｌの元である。第２のアルゴリズム（ABM.col2）は、入力を数値ξと平文ｘ、出力を乱数ｒとする。ただし、乱数ｒは以下の条件を満たす。
【００３１】
・乱数ｒは内部乱数空間ＣＯＩＮである。
【００３２】
・秘密鍵ｓｋとタグｔと乱数ｒ’を用いてサンプリングアルゴリズムで出力される値がサンプル値ｕと同一である。
【００３３】
・公開鍵ｐｋと乱数ｒとタグｔとサンプル値ｕとを用いて平文ｘを暗号化アルゴリズムで暗号化した結果が暗号文ｃと同一である。
【００３４】
非対話、ＣＲＳ再利用、情報廃棄不要汎用結合コミットメントを提供するためには、all-but-many property, dual mode, pseudo-randomness, unpredictabilityの４つの安全性条件を満たすことが必要である。図６にＡＢＭ暗号の構成をより厳密に示し、図７に上記の４つの安全性条件を具体的に示す。また、図８−１１に、ＡＢＭ暗号が上記の４つの安全性条件を満たすことの証明を示す。なお、使用されている英語の用語には当業者間で共有された定義が存在するが、同じ定義がなされた日本語が存在しない用語がある。このような事情から、当業者にとっては英語表記の方が分かりやすくかつ正確なので、図６−１１は英語で表記している。
【００３５】
本発明のコミットメントシステムは、上記の４つの安全性条件を満たすＡＢＭ暗号の鍵生成アルゴリズム（ABM.gen）と暗号化アルゴリズム（ABM.enc）を用いている。したがって、非対話、ＣＲＳ再利用、情報廃棄不要汎用結合コミットメントを提供できる。なお、サンプリングアルゴリズム（ABM.spl）、復号アルゴリズム（ABM.dec）、コリジョンアルゴリズム（ABM.col）は、実際のコミットメントシステムには使用しないが、実際のコミットメントシステムが４つの安全性条件を満たすことの証明に必要なアルゴリズムである。
【実施例２】
【００３６】
＜具体的なシステム＞
実施例２のコミットメントシステムは、実施例１のコミットメントシステムをより具体化した１つの実施例である。コミットメントシステムの構成は図１、共通参照情報生成装置の機能構成は図２、コミット生成装置の機能構成は図３、コミット受信装置の機能構成は図４と同じである。実施例２では、ｑ１，ｑ２を素数、ｇ１を位数ｑ１の群Ｇ１の生成元、ｇ２を位数ｑ２の群Ｇ２の生成元、ｘ１１，ｘ１２，ｙ１０，ｙ１１，…，ｙ１κを０以上ｑ１−１以下の整数、ｘ２１，ｘ２２，ｙ２０，ｙ２１，…，ｙ２κを０以上ｑ２−１以下の整数、ｉを１または２、ｊを１以上κ以下の整数、ｍを１または２、＾をべき乗を示す記号、ｔｎをｔのｎビット目、λをＯ（ｌｏｇκ）の秘密情報長（言い換えると、平文ｘはλビットで表現できる）、集合Ｓ１ｕを群Ｇ１の２つの元の組み合わせの集合、集合Ｓ２ｕを群Ｇ２の２つの元の組み合わせの集合、Ｈｍ（ｔ）を
【００３７】
【数１】
0005755600.tif 000002
【００３８】
とする。
実施例２では、ステップＳ１１０では、鍵生成部１１０が、ｇ１，ｘ１１，ｘ１２，ｙ１０，ｙ１１，…，ｙ１κをランダムに選び、ｇ１１，ｇ１２，ｈ１０，ｈ１１，…，ｈ１κをｇ１ｉ＝ｇ１＾ｘ１ｉ、ｈ１ｊ＝ｇ１＾ｙ１ｊのように計算する。そして、ｐｋ１＝（Ｇ１，ｇ１，ｑ１，λ，（Ｓ１，Ｌ１），ｇ１１，ｇ１２，ｈ１０，ｈ１１，…，ｈ１κ）とｓｋ１＝（ｐｋ１，ｘ１２，ｙ１０，ｙ１１，…，ｙ１κ）のように（ｐｋ１，ｓｋ１）を生成する。さらに、鍵生成部１１０が、ｇ２，ｘ２１，ｘ２２，ｙ２０，ｙ２１，…，ｙ２κをランダムに選び、ｇ２１，ｇ２２，ｈ２０，ｈ２１，…，ｈ２κをｇ２ｉ＝ｇ２＾ｘ２ｉ、ｈ２ｊ＝ｇ２＾ｙ２ｊのように計算する。そして、ｐｋ２＝（Ｇ２，ｇ２，ｑ２，λ，（Ｓ２，Ｌ２），ｇ２１，ｇ２２，ｈ２０，ｈ２１，…，ｈ２κ）とｓｋ２＝（ｐｋ２，ｘ２２，ｙ２０，ｙ２１，…，ｙ２κ）のように（ｐｋ２，ｓｋ２）を生成する。
【００３９】
ステップＳ２２０では、サンプル値選択部２２０が、群Ｇ１の中の２つの元の組（ｕ１ｒ，ｕ１ｔ）をランダムに選定し、サンプル値ｕ１＝（ｕ１ｒ，ｕ１ｔ）とし、群Ｇ２の中の２つの元の組（ｕ２ｒ，ｕ２ｔ）をランダムに選定し、サンプル値ｕ２＝（ｕ２ｒ，ｕ２ｔ）とする。ステップＳ２３０では、乱数生成部２３０が、内部乱数ｒ１として、０以上ｑ−１以下の整数である乱数ｚ１と乱数ｓ１を生成し、内部乱数ｒ２として、０以上ｑ−１以下の整数である乱数ｚ２と乱数ｓ２を生成する。ステップＳ２４０では、暗号化部２４０が、
Ａ１＝（ｇ１１＾ｚ１）（Ｈ１（ｔ）＾ｓ１）（ｕ１ｔ＾ｘ１）
ａ１＝（ｇ１＾ｚ１）（ｇ１２＾ｘ１）
ｂ１＝（ｇ１＾ｓ１）（ｕ１ｒ＾ｘ１）
を計算してｃ１＝（Ａ１，ａ１，ｂ１）とし、
Ａ２＝（ｇ２１＾ｚ１）（Ｈ２（ｔ）＾ｓ２）（ｕ２ｔ＾ｘ２）
ａ２＝（ｇ２＾ｚ２）（ｇ２２＾ｘ２）
ｂ２＝（ｇ２＾ｓ２）（ｕ２ｒ＾ｘ２）
を計算してｃ２＝（Ａ２，ａ２，ｂ２）として、（ｃ１，ｃ２）をコミットメントｃとする。
【００４０】
実施例２のコミットメントシステムは、実施例１のコミットメントシステムの下位概念に相当するので、実施例１で説明した４つの安全性条件を満たす。したがって、実施例２のコミットメントシステムも実施例１のコミットメントシステムと同じ効果が得られる。
【００４１】
＜理論的な裏づけ＞
実施例２のコミットメントシステムが使用しているＡＢＭ暗号は、実施例１で示したＡＢＭ暗号をより具体的にしたものである。以下に、実施例２の場合の鍵生成アルゴリズム（ABM.gen）、サンプリングアルゴリズム（ABM.spl）、暗号化アルゴリズム（ABM.enc）、復号アルゴリズム（ABM.dec）、コリジョンアルゴリズム（ABM.col）を示す。
【００４２】
鍵生成アルゴリズム（ABM.gen）では、ｇ，ｘ１，ｘ２，ｙ０，ｙ１，…，ｙκをランダムに選び、ｇ１，ｇ２，ｈ０，ｈ１，…，ｈκをｇｉ＝ｇ＾ｘｉ、ｈｊ＝ｇ＾ｙｊのように計算する。そして、ｐｋ＝（Ｇ，ｇ，ｑ，λ，（Ｓ，Ｌ），ｇ１，ｇ２，ｈ０，ｈ１，…，ｈκ）とｓｋ＝（ｐｋ，ｘ２，ｙ０，ｙ１，…，ｙκ）のように（ｐｋ，ｓｋ）を生成する。
【００４３】
サンプリングアルゴリズム（ABM.spl）では、内部乱数空間ＣＯＩＮｓｐｌを０以上ｑ−１以下の整数とする。そして、内部乱数ｒｓｐｌを０以上ｑ−１以下の整数の中からランダムに選ぶ。そして、ｕｒ＝ｇ＾ｒｓｐｌとｕｔ＝（ｇ１＾ｘ２）（Ｈ（ｔ）＾ｒｓｐｌ）を計算し、（ｕｒ，ｕｔ）をサンプル値ｕとする。なお、実施例２のサンプリングアルゴリズムでは、集合Ｓｕは群Ｇの２つの元の組み合わせの集合である。そして、集合Ｌｕは、０以上ｑ−１以下の整数をｒｓｐｌとしたときに、ｕｒ＝ｇ＾ｒｓｐｌとｕｔ＝（ｇ１＾ｘ２）（Ｈ（ｔ）＾ｒｓｐｌ）のように求められる値（ｕｒ，ｕｔ）を元とする集合（集合Ｓｕの部分集合）である。
【００４４】
暗号化アルゴリズム（ABM.enc）では、内部乱数空間ＣＯＩＮを２つの０以上ｑ−１以下の整数の組み合わせを元とする空間とする。そして、内部乱数ｒとして、０以上ｑ−１以下の整数である乱数ｚと乱数ｓを生成する。そして、
Ａ＝（ｇ１＾ｚ）（Ｈ（ｔ）＾ｓ）（ｕｔ＾ｘ）
ａ＝ｇｚｇ２ｘ
ｂ＝ｇｓｕｒｘ
を計算し、を暗号文ｃ＝（Ａ，ａ，ｂ）を出力する。
【００４５】
復号アルゴリズム（ABM.dec）では、
【００４６】
【数２】
0005755600.tif 000003
【００４７】
ただし、
【００４８】
【数３】
0005755600.tif 000004
【００４９】
となるλビットの平文ｘを探索し出力する。
【００５０】
コリジョンアルゴリズム（ABM.col）の第１のアルゴリズム（ABM.col1）では、乱数ω，ηを０以上ｑ−１以下の整数からランダムに選定し、
Ａ＝（ｇ１＾ω）（Ｈ（ｔ）＾η）
ａ＝ｇω
ｂ＝ｇη
を計算し、をｃ＝（Ａ，ａ，ｂ）とξ＝（ｘ，ｒ’，ω，η）を出力する。第２のアルゴリズム（ABM.col2）では、
ｚ＝ω−ｘｘ２  ｍｏｄｑ
ｓ＝η−ｘｒ’  ｍｏｄｑ
を計算し、（ｚ，ｓ）を出力する。
【００５１】
上述のように、実施例２で使用しているＡＢＭ暗号は、実施例１で説明したＡＢＭ暗号の下位概念（具体例）に相当しているので、図７に示した４つの安全性条件を満たす。
【実施例３】
【００５２】
＜具体的なシステム＞
実施例３のコミットメントシステムも、実施例１のコミットメントシステムをより具体化した１つの実施例である。コミットメントシステムの構成は図１、共通参照情報生成装置の機能構成は図２、コミット生成装置の機能構成は図３、コミット受信装置の機能構成は図４と同じである。実施例３では、Ｐ１，Ｑ１，Ｐ２，Ｑ２を整数、Ｎ１＝Ｐ１Ｑ１、Ｎ２＝Ｐ２Ｑ２、ｖ１，ｖ２を正の整数、ｉを１または２、ｊを１以上κ以下の整数、ｍを１または２、＾をべき乗を示す記号、ｘ１ｉとｙ１ｊを０以上Ｎ１＾ｖ１−１以下の整数、ｘ２ｉとｙ２ｊを０以上Ｎ２＾ｖ２−１以下の整数、Ｓｕ１を０以上Ｎ１＾（ｖ１＋１）−１以下の整数の中の２つの整数の組み合わせの集合、Ｓ２ｕを０以上Ｎ２＾（ｖ２＋１）−１以下の整数の中の２つの整数の組み合わせの集合、ｇ１＝１＋Ｎ１、ｇ２＝１＋Ｎ２、平文ｘを０以上Ｎ１＾ｖ１−１以下の整数かつ０以上Ｎ２＾ｖ２−１以下の整数、Ｈｍ（ｔ）を
【００５３】
【数４】
0005755600.tif 000005
【００５４】
とする。
実施例３では、ステップＳ１１０では、鍵生成部１１０が、ｘ１１，ｘ１２，ｙ１０，ｙ１１，…，ｙ１κをランダムに選び、０以上Ｎ１＾（ｖ１＋１）−１の整数である乱数Ｒ１１，Ｒ１２を生成する。そして、ｇ１１，ｇ１２，ｈ１０，ｈ１１，…，ｈ１κを
ｇ１ｉ＝（ｇ１＾ｘ１ｉ）Ｒ１ｉ＾Ｎ１＾ｖ１  ｍｏｄＮ１＾（ｖ１＋１）
ｈ１ｊ＝ｇ１＾ｙ１ｊ  ｍｏｄＮ１＾（ｖ１＋１）
のように計算し、ｐｋ１＝（Ｎ１，ｖ１，（Ｓ１，Ｌ１），ｇ１１，ｇ１２，ｈ１０，ｈ１１，…，ｈ１κ）とｓｋ１＝（ｘ１２，ｙ１０，ｙ１１，…，ｙ１κ）のように（ｐｋ１，ｓｋ１）を生成する。さらに、鍵生成部１１０が、ｘ２１，ｘ２２，ｙ２０，ｙ２１，…，ｙ２κをランダムに選び、０以上Ｎ２＾（ｖ２＋１）−１の整数である乱数Ｒ２１，Ｒ２２を生成する。そして、ｇ２１，ｇ２２，ｈ２０，ｈ２１，…，ｈ２κを
ｇ２ｉ＝（ｇ２＾ｘ２ｉ）Ｒ２ｉ＾Ｎ２＾ｖ２  ｍｏｄＮ２＾（ｖ２＋１）
ｈ２ｊ＝ｇ２＾ｙ２ｊ  ｍｏｄＮ２＾（ｖ２＋１）
のように計算し、ｐｋ２＝（Ｎ２，ｖ２，（Ｓ２，Ｌ２），ｇ２１，ｇ２２，ｈ２０，ｈ２１，…，ｈ２κ）とｓｋ２＝（ｘ２２，ｙ２０，ｙ２１，…，ｙ２κ）のように（ｐｋ２，ｓｋ２）を生成する。
【００５５】
ステップＳ２２０では、サンプル値選択部２２０が、０以上Ｎ１＾（ｖ１＋１）−１以下の整数の中の２つの整数の組み合わせ（ｕ１ｒ，ｕ１ｔ）をランダムに選定してサンプル値ｕ１＝（ｕ１ｒ，ｕ１ｔ）とする。また、サンプル値選択部２２０が、０以上Ｎ２＾（ｖ２＋１）−１以下の整数の中の２つの整数の組み合わせ（ｕ２ｒ，ｕ２ｔ）をランダムに選定してサンプル値ｕ２＝（ｕ２ｒ，ｕ２ｔ）とする。ステップＳ２３０では、乱数生成部２３０が、内部乱数ｒ１として、０以上Ｎ１＾ｖ１−１以下の整数である乱数ｚ１と乱数ｓ１を生成し、０以上Ｎ１＾（ｖ１＋１）−１以下の整数である乱数Ｒ１Ａ，Ｒ１ａ，Ｒ１ｂを生成する。さらに、乱数生成部２３０が、内部乱数ｒ２として、０以上Ｎ２＾ｖ２−１以下の整数である乱数ｚ２と乱数ｓ２を生成し、０以上Ｎ２＾（ｖ２＋１）−１以下の整数である乱数Ｒ２Ａ，Ｒ２ａ，Ｒ２ｂを生成する。ステップＳ２４０では、暗号化部２４０が、
Ａ１＝（ｇ１１＾ｚ１）（Ｈ１（ｔ）＾ｓ１）（ｕ１ｔ＾ｘ１）（Ｒ１Ａ＾Ｎ１＾ｖ１）
ｍｏｄＮ１＾（ｖ１＋１）
ａ１＝（（ｇ１＾ｚ１）（Ｒ１ａ＾Ｎ１＾ｖ１）  ｍｏｄＮ１＾（ｖ１＋１））（ｇ１２＾ｘ１）
ｂ１＝（（ｇ１＾ｓ１）（Ｒ１ｂ＾Ｎ１＾ｖ１）  ｍｏｄＮ１＾（ｖ１＋１））（ｕ１ｒ＾ｘ１）
を計算してｃ１＝（Ａ１，ａ１，ｂ１）とし、
Ａ２＝（ｇ２１＾ｚ２）（Ｈ２（ｔ）＾ｓ２）（ｕ２ｔ＾ｘ２）（Ｒ２Ａ＾Ｎ２＾ｖ２）
ｍｏｄＮ２＾（ｖ２＋１）
ａ２＝（（ｇ２＾ｚ２）（Ｒ２ａ＾Ｎ２＾ｖ２）  ｍｏｄＮ２＾（ｖ２＋１））（ｇ２２＾ｘ２）
ｂ２＝（（ｇ２＾ｓ２）（Ｒ２ｂ＾Ｎ２＾ｖ２）  ｍｏｄＮ２＾（ｖ２＋１））（ｕ２ｒ＾ｘ２）
を計算してｃ２＝（Ａ２，ａ２，ｂ２）として、（ｃ１，ｃ２）をコミットメントｃとする。
【００５６】
実施例３のコミットメントシステムは、実施例１のコミットメントシステムの下位概念に相当するので、実施例１で説明した４つの安全性条件を満たす。したがって、実施例３のコミットメントシステムも実施例１のコミットメントシステムと同じ効果が得られる。
【００５７】
＜理論的な裏づけ＞
実施例３のコミットメントシステムが使用しているＡＢＭ暗号は、実施例２の方式とは別の方式でＡＢＭ暗号を具体的にしたものである。以下に、実施例３の場合の鍵生成アルゴリズム（ABM.gen）、サンプリングアルゴリズム（ABM.spl）、暗号化アルゴリズム（ABM.enc）、復号アルゴリズム（ABM.dec）、コリジョンアルゴリズム（ABM.col）を示す。ここで、Π＝（Ｋ，Ｅ，Ｄ）は参考文献１（I. Damgard and M. Jurik,“A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system”, In Kwangjo Kim, editor, PKC 2001, volume 1992 of Lecture Notes in Computer Science, pages 125-140. Springer-Verlag, 2001.）に示された公開鍵暗号アルゴリズム（以下、ＤＪ暗号と呼ぶ）の鍵生成、暗号化、復号アルゴリズムとする。（Ｎ，ｖ）はＤＪ暗号の公開鍵に対応し、（Ｐ，Ｑ）はＤＪ暗号の秘密鍵に対応する。なお、
Ｅ（ｘ；Ｒ）＝（ｇ＾ｘ）Ｒ＾Ｎｖ  ｍｏｄＮｖ＋１
Ｅ（ｙ）＝（ｇ＾ｙ）  ｍｏｄＮｖ＋１
である。
【００５８】
鍵生成アルゴリズム（ABM.gen）では、ｘ１，ｘ２，ｙ０，ｙ１，…，ｙκをランダムに選び、０以上Ｎｖ＋１−１の整数である乱数Ｒ１，Ｒ２を生成する。そして、ｇ１，ｇ２，ｈ０，ｈ１，…，ｈκを
ｇｉ＝Ｅ（ｘｉ；Ｒｉ）＝（ｇ＾ｘｉ）Ｒｉ＾Ｎｖ  ｍｏｄＮｖ＋１
ｈｊ＝Ｅ（ｙｊ）＝ｇ＾ｙｊ  ｍｏｄＮｖ＋１
のように計算し、集合の組（Ｓ，Ｌ）を決定する。そして、ｐｋ＝（Ｎ，ｖ，（Ｓ，Ｌ），ｇ１，ｇ２，ｈ０，ｈ１，…，ｈκ）とｓｋ＝（ｘ２，ｙ０，ｙ１，…，ｙκ）のように（ｐｋ，ｓｋ）を生成する。
【００５９】
サンプリングアルゴリズム（ABM.spl）では、内部乱数空間ＣＯＩＮｓｐｌを０以上Ｎｓ−１以下の整数とする。そして、内部乱数ｒｓｐｌを０以上Ｎｓ−１以下の整数の中からランダムに選ぶ。そして、０以上Ｎｖ＋１−１以下の整数である乱数Ｒｒ，Ｒｔを生成し、
ｕｒ＝（ｇ＾ｒｓｐｌ）Ｒｒ＾Ｎｖ  ｍｏｄＮｖ＋１
ｕｔ＝（（ｇ＾ｘ１ｘ２）Ｒｔ＾Ｎｖ  ｍｏｄＮｖ＋１）（Ｈ（ｔ）＾ｒｓｐｌ）
を計算し、（ｕｒ，ｕｔ）をサンプル値ｕとする。なお、実施例３のサンプリングアルゴリズムでは、集合Ｓｕは２つの０以上Ｎｖ＋１−１以下の整数の組み合わせの集合である。そして、集合Ｌｕは、０以上Ｎｓ−１以下の整数をｒｓｐｌ、０以上Ｎｖ＋１−１以下の整数をＲｒ，Ｒｔをとしたときに、
ｕｒ＝（ｇ＾ｒｓｐｌ）Ｒｒ＾Ｎｖ  ｍｏｄＮｖ＋１
ｕｔ＝（（ｇ＾ｘ１ｘ２）Ｒｔ＾Ｎｖ  ｍｏｄＮｖ＋１）（Ｈ（ｔ）＾ｒｓｐｌ）
のように求められる値（ｕｒ，ｕｔ）を元とする集合（集合Ｓｕの部分集合）である。
【００６０】
暗号化アルゴリズム（ABM.enc）では、平文ｘが０以上Ｎｖ−１以下の整数の場合に、内部乱数空間ＣＯＩＮを２つの０以上Ｎｖ−１以下の整数の組み合わせを元とする空間とする。そして、内部乱数ｒとして、０以上Ｎｖ−１以下の整数である乱数ｚと乱数ｓを生成する。また、０以上Ｎｖ＋１−１以下の整数である乱数ＲＡ，Ｒａ，Ｒｂを生成する。そして、
Ａ＝（ｇ１＾ｚ）（Ｈ（ｔ）＾ｓ）（ｕｔ＾ｘ）（ＲＡ＾Ｎｖ）  ｍｏｄＮｖ＋１
ａ＝（（ｇ＾ｚ）（Ｒａ＾Ｎｖ）  ｍｏｄＮｖ＋１）（ｇ２＾ｘ）
ｂ＝（（ｇ＾ｓ）（Ｒｂ＾Ｎｖ）  ｍｏｄＮｖ＋１）（ｕｒ＾ｘ）
を計算し、を暗号文ｃ＝（Ａ，ａ，ｂ）を出力する。
【００６１】
復号アルゴリズム（ABM.dec）では、ＤＪ暗号の復号アルゴリズムＤを用いて
ω＝Ｄ（ａ）
η＝Ｄ（ｂ）
ω’＝Ｄ（Ａ・（Ｈ（ｔ）＾（−η）））
ｘ２’＝Ｄ（ｕｔ・（Ｈ（ｔ）＾（−ｒ）））
を計算し、平文ｘを
ｘ＝（ω−ω’）（ｘ２−ｘ２’）−１  ｍｏｄＮｖ
のように計算し、出力する。
【００６２】
コリジョンアルゴリズム（ABM.col）の第１のアルゴリズム（ABM.col1）では、乱数ω，ηを０以上Ｎｖ−１以下の整数からランダムに選定し、乱数ＲＡ’，Ｒａ’，Ｒｂ’を０以上Ｎｖ＋１−１以下の整数からランダムに選定する。そして、
Ａ＝（ｇ１＾ω）（Ｈ（ｔ）＾η）（ＲＡ’＾Ｎｖ）  ｍｏｄＮｖ＋１
ａ＝（ｇ＾ω）（Ｒａ’＾Ｎｖ）  ｍｏｄＮｖ＋１
ｂ＝（ｇ＾η）（Ｒｂ’＾Ｎｖ）  ｍｏｄＮｖ＋１
を計算し、をｃ＝（Ａ，ａ，ｂ）とξ＝（ｘ２，ｒ’，ω，η）を出力する。第２のアルゴリズム（ABM.col2）では、ｚ，ｓ，α，βを
ｚ＝ω−ｘｘ２  ｍｏｄＮｖ
ｓ＝η−ｘｒ  ｍｏｄＮｖ
αを（ω−ｘｘ２−ｚ）／Ｎｖを超えない最大の整数
βを（η−ｘｒ’−ｓ）／Ｎｖを超えない最大の整数
のように求める。さらに、ＲＡ，Ｒａ，Ｒｂを
ＲＡ＝ＲＡ’（Ｒｔ＾（−ｘ））（ｇ１＾α）（Ｈ（ｔ）＾β）
Ｒａ＝Ｒａ’（Ｒ２＾（−ｘ））（ｇ＾α）
ＲＡ＝Ｒｂ’（Ｒｒ＾（−ｘ））（ｇ＾β）
のように求め、（ｚ，ｓ，ＲＡ，Ｒａ，Ｒｂ）を出力する。なお、このとき、
Ａ＝（ｇ１＾ｚ）（Ｈ（ｔ）＾ｓ）（ｕｔ＾ｘ）（ＲＡ＾Ｎｖ）  ｍｏｄＮｖ＋１
ａ＝Ｅ（ｚ；Ｒａ）（ｇ２＾ｘ）＝（（ｇ＾ｚ）（Ｒａ＾Ｎｖ）  ｍｏｄＮｖ＋１）（ｇ２＾ｘ）
ｂ＝Ｅ（ｓ；Ｒｂ）（ｕｒ＾ｘ）＝（（ｇ＾ｓ）（Ｒｂ＾Ｎｖ）  ｍｏｄＮｖ＋１）（ｕｒ＾ｘ）
が常に成り立っている。
【００６３】
上述のように、実施例３で使用しているＡＢＭ暗号は、実施例１で説明したＡＢＭ暗号の下位概念（具体例）に相当しているので、図７に示した４つの安全性条件を満たす。
【００６４】
＜実施例２，３と従来方式との比較＞
図１２に、実施例２，３の方式と従来技術の比較を示す。また、図１３に実施例２の方式と従来技術との効率に関する比較を示す。図１２，１３において、κはセキュリティパラメータを表し、ａ／ｂはコミットフェーズに必要とされる交信数ａとデコミットフェーズに必要とされる交信数ｂを表す。また、比率は、１ビットの秘密情報をコミットするために必要なコミットメントのサイズであり、理想はＯ（１）である。図１２から分かるように、実施例３のコミットメントシステムの場合は、ｋビットの秘密（ｋビットの平文ｘ）をＯ（ｋ）ビットでコミットできるので、理想的な効率も実現できている。
【００６５】
実施例２の方式は、同様のＣＲＳ再利用型で交信回数１／１である非特許文献７，８の方式に劣っているように見える。しかし、現実のセキュリティパラメータのもとでは、実は効率が良い（図１３参照）。さらに、実施例２の方式は、情報廃棄不要型であるが、非特許文献７，８の方式は適切な途中情報の廃棄が無いと、安全にならない。
【００６６】
図１３では、Texp(k) はｋビットのべき乗剰余演算１回のコストを表す。Ｇはペアリングを持たないアーベル群、Ｇ＾は対象ペアリングを持つアーベル群、ＧＴは対象ペアリングの有限体に埋め込まれた像とする。すなわち、ｅ（  ，  ）：Ｇ＾ ×Ｇ＾ →ＧＴで定義されるペアリングの像であるアーベル群での拡大次数は、高々６（｜ＧＴ｜≦６｜Ｇ＾｜）とする。λは、コミットされる秘密情報のサイズであり、ρ＝λ・λ０−１とする。このρが小さいほど、実施例２の効率は良くなるが、λ０＝Ｏ（ｌｏｇκ）である。本発明の汎用結合コミットメントでは、このλ０は、小さなべきの離散対数問題を解くベイビーステップ・ジャイアントステップ法の効率に依存する。べきのサイズをλ０としたとき、ベイビーステップ・ジャイアントステップ法で離散対数問題を解く時間はΩ（√（２＾λ０））である（参考文献２（Alfred Menezes, Paul Oorschot, and Scott Vanstone,“Handbook of Applied Cryptography”, CRC Press, 1997.）参照）。汎用結合コミットメントに利用される場合、この離散対数問題の解読は、証明の中でのみ使われる。そのため、効率良く解けなくてもよい。現在の計算機の能力からすると、√（２＾λ０）＝２４０は、パソコンで数時間で計算可能な計算量であるので、λ０＝８０としてよい。一方、８０ビット安全性を確保するには、κ＝１６０，λ＝１６０，｜Ｇ｜＝１６０，（｜ＧＴ｜がおよそ１０００となる必要があるので）｜Ｇ＾｜＝１７０が必要である。また、１６０ビット安全性を確保するには、κ＝３２０，λ＝３２０，｜Ｇ｜＝３２０，（｜ＧＴ｜がおよそ３０００となる必要があるので）｜Ｇ＾｜＝５１２が必要である。この条件のもとでは実施例２の通信量は、非特許文献７，８の通信量より少ない。また、計算量も非特許文献８よりはるかに少なく、非特許文献７と比べてもほぼ同等である。
【００６７】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００６８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００６９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００７３】
本発明は、情報を交換するシステムにおいて、情報のセキュリティを確保する技術として利用できる。
【符号の説明】
【００７４】
１００  共通参照情報生成装置            １１０  鍵生成部
１２０  秘密鍵廃棄部                    １３０  公開部
１９０、２９０、３９０  記録部          ２００  コミット生成装置
２１０  入力情報取得部                  ２２０  サンプル値選択部
２３０  乱数生成部                      ２４０  暗号化部
２５０  コミット送信部                  ２６０  デコミット送信部
３００  コミット受信装置                ３１０  公開情報取得部
３２０  コミット受信部                  ３３０  デコミット受信部
３４０  確認部                          １０００  ネットワーク
【図１】
0005755600.tif 000008
【図２】
0005755600.tif 000009
【図３】
0005755600.tif 000010
【図４】
0005755600.tif 000011
【図５】
0005755600.tif 000012
【図１２】
0005755600.tif 000013
【図１３】
0005755600.tif 000014
【図６】
0005755600.tif 000015
【図７】
0005755600.tif 000016
【図８】
0005755600.tif 000017
【図９】
0005755600.tif 000018
【図１０】
0005755600.tif 000019
【図１１】
0005755600.tif 000020