(57)【特許請求の範囲】
【請求項１】
送信装置、受信装置、マスター装置で構成されるコミットメントシステムであって、
前記マスター装置は、
λはセキュリティパラメータ、ｆは１λに依存する整数、ｐ、ｑは互いに異なるλビットの奇素数、Ｆは任意ビットのビット列をｆビットのビット列に変換する擬似ランダム関数とし、
２ｆ＜φ（Ｎ）＝（ｐ−１）（ｑ−１）＜２ｆ＋２であるＲＳＡモジュラスＮ＝ｐｑを出力するＲＳＡモジュラス部と、
１以上Ｎ−１以下の任意の整数ｈと、擬似ランダム関数Ｆの鍵Ｋと、ｆビットのビット列ｃとをランダムに選ぶマスター選定部と、
関数ＰＫ，ｃを、
【数１４】
0005448864.tif 000015
のように定義する関数定義部と、
（Ｎ，ｈ，ｃ，Ｋ）をマスター公開鍵ＰＫとし、（ｐ，ｑ，ＰＫ）をマスタートラップドアＴＫとするマスター鍵生成部と、
マスター公開鍵ＰＫとＪビットのビット列を出力するハッシュ関数Ｈを含む共通参照情報ｃｒｓを生成し、前記送信装置と前記受信装置に送信する共通参照情報生成部
を備え、
前記送信装置は、
前記共通参照情報ｃｒｓと文書ｍとを受け取る送信入力部と、
乱数ｒを生成する乱数生成部と、
ワンタイム署名の署名検証鍵ｖｋ０と署名生成鍵ｓｋ０とを生成するワンタイム署名鍵生成部と、
Ｈ（ｖｋ０）を個別公開鍵ｐｋとし、
ｅｊ＝ＰＫ，ｃ（ｐｋ（ｊ））、ただしｐｋ（ｊ）はｐｋの先頭のｊビット
をｊ＝１からｊ＝Ｊまで計算し、ｅｍｉｎをｅ１，…，ｅＪのうちで最小の値とし、
ｍｊ＝ｍ  ｍｏｄ  ｅｊ
をｊ＝１からｊ＝Ｊまで計算し、
Ｍ  ｍｏｄ  ｅｊ＝ｍｊ
がすべてのｊに対して成り立つＭを０以上
【数１５】
0005448864.tif 000016
以下の整数の中から求め、
０以上ｅｍｉｎ−１以下の整数である文書ｍをコミットするために、コミットメント要素Ｃ、デコミットメント要素Ｄを、
【数１６】
0005448864.tif 000017
のように求めるコミットメント要素生成部と、
コミットメント要素Ｃに対するワンタイム署名σ０を、署名生成鍵ｓｋ０を用いて生成するワンタイム署名生成部と、
コミットメント要素Ｃと署名検証鍵ｖｋ０を含むコミットメントｃｏｍを、前記受信装置に送信するコミットメント送信部と、
デコミットメント要素Ｄと文書ｍとワンタイム署名σ０を含むデコミットメントｄｅｃを、前記受信装置に送信するデコミットメント送信部と、
を備え、
前記受信装置は、
前記共通参照情報ｃｒｓと、コミットメント要素Ｃ’と署名検証鍵ｖｋ０’を含むコミットメントｃｏｍと、デコミットメント要素Ｄ’＝（Ｍ’，ｒ’）と文書ｍ’とワンタイム署名σ０’を含むデコミットメントｄｅｃとを受け取る受信入力部と、
署名検証鍵ｖｋ０’を用いて、コミットメント要素Ｃ’に対するワンタイム署名σ０’の正当性を検証するワンタイム署名検証部と、
Ｈ（ｖｋ０’）を個別公開鍵ｐｋ’とし、
ｅｊ’＝ＰＫ，ｃ（ｐｋ’（ｊ））、ただしｐｋ’（ｊ）はｐｋ’の先頭のｊビット
および、
ｍｊ’＝Ｍ’  ｍｏｄ  ｅｊ’
をｊ＝１からｊ＝Ｊまで計算し、
ｍ１’＝ｍ２’＝，…，＝ｍＪ’
かつ
【数１７】
0005448864.tif 000018
であることを検証するコミットメント検証部と、
を備える
ことを特徴とするコミットメントシステム。
【請求項２】
λはセキュリティパラメータ、ｆは１λに依存する整数、ｐ、ｑは互いに異なるλビットの奇素数、Ｆは任意ビットのビット列をｆビットのビット列に変換する擬似ランダム関数とし、
２ｆ＜φ（Ｎ）＝（ｐ−１）（ｑ−１）＜２ｆ＋２であるＲＳＡモジュラスＮ＝ｐｑを出力するＲＳＡモジュラス部と、
１以上Ｎ−１以下の任意の整数ｈと、擬似ランダム関数Ｆの鍵Ｋと、ｆビットのビット列ｃとをランダムに選ぶマスター選定部と、
関数ＰＫ，ｃを、
【数２１】
0005448864.tif 000019
のように定義する関数定義部と、
（Ｎ，ｈ，ｃ，Ｋ）をマスター公開鍵ＰＫとし、（ｐ，ｑ，ＰＫ）をマスタートラップドアＴＫとするマスター鍵生成部と、
マスター公開鍵ＰＫとＪビットのビット列を出力するハッシュ関数Ｈを含む共通参照情報ｃｒｓを生成する共通参照情報生成部
を備えるマスター装置。
【請求項３】
λはセキュリティパラメータ、ｆは１λに依存する整数、ｐ、ｑは互いに異なるλビットの奇素数、Ｆは任意ビットのビット列をｆビットのビット列に変換する擬似ランダム関数、ＰＫ，ｃを、
【数２２】
0005448864.tif 000020
のように定義される関数、ＮはＮ＝ｐｑ、ｈは１以上Ｎ−１以下の任意の整数、Ｋは擬似ランダム関数Ｆの鍵、ｃはｆビットのビット列とし、
マスター公開鍵ＰＫ＝（Ｎ，ｈ，ｃ，Ｋ）とＪビットのビット列を出力するハッシュ関数Ｈを含む共通参照情報ｃｒｓと文書ｍとを受け取る送信入力部と、
乱数ｒを生成する乱数生成部と、
ワンタイム署名の署名検証鍵ｖｋ０と署名生成鍵ｓｋ０とを生成するワンタイム署名鍵生成部と、
Ｈ（ｖｋ０）を個別公開鍵ｐｋとし、
ｅｊ＝ＰＫ，ｃ（ｐｋ（ｊ））、ただしｐｋ（ｊ）はｐｋの先頭のｊビット
をｊ＝１からｊ＝Ｊまで計算し、ｅｍｉｎをｅ１，…，ｅＪのうちで最小の値とし、
ｍｊ＝ｍ  ｍｏｄ  ｅｊ
をｊ＝１からｊ＝Ｊまで計算し、
Ｍ  ｍｏｄ  ｅｊ＝ｍｊ
がすべてのｊに対して成り立つＭを０以上
【数２３】
0005448864.tif 000021
以下の整数の中から求め、
０以上ｅｍｉｎ−１以下の整数である文書ｍをコミットするために、コミットメント要素Ｃ、デコミットメント要素Ｄを、
【数２４】
0005448864.tif 000022
のように求めるコミットメント要素生成部と、
コミットメント要素Ｃに対するワンタイム署名σ０を、署名生成鍵ｓｋ０を用いて生成するワンタイム署名生成部と、
コミットメント要素Ｃと署名検証鍵ｖｋ０を含むコミットメントｃｏｍを送信するコミットメント送信部と、
デコミットメント要素Ｄと文書ｍとワンタイム署名σ０を含むデコミットメントｄｅｃを送信するデコミットメント送信部と、
を備える送信装置。
【請求項４】
λはセキュリティパラメータ、ｆは１λに依存する整数、ｐ、ｑは互いに異なるλビットの奇素数、Ｆは任意ビットのビット列をｆビットのビット列に変換する擬似ランダム関数、ＰＫ，ｃを、
【数２７】
0005448864.tif 000023
のように定義される関数、ＮはＮ＝ｐｑ、ｈは１以上Ｎ−１以下の任意の整数、Ｋは擬似ランダム関数Ｆの鍵、ｃはｆビットのビット列とし、
マスター公開鍵ＰＫ＝（Ｎ，ｈ，ｃ，Ｋ）とＪビットのビット列を出力するハッシュ関数Ｈを含む共通参照情報ｃｒｓと、コミットメント要素Ｃ’と署名検証鍵ｖｋ０’を含むコミットメントｃｏｍと、デコミットメント要素Ｄ’＝（Ｍ’，ｒ’）と文書ｍ’とワンタイム署名σ０’を含むデコミットメントｄｅｃとを受け取る受信入力部と、
署名検証鍵ｖｋ０’を用いて、コミットメント要素Ｃ’に対するワンタイム署名σ０’の正当性を検証するワンタイム署名検証部と、
Ｈ（ｖｋ０’）を個別公開鍵ｐｋ’とし、
ｅｊ’＝ＰＫ，ｃ（ｐｋ’（ｊ））、ただしｐｋ’（ｊ）はｐｋ’の先頭のｊビット
および、
ｍｊ’＝Ｍ’  ｍｏｄ  ｅｊ’
をｊ＝１からｊ＝Ｊまで計算し、
ｍ１’＝ｍ２’＝，…，＝ｍＪ’
かつ
【数２８】
0005448864.tif 000024
であることを検証するコミットメント検証部と
を備える受信装置。
【請求項５】
送信装置、受信装置、マスター装置で構成されるコミットメントシステムを用いたコミットメント方法であって、
λはセキュリティパラメータ、ｆは１λに依存する整数、ｐ、ｑは互いに異なるλビットの奇素数、Ｆは任意ビットのビット列をｆビットのビット列に変換する擬似ランダム関数とし、
封フェーズでは、
前記マスター装置が、２ｆ＜φ（Ｎ）＝（ｐ−１）（ｑ−１）＜２ｆ＋２であるＲＳＡモジュラスＮ＝ｐｑを出力するＲＳＡモジュラスステップと、
前記マスター装置が、１以上Ｎ−１以下の任意の整数ｈと、擬似ランダム関数Ｆの鍵Ｋと、ｆビットのビット列ｃとをランダムに選ぶマスター選定ステップと、
前記マスター装置が、関数ＰＫ，ｃを、
【数３０】
0005448864.tif 000025
のように定義する関数定義ステップと、
前記マスター装置が、（Ｎ，ｈ，ｃ，Ｋ）をマスター公開鍵ＰＫとし、（ｐ，ｑ，ＰＫ）をマスタートラップドアＴＫとするマスター鍵生成ステップと、
前記マスター装置が、マスター公開鍵ＰＫとＪビットのビット列を出力するハッシュ関数Ｈを含む共通参照情報ｃｒｓを生成し、前記送信装置と前記受信装置に送信する共通参照情報生成ステップと、
前記送信装置が、前記共通参照情報ｃｒｓと文書ｍとを受け取る送信入力ステップと、
前記受信装置が、前記共通参照情報ｃｒｓを受け取る第１受信入力ステップと、
前記送信装置が、乱数ｒを生成する乱数生成ステップと、
前記送信装置が、ワンタイム署名の署名検証鍵ｖｋ０と署名生成鍵ｓｋ０とを生成するワンタイム署名鍵生成ステップと、
前記送信装置が、Ｈ（ｖｋ０）を個別公開鍵ｐｋとし、
ｅｊ＝ＰＫ，ｃ（ｐｋ（ｊ））、ただしｐｋ（ｊ）はｐｋの先頭のｊビット
をｊ＝１からｊ＝Ｊまで計算し、ｅｍｉｎをｅ１，…，ｅＪのうちで最小の値とし、
ｍｊ＝ｍ  ｍｏｄ  ｅｊ
をｊ＝１からｊ＝Ｊまで計算し、
Ｍ  ｍｏｄ  ｅｊ＝ｍｊ
がすべてのｊに対して成り立つＭを０以上
【数３１】
0005448864.tif 000026
以下の整数の中から求め、
０以上ｅｍｉｎ−１以下の整数である文書ｍをコミットするために、コミットメント要素Ｃ、デコミットメント要素Ｄを、
【数３２】
0005448864.tif 000027
のように求めるコミットメント要素生成ステップと、
前記送信装置が、コミットメント要素Ｃに対するワンタイム署名σ０を、署名生成鍵ｓｋ０を用いて生成するワンタイム署名生成ステップと、
前記送信装置が、コミットメント要素Ｃと署名検証鍵ｖｋ０を含むコミットメントｃｏｍを、前記受信装置に送信するコミットメント送信ステップと、
前記受信装置が、コミットメント要素Ｃ’と署名検証鍵ｖｋ０’を含むコミットメントｃｏｍを受け取る第２受信入力ステップと
を有し、
開封フェーズでは、
前記送信装置が、デコミットメント要素Ｄと文書ｍとワンタイム署名σ０を含むデコミットメントｄｅｃを、前記受信装置に送信するデコミットメント送信ステップと、
前記受信装置が、デコミットメント要素Ｄ’＝（Ｍ’，ｒ’）と文書ｍ’とワンタイム署名σ０’を含むデコミットメントｄｅｃとを受け取る第３受信入力ステップと、
前記受信装置が、署名検証鍵ｖｋ０’を用いて、コミットメント要素Ｃ’に対するワンタイム署名σ０’の正当性を検証するワンタイム署名検証ステップと、
前記受信装置が、Ｈ（ｖｋ０’）を個別公開鍵ｐｋ’とし、
ｅｊ’＝ＰＫ，ｃ（ｐｋ’（ｊ））、ただしｐｋ’（ｊ）はｐｋ’の先頭のｊビット
および、
ｍｊ’＝Ｍ’  ｍｏｄ  ｅｊ’
をｊ＝１からｊ＝Ｊまで計算し、
ｍ１’＝ｍ２’＝，…，＝ｍＪ’
かつ
【数３３】
0005448864.tif 000028
であることを検証するコミットメント検証ステップと
を有する
ことを特徴とするコミットメント方法。
【請求項６】
請求項２記載のマスター装置、請求項３記載の送信装置、もしくは請求項４記載の受信装置としてコンピュータを機能させるプログラム。
【請求項７】
請求項６記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、非対話型かつ共通参照情報が再利用可能で、頑強なコミットメントを実現するコミットメントシステム、マスター装置、送信装置、受信装置、コミットメント方法、プログラム、記録媒体に関する。
【背景技術】
【０００２】
代表的な非対話型かつ共通参照情報が再利用可能で頑強なコミットメント方式として、非特許文献１，２，３がある。非特許文献１は、安全性が強ＲＳＡ仮定という強い仮定に基づいている。非特許文献２は、安全性が強ＲＳＡ仮定またはＤＳＡ仮定という強い仮定に基づいている。非特許文献３は、安全性が強ＲＳＡまたはｑ−強ＤＨ仮定という強い仮定に基づいている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】I. Damgard and J. Groth, “Non-interactive and reusable non-malleable commitment schemes,” In STOC, pp.426-437, ACM, 2003.
【非特許文献２】P.D. MacKenzie and K. Yang, “On Simulation-Sound Trapdoor Commitments,” In EUROCRYPT, volume 3027 of Lecture Notes in Computer Science, pp.382-400, Springer, 2004.
【非特許文献３】R. Gennaro, “Multi-trapdoor Commitments and Their Applications to Proofs of Knowledge Secure Under Concurrent Man-in-the-Middle Attacks,” In CRYPTO, volume 3152 of Lecture Notes in Computer Science, pp. 220-236, Springer, 2004.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来技術は全て強い仮定に基づいて安全性を達しているため、仮定が標準的ではなく、安全性の信頼性が低いという課題がある。
【０００５】
本発明は、非対話型かつ共通参照情報が再利用可能で、ＲＳＡ仮定または計算ＤＨ仮定という標準的な仮定に基づいて安全性を達成できる頑強なコミットメント方式を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明のコミットメントシステムは、送信装置、受信装置、マスター装置で構成される。マスター装置は、少なくともマスター公開鍵ＰＫとハッシュ関数Ｈを含む共通参照情報ｃｒｓを生成し、送信装置と受信装置に送信する共通参照情報生成部を備える。送信装置は、送信入力部、乱数生成部、ワンタイム署名鍵生成部、コミットメント要素生成部、ワンタイム署名生成部、コミットメント送信部、デコミットメント送信部を備える。送信入力部は、共通参照情報ｃｒｓと文書ｍとを受け取る。乱数生成部は、乱数ｒを生成する。ワンタイム署名鍵生成部は、ワンタイム署名の署名検証鍵ｖｋ０と署名生成鍵ｓｋ０とを生成する。コミットメント要素生成部は、Ｈ（ｖｋ０）をマルチトラップドアコミットメントの個別公開鍵ｐｋとし、文書ｍをコミットするために、マスター公開鍵ＰＫ、個別公開鍵ｐｋ、文書ｍ、乱数ｒを用いてコミットメント要素Ｃ、デコミットメント要素Ｄを求める。ワンタイム署名生成部は、コミットメント要素Ｃに対するワンタイム署名σ０を、署名生成鍵ｓｋ０を用いて生成する。コミットメント送信部は、コミットメント要素Ｃと署名検証鍵ｖｋ０を含むコミットメントｃｏｍを、受信装置に送信する。デコミットメント送信部は、デコミットメント要素Ｄと文書ｍとワンタイム署名σ０を含むデコミットメントｄｅｃを、受信装置に送信する。受信装置は、受信入力部、ワンタイム署名検証部、コミットメント検証部を備える。受信入力部は、共通参照情報ｃｒｓと、コミットメント要素Ｃ’と署名検証鍵ｖｋ０’を含むコミットメントｃｏｍと、デコミットメント要素Ｄ’と文書ｍ’とワンタイム署名σ０’を含むデコミットメントｄｅｃとを受け取る。ワンタイム署名検証部は、署名検証鍵ｖｋ０’を用いて、コミットメント要素Ｃ’に対するワンタイム署名σ０’の正当性を検証する。コミットメント検証部は、マルチトラップドアコミットメントの検証アルゴリズムによって、コミットメント要素Ｃ’とデコミットメント要素Ｄ’の正当性を検証する。
【発明の効果】
【０００７】
本発明のコミットメントシステムは、マルチトラップドアコミットメントの構成が、弱選択文書攻撃に対して存在的偽造不可能な署名方式を利用している。また、マスター公開鍵ＰＫが署名方式の検証鍵に、マスタートラップドアが署名方式の署名鍵に、個別公開鍵が署名方式の文書に、個別公開鍵のトラップドアが署名方式の署名にそれぞれ対応している。つまり、コミットメントの拘束性を破ることがトラップドアの取得と等価となっている。本発明のコミットメントシステムは、ＲＳＡ仮定または計算ＤＨ仮定が成立しているならば、非対話型かつ共通参照情報が再利用可能で頑強なコミットメント方式である。よって、本発明のコミットメントシステムによれば、非対話型かつ共通参照情報が再利用可能で、ＲＳＡ仮定または計算ＤＨ仮定という標準的な仮定に基づいて安全性を達成できる頑強なコミットメント方式を提供できる。
【図面の簡単な説明】
【０００８】
【図１】実施例１のコミットメントシステムの構成例を示す図。
【図２】実施例１のコミットメントシステムの処理フローを示す図。
【図３】実施例２のコミットメントシステムの構成例を示す図。
【図４】実施例２のコミットメントシステムの処理フローを示す図。
【図５】実施例３のコミットメントシステムの構成例を示す図。
【図６】実施例３のコミットメントシステムの処理フローを示す図。
【発明を実施するための形態】
【０００９】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１０】
図１に実施例１のコミットメントシステムの構成例を、図２に実施例１のコミットメントシステムの処理フローを示す。本実施例のコミットメントシステムは、送信装置２００、受信装置３００、マスター装置１００で構成され、各装置はネットワーク１０００で接続されている。マスター装置１００は、少なくともマスター公開鍵ＰＫとハッシュ関数Ｈを含む共通参照情報ｃｒｓを生成し、送信装置と受信装置に送信する共通参照情報生成部１５０、マスター記録部１９０を備える。送信装置２００は、送信入力部２１０、乱数生成部２２０、ワンタイム署名鍵生成部２３０、コミットメント要素生成部２４０、ワンタイム署名生成部２５０、コミットメント送信部２６０、デコミットメント送信部２７０、送信記録部２９０を備える。受信装置３００は、受信入力部３１０、ワンタイム署名検証部３２０、コミットメント検証部３３０、受信記録部３９０を備える。
【００１１】
封フェーズでは、マスター装置１００の共通参照情報生成部１５０が、マスター公開鍵ＰＫとハッシュ関数Ｈを含む共通参照情報ｃｒｓを生成し、マスター記録部１９０に記録し、送信装置２００と受信装置３００に送信する（Ｓ１５０）。送信装置２００の送信入力部２１０は、共通参照情報ｃｒｓと文書ｍとを受け取り、送信記録部２９０に記録する（Ｓ２１０）。また、受信装置３００の受信入力部も、共通参照情報ｃｒｓを受け取り、受信記録部３９０に記録する（Ｓ３１１）。
【００１２】
送信装置２００の乱数生成部２２０が、乱数ｒを生成し、送信記録部２９０に記録する（Ｓ２２０）。ワンタイム署名鍵生成部２３０が、ワンタイム署名の署名検証鍵ｖｋ０と署名生成鍵ｓｋ０とを生成し、送信記録部２９０に記録する（Ｓ２３０）。コミットメント要素生成部２４０が、Ｈ（ｖｋ０）をマルチトラップドアコミットメントの個別公開鍵ｐｋとし、文書ｍをコミットするために、マスター公開鍵ＰＫ、個別公開鍵ｐｋ、文書ｍ、乱数ｒを用いてコミットメント要素Ｃ、デコミットメント要素Ｄを求め、送信記録部２９０に記録する（Ｓ２４０）。ワンタイム署名生成部２５０は、コミットメント要素Ｃに対するワンタイム署名σ０を、署名生成鍵ｓｋ０を用いて生成し、送信記録部２９０に記録する（Ｓ２５０）。コミットメント送信部２６０は、コミットメント要素Ｃと署名検証鍵ｖｋ０を含むコミットメントｃｏｍを、受信装置３００に送信する（Ｓ２６０）。そして、受信装置３００の受信入力部３１０が、コミットメント要素Ｃ’と署名検証鍵ｖｋ０’を含むコミットメントｃｏｍを受信し、受信記録部３９０に記録する（Ｓ３１２）。
【００１３】
開封フェーズでは、送信装置２００のデコミットメント送信部２７０が、デコミットメント要素Ｄと文書ｍとワンタイム署名σ０を含むデコミットメントｄｅｃを、受信装置３００に送信する（Ｓ２７０）。受信装置３００の受信入力部３１０は、デコミットメント要素Ｄ’と文書ｍ’とワンタイム署名σ０’を含むデコミットメントｄｅｃを受信し、受信記録部３９０に記録する（Ｓ３１３）。ワンタイム署名検証部３２０は、署名検証鍵ｖｋ０’を用いて、コミットメント要素Ｃ’に対するワンタイム署名σ０’の正当性を検証する（Ｓ３２０）。コミットメント検証部３３０は、マルチトラップドアコミットメントの検証アルゴリズムによって、コミットメント要素Ｃ’とデコミットメント要素Ｄ’の正当性を検証する（Ｓ３３０）。なお、ステップＳ３２０，Ｓ３３０の検証が失敗した場合には、エラーを出力し、処理を中止すればよい。
【００１４】
本実施例のコミットメントシステムは、マルチトラップドアコミットメントの構成が、弱選択文書攻撃に対して存在的偽造不可能な署名方式を利用している。また、マスター公開鍵ＰＫが署名方式の検証鍵に、マスタートラップドアが署名方式の署名鍵に、個別公開鍵が署名方式の文書に、個別公開鍵のトラップドアが署名方式の署名にそれぞれ対応している。つまり、コミットメントの拘束性を破ることがトラップドアの取得と等価となっている。本実施例のコミットメントシステムは、ＲＳＡ仮定または計算ＤＨ仮定が成立しているならば、非対話型かつ共通参照情報が再利用可能で頑強なコミットメント方式である。
【実施例２】
【００１５】
図３に実施例２のコミットメントシステムの構成例を、図４に実施例２のコミットメントシステムの処理フローを示す。本実施例のコミットメントシステムは、送信装置５００、受信装置６００、マスター装置４００で構成され、各装置はネットワーク１０００で接続されている。マスター装置４００は、ＲＳＡモジュラス部４１０、マスター選定部４２０、関数定義部４３０、マスター鍵生成部４４０、共通参照情報生成部４５０、マスター記録部４９０を備える。送信装置５００は、送信入力部５１０、乱数生成部２２０、ワンタイム署名鍵生成部２３０、コミットメント要素生成部５４０、ワンタイム署名生成部２５０、コミットメント送信部２６０、デコミットメント送信部２７０、送信記録部５９０を備える。受信装置６００は、受信入力部６１０、ワンタイム署名検証部３２０、コミットメント検証部６３０、受信記録部６９０を備える。なお、本実施例では、λはセキュリティパラメータ、ｆは１λに依存する整数、ｐ、ｑは互いに異なるλビットの奇素数、Ｆは任意ビットのビット列をｆビットのビット列に変換する擬似ランダム関数とする。
【００１６】
封フェーズでは、マスター装置４００のＲＳＡモジュラス部４１０が、
２ｆ＜φ（Ｎ）＝（ｐ−１）（ｑ−１）＜２ｆ＋２
であるＲＳＡモジュラスＮ＝ｐｑを求め、出力するとともに、マスター記録部４９０に記録する（Ｓ４１０）。マスター選定部４２０が、１以上Ｎ−１以下の任意の整数ｈと、擬似ランダム関数Ｆの鍵Ｋと、ｆビットのビット列ｃとをランダムに選び、マスター記録部４９０に記録する（Ｓ４２０）。関数定義部４３０が、関数ＰＫ，ｃを、
【００１７】
【数１】
0005448864.tif 000002
【００１８】
のように定義し、マスター記録部４９０に記録する（Ｓ４３０）。マスター鍵生成部４４０が、（Ｎ，ｈ，ｃ，Ｋ）をマスター公開鍵ＰＫとし、（ｐ，ｑ，ＰＫ）をマスタートラップドアＴＫとし、マスター記録部４９０に記録する（Ｓ４４０）。共通参照情報生成部４５０が、マスター公開鍵ＰＫとＪビットのビット列を出力するハッシュ関数Ｈを含む共通参照情報ｃｒｓを生成し、送信装置５００と受信装置６００に送信する（Ｓ４５０）。送信装置５００の送信入力部５１０は、共通参照情報ｃｒｓと文書ｍとを受け取り、送信記録部５９０に記録する（Ｓ５１０）。また、受信装置６００の受信入力部も、共通参照情報ｃｒｓを受け取り、受信記録部６９０に記録する（Ｓ６１１）。
【００１９】
乱数生成部２２０が、乱数ｒを生成し、送信記録部５９０に記録する（Ｓ２２０）。ワンタイム署名鍵生成部２３０が、ワンタイム署名の署名検証鍵ｖｋ０と署名生成鍵ｓｋ０とを生成し、送信記録部５９０に記録する（Ｓ２３０）。コミットメント要素生成部５４０が、
（１）Ｈ（ｖｋ０）を個別公開鍵ｐｋとし、
（２）ｅｊ＝ＰＫ，ｃ（ｐｋ（ｊ））、ただしｐｋ（ｊ）はｐｋの先頭のｊビット
をｊ＝１からｊ＝Ｊまで計算し、ｅｍｉｎをｅ１，…，ｅＪのうちで最小の値とし、
（３）ｍｊ＝ｍ  ｍｏｄ  ｅｊ
をｊ＝１からｊ＝Ｊまで計算し、
（４）Ｍ  ｍｏｄ  ｅｊ＝ｍｊ
がすべてのｊに対して成り立つＭを０以上
【００２０】
【数２】
0005448864.tif 000003
【００２１】
以下の整数の中から求め、
（５）０以上ｅｍｉｎ−１以下の整数である文書ｍをコミットするために、コミットメント要素Ｃ、デコミットメント要素Ｄを、
【００２２】
【数３】
0005448864.tif 000004
【００２３】
のように求め、送信記録部５９０に記録する（Ｓ５４０）。ワンタイム署名生成部２５０が、コミットメント要素Ｃに対するワンタイム署名σ０を、署名生成鍵ｓｋ０を用いて生成し、送信記録部５９０に記録する（Ｓ２５０）。コミットメント送信部２６０が、コミットメント要素Ｃと署名検証鍵ｖｋ０を含むコミットメントｃｏｍを、受信装置６００に送信する（Ｓ２６０）。そして、受信装置６００の受信入力部６１０が、コミットメント要素Ｃ’と署名検証鍵ｖｋ０’を含むコミットメントｃｏｍを受信し、受信記録部６９０に記録する（Ｓ６１２）。
【００２４】
開封フェーズでは、送信装置５００のデコミットメント送信部２７０が、デコミットメント要素Ｄと文書ｍとワンタイム署名σ０を含むデコミットメントｄｅｃを、受信装置６００に送信する（Ｓ２７０）。受信装置６００の受信入力部６１０は、デコミットメント要素Ｄ’＝（Ｍ’，ｒ’）と文書ｍ’とワンタイム署名σ０’を含むデコミットメントｄｅｃを受信し、受信記録部６９０に記録する（Ｓ６１３）。ワンタイム署名検証部３２０が、署名検証鍵ｖｋ０’を用いて、コミットメント要素Ｃ’に対するワンタイム署名σ０’の正当性を検証する（Ｓ３２０）。コミットメント検証部６３０が、
（１）Ｈ（ｖｋ０’）を個別公開鍵ｐｋ’とし、
（２）ｅｊ’＝ＰＫ，ｃ（ｐｋ’（ｊ））、ただしｐｋ’（ｊ）はｐｋ’の先頭のｊビット
および、
ｍｊ’＝Ｍ’  ｍｏｄ  ｅｊ’
をｊ＝１からｊ＝Ｊまで計算し、
（３）ｍ１’＝ｍ２’＝，…，＝ｍＪ’
かつ
【００２５】
【数４】
0005448864.tif 000005
【００２６】
であることを検証する（Ｓ６３０）。なお、ステップＳ３２０，Ｓ６３０の検証が失敗した場合には、エラーを出力し、処理を中止すればよい。
【００２７】
本実施例のコミットメントシステムでは、送信装置５００が、トラップドアｔｄを
【００２８】
【数５】
0005448864.tif 000006
【００２９】
のように生成できる。また、Ｍ〜を
ｍｊ〜＝Ｍ〜  ｍｏｄ  ｅｊ
をｊ＝１からｊ＝Ｊまで計算したときに、
ｍ１〜＝ｍ２〜＝，…，＝ｍＪ〜
が成り立ち、かつ、Ｍ〜≠Ｍとし、
【００３０】
【数６】
0005448864.tif 000007
【００３１】
とし、デコミットメント要素をＤ〜＝（Ｍ〜，ｒ〜）とすると、
【００３２】
【数７】
0005448864.tif 000008
【００３３】
となる。つまり、両開きできる。このように、本実施例のコミットメントシステムは、マルチトラップドアコミットメントの６つのアルゴリズムを有している。
【００３４】
本実施例のコミットメントシステムは、マルチトラップドアコミットメントの構成が、弱選択文書攻撃に対して存在的偽造不可能な署名方式を利用している。また、マスター公開鍵ＰＫが署名方式の検証鍵に、マスタートラップドアが署名方式の署名鍵に、個別公開鍵が署名方式の文書に、個別公開鍵のトラップドアが署名方式の署名にそれぞれ対応している。つまり、コミットメントの拘束性を破ることがトラップドアの取得と等価となっている。本実施例のコミットメントシステムは、ＲＳＡ仮定が成立しているならば、非対話型かつ共通参照情報が再利用可能で頑強なコミットメント方式である。
【実施例３】
【００３５】
図５に実施例３のコミットメントシステムの構成例を、図６に実施例３のコミットメントシステムの処理フローを示す。本実施例のコミットメントシステムは、送信装置８００、受信装置９００、マスター装置７００で構成され、各装置はネットワーク１０００で接続されている。マスター装置７００は、マスター選定部７２０、マスター鍵生成部７４０、共通参照情報生成部７５０、マスター記録部７９０を備える。送信装置８００は、送信入力部８１０、乱数生成部８２０、ワンタイム署名鍵生成部２３０、コミットメント要素生成部８４０、ワンタイム署名生成部２５０、コミットメント送信部２６０、デコミットメント送信部２７０、送信記録部８９０を備える。受信装置９００は、受信入力部９１０、ワンタイム署名検証部３２０、コミットメント検証部９３０を備える。なお、本実施例では、λはセキュリティパラメータ、ＧとＧＴは２λより大きい素数位数ｐの双線型群、Ｊはあらかじめ定めた正の整数、ＥはＧ×Ｇの元をＧＴの元に変換する双線型写像とする。
【００３６】
封フェーズでは、マスター装置７００のマスター選定部７２０が、０以上ｐ−１以下の整数ａと、群Ｇの生成元ｇと群Ｇの元ｖ０，…，ｖＪをランダムに選び、マスター記録部７９０に記録する（Ｓ７２０）。マスター鍵生成部７４０が、（ｇ，ｖ０，…，ｖＪ，Ｅ（ｇ，ｇ）ａ）をマスター公開鍵ＰＫとし、ａをマスタートラップドアとし、マスター記録部７９０に記録する（Ｓ７４０）。共通参照情報生成部７５０が、マスター公開鍵ＰＫとＪビットのビット列を出力するハッシュ関数Ｈを含む共通参照情報ｃｒｓを生成し、送信装置８００と受信装置９００に送信する（Ｓ７５０）。送信装置８００の送信入力部８１０は、共通参照情報ｃｒｓと文書ｍとを受け取り、送信記録部８９０に記録する（Ｓ８１０）。また、受信装置９００の受信入力部も、共通参照情報ｃｒｓを受け取り、受信記録部９９０に記録する（Ｓ９１１）。
【００３７】
乱数生成部８２０が、乱数ｒ１，ｒ２を生成し、送信記録部８９０に記録する（Ｓ８２０）。ワンタイム署名鍵生成部２３０が、ワンタイム署名の署名検証鍵ｖｋ０と署名生成鍵ｓｋ０とを生成し、送信記録部８９０に記録する（Ｓ２３０）。コミットメント要素生成部８４０が、
（１）Ｈ（ｖｋ０）を個別公開鍵ｐｋとし、
（２）群Ｇの元ρ１とρ２をランダムに選定し、
（３）Ｅ（ρ１，ｇ）をβ１、Ｅ（ρ２，Ｖｐｋ−１）をβ２、Ｅ（ｇ，ｇ）ａをβ
ただし、
【００３８】
【数８】
0005448864.tif 000009
【００３９】
ｐｋｊはｐｋのｊ番目のビット
とし、
（４）０以上ｐ−１以下の整数である文書ｍをコミットするために、コミットメント要素Ｃ、デコミットメント要素Ｄを、
【００４０】
【数９】
0005448864.tif 000010
【００４１】
のように求め、送信記録部８９０に記録する（Ｓ８４０）。ワンタイム署名生成部２５０が、コミットメント要素Ｃに対するワンタイム署名σ０を、署名生成鍵ｓｋ０を用いて生成し、送信記録部８９０に記録する（Ｓ２５０）。コミットメント送信部２６０が、コミットメント要素Ｃと署名検証鍵ｖｋ０を含むコミットメントｃｏｍを、受信装置９００に送信する（Ｓ２６０）。そして、受信装置９００の受信入力部９１０が、コミットメント要素Ｃ’と署名検証鍵ｖｋ０’を含むコミットメントｃｏｍを受信し、受信記録部９９０に記録する（Ｓ９１２）。
【００４２】
開封フェーズでは、送信装置８００のデコミットメント送信部２７０が、デコミットメント要素Ｄと文書ｍとワンタイム署名σ０を含むデコミットメントｄｅｃを、受信装置９００に送信する（Ｓ２７０）。受信装置９００の受信入力部９１０は、デコミットメント要素Ｄ’＝（ｍ’，ｒ１’，ｒ２’）と文書ｍ’とワンタイム署名σ０’を含むデコミットメントｄｅｃとを受信し、受信記録部９９０に記録する（Ｓ９１３）。ワンタイム署名検証部３２０が、署名検証鍵ｖｋ０’を用いて、コミットメント要素Ｃ’に対するワンタイム署名σ０’の正当性を検証する（Ｓ３２０）。コミットメント検証部９３０が、
（１）Ｈ（ｖｋ０’）を個別公開鍵ｐｋ’とし、
（２）Ｅ（ρ１’，ｇ）をβ１’、Ｅ（ρ２’，Ｖｐｋ−１）をβ２’、Ｅ（ｇ，ｇ）ａをβ’とし、
（３）
【００４３】
【数１０】
0005448864.tif 000011
【００４４】
であることを検証する（Ｓ９３０）。なお、ステップＳ３２０，Ｓ６３０の検証が失敗した場合には、エラーを出力し、処理を中止すればよい。
【００４５】
本実施例のコミットメントシステムでは、送信装置５００が、トラップドアｔｄ＝（σ１，σ２）を生成できる。ここで、σ１，σ２は、
【００４６】
【数１１】
0005448864.tif 000012
【００４７】
ただし、ｐｋｊはｐｋのｊ番目のビット、ｗは０以上ｐ−１以下からランダムに選ばれた整数
である。また、ｍ〜をｍ〜≠ｍ、ｒ−１とｒ−２を
【００４８】
【数１２】
0005448864.tif 000013
【００４９】
を満たす整数、ｒ〜１とｒ〜２を
ｒ〜１＝ｒ１−（ｍ〜−ｍ）ｒ−１  ｍｏｄ  ｐ
ｒ〜２＝ｒ２−（ｍ〜−ｍ）ｒ−２  ｍｏｄ  ｐ
とし、デコミットメント要素をＤ〜＝（ｍ〜，ｒ〜1，ｒ〜２）とすると、
【００５０】
【数１３】
0005448864.tif 000014
【００５１】
となる。つまり、両開きできる。このように、本実施例のコミットメントシステムは、マルチトラップドアコミットメントの６つのアルゴリズムを有している。
【００５２】
本実施例のコミットメントシステムは、マルチトラップドアコミットメントの構成が、弱選択文書攻撃に対して存在的偽造不可能な署名方式を利用している。また、マスター公開鍵ＰＫが署名方式の検証鍵に、マスタートラップドアが署名方式の署名鍵に、個別公開鍵が署名方式の文書に、個別公開鍵のトラップドアが署名方式の署名にそれぞれ対応している。つまり、コミットメントの拘束性を破ることがトラップドアの取得と等価となっている。本実施例のコミットメントシステムは、計算ＤＨ仮定が成立しているならば、非対話型かつ共通参照情報が再利用可能で頑強なコミットメント方式である。
【００５３】
安全性に関する補足説明
上述の説明の中で使われている用語について以下に説明する。なお、この補足説明の内容は本願の出願日前から既知の内容である。
【００５４】
マルチトラップドアコミットメントについては非特許文献３に詳細に示されている。その一部を紹介すると、マルチトラップコミットメントは６つのアルゴリズム（マスター鍵生成ＫＧｅｎ．，選択Ｓｅｌ．，トラップドア生成ＴＧｅｎ．，コミットメントＣｏｍ．，検証Ｖｒｆｙ．，両開きＥｑｕｉｖ．）からなる。そして、マルチトラップドアコミットメントは、正当性、情報理論的秘匿性、拘束性の性質を持つ。
【００５５】
署名方式は、３つの確率的多項式時間アルゴリズム（鍵生成アルゴリズムＳｉｇ．Ｇｅｎ，署名アルゴリズムＳｉｇ．Ｓｉｇｎ，検証アルゴリズムＳｉｇ．Ｖｒｆｙ）からなる。そして、署名方式が弱選択文書攻撃に対して存在的偽造不可能とは、どのような敵（攻撃者）に対しても敵が次のゲームに勝つ確率が無視できることである。
【００５６】
（１）質問：敵は最初に文書ｍ１，…，ｍｋのリストＱを送る。
【００５７】
（２）答え：検証鍵と署名鍵の対（ｖｋ，ｓｋ）および、質問された文書に対する署名σ１，…，σｋを敵に送る。
【００５８】
（３）出力：敵は（ｍ＊，σ＊）を出力する。もし、ｍ＊がＱに含まれておらず、かつｍ＊に対する署名σ＊が正当ならば敵がゲームに勝ったという。
【００５９】
λはセキュリティパラメータ、ｐ、ｑは互いに異なるλビットの奇素数とする。そして、ＲＳＡモジュラスＮ＝ｐｑ、φ（Ｎ）＝（ｐ−１）（ｑ−１）と互いに素な正の整数ｅ、１以上Ｎ−１以下のランダムな整数ｙが与えられたときに、ｘｅ＝ｙ  ｍｏｄ  Ｎ  なるｘを計算することが困難であることをＲＳＡ仮定という。つまり、ＲＳＡ仮定では、どのような敵に対しても、ｘを計算できる優位性が無視できる。
【００６０】
ＧとＧＴは素数位数ｐの巡回群、ＥはＧ×Ｇの元をＧＴの元に変換する双線型写像であり、双線型性と非退化性を満たすとする。また、ｇは群Ｇの生成元、ａとｂは０以上ｐ−１以下の任意の整数とする。そして、（Ｇ，ＧＴ，ｐ，ｇ，Ｅ）と（ｇａ，ｇｂ）が与えられたときに、ｇａｂを計算することが困難であることを計算ＤＨ（ディッフィー・へルマン）仮定という。つまり、計算ＤＨ仮定では、どのような敵に対しても、ｇａｂを計算できる優位性が無視できる。
【００６１】
プログラム、記録媒体
上述の構成をコンピュータによって実現する場合、マスター装置、送信装置、受信装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００６２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、マスター装置、送信装置、受信装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００６６】
本発明は、電気通信システムでのコミットメント方式に利用することができる。
【符号の説明】
【００６７】
１００、４００、７００  マスター装置
１５０、４５０、７５０  共通参照情報生成部
１９０、４９０、７９０  マスター記録部
２００、５００、８００  送信装置
２１０、５１０、８１０  送信入力部
２２０、８２０  乱数生成部
２３０  ワンタイム署名鍵生成部
２４０、５４０、８４０  コミットメント要素生成部
２５０  ワンタイム署名生成部
２６０  コミットメント送信部
２７０  デコミットメント送信部
２９０、５９０、８９０  送信記録部
３００、６００、９００  受信装置
３１０、６１０、９１０  受信入力部
３２０  ワンタイム署名検証部
３３０、６３０、９３０  コミットメント検証部
３９０、６９０、９９０  受信記録部
４１０  ＲＳＡモジュラス部
４２０、７２０  マスター選定部
４３０  関数定義部
４４０、７４０  マスター鍵生成部
１０００  ネットワーク
【図１】
0005448864.tif 000029
【図２】
0005448864.tif 000030
【図３】
0005448864.tif 000031
【図４】
0005448864.tif 000032
【図５】
0005448864.tif 000033
【図６】
0005448864.tif 000034