(57)【特許請求の範囲】
【請求項１】
少なくとも証明装置と検証装置とを備える署名システムであって、
Ｇ１、Ｇ２、Ｇ３は素数ｖを位数として持つ群、ｅはＧ１×Ｇ２からＧ３への双線形写像、ｇはＧ１の生成元、ｘは乱数であって０からｖ−１までの整数、ｈは任意長ビット列を入力としＧ１の元を出力するハッシュ関数であり、
前記証明装置は、
秘密鍵ｓｋ、公開鍵ｐｋ、メッセージｍ、署名ｓ（ただし、ｓｋ＝ｘ、ｐｋ＝ｙ＝ｇｘ、ｓ＝ｈ（ｍ）ｘ）を記録する証明用記録部と、
乱数ｒ（ただし、ｒは０からｖ−１までの整数）を生成し、Ｘ１＝ｇｒを計算し、Ｘ１を前記検証装置に送信する第１計算部と、
前記検証装置との間で、ランダムなＧ２の元ｔを共有する証明用元共有部と、
Ｘ２＝ｅ（ｈ（ｍ）ｒ，ｔ）を計算し、Ｘ２を前記検証装置に送信する第２計算部と、
σ＝ｒ＋ｃｘ  （ｍｏｄ  ｖ）を計算し、σを前記検証装置に送信する第３計算部と
を具備し、
前記検証装置は、
公開鍵ｐｋ、署名ｓ’、メッセージｍを取得する検証用取得部と、
前記証明装置との間で、ランダムなＧ２の元ｔを共有する検証用元共有部と、
乱数ｃ（ただし、ｃは０からｖ−１までの整数）を生成し、ｃを前記証明装置に送信する検証用乱数生成部と、
Ｘ１・ｙｃ＝ｇσと、Ｘ２・ｅ（ｓ’，ｔ）ｃ＝ｅ（ｈ（ｍ），ｔ）σが成り立つかを検証する検証部と
を具備する
ことを特徴とする署名システム。
【請求項２】
少なくとも証明装置と検証装置とを備える署名システムであって、
楕円曲線Ｅは要素数ｑの有限体Ｆｑ上定義された非超特異楕円曲線、楕円曲線ＥのＦｑ有理点Ｅ（Ｆｑ）の数Ｎ（Ｅ（Ｆｑ））はｖで一度だけ割れる、ｋはｖ｜（ｑｋ−１）を満たす最小の整数とし、
Ｇ１はＦｑ有理点Ｅ（Ｆｑ）の位数ｖの部分群、Ｇ２はＧ１とは異なるＦｑのｋ次拡大体Ｆｑｋ有理点Ｅ（Ｆｑｋ）の位数ｖの部分群、Ｇ３はＦｑのｋ次拡大体Ｆｑｋの位数ｖの乗法部分群、ｅはＧ１×Ｇ２からＧ３へのWeil pairingまたはTate pairing、ｇはＧ１の生成元、ｘは乱数であって０からｖ−１までの整数、ｈは任意長ビット列を入力としＧ１の元を出力するハッシュ関数であり、
前記証明装置は、
秘密鍵ｓｋ、公開鍵ｐｋ、メッセージｍ、署名ｓ（ただし、ｓｋ＝ｘ、ｐｋ＝ｙ＝ｇｘ、ｓ＝ｈ（ｍ）ｘ）を記録する証明用記録部と、
乱数ｒ（ただし、ｒは０からｖ−１までの整数）を生成し、Ｘ１＝ｇｒを計算し、Ｘ１を前記検証装置に送信する第１計算部と、
前記検証装置との間で、ランダムなＧ２の元ｔを共有する証明用元共有部と、
Ｘ２＝ｅ（ｈ（ｍ）ｒ，ｔ）を計算し、Ｘ２を前記検証装置に送信する第２計算部と、
σ＝ｒ＋ｃｘ  （ｍｏｄ  ｖ）を計算し、σを前記検証装置に送信する第３計算部と
を具備し、
前記検証装置は、
公開鍵ｐｋ、署名ｓ’、メッセージｍを取得する検証用取得部と、
前記証明装置との間で、ランダムなＧ２の元ｔを共有する検証用元共有部と、
乱数ｃ（ただし、ｃは０からｖ−１までの整数）を生成し、ｃを前記証明装置に送信する検証用乱数生成部と、
Ｘ１・ｙｃ＝ｇσと、Ｘ２・ｅ（ｓ’，ｔ）ｃ＝ｅ（ｈ（ｍ），ｔ）σが成り立つかを検証する検証部と
を具備する
ことを特徴とする署名システム。
【請求項３】
請求項１または２記載の署名システムであって、
ＢＣをビットコミットメント関数とし、
前記証明用元共有部は、
ランダムにＧ２の元ｔ１を選び、乱数ｕ１を用いてｗ１（ただし、ｗ１＝ＢＣ（ｔ１，ｕ１））を計算し、ｗ１を前記検証装置に送信するビットコミットメント計算手段と、
ｔ１とｕ１を前記検証装置に送信する元送信手段と、
前記検証装置から受信したｔ２を用いて、元ｔ（ただし、ｔ＝ｔ１・ｔ２）を計算する証明用元ｔ計算手段と
を有し、
前記検証用元共有部は、
ランダムにＧ２の元ｔ２を選び、ｔ２を前記証明装置に送信する元ｔ２選定手段と、
前記証明装置から受信したｗ１、ｔ１、ｕ１がｗ１＝ＢＣ（ｔ１，ｕ１）の関係であることを確認するビットコミットメント確認手段と、
前記証明装置から受信したｔ１を用いて、元ｔ（ただし、ｔ＝ｔ１・ｔ２）を計算する検証用元ｔ計算手段と
を有する
ことを特徴とする署名システム。
【請求項４】
請求項１または２記載の署名システムであって、
ＢＣをビットコミットメント関数とし、
前記検証用元共有部は、
ランダムにＧ２の元ｔ２を選び、乱数ｕ２を用いてｗ２（ただし、ｗ２＝ＢＣ（ｔ２，ｕ２））を計算し、ｗ２を前記証明装置に送信するビットコミットメント計算手段と、
ｔ２とｕ２を前記証明装置に送信する元送信手段と、
前記証明装置から受信したｔ１を用いて、元ｔ（ただし、ｔ＝ｔ１・ｔ２）を計算する検証用元ｔ計算手段と
を有し、
前記証明用元共有部は、
ランダムにＧ２の元ｔ１を選び、ｔ１を前記検証装置に送信する元ｔ１選定手段と、
前記検証装置から受信したｗ２、ｔ２、ｕ２がｗ２＝ＢＣ（ｔ２，ｕ２）の関係であることを確認するビットコミットメント確認手段と、
前記検証装置から受信したｔ２を用いて、元ｔ（ただし、ｔ＝ｔ１・ｔ２）を計算する証明用元ｔ計算手段と
を有する
ことを特徴とする署名システム。
【請求項５】
少なくとも証明装置と検証装置とを動作させる署名方法であって、
Ｇ１、Ｇ２、Ｇ３は素数ｖを位数として持つ群、ｅはＧ１×Ｇ２からＧ３への双線形写像、ｇはＧ１の生成元、ｘは乱数であって０からｖ−１までの整数、ｈは任意長ビット列を入力としＧ１の元を出力するハッシュ関数であり、
あらかじめ前記証明装置に、秘密鍵ｓｋ、公開鍵ｐｋ、メッセージｍ、署名ｓ（ただし、ｓｋ＝ｘ、ｐｋ＝ｙ＝ｇｘ、ｓ＝ｈ（ｍ）ｘ）を記録させておき、
前記検証装置が、公開鍵ｐｋ、署名ｓ’、メッセージｍを取得する検証用取得ステップと、
前記証明装置が、乱数ｒ（ただし、ｒは０からｖ−１までの整数）を生成し、Ｘ１＝ｇｒを計算し、Ｘ１を前記検証装置に送信する第１計算ステップと、
前記証明装置と前記検証装置とが、ランダムなＧ２の元ｔを共有する元共有ステップと、
前記証明装置が、Ｘ２＝ｅ（ｈ（ｍ）ｒ，ｔ）を計算し、Ｘ２を前記検証装置に送信する第２計算ステップと、
前記検証装置が、乱数ｃ（ただし、ｃは０からｖ−１までの整数）を生成し、ｃを前記証明装置に送信する検証用乱数生成ステップと、
前記証明装置が、σ＝ｒ＋ｃｘ  （ｍｏｄ  ｖ）を計算し、σを前記検証装置に送信する第３計算ステップと、
前記検証装置が、Ｘ１・ｙｃ＝ｇσと、Ｘ２・ｅ（ｓ’，ｔ）ｃ＝ｅ（ｈ（ｍ），ｔ）σが成り立つかを検証する検証ステップと
を有する署名方法。
【請求項６】
少なくとも証明装置と検証装置とを動作させる署名方法であって、
楕円曲線Ｅは要素数ｑの有限体Ｆｑ上定義された非超特異楕円曲線、楕円曲線ＥのＦｑ有理点Ｅ（Ｆｑ）の数Ｎ（Ｅ（Ｆｑ））はｖで一度だけ割れる、ｋはｖ｜（ｑｋ−１）を満たす最小の整数とし、
Ｇ１はＦｑ有理点Ｅ（Ｆｑ）の位数ｖの部分群、Ｇ２はＧ１とは異なるＦｑのｋ次拡大体Ｆｑｋ有理点Ｅ（Ｆｑｋ）の位数ｖの部分群、Ｇ３はＦｑのｋ次拡大体Ｆｑｋの位数ｖの乗法部分群、ｅはＧ１×Ｇ２からＧ３へのWeil pairingまたはTate pairing、ｇはＧ１の生成元、ｘは乱数であって０からｖ−１までの整数、ｈは任意長ビット列を入力としＧ１の元を出力するハッシュ関数であり、
あらかじめ前記証明装置に、秘密鍵ｓｋ、公開鍵ｐｋ、メッセージｍ、署名ｓ（ただし、ｓｋ＝ｘ、ｐｋ＝ｙ＝ｇｘ、ｓ＝ｈ（ｍ）ｘ）を記録させておき、
前記検証装置が、公開鍵ｐｋ、署名ｓ’、メッセージｍを取得する検証用取得ステップと、
前記証明装置が、乱数ｒ（ただし、ｒは０からｖ−１までの整数）を生成し、Ｘ１＝ｇｒを計算し、Ｘ１を前記検証装置に送信する第１計算ステップと、
前記証明装置と前記検証装置とが、ランダムなＧ２の元ｔを共有する元共有ステップと、
前記証明装置が、Ｘ２＝ｅ（ｈ（ｍ）ｒ，ｔ）を計算し、Ｘ２を前記検証装置に送信する第２計算ステップと、
前記検証装置が、乱数ｃ（ただし、ｃは０からｖ−１までの整数）を生成し、ｃを前記証明装置に送信する検証用乱数生成ステップと、
前記証明装置が、σ＝ｒ＋ｃｘ  （ｍｏｄ  ｖ）を計算し、σを前記検証装置に送信する第３計算ステップと、
前記検証装置が、Ｘ１・ｙｃ＝ｇσと、Ｘ２・ｅ（ｓ’，ｔ）ｃ＝ｅ（ｈ（ｍ），ｔ）σが成り立つかを検証する検証ステップと
を有する署名方法。
【請求項７】
請求項５または６記載の署名方法であって、
ＢＣをビットコミットメント関数とし、
前記元共有ステップは、
前記証明装置が、ランダムにＧ２の元ｔ１を選び、乱数ｕ１を用いてｗ１（ただし、ｗ１＝ＢＣ（ｔ１，ｕ１））を計算し、ｗ１を前記検証装置に送信するビットコミットメント計算サブステップと、
前記検証装置が、ランダムにＧ２の元ｔ２を選び、ｔ２を前記証明装置に送信する元ｔ２選定サブステップと、
前記証明装置が、ｔ１とｕ１を前記検証装置に送信する元送信サブステップと、
前記検証装置が、前記証明装置から受信したｗ１、ｔ１、ｕ１がｗ１＝ＢＣ（ｔ１，ｕ１）の関係であることを確認するビットコミットメント確認サブステップと、
前記証明装置が、前記検証装置から受信したｔ２を用いて、元ｔ（ただし、ｔ＝ｔ１・ｔ２）を計算する証明用元ｔ計算サブステップと、
前記検証装置が、前記証明装置から受信したｔ１を用いて、元ｔ（ただし、ｔ＝ｔ１・ｔ２）を計算する検証用元ｔ計算サブステップと
を有する
ことを特徴とする署名方法。
【請求項８】
請求項５または６記載の署名方法であって、
ＢＣをビットコミットメント関数とし、
前記元共有ステップは、
前記検証装置が、ランダムにＧ２の元ｔ２を選び、乱数ｕ２を用いてｗ２（ただし、ｗ２＝ＢＣ（ｔ２，ｕ２））を計算し、ｗ２を前記証明装置に送信するビットコミットメント計算サブステップと、
前記証明装置が、ランダムにＧ２の元ｔ１を選び、ｔ１を前記検証装置に送信する元ｔ１選定サブステップと、
前記検証装置が、ｔ２とｕ２を前記証明装置に送信する元送信サブステップと、
前記証明装置が、前記検証装置から受信したｗ２、ｔ２、ｕ２がｗ２＝ＢＣ（ｔ２，ｕ２）の関係であることを確認するビットコミットメント確認サブステップと、
前記検証装置が、前記証明装置から受信したｔ１を用いて、元ｔ（ただし、ｔ＝ｔ１・ｔ２）を計算する検証用元ｔ計算サブステップと、
前記証明装置が、前記検証装置から受信したｔ２を用いて、元ｔ（ただし、ｔ＝ｔ１・ｔ２）を計算する証明用元ｔ計算サブステップと
を有する
ことを特徴とする署名方法。
【請求項９】
検証装置との間で署名検証を行うための証明装置であって、
Ｇ１、Ｇ２、Ｇ３は素数ｖを位数として持つ群、ｅはＧ１×Ｇ２からＧ３への双線形写像、ｇはＧ１の生成元、ｘは乱数であって０からｖ−１までの整数、ｈは任意長ビット列を入力としＧ１の元を出力するハッシュ関数であり、
秘密鍵ｓｋ、公開鍵ｐｋ、メッセージｍ、署名ｓ（ただし、ｓｋ＝ｘ、ｐｋ＝ｇｘ、ｓ＝ｈ（ｍ）ｘ）を記録する証明用記録部と、
乱数ｒ（ただし、ｒは０からｖ−１までの整数）を生成し、Ｘ１＝ｇｒを計算し、Ｘ１を前記検証装置に送信する第１計算部と、
前記検証装置との間で、ランダムなＧ２の元ｔを共有する証明用元共有部と、
Ｘ２＝ｅ（ｈ（ｍ）ｒ，ｔ）を計算し、Ｘ２を前記検証装置に送信する第２計算部と、
前記検証装置から受信した乱数ｃ（ただし、ｃは０からｖ−１までの整数）を用いて、σ＝ｒ＋ｃｘ  （ｍｏｄ  ｖ）を計算し、σを前記検証装置に送信する第３計算部と
を備える証明装置。
【請求項１０】
検証装置との間で署名検証を行うための証明装置であって、
楕円曲線Ｅは要素数ｑの有限体Ｆｑ上定義された非超特異楕円曲線、楕円曲線ＥのＦｑ有理点Ｅ（Ｆｑ）の数Ｎ（Ｅ（Ｆｑ））はｖで一度だけ割れる、ｋはｖ｜（ｑｋ−１）を満たす最小の整数とし、
Ｇ１はＦｑ有理点Ｅ（Ｆｑ）の位数ｖの部分群、Ｇ２はＧ１とは異なるＦｑのｋ次拡大体Ｆｑｋ有理点Ｅ（Ｆｑｋ）の位数ｖの部分群、Ｇ３はＦｑのｋ次拡大体Ｆｑｋの位数ｖの乗法部分群、ｅはＧ１×Ｇ２からＧ３へのWeil pairingまたはTate pairing、ｇはＧ１の生成元、ｘは乱数であって０からｖ−１までの整数、ｈは任意長ビット列を入力としＧ１の元を出力するハッシュ関数であり、
秘密鍵ｓｋ、公開鍵ｐｋ、メッセージｍ、署名ｓ（ただし、ｓｋ＝ｘ、ｐｋ＝ｇｘ、ｓ＝ｈ（ｍ）ｘ）を記録する証明用記録部と、
乱数ｒ（ただし、ｒは０からｖ−１までの整数）を生成し、Ｘ１＝ｇｒを計算し、Ｘ１を前記検証装置に送信する第１計算部と、
前記検証装置との間で、ランダムなＧ２の元ｔを共有する証明用元共有部と、
Ｘ２＝ｅ（ｈ（ｍ）ｒ，ｔ）を計算し、Ｘ２を前記検証装置に送信する第２計算部と、
前記検証装置から受信した乱数ｃ（ただし、ｃは０からｖ−１までの整数）を用いて、σ＝ｒ＋ｃｘ  （ｍｏｄ  ｖ）を計算し、σを前記検証装置に送信する第３計算部と
を備える証明装置。
【請求項１１】
請求項９または１０記載の証明装置であって、
ＢＣをビットコミットメント関数とし、
前記証明用元共有部は、
ランダムにＧ２の元ｔ１を選び、乱数ｕ１を用いてｗ１（ただし、ｗ１＝ＢＣ（ｔ１，ｕ１））を計算し、ｗ１を前記検証装置に送信するビットコミットメント計算手段と、
ｔ１とｕ１を前記検証装置に送信する元送信手段と、
前記検証装置から受信したｔ２を用いて、元ｔ（ただし、ｔ＝ｔ１・ｔ２）を計算する証明用元ｔ計算手段と
を有することを特徴とする証明装置。
【請求項１２】
請求項９または１０記載の証明装置であって、
ＢＣをビットコミットメント関数とし、
前記証明用元共有部は、
ランダムにＧ２の元ｔ１を選び、ｔ１を前記検証装置に送信する元ｔ１選定手段と、
前記検証装置から受信したｗ２、ｔ２、ｕ２がｗ２＝ＢＣ（ｔ２，ｕ２）の関係であることを確認するビットコミットメント確認手段と、
前記検証装置から受信したｔ２を用いて、元ｔ（ただし、ｔ＝ｔ１・ｔ２）を計算する証明用元ｔ計算手段と
を有することを特徴とする証明装置。
【請求項１３】
証明装置との間で署名検証を行うための検証装置であって、
Ｇ１、Ｇ２、Ｇ３は素数ｖを位数として持つ群、ｅはＧ１×Ｇ２からＧ３への双線形写像、ｇはＧ１の生成元、ｘは乱数であって０からｖ−１までの整数、ｈは任意長ビット列を入力としＧ１の元を出力するハッシュ関数であり、
公開鍵ｐｋ、署名ｓ’、メッセージｍ（ただし、ｐｋ＝ｙ＝ｇｘ）を取得する検証用取得部と、
前記証明装置との間で、ランダムなＧ２の元ｔを共有する検証用元共有部と、
乱数ｃ（ただし、ｃは０からｖ−１までの整数）を生成し、ｃを前記証明装置に送信する検証用乱数生成部と、
前記証明装置から受信したＸ１（ただし、Ｘ１＝ｇｒであり、ｒは乱数であって０からｖ−１までの整数）とＸ２（ただし、Ｘ２＝ｅ（ｈ（ｍ）ｒ，ｔ））とσ（ただし、σ＝ｒ＋ｃｘ  （ｍｏｄ  ｖ））とを用いて、Ｘ１・ｙｃ＝ｇσと、Ｘ２・ｅ（ｓ’，ｔ）ｃ＝ｅ（ｈ（ｍ），ｔ）σが成り立つかを検証する検証部と
を備える検証装置。
【請求項１４】
証明装置との間で署名検証を行うための検証装置であって、
楕円曲線Ｅは要素数ｑの有限体Ｆｑ上定義された非超特異楕円曲線、楕円曲線ＥのＦｑ有理点Ｅ（Ｆｑ）の数Ｎ（Ｅ（Ｆｑ））はｖで一度だけ割れる、ｋはｖ｜（ｑｋ−１）を満たす最小の整数とし、
Ｇ１はＦｑ有理点Ｅ（Ｆｑ）の位数ｖの部分群、Ｇ２はＧ１とは異なるＦｑのｋ次拡大体Ｆｑｋ有理点Ｅ（Ｆｑｋ）の位数ｖの部分群、Ｇ３はＦｑのｋ次拡大体Ｆｑｋの位数ｖの乗法部分群、ｅはＧ１×Ｇ２からＧ３へのWeil pairingまたはTate pairing、ｇはＧ１の生成元、ｘは乱数であって０からｖ−１までの整数、ｈは任意長ビット列を入力としＧ１の元を出力するハッシュ関数であり、
公開鍵ｐｋ、署名ｓ’、メッセージｍ（ただし、ｐｋ＝ｙ＝ｇｘ）を取得する検証用取得部と、
前記証明装置との間で、ランダムなＧ２の元ｔを共有する検証用元共有部と、
乱数ｃ（ただし、ｃは０からｖ−１までの整数）を生成し、ｃを前記証明装置に送信する検証用乱数生成部と、
前記証明装置から受信したＸ１（ただし、Ｘ１＝ｇｒであり、ｒは乱数であって０からｖ−１までの整数）とＸ２（ただし、Ｘ２＝ｅ（ｈ（ｍ）ｒ，ｔ））とσ（ただし、σ＝ｒ＋ｃｘ  （ｍｏｄ  ｖ））とを用いて、Ｘ１・ｙｃ＝ｇσと、Ｘ２・ｅ（ｓ’，ｔ）ｃ＝ｅ（ｈ（ｍ），ｔ）σが成り立つかを検証する検証部と
を備える検証装置。
【請求項１５】
請求項１３または１４記載の検証装置であって、
ＢＣをビットコミットメント関数とし、
前記検証用元共有部は、
ランダムにＧ２の元ｔ２を選び、ｔ２を前記証明装置に送信する元ｔ２選定手段と、
前記証明装置から受信したｗ１、ｔ１、ｕ１がｗ１＝ＢＣ（ｔ１，ｕ１）の関係であることを確認するビットコミットメント確認手段と、
前記証明装置から受信したｔ１を用いて、元ｔ（ただし、ｔ＝ｔ１・ｔ２）を計算する検証用元ｔ計算手段と
を有することを特徴とする検証装置。
【請求項１６】
請求項１３または１４記載の検証装置であって、
ＢＣをビットコミットメント関数とし、
前記検証用元共有部は、
ランダムにＧ２の元ｔ２を選び、乱数ｕ２を用いてｗ２（ただし、ｗ２＝ＢＣ（ｔ２，ｕ２））を計算し、ｗ２を前記証明装置に送信するビットコミットメント計算手段と、
ｔ２とｕ２を前記証明装置に送信する元送信手段と、
前記証明装置から受信したｔ１を用いて、元ｔ（ただし、ｔ＝ｔ１・ｔ２）を計算する検証用元ｔ計算手段と
を有することを特徴とする検証装置。
【請求項１７】
検証装置との間で署名検証を行うための証明装置を動作させる証明方法であって、
Ｇ１、Ｇ２、Ｇ３は素数ｖを位数として持つ群、ｅはＧ１×Ｇ２からＧ３への双線形写像、ｇはＧ１の生成元、ｘは乱数であって０からｖ−１までの整数、ｈは任意長ビット列を入力としＧ１の元を出力するハッシュ関数であり、
あらかじめ証明用記録部に、秘密鍵ｓｋ、公開鍵ｐｋ、メッセージｍ、署名ｓ（ただし、ｓｋ＝ｘ、ｐｋ＝ｇｘ、ｓ＝ｈ（ｍ）ｘ）を記録させておき、
第１計算部が、乱数ｒ（ただし、ｒは０からｖ−１までの整数）を生成し、Ｘ１＝ｇｒを計算し、Ｘ１を前記検証装置に送信する第１計算ステップと、
証明用元共有部が、前記検証装置との間で、ランダムなＧ２の元ｔを共有する証明用元共有ステップと、
第２計算部が、Ｘ２＝ｅ（ｈ（ｍ）ｒ，ｔ）を計算し、Ｘ２を前記検証装置に送信する第２計算ステップと、
第３計算部が、前記検証装置から受信した乱数ｃ（ただし、ｃは０からｖ−１までの整数）を用いて、σ＝ｒ＋ｃｘ  （ｍｏｄ  ｖ）を計算し、σを前記検証装置に送信する第３計算ステップと
を有する証明方法。
【請求項１８】
検証装置との間で署名検証を行うための証明装置を動作させる証明方法であって、
楕円曲線Ｅは要素数ｑの有限体Ｆｑ上定義された非超特異楕円曲線、楕円曲線ＥのＦｑ有理点Ｅ（Ｆｑ）の数Ｎ（Ｅ（Ｆｑ））はｖで一度だけ割れる、ｋはｖ｜（ｑｋ−１）を満たす最小の整数とし、
Ｇ１はＦｑ有理点Ｅ（Ｆｑ）の位数ｖの部分群、Ｇ２はＧ１とは異なるＦｑのｋ次拡大体Ｆｑｋ有理点Ｅ（Ｆｑｋ）の位数ｖの部分群、Ｇ３はＦｑのｋ次拡大体Ｆｑｋの位数ｖの乗法部分群、ｅはＧ１×Ｇ２からＧ３へのWeil pairingまたはTate pairing、ｇはＧ１の生成元、ｘは乱数であって０からｖ−１までの整数、ｈは任意長ビット列を入力としＧ１の元を出力するハッシュ関数であり、
あらかじめ証明用記録部に、秘密鍵ｓｋ、公開鍵ｐｋ、メッセージｍ、署名ｓ（ただし、ｓｋ＝ｘ、ｐｋ＝ｇｘ、ｓ＝ｈ（ｍ）ｘ）を記録させておき、
第１計算部が、乱数ｒ（ただし、ｒは０からｖ−１までの整数）を生成し、Ｘ１＝ｇｒを計算し、Ｘ１を前記検証装置に送信する第１計算ステップと、
証明用元共有部が、前記検証装置との間で、ランダムなＧ２の元ｔを共有する証明用元共有ステップと、
第２計算部が、Ｘ２＝ｅ（ｈ（ｍ）ｒ，ｔ）を計算し、Ｘ２を前記検証装置に送信する第２計算ステップと、
第３計算部が、前記検証装置から受信した乱数ｃ（ただし、ｃは０からｖ−１までの整数）を用いて、σ＝ｒ＋ｃｘ  （ｍｏｄ  ｖ）を計算し、σを前記検証装置に送信する第３計算ステップと
を有する証明方法。
【請求項１９】
請求項１７または１８記載の証明方法であって、
ＢＣをビットコミットメント関数とし、
前記証明用元共有ステップは、
ランダムにＧ２の元ｔ１を選び、乱数ｕ１を用いてｗ１（ただし、ｗ１＝ＢＣ（ｔ１，ｕ１））を計算し、ｗ１を前記検証装置に送信するビットコミットメント計算サブステップと、
ｔ１とｕ１を前記検証装置に送信する元送信サブステップと、
前記検証装置から受信したｔ２を用いて、元ｔ（ただし、ｔ＝ｔ１・ｔ２）を計算する証明用元ｔ計算サブステップと
を有することを特徴とする証明方法。
【請求項２０】
請求項１７または１８記載の証明方法であって、
ＢＣをビットコミットメント関数とし、
前記証明用元共有ステップは、
ランダムにＧ２の元ｔ１を選び、ｔ１を前記検証装置に送信する元ｔ１選定サブステップと、
前記検証装置から受信したｗ２、ｔ２、ｕ２がｗ２＝ＢＣ（ｔ２，ｕ２）の関係であることを確認するビットコミットメント確認サブステップと、
前記検証装置から受信したｔ２を用いて、元ｔ（ただし、ｔ＝ｔ１・ｔ２）を計算する証明用元ｔ計算サブステップと
を有することを特徴とする証明方法。
【請求項２１】
証明装置との間で署名検証を行うための検証装置を動作させる検証方法であって、
Ｇ１、Ｇ２、Ｇ３は素数ｖを位数として持つ群、ｅはＧ１×Ｇ２からＧ３への双線形写像、ｇはＧ１の生成元、ｘは乱数であって０からｖ−１までの整数、ｈは任意長ビット列を入力としＧ１の元を出力するハッシュ関数であり、
検証用取得部が、公開鍵ｐｋ、署名ｓ’、メッセージｍ（ただし、ｐｋ＝ｙ＝ｇｘ）を取得する検証用取得ステップと、
検証用元共有部が、前記証明装置との間で、ランダムなＧ２の元ｔを共有する検証用元共有ステップと、
検証用乱数生成部が、乱数ｃ（ただし、ｃは０からｖ−１までの整数）を生成し、ｃを前記証明装置に送信する検証用乱数生成ステップと、
検証部が、前記証明装置から受信したＸ１（ただし、Ｘ１＝ｇｒであり、ｒは乱数であって０からｖ−１までの整数）とＸ２（ただし、Ｘ２＝ｅ（ｈ（ｍ）ｒ，ｔ））とσ（ただし、σ＝ｒ＋ｃｘ  （ｍｏｄ  ｖ））とを用いて、Ｘ１・ｙｃ＝ｇσと、Ｘ２・ｅ（ｓ’，ｔ）ｃ＝ｅ（ｈ（ｍ），ｔ）σが成り立つかを検証する検証ステップと
を有する検証方法。
【請求項２２】
証明装置との間で署名検証を行うための検証装置を動作させる検証方法であって、
楕円曲線Ｅは要素数ｑの有限体Ｆｑ上定義された非超特異楕円曲線、楕円曲線ＥのＦｑ有理点Ｅ（Ｆｑ）の数Ｎ（Ｅ（Ｆｑ））はｖで一度だけ割れる、ｋはｖ｜（ｑｋ−１）を満たす最小の整数とし、
Ｇ１はＦｑ有理点Ｅ（Ｆｑ）の位数ｖの部分群、Ｇ２はＧ１とは異なるＦｑのｋ次拡大体Ｆｑｋ有理点Ｅ（Ｆｑｋ）の位数ｖの部分群、Ｇ３はＦｑのｋ次拡大体Ｆｑｋの位数ｖの乗法部分群、ｅはＧ１×Ｇ２からＧ３へのWeil pairingまたはTate pairing、ｇはＧ１の生成元、ｘは乱数であって０からｖ−１までの整数、ｈは任意長ビット列を入力としＧ１の元を出力するハッシュ関数であり、
検証用取得部が、公開鍵ｐｋ、署名ｓ’、メッセージｍ（ただし、ｐｋ＝ｙ＝ｇｘ）を取得する検証用取得ステップと、
検証用元共有部が、前記証明装置との間で、ランダムなＧ２の元ｔを共有する検証用元共有ステップと、
検証用乱数生成部が、乱数ｃ（ただし、ｃは０からｖ−１までの整数）を生成し、ｃを前記証明装置に送信する検証用乱数生成ステップと、
検証部が、前記証明装置から受信したＸ１（ただし、Ｘ１＝ｇｒであり、ｒは乱数であって０からｖ−１までの整数）とＸ２（ただし、Ｘ２＝ｅ（ｈ（ｍ）ｒ，ｔ））とσ（ただし、σ＝ｒ＋ｃｘ  （ｍｏｄ  ｖ））とを用いて、Ｘ１・ｙｃ＝ｇσと、Ｘ２・ｅ（ｓ’，ｔ）ｃ＝ｅ（ｈ（ｍ），ｔ）σが成り立つかを検証する検証ステップと
を有する検証方法。
【請求項２３】
請求項２１または２２記載の検証方法であって、
ＢＣをビットコミットメント関数とし、
前記検証用元共有ステップは、
ランダムにＧ２の元ｔ２を選び、ｔ２を前記証明装置に送信する元ｔ２選定サブステップと、
前記証明装置から受信したｗ１、ｔ１、ｕ１がｗ１＝ＢＣ（ｔ１，ｕ１）の関係であることを確認するビットコミットメント確認サブステップと、
前記証明装置から受信したｔ１を用いて、元ｔ（ただし、ｔ＝ｔ１・ｔ２）を計算する検証用元ｔ計算サブステップと
を有することを特徴とする検証方法。
【請求項２４】
請求項２１または２２記載の検証方法であって、
ＢＣをビットコミットメント関数とし、
前記検証用元共有ステップは、
ランダムにＧ２の元ｔ２を選び、乱数ｕ２を用いてｗ２（ただし、ｗ２＝ＢＣ（ｔ２，ｕ２））を計算し、ｗ２を前記証明装置に送信するビットコミットメント計算サブステップと、
ｔ２とｕ２を前記証明装置に送信する元送信サブステップと、
前記証明装置から受信したｔ１を用いて、元ｔ（ただし、ｔ＝ｔ１・ｔ２）を計算する検証用元ｔ計算サブステップと
を有することを特長とする検証方法。
【請求項２５】
請求項９〜１６のいずれかに記載された装置としてコンピュータを動作させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の応用技術に関するものであり、署名者の協力があってはじめて署名の正当性検証あるいは偽造署名を否認できる否認不可署名用の署名システム、署名方法、証明装置、検証装置、証明方法、検証方法、プログラムに関する。
【背景技術】
【０００２】
否認不可署名の従来技術には、非特許文献１に示された技術があった。
【非特許文献１】David Chaum, Hans Van Antwerpen, “Undeniable Signatures”, CRYPTO 1989, pp.212-216.
【発明の開示】
【発明が解決しようとする課題】
【０００３】
非特許文献１の技術では、署名の正当性検証と偽造署名の否認を別々の手続で行う必要があった。また、正当性検証と否認を効率的にし、署名のデータ長を短くするために、楕円曲線の群を用いていなかった。
【０００４】
本発明の目的は、署名の正当性検証と偽造署名の否認を同一の手続で行えるようにすることと、署名のデータ長を短くするために、楕円曲線の群を適用できるようにすることである。
【課題を解決するための手段】
【０００５】
本発明の署名システムは、少なくとも証明装置と検証装置とを備える。この他に、当該署名システムの中に、例えば鍵生成装置と署名生成装置を備えてもよい。まず、Ｇ１、Ｇ２、Ｇ３は素数ｖを位数として持つ群、ｅはＧ１×Ｇ２からＧ３への双線形写像、ｇはＧ１の生成元、ｘは乱数であって０からｖ−１までの整数、ｈは任意長ビット列を入力としＧ１の元を出力するハッシュ関数とする。
【０００６】
鍵生成装置と署名生成装置が当該署名システムの中に備えられているか、外部にあるかに関係なく、鍵生成装置が秘密鍵ｓｋと公開鍵ｐｋを生成し、署名生成装置がメッセージｍから署名ｓを生成する。ただし、ｓｋ＝ｘ、ｐｋ＝ｇｘ、ｓ＝ｈ（ｍ）ｘである。そして、あらかじめ秘密鍵ｓｋ、公開鍵ｐｋ、メッセージｍ、署名ｓが証明装置に記録される。
【０００７】
証明装置は、証明用記録部、第１計算部、証明用元共有部、第２計算部、第３計算部を具備する。証明用記録部は、秘密鍵ｓｋ、公開鍵ｐｋ、メッセージｍ、署名ｓを記録する。第１計算部は、乱数ｒ（ただし、ｒは０からｖ−１までの整数）を生成し、Ｘ１＝ｇｒを計算し、Ｘ１を検証装置に送信する。証明用元共有部は、検証装置との間で、ランダムなＧ２の元ｔを共有する。第２計算部は、Ｘ２＝ｅ（ｈ（ｍ）ｒ，ｔ）を計算し、Ｘ２を検証装置に送信する。第３計算部は、σ＝ｒ＋ｃｘ  （ｍｏｄ  ｖ）を計算し、σを検証装置に送信する。
【０００８】
検証装置は、検証用取得部、検証用元共有部、検証用乱数生成部、検証部を具備する。検証用取得部は、公開鍵ｐｋ、署名ｓ’、メッセージｍを取得する。検証用元共有部は、  証明装置との間で、ランダムなＧ２の元ｔを共有する。検証用乱数生成部は、乱数ｃ（ただし、ｃは０からｖ−１までの整数）を生成し、ｃを証明装置に送信する。検証部は、Ｘ１・ｙｃ＝ｇσと、Ｘ２・ｅ（ｓ’，ｔ）ｃ＝ｅ（ｈ（ｍ），ｔ）σが成り立つかを検証する。両方の式が成り立つ場合には署名検証であることを示す情報（例えば“１”）を出力し、そうでなければ偽造署名否認であることを示す情報（例えば“０”）を出力する。
【０００９】
また、楕円曲線Ｅは要素数ｑの有限体Ｆｑ上定義された非超特異楕円曲線、楕円曲線ＥのＦｑ有理点Ｅ（Ｆｑ）の数Ｎ（Ｅ（Ｆｑ））はｖで一度だけ割れる、ｋはｖ｜（ｑｋ−１）を満たす最小の整数とする。そして、Ｇ１はＦｑ有理点Ｅ（Ｆｑ）の位数ｖの部分群、Ｇ２はＧ１とは異なるＦｑのｋ次拡大体Ｆｑｋ有理点Ｅ（Ｆｑｋ）の位数ｖの部分群、Ｇ３はＦｑのｋ次拡大体Ｆｑｋの位数ｖの乗法部分群、ｅはＧ１×Ｇ２からＧ３へのWeil pairingまたはTate pairingとしてもよい。
【発明の効果】
【００１０】
本発明の署名システムによれば、同一の手続で署名検証も偽造署名否認も行うことができる。したがって、署名検証と偽造署名否認を効率的に行うことができると共に、計算装置や計算プログラムも簡素化できる。さらに、上述のようなＧ１とＧ２を楕円曲線の有理点の成す群とし、署名ｓをＧ１の元とすることで、署名ｓのデータ長を短くできる。
【発明を実施するための最良の形態】
【００１１】
以下に、本発明の実施例を説明する。なお、同じ機能の構成部や同じ処理には同一の番号を付け、重複説明を省略する。
【実施例１】
【００１２】
図１に実施例１の署名システムの処理フローを示す。図２に署名システムの構成例を示す。署名システム１０は、鍵生成装置１００、署名生成装置２００、証明装置３００、検証装置４００で構成される。鍵生成装置１００は、鍵生成部１１０と鍵生成用記録部１９０を有する。署名生成装置２００は、署名生成用取得部２０５、署名生成部２１０、署名生成用記録部２９０を有する。証明装置３００は、証明用記録部３９０、証明用取得部３０５、第１計算部３１０、証明用元共有部３２０、第２計算部３３０、第３計算部３５０を具備する。検証装置４００は、検証用取得部４０５、検証用元共有部４２０、検証用乱数生成部４４０、検証部４６０、検証用記録部４９０を具備する。
【００１３】
まず、Ｇ１、Ｇ２、Ｇ３は素数ｖを位数として持つ群、ｅはＧ１×Ｇ２からＧ３への双線形写像、ｇはＧ１の生成元、ｘは乱数であって０からｖ−１までの整数、ｈは任意長ビット列を入力としＧ１の元を出力するハッシュ関数とする。ただし、ｅがＧ１×Ｇ２からＧ３への双線形写像であるとは、ｘがＧ１の元、ｙがＧ２の元の場合に、ｅ（ｘ，ｙ）がＧ３の元であり、
ｅ（ｘ１・ｘ２，ｙ）＝ｅ（ｘ１，ｙ）・ｅ（ｘ２，ｙ）
ｅ（ｘ，ｙ１・ｙ２）＝ｅ（ｘ，ｙ１）・ｅ（ｘ，ｙ２）
を満たすことである。なお、双線形写像に関する一般的な内容は、I.F. Blake, N.P. Smart, G. Seroussi,“楕円曲線暗号”, ピアソン・エヂュケーション, III.５章などに記載されている。
【００１４】
鍵生成装置１００の鍵生成部１１０は、乱数ｘ（ただし、ｘは０からｖ−１までの整数）を生成し、秘密鍵ｓｋ＝ｘと公開鍵ｐｋ＝ｙ＝ｇｘを、鍵生成用記録部１９０に記録すると共に送信する（Ｓ１１０）。署名生成装置２００の署名生成用取得部２０５は、秘密鍵ｓｋと公開鍵ｐｋとメッセージｍとを取得し、署名生成用記録部２９０に記録する（Ｓ２０５）。署名生成部２１０は、署名ｓ＝ｈ（ｍ）ｘを生成し、出力する（Ｓ２１０）。ここまでが鍵と署名を生成する処理であり、あらかじめ行っておいてもよい。
【００１５】
証明装置３００の証明用取得部３０５は、秘密鍵ｓｋ、公開鍵ｐｋ、メッセージｍ、署名ｓを取得し、証明用記録部３９０に、秘密鍵ｓｋ、公開鍵ｐｋ、メッセージｍ、署名ｓを記録する（Ｓ３０５）。また、検証装置４００の検証用取得部４０５は、公開鍵ｐｋ、署名ｓ’、メッセージｍを取得し、検証用記録部４９０に記録する（Ｓ４０５）。
【００１６】
証明装置３００の第１計算部３１０は、乱数ｒ（ただし、ｒは０からｖ−１までの整数）を生成し、Ｘ１＝ｇｒを計算し、Ｘ１を検証装置４００に送信する（Ｓ３１０）。証明装置３００の証明用元共有部３２０と、検証装置４００の検証用元共有部４２０とは、ランダムなＧ２の元ｔを共有する（Ｓ３２０、Ｓ４２０）。証明装置３００の第２計算部３３０は、Ｘ２＝ｅ（ｈ（ｍ）ｒ，ｔ）を計算し、Ｘ２を検証装置４００に送信する（Ｓ３３０）。検証装置４００の検証用乱数生成部４４０は、乱数ｃ（ただし、ｃは０からｖ−１までの整数）を生成し、ｃを証明装置３００に送信する（Ｓ４４０）。証明装置３００の第３計算部３５０は、σ＝ｒ＋ｃｘ  （ｍｏｄ  ｖ）を計算し、σを検証装置４００に送信する（Ｓ３５０）。検証装置４００の検証部４６０は、Ｘ１・ｙｃ＝ｇσと、Ｘ２・ｅ（ｓ’，ｔ）ｃ＝ｅ（ｈ（ｍ），ｔ）σが成り立つかを検証する。両方の式が成り立つ場合には署名検証であることを示す情報（例えば“１”）を出力し、そうでなければ偽造署名否認であることを示す情報（例えば“０”）を出力する（Ｓ４６０）。
【００１７】
次に、なぜステップＳ４６０の２つの式が成り立てばよいのかを説明する。署名ｓ’が正しい否認不可署名（署名ｓと同じ）ならばｓ’＝ｓである。また、上述の処理を行っているので、
ｓ’＝ｈ（ｍ）ｘ
ｙ＝ｇｘ
Ｘ１＝ｇｒ
Ｘ２＝ｅ（ｈ（ｍ）ｒ，ｔ）
σ＝ｒ＋ｃｘ  （ｍｏｄ  ｖ）
が成り立つ。これらのことから、１つ目の式の左辺は、
Ｘ１・ｙｃ＝ｇｒ・（ｇｘ）ｃ
＝ｇｒ＋ｃｘ
＝ｇσ
のように変形でき、１つ目の式が成り立つことが分かる。さらに、ｅが双線形写像であることから、２つ目の式の左辺は、
Ｘ２・ｅ（ｓ’，ｔ）ｃ＝ｅ（ｈ（ｍ）ｒ，ｔ）・ｅ（ｈ（ｍ）ｘ，ｔ）ｃ
＝ｅ（ｈ（ｍ），ｔ）ｒ・ｅ（ｈ（ｍ），ｔ）ｃｘ
＝ｅ（ｈ（ｍ），ｔ）ｒ＋ｃｘ
＝ｅ（ｈ（ｍ），ｔ）σ
のように変形でき、２つ目の式が成り立つことが分かる。したがって、ステップＳ４６０の２つの式が成り立つかを確認すればよい。
【００１８】
実施例１の署名システムによれば、同一の手続で署名検証も偽造署名否認も行うことができる。したがって、署名検証と偽造署名否認を効率的に行うことができると共に、計算装置や計算プログラムも簡素化できる。
【００１９】
また、実施例１では、鍵生成装置１００、署名生成装置２００、証明装置３００を別々の装置として示したが、一体化された証明装置３０でもよい。この場合は、鍵生成用記録部１９０、署名生成用取得部２０５、署名生成用記録部２９０、証明用取得部３０５は不要となる。鍵生成部１１０で生成された秘密鍵ｓｋと公開鍵ｐｋ、メッセージｍ、署名生成部２１０で生成された署名ｓは、直接、証明用記録部３９０に記録すればよい。
【００２０】
なお、署名システム１０は、少なくとも証明装置３００と検証装置４００を含めばよい。この場合には、鍵生成装置１００と署名生成装置２００は、署名システムの外部にあることになる。このときにも、鍵生成装置１００が秘密鍵ｓｋと公開鍵ｐｋを生成し、署名生成装置２００がメッセージｍから署名ｓを生成する。ただし、ｓｋ＝ｘ、ｐｋ＝ｇｘ、ｓ＝ｈ（ｍ）ｘである。そして、あらかじめ秘密鍵ｓｋ、公開鍵ｐｋ、メッセージｍ、署名ｓが証明装置３００の証明用記録部３９０に記録される。
【実施例２】
【００２１】
実施例２では、Ｇ１、Ｇ２を有限体上で定義された楕円関数の有理点の成す群、Ｇ３を有限体の乗法部分群とすることで、署名ｓのデータ長を短くする。
【００２２】
楕円曲線Ｅは要素数ｑの有限体Ｆｑ上定義された非超特異楕円曲線、楕円曲線ＥのＦｑ有理点Ｅ（Ｆｑ）の数Ｎ（Ｅ（Ｆｑ））はｖで一度だけ割れる、ｋはｖ｜（ｑｋ−１）を満たす最小の整数とする。そして、Ｇ１をＦｑ有理点Ｅ（Ｆｑ）の位数ｖの部分群とする。このとき、Ｆｑのｋ次拡大体Ｆｑｋを考えると、Ｆｑｋ有理点Ｅ（Ｆｑｋ）の数Ｎ（Ｅ（Ｆｑｋ））はｖで２度以上割れる。つまり、Ｇ１とは異なるＦｑｋ有理点Ｅ（Ｆｑｋ）の位数ｖの部分群が存在する。そこで、Ｇ２をＧ１とは異なるＦｑｋ有理点Ｅ（Ｆｑｋ）の位数ｖの部分群とする。そして、Ｇ３をＦｑのｋ次拡大体Ｆｑｋの位数ｖの乗法部分群とする。また、ｅをＧ１×Ｇ２からＧ３へのWeil pairingまたはTate pairingとする。なお、楕円曲線、Weil pairing、Tate pairing についての一般的な内容は、I.F. Blake, N.P. Smart, G. Seroussi,“楕円曲線暗号”, ピアソン・エヂュケーション, III.５章などに記載されている。
【００２３】
また、ｇがＧ１の生成元、ｘが乱数であって０からｖ−１までの整数、ｈが任意長ビット列を入力としＧ１の元を出力するハッシュ関数であることは実施例１と同じである。
【００２４】
このように定めたＧ１、Ｇ２、Ｇ３、ｅを用いて実施例１と同じ処理（ステップＳ１１０〜Ｓ４６０）を行えば、署名ｓのデータ長を短くした上に、実施例１と同じ効果も得ることができる。
【実施例３】
【００２５】
実施例３では、実施例１および実施例２のステップＳ３２０、Ｓ４２０の具体的な処理フローを示す。ステップＳ３２０、Ｓ４２０では、証明装置３００の証明用元共有部３２０と、検証装置４００の検証用元共有部４２０とは、ランダムなＧ２の元ｔを共有する。この元ｔの共有のために、証明装置３００の証明用元共有部３２０と、検証装置４００の検証用元共有部４２０とは、ビットコミットメント関数ＢＣを用いて、図３に示す処理フローを行う。また、図４に証明用元共有部３２０の機能構成例を、図５に検証用元共有部４２０の機能構成例を示す。
【００２６】
ビットコミットメントとは、入力メッセージｄ、入力乱数ｕに対して値ＢＣ（ｄ，ｕ）を対応させるものである。そして、値ＢＣ（ｄ，ｕ）が何れの入力メッセージにより計算されたかを判定することができず、また、値ｗ＝ＢＣ（ｄ，ｕ）に対して異なるｄ’、ｕ’を見つけて、ｗ＝ＢＣ（ｄ’，ｕ’）とすることはできない。なお、ビットコミットメントについての一般的な内容は、Douglas R. Stinson, “暗号理論の基礎”, 共立出版の１３.３章などに記載されている。
【００２７】
証明用元共有部３２０は、ビットコミットメント計算手段３２１、元送信手段３２３、証明用元ｔ計算手段３２５を備える。検証用元共有部４２０は、元ｔ２選定手段４２２、ビットコミットメント確認手段４２４、検証用元ｔ計算手段４２５を備える。
【００２８】
証明用元共有部３２０のビットコミットメント計算手段３２１は、ランダムにＧ２の元ｔ１を選び、乱数ｕ１を用いてｗ１（ただし、ｗ１＝ＢＣ（ｔ１，ｕ１））を計算し、ｗ１を検証用元共有部４２０に送信する（Ｓ３２１）。検証用元共有部４２０の元ｔ２選定手段４２２は、ランダムにＧ２の元ｔ２を選び、ｔ２を証明用元共有部３２０に送信する（Ｓ４２２）。
【００２９】
証明用元共有部３２０の元送信手段３２３は、ｔ１とｕ１を検証用元共有部４２０に送信する（Ｓ３２３）。検証用元共有部４２０のビットコミットメント確認手段４２４は、証明用元共有部３２０から受信したｗ１、ｔ１、ｕ１がｗ１＝ＢＣ（ｔ１，ｕ１）の関係であることを確認する（Ｓ４２４）。証明用元共有部３２０の証明用元ｔ計算手段３２５は、検証用元共有部４２０のから受信したｔ２を用いて、元ｔ＝ｔ１・ｔ２を計算する（Ｓ３２５）。検証用元共有部４２０の検証用元ｔ計算手段４２５は、証明用元共有部３２０から受信したｔ１を用いて、元ｔ＝ｔ１・ｔ２を計算する（Ｓ４２５）。
【００３０】
このように元ｔを共有するので、証明装置３００も検証装置４００もｔ１・ｔ２の結果であるｔの値をコントロールできないように、元ｔを証明装置３００と検証装置４００とで共有できる。
【００３１】
［変形例］
本変形例では、証明装置３００’の証明用元共有部３２０’と、検証装置４００’の検証用元共有部４２０’とは、ビットコミットメント関数ＢＣを用いて、図６に示す処理フローを行う。また、図７に証明用元共有部３２０’の機能構成例を、図８に検証用元共有部４２０’の機能構成例を示す。
【００３２】
証明用元共有部３２０’は、元ｔ１選定手段３２２、ビットコミットメント確認手段３２４、検証用元ｔ計算手段３２５を備える。検証用元共有部４２０’は、ビットコミットメント計算手段４２１、元送信手段４２３、証明用元ｔ計算手段４２５を備える。
【００３３】
検証用元共有部４２０’のビットコミットメント計算手段４２１は、ランダムにＧ２の元ｔ２を選び、乱数ｕ２を用いてｗ２（ただし、ｗ２＝ＢＣ（ｔ２，ｕ２））を計算し、ｗ２を証明用元共有部３２０に送信する（Ｓ４２１）。証明用元共有部３２０’の元ｔ１選定手段３２２は、ランダムにＧ１の元ｔ１を選び、ｔ１を検証用元共有部４２０’に送信する（Ｓ４２２）。
【００３４】
検証用元共有部４２０’の元送信手段４２３は、ｔ２とｕ２を証明用元共有部３２０’に送信する（Ｓ４２３）。証明用元共有部３２０’のビットコミットメント確認手段３２４は、検証用元共有部４２０’から受信したｗ２、ｔ２、ｒ２がｗ２＝ＢＣ（ｔ２，ｕ２）の関係であることを確認する（Ｓ３２４）。検証用元共有部４２０’の検証用元ｔ計算手段４２５は、証明用元共有部３２０’から受信したｔ１を用いて、元ｔ＝ｔ１・ｔ２を計算する（Ｓ４２５）。証明用元共有部３２０’の証明用元ｔ計算手段３２５’は、検証用元共有部４２０のから受信したｔ２を用いて、元ｔ＝ｔ１・ｔ２を計算する（Ｓ３２５）。
【００３５】
このように元ｔを共有するので、証明装置３００’も検証装置４００’もｔ１・ｔ２の結果であるｔの値をコントロールできないように、元ｔを証明装置３００と検証装置４００とで共有できる。
【００３６】
図９にコンピュータの機能構成例を示す。上述の実施例は、図９に示すコンピュータの記録部２０２０に、上記装置としてコンピュータを実行させるプログラムを読み込ませ、制御部２０１０、入力部２０３０、出力部２０４０などに動作させることで実施できる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。
【図面の簡単な説明】
【００３７】
【図１】実施例１の署名システムの処理フローを示す図。
【図２】実施例１の署名システムの構成例を示す図。
【図３】実施例３の証明用元共有部と検証用元共有部の処理フローを示す図。
【図４】実施例３の証明用元共有部の機能構成例を示す図。
【図５】実施例３の検証用元共有部の機能構成例を示す図。
【図６】実施例４の証明用元共有部と検証用元共有部の処理フローを示す図。
【図７】実施例４の証明用元共有部の機能構成例を示す図。
【図８】実施例４の検証用元共有部の機能構成例を示す図。
【図９】コンピュータの構成例を示す図。
【符号の説明】
【００３８】
１０  署名システム                      ３０  証明装置
１００  鍵生成装置                      １１０  鍵生成部
１９０  鍵生成用記録部                  ２００  署名生成装置
２０５  署名生成用取得部                ２１０  署名生成部
２９０  署名生成用記録部                ３００  証明装置
３０５  証明用取得部                    ３１０  第1計算部
３２０  証明用元共有部                  ３２１  ビットコミットメント計算手段
３２２  元ｔ１選定手段                  ３２３  元送信手段
３２４  ビットコミットメント確認手段    ３２５  証明用元ｔ計算手段
３３０  第２計算部                      ３５０  第３計算部
３９０  証明用記録部                    ４００  検証装置
４０５  検証用取得部                    ４２０  検証用元共有部
４２１  ビットコミットメント計算手段    ４２２  元ｔ２選定手段
４２３  元送信手段                      ４２４  ビットコミットメント確認手段
４２５  検証用元ｔ計算手段              ４４０  検証用乱数生成部
４６０  検証部                          ４９０  検証用記録部
【図１】
0005069157.tif 000002
【図２】
0005069157.tif 000003
【図３】
0005069157.tif 000004
【図４】
0005069157.tif 000005
【図５】
0005069157.tif 000006
【図６】
0005069157.tif 000007
【図７】
0005069157.tif 000008
【図８】
0005069157.tif 000009
【図９】
0005069157.tif 000010