(57)【要約】【課題】  閾値つき電子署名技術で、参加者が署名生成に協力したことを証明することができない。何人の参加者が証明できるのかを署名から確認できない。署名生成に協力したことを証明後に秘密鍵と公開鍵が使用できなくなる。【解決手段】あらかじめ署名者証拠を記録しておき、署名生成に協力したことを証明したい時に署名者証拠を公開し、確認する。また、署名生成に協力していない参加装置に対するダミー公開鍵を少なくとも１つ生成し、ダミー公開鍵も用いて電子署名を生成する。さらに、２種類の秘密鍵と公開鍵の組を生成し、ダミー鍵生成装置で少なくとも１つの第２の公開鍵に対するダミー公開鍵を生成する。参加装置ごとの第１の公開鍵と第２の公開鍵を利用し、第１の署名と第２の署名とを生成する。もしくは、第１の秘密鍵と関連つけられた第２の秘密鍵を用いて署名を生成し、署名を検証する。【選択図】図５０
2006203754.tif 000002
【特許請求の範囲】
【請求項１】
閾値つき電子署名システムの構成装置として電子署名を行う参加装置であって、
署名者証拠を記録する記録部と、
署名者証拠を公開する署名者証拠公開部と、
を備える参加装置。
【請求項２】
請求項１記載の参加装置であって、
第１の秘密鍵と公開鍵とを生成する第１の鍵生成部と、
署名生成に用いる第２の秘密鍵と公開鍵とを生成する第２の鍵生成部と、
を備える参加装置。
【請求項３】
請求項１記載の参加装置であって、
第１の秘密鍵と公開鍵とを生成する第１の鍵生成部と、
第1の秘密鍵から署名生成に用いる第２の秘密鍵を生成する第２の鍵生成部と、
を備える参加装置。
【請求項４】
請求項３記載の参加装置であって、
ｎ台の参加装置があり、任意のｔ台の参加装置が署名に協力した場合であって、
上記閾値つき電子署名システムを構成する参加装置の第１の公開鍵ＰＫｉ（ｉ＝１，…，ｎ）とメッセージｍから、任意長のビット列を離散対数問題の難しい加法による巡回群の元に変換するハッシュ関数Ｈを用いて
Ｑｍ＝Ｈ（ｔ，ｎ，ＰＫ１，…，ＰＫｎ，ｍ）
とし、参加装置の第１の秘密鍵ＳＫｉを用いて、
ｓｋｉ＝ＳＫｉＱｍ
として第２の秘密鍵ｓｋｉを生成する上記第２の鍵生成部と、
ｐを法とする剰余類Ｚｐから等確率でランダムに選択した１つの元を署名者証拠ｒｉとし、第１の鍵生成部で使用した離散対数問題の難しい加法による巡回群の元Ｐを用いて、
【数１】
2006203754.tif 000020
によりコミットメントａｉを生成する署名者証拠生成部と、
を備える参加装置。
【請求項５】
閾値つき電子署名システムの構成装置としてダミーの公開鍵を生成するダミー鍵生成装置であって、
少なくとも１つの署名生成に協力していない参加装置の公開鍵を生成し、当該公開鍵および公開鍵生成時に使用した離散対数問題の難しい巡回群の元を公開する計算部
を備えるダミー鍵生成装置。
【請求項６】
請求項５記載のダミー鍵生成装置であって、
ｎ台の参加装置がある場合に、署名生成に協力していない１つの参加装置の公開鍵ｐｋｎを、その他の参加装置の公開鍵ｐｋｉ（ｉ＝１，…，ｎ−１）と離散対数問題が難しい巡回群の元ｘから、
ｐｋｎ＝ｘ/ｐｋ１ｐｋ２…ｐｋｎ−１
と定める上記計算部
を備えるダミー鍵生成装置。
【請求項７】
請求項５記載のダミー鍵生成装置であって、
ｎ台の参加装置があり、任意のｔ台の参加装置が署名に協力した場合であって、ｔ≦ｔ’≦ｎの関係があるときに、
署名生成に協力していない（ｎ−ｔ’）の参加装置の公開鍵ｐｋｉ（ｉ＝ｔ'＋１，…，ｎ）を、その他の参加装置の公開鍵ｐｋｉ（ｉ＝１，…，ｔ'）と離散対数問題が難しい巡回群の元Ａ０から、（ｍｉｊ）を、
【数２】
2006203754.tif 000021
のｔ'×ｔ'行列（ｉｊ）の逆行列として、Ａｉ（ｉ＝１，…，ｔ'）を
【数３】
2006203754.tif 000022
と定め、
【数４】
2006203754.tif 000023
として生成する上記計算部
を備えるダミー鍵生成装置。
【請求項８】
２つの公開鍵を用いる閾値つき電子署名システムの構成装置として、署名に用いる第２の公開鍵を生成するダミー鍵生成装置であって、
少なくとも１つの署名生成に協力していない参加装置の第２の公開鍵を、他の参加装置の第２の公開鍵を利用して生成し、当該公開鍵および公開鍵生成時に使用した離散対数問題の難しい巡回群の元を公開する計算部
を備えるダミー鍵生成装置。
【請求項９】
請求項８記載のダミー鍵生成装置であって、
ｎ台の参加装置がある場合に、署名生成に協力していない任意の１つの参加装置に対応するダミー公開鍵ｐｋｎを、その他の参加装置の第２の公開鍵ｐｋｉ（ｉ＝１，…，ｎ−１）と離散対数問題が難しい巡回群に属する元ｘから、
ｐｋｎ＝ｘ/ｐｋ１ｐｋ２…ｐｋｎ−１
と定める上記計算部
を備えるダミー鍵生成装置。
【請求項１０】
請求項８記載のダミー鍵生成装置であって、
ｎ台の参加装置があり、任意のｔ台の参加装置が署名に協力した場合であって、ｔ≦ｔ’≦ｎの関係があるときに、
署名生成に協力していない任意の（ｎ−ｔ’）の参加装置に対応するダミー公開鍵ｐｋｉ（ｉ＝ｔ'＋１，…，ｎ）を、その他の参加装置の第２の公開鍵ｐｋｉ（ｉ＝１，…，ｔ'）と離散対数問題が難しい巡回群に属する元Ａ０から、（ｍｉｊ）を、
【数５】
2006203754.tif 000024
のｔ'×ｔ'行列（ｉｊ）の逆行列として、Ａｉ（ｉ＝１，…，ｔ'）を
【数６】
2006203754.tif 000025
と定め、
【数７】
2006203754.tif 000026
として生成する上記計算部
を備えるダミー鍵生成装置。
【請求項１１】
閾値つき電子署名システムの構成装置として電子署名を検証する署名検証装置であって、
参加装置が公開する署名者証拠を取得する情報取得部と、
署名者証拠を確認する署名者証拠確認部と、
を備える署名検証装置。
【請求項１２】
請求項１１記載の署名検証装置であって、
参加装置間の公開鍵の関係から署名者参加者数を確認する署名者参加者数確認部、
を備える署名検証装置。
【請求項１３】
請求項１２記載の署名検証装置であって、
ｎ台の参加装置がある場合に、参加装置の公開鍵ｐｋｉ（ｉ＝１，…，ｎ）と離散対数問題が難しい巡回群の元ｘから、
ｐｋ１ｐｋ２…ｐｋｎ＝ｘ
となることを確認する署名者参加者数確認部
を備える署名検証装置。
【請求項１４】
請求項１２記載の署名検証装置であって、
ｎ台の参加装置があり、任意のｔ台の参加装置が署名に協力した場合であって、ｔ≦ｔ’≦ｎの関係があるときに、
参加装置の公開鍵ｐｋｉ（ｉ＝１，…，ｎ）と離散対数問題が難しい巡回群の元Ａｉ（ｉ＝０，…，ｔ'）から、
【数８】
2006203754.tif 000027
となることを確認する署名者参加者数確認部
を備える署名検証装置。
【請求項１５】
請求項１１〜１４のいずれかに記載の署名検証装置であって、
参加者装置ごとの第１の公開鍵、第２の公開鍵を取得する上記情報取得部と、
第１の署名および第２の署名の確認を行う署名確認部
を備える署名検証装置。
【請求項１６】
請求項１１記載の署名検証装置であって、
参加装置が公開する第１の公開鍵と鍵生成に使用した離散対数問題の難しい巡回群の元、および第２の秘密鍵生成に使用した離散対数問題の難しい巡回群の元を取得する上記情報取得部と、
第２の秘密鍵生成時に使用した元を確認する元確認部と、
チャレンジと多項式とを確認する上記チャレンジ・多項式確認部と、
を備える署名検証装置。
【請求項１７】
閾値つき電子署名システムの構成装置として電子署名を生成する署名生成装置であって、
閾値つき電子署名システムを構成する参加装置ごとの第１の公開鍵と第２の公開鍵、および公開鍵生成時に使用した離散対数問題の難しい巡回群の元を取得する情報取得部と、
第１の署名と第２の署名とを生成し、第１の署名と第２の署名とを公開する計算部と、
を備える署名生成装置。
【請求項１８】
２つの秘密鍵を用いる閾値つき電子署名システムの構成装置として電子署名を生成する署名生成装置であって、
第１の秘密鍵に関連付けられた第２の秘密鍵を用いた署名を生成する計算部
を備える署名生成装置。
【請求項１９】
請求項１８記載の署名生成装置であって、
全参加装置の第１の公開鍵ＰＫｉ（ｉ＝１，…，ｎ）、第１の鍵生成と第２の鍵生成で使用された離散対数問題の難しい加法による巡回群の元Ｐと元Ｑｍを用いて、
離散対数問題の難しい加法による巡回群から等確率ランダムに選ばれた元をダミーレスポンスｅｉとし、
有限体の座標値をｐを法とする剰余類Ｚｐに変換するハッシュ関数Ｉを用いて、有限体の座標値ｙｉから、ｃｉ＝Ｉ（ｙｉ）によりダミーチャレンジｃｉを求め、
【数９】
2006203754.tif 000028
によりダミーコミットメントａｉを生成するダミー生成部
を備える署名生成装置。
【請求項２０】
閾値つき電子署名方法であって、
あらかじめ参加装置の記録部で、署名者証拠を記録しておき、
上記参加装置の署名者証拠公開部で、上記署名者証拠を公開し、
署名検証装置で、上記署名者証拠を確認する
ことを特徴とする閾値つき電子署名方法。
【請求項２１】
請求項２０記載の閾値つき電子署名方法であって、
ダミー鍵生成装置の計算部で、少なくとも１つの署名生成に協力していない参加装置の鍵生成部の代わりに公開鍵を生成し、当該公開鍵および当該ダミー鍵生成装置が使用した離散対数問題の難しい巡回群の元を公開し、
署名生成装置で、上記ダミー鍵生成装置が生成した公開鍵も用いて電子署名を生成し、
上記署名検証装置の署名者参加者数確認部で、参加装置間の公開鍵の関係から署名者参加者数を確認する
ことを特徴とする閾値つき電子署名方法。
【請求項２２】
請求項２１記載の閾値つき電子署名方法であって、
ｎ台の参加装置がある場合に、上記ダミー鍵生成装置の計算部で、署名生成に協力していない１つの参加装置の公開鍵ｐｋｎを、その他の参加装置の公開鍵ｐｋｉ（ｉ＝１，…，ｎ−１）と離散対数問題が難しい巡回群の元ｘから、
ｐｋｎ＝ｘ/ｐｋ１ｐｋ２…ｐｋｎ−１
と定め、
上記署名検証装置の署名者参加者数確認部で、公開鍵ｐｋｉ（ｉ＝１，…，ｎ）と離散対数問題が難しい巡回群の元ｘから、
ｐｋ１ｐｋ２…ｐｋｎ＝ｘ
となることを確認する
ことを特徴とする閾値つき電子署名方法。
【請求項２３】
請求項２１記載の閾値つき電子署名方法であって、
ｎ台の参加装置があり、任意のｔ台の参加装置が署名に協力した場合であって、ｔ≦ｔ’≦ｎの関係があるときに、
上記ダミー鍵生成装置の計算部で、署名生成に協力していない（ｎ−ｔ’）の参加装置の公開鍵ｐｋｉ（ｉ＝ｔ'＋１，…，ｎ）を、その他の参加装置の公開鍵ｐｋｉ（ｉ＝１，…，ｔ'）および離散対数問題が難しい巡回群の元Ａ０から、（ｍｉｊ）を、
【数１０】
2006203754.tif 000029
のｔ'×ｔ'行列（ｉｊ）の逆行列として、Ａｉ（ｉ＝１，…，ｔ'）を
【数１１】
2006203754.tif 000030
と定め、
【数１２】
2006203754.tif 000031
として生成し、
上記署名検証装置の署名者参加者数確認部で、参加装置に対応する公開鍵ｐｋｉ（ｉ＝１，…，ｎ）と離散対数問題が難しい巡回群に属する元Ａｉ（ｉ＝０，…，ｔ'）から、
【数１３】
2006203754.tif 000032
となることを確認する
ことを特徴とする閾値つき電子署名方法。
【請求項２４】
請求項２０記載の閾値つき電子署名方法であって、
上記参加装置の第１の鍵生成部で、第１の秘密鍵と公開鍵とを生成し、
上記参加装置の第２の鍵生成部で、署名生成に用いる第２の秘密鍵と公開鍵とを生成し、
ダミー鍵生成装置の計算部で、少なくとも１つの署名生成に協力していない参加装置の第２の公開鍵を生成し、
上記署名生成装置の計算部で、第１の署名と第２の署名とを生成し、
上記署名検証装置の署名確認部で、第１の署名および第２の署名の確認を行い、
上記署名検証装置の署名者参加者数確認部で、参加装置間の公開鍵の関係から署名者参加者数を確認する
ことを特徴とする閾値つき電子署名方法。
【請求項２５】
請求項２４記載の閾値つき電子署名方法であって、
ｎ台の参加装置がある場合に、上記ダミー鍵生成装置の計算部で、署名生成に協力していない１つの参加装置の公開鍵ｐｋｎを、その他の参加装置の第２の公開鍵ｐｋｉ（ｉ＝１，…，ｎ−１）と離散対数問題が難しい巡回群の元ｘから、
ｐｋｎ＝ｘ/ｐｋ１ｐｋ２…ｐｋｎ−１
と定め、
上記署名検証装置の署名者参加者数確認部で、第２の公開鍵ｐｋｉ（ｉ＝１，…，ｎ）と離散対数問題が難しい巡回群の元ｘから、
ｐｋ１ｐｋ２…ｐｋｎ＝ｘ
となることを確認する
ことを特徴とする閾値つき電子署名方法。
【請求項２６】
請求項２４記載の閾値つき電子署名方法であって、
ｎ台の参加装置があり、任意のｔ台の参加装置が署名に協力した場合であって、ｔ≦ｔ’≦ｎの関係があるときに、
上記ダミー鍵生成装置の計算部で、署名生成に協力していない（ｎ−ｔ’）の参加装置の公開鍵ｐｋｉ（ｉ＝ｔ'＋１，…，ｎ）を、その他の参加装置の第２の公開鍵ｐｋｉ（ｉ＝１，…，ｔ'）および離散対数問題が難しい巡回群の元Ａ０から、（ｍｉｊ）を、
【数１４】
2006203754.tif 000033
のｔ'×ｔ'行列（ｉｊ）の逆行列として、Ａｉ（ｉ＝１，…，ｔ'）を
【数１５】
2006203754.tif 000034
と定め、
【数１６】
2006203754.tif 000035
として生成し、
上記署名検証装置の署名者参加者数確認部で、参加装置に対応する第２の公開鍵ｐｋｉ（ｉ＝１，…，ｎ）と離散対数問題が難しい巡回群に属する元Ａｉ（ｉ＝０，…，ｔ'）から、
【数１７】
2006203754.tif 000036
となることを確認する
ことを特徴とする閾値つき電子署名方法。
【請求項２７】
請求項２０記載の閾値つき電子署名方法であって、
上記参加装置の第１の鍵生成部で、第１の秘密鍵と公開鍵とを生成し、
上記参加装置の第２の鍵生成部で、第１の秘密鍵から署名生成に用いる第２の秘密鍵を生成し、
上記署名生成装置の計算部で、第２の秘密鍵を用いた署名を生成し、
上記署名検証装置で、上記署名を確認する
ことを特徴とする閾値つき電子署名方法。
【請求項２８】
請求項２７記載の閾値つき電子署名方法であって、
ｎ台の参加装置があり、任意のｔ台の参加装置が署名に協力した場合であって、
上記参加装置の第２の鍵生成部で、上記閾値つき電子署名システムを構成する参加装置の第１の公開鍵ＰＫｉ（ｉ＝１，…，ｎ）とメッセージｍから、任意長のビット列を離散対数問題の難しい加法による巡回群の元に変換するハッシュ関数Ｈを用いて
Ｑｍ＝Ｈ（ｔ，ｎ，ＰＫ１，…，ＰＫｎ，ｍ）
とし、参加装置の第１の秘密鍵ＳＫｉを用いて、
ｓｋｉ＝ＳＫｉＱｍ
として第２の秘密鍵ｓｋｉを生成し、
上記参加装置の署名者証拠生成部では、ｐを法とする剰余類Ｚｐから等確率でランダムに選択した１つの元を署名者証拠ｒｉとし、第１の鍵生成部で使用した離散対数問題の難しい加法による巡回群の元Ｐを用いて、
【数１８】
2006203754.tif 000037
によりコミットメントａｉを生成し、
上記署名生成装置のダミー生成部では、離散対数問題の難しい加法による巡回群から等確率ランダムに選ばれた元をダミーレスポンスｅｉとし、
有限体の座標値をｐを法とする剰余類Ｚｐに変換するハッシュ関数Ｉを用いて、有限体の座標値ｙｉから、ｃｉ＝Ｉ（ｙｉ）によりダミーチャレンジｃｉを求め、
【数１９】
2006203754.tif 000038
によりダミーコミットメントａｉを生成する
ことを特徴とする閾値つき電子署名方法。
【請求項２９】
請求項１〜１９のいずれかに記載の装置をコンピュータにより実現するプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術に関するものであり、閾値つき電子署名技術に関する。
【背景技術】
【０００２】
閾値つき電子署名技術は、複数の参加者の一部が協力することで署名が生成されたことを、誰が署名生成に協力したのかが分からないように署名のみから確認できる電子署名である。ｎ人の参加者うち任意のｔ人以上が協力することで署名が生成されたことを、誰が署名生成に協力したのかが分からないように署名のみから確認できる電子署名の方式を、（ｔ，ｎ）閾値電子署名方式と呼ぶ。従来の方法として非特許文献１に示された方法がある。最初に本説明中で使用する記号について説明する。離散対数問題が難しいと考えられている巡回群をＧとし、その生成元をｇ、群の位数をｑとする（Ｇ＝＜ｇ＞，＃Ｇ＝ｑ）。Ｚｑは、ｑを法とする剰余類{０，１，２，…，ｑ−１}である。∈Ｕは一様ランダムに元を取り出すことを、{０，１}＊は０または１が任意長並んだビット列を、Ｋは有限体を意味する。また、Ｈ，Ｉ，ＪはそれぞれＨ：{０，１}＊→Ｇ，Ｉ：Ｋ→Ｚｑ，Ｊ：{０，１}＊→Ｋのように変換するハッシュ関数である。以下に非特許文献１に示された方法について説明する。
【０００３】
図１に、閾値つき電子署名システムの構成例と流れを示す。本システムへの参加者の総数はｎ人であり、ｎ台の参加装置９１０−ｉ（ｉ＝１，…，ｎ）では、あらかじめ定められた巡回群Ｇの元ｇ（ｇ∈Ｇ）を用いて、各参加装置の秘密鍵ｓｋｉと公開鍵ｐｋｉとが生成され、公開鍵ｐｋｉは公開される。署名を作成する場合は、ｎ人中の任意のｔ人以上が参加装置９１０−ｉ（ｉ＝１，…，ｔ）でコミットメントａｉを生成し、署名生成部９２０を備える装置に送信する。ここで、説明を簡略化するために、ｉ＝１，…，ｔを署名生成に使用した（協力した）参加装置を示す数、ｉ＝ｔ＋１，…，ｎを署名作成に使用していない（協力しなかった）参加装置を示す数とするが、ｔ台の参加装置はｎ台の参加装置中のどれでも良い。
【０００４】
署名生成部９２０は、独立した装置ででもかまわないし、いずれかの参加装置内に備えさせてもかまわない。署名生成部９２０は、ｉ＝ｔ＋１，…，ｎに対するダミーレスポンスｅｉ、ダミーチャレンジｃｉ、およびダミーコミットメントａｉを生成した上で、ｎ−ｔ次多項式ｆ（ｘ）、ｉ＝１，…，ｔに対するチャレンジｃｉとレスポンスｅｉとを生成し、署名σ（ｍ）を作成する。この署名σ（ｍ）はｔ台の参加装置９１０−ｉ（ｉ＝１，…，ｔ）から取得したコミットメントａｉと、署名生成部９２０がダミーとして生成したコミットメントａｉ（ｉ＝ｔ＋１，…，ｎ）等から生成されており、ｔ人が協力した署名生成になっているだけでなく、どのｔ人が協力したのかが分からない署名になっている。
【０００５】
署名検証部９３０は、署名検証を行いたい任意の装置内に備えてかまわない。署名検証部では、多項式ｆ（ｘ）の次数がｎ−ｔであること、チャレンジｃｉ（ｉ＝１，…，ｎ）とｆ（０）の値が正しいことなどを検証する。
図２は、参加装置９１０−ｉの機能構成例を示す図である。参加装置９１０−ｉは、鍵生成部９１１−ｉ、署名者証拠生成部９１２−ｉ、記録部９１３−ｉ、および通信部９１４−ｉから構成される。図３は鍵生成部９１１−ｉの処理フローを示す図であり、図４は署名者証拠生成部９１２−ｉの処理フローを示す図である。
【０００６】
鍵生成部９１１−ｉは、秘密鍵ｓｋｉ生成手段９１１１−ｉと公開鍵ｐｋｉ生成手段９１１２−ｉとで構成される。鍵生成部９１１-ｉでの具体的な鍵生成方法の例を次に示す。秘密鍵ｓｋｉ生成手段９１１１−ｉでは、ｑを法とする剰余類Ｚｑから等確率でランダムに１つの元を選択して秘密鍵ｓｋｉとし（ｓｋｉ∈ＵＺｑ）（Ｓ９１１１）、秘密鍵ｓｋｉを記録部９１３−ｉに記録する（Ｓ９１１２）。公開鍵ｐｋｉ生成手段９１１２−ｉでは、あらかじめ定められた巡回群Ｇの元ｇを用いて、
【数２０】
2006203754.tif 000003
により公開鍵ｐｋｉ（ｐｋｉ∈Ｇ＝{１，ｇ，ｇ２，…，ｇｑ−１}）を生成し（Ｓ９１１３）、公開鍵ｐｋｉを記録部９１３−ｉに記録する（Ｓ９１１４）。ここで、巡回群Ｇは、離散対数問題が難しい群から選ばれているため、公開鍵ｐｋｉと元ｇが分かっても、秘密鍵ｓｋｉは分からない。このように生成された公開鍵ｐｋｉは、元ｇの情報とともに通信部９１４−ｉを介して公開される。
【０００７】
署名者証拠生成部９１２−ｉは、署名生成に協力する場合に動作する構成部であり、署名者証拠ｒｉ生成手段９１２１−ｉ、コミットメントａｉ生成手段９１２２−ｉ、チャレンジｃｉ取得手段９１２３−ｉ、およびレスポンスｅｉ生成手段９１２２−ｉで構成される。署名者証拠生成部９１２−ｉでの具体的な処理手順の例を次に示す。参加者が署名に協力する場合には、署名者証拠ｒｉ生成手段９１２１−ｉでは、ｑを法とする剰余類Ｚｑから等確率でランダムに１つの元を選択して署名者証拠ｒｉとする（ｒｉ∈ＵＺｑ）（Ｓ９１２１）。次にコミットメントａｉ生成手段９１２２−ｉでは、元ｇを用いて、
【数２１】
2006203754.tif 000004
によりコミットメントａｉ（∈Ｇ）を生成し（Ｓ９１２２）、コミットメントａｉを記録部９１３−ｉに記録し、通信部９１４−ｉを介して署名生成部９２０を備える装置に送信する（Ｓ９１２３）。通常、署名者証拠ｒｉはコミットメントａｉを生成すれば不要となるため、記録部９１３−ｉに記録されること無く消去される。署名生成部９２０で署名生成処理が行われると、署名生成部９２０の計算部９２２の処理過程で生成されたチャレンジｃｉが署名生成部９２０から、署名生成に協力している参加装置９１０−ｉ（ｉ＝１，…，ｔ）に送信される。このチャレンジｃｉをチャレンジｃｉ取得手段９１２３−ｉで取得し（Ｓ９１２４）、記録部９１３−ｉに記録する（Ｓ９１２５）。また、レスポンスｅｉ生成手段９１２２−ｉで、ｅｉ：＝ｒｉ−ｃｉｓｋｉ（ｅｉ∈Ｚｑ）により、ｅｉ（ｉ＝１，…，ｔ）を求め（Ｓ９１２６）、記録部９１３−ｉに記録するとともに署名生成部９２０に送信する（Ｓ９１２７）。
【０００８】
図５に署名生成部９２０の機能構成例を示す。署名生成部９２０は、ダミー生成部９２１、計算部９２２、情報取得部９２３、記録部９２４、および通信部９２５から構成されている。また、図６は署名生成部９２０の処理フローを示す図である。
署名生成部９２０では、以下の手順で署名σ（ｍ）が生成される。通信部９２５を介して情報取得部９２３の公開鍵ｐｋｉ（ｉ＝１，…，ｎ）取得手段９２３１により、参加装置９１０−ｉ（ｉ＝１，…，ｎ）の公開鍵ｐｋｉを取得する（Ｓ９２３１）。ダミー生成部９２１では、次のように、ダミーレスポンスｅｉ、ダミーチャレンジｃｉ、ダミーコミットメントａｉ（ｉ＝ｔ＋１，…，ｎ）を生成する。ダミーレスポンスｅｉ（ｉ＝ｔ＋１，…，ｎ）生成手段９２１１により、ｑを法とする剰余類Ｚｑから等確率でランダムに１つの元を選択してダミーレスポンスｅｉ（ｉ＝ｔ＋１，…，ｎ）とし（ｅｉ∈ＵＺｑ）（Ｓ９２１１）、記録部９２４に記録する（Ｓ９２１２）。ダミーチャレンジｃｉ（ｉ＝ｔ＋１，…，ｎ）生成手段９２１２により、有限体Ｋから等確率でランダムに１つの座標値ｙｉを選び、そのハッシュ関数をダミーチャレンジｃｉ（ｉ＝ｔ＋１，…，ｎ）とし（ｙｉ∈ＵＫ，ｃｉ：＝Ｉ（ｙｉ）∈Ｚｑ）（Ｓ９２１３）、記録部９２４に記録する（Ｓ９２１４）。また、ダミーコミットメントａｉ（ｉ＝ｔ＋１，…，ｎ）生成手段９２１３により、元ｇと公開鍵ｐｋｉを用いて、
【数２２】
2006203754.tif 000005
によりダミーコミットメントａｉ（ｉ＝ｔ＋１，…，ｎ）を生成し（Ｓ９２１５）、記録部９２４に記録する（Ｓ９２１６）。
【０００９】
また、通信部９２５を介して情報取得部９２３のコミットメントａｉ（ｉ＝１，…，ｔ）取得手段９２３２により、参加装置９１０−ｉ（ｉ＝１，…，ｔ）のコミットメントａｉを取得する（Ｓ９２３２）。
【００１０】
次に、計算部９２２では、以下のようにメッセージｍの（ｔ，ｎ）閾値署名σ（ｍ）を求める。ｎ−ｔ次多項式ｆ（ｘ）計算手段９２２１により、ｎ−ｔ次の多項式ｆ（ｘ）（ｆ（ｘ）＝α０＋α１ｘ＋α２ｘ２＋…＋αｎ−ｔｘｎ−ｔ，αｊ∈Ｋ）と定め、ｆ（０）＝Ｊ（ｔ，ｎ，ｐｋ１，…，ｐｋｎ，ａ１，…，ａｎ，ｍ）とｆ（ｉ）＝ｙｉ（ｉ＝ｔ＋１，…，ｎ）の条件からαｊ（ｊ＝０，…，ｎ−ｔ）を計算することでｎ−ｔ次多項式ｆ（ｘ）を求める（Ｓ９２２１）。また、求めたｎ−ｔ次多項式ｆ（ｘ）を記録部９２４に記録する（Ｓ９２２２）。チャレンジｃｉ（ｉ＝１，…，ｔ）生成手段９２２２では、ｃｉ：＝Ｉ（ｆ（ｉ））により、チャレンジｃｉ（ｉ＝１，…，ｔ）を求め（Ｓ９２２３）、記録部９２４に記録するとともに、チャレンジｃｉに対応する参加装置９１０−ｉ（ｉ＝１，…，ｔ）にチャレンジｃｉを送信する（Ｓ９２２４）。各参加者装置９１０−ｉ（ｉ＝１，…，ｔ）では、送信されたチャレンジｃｉを用いて、上記のようにレスポンスｅｉを生成し署名生成部９２０に送信する（Ｓ９１２４〜Ｓ９１２７）。そこで、レスポンスｅｉ（ｉ＝１，…，ｔ）取得手段９２２３は、レスポンスｅｉ（ｉ＝１，…，ｔ）を取得し（Ｓ９２２５）、記録部９２４に記録する（Ｓ９２２６）。署名σ（ｍ）作成手段９２２３では、σ（ｍ）＝（ｔ，ｎ，ｆ，ｃ１，…，ｃｎ，ｅ１，…，ｅｎ）により、σ（ｍ）を求め（Ｓ９２２７）、記録部９２４に記録する（Ｓ９２２８）。このようにしてメッセージｍに対する（ｔ，ｎ）閾値署名σ（ｍ）を求める。
【００１１】
図７に署名検証部９３０の機能構成例を示す。また、図８に署名検証部９３０での署名σ（ｍ）を検証するフローを示す。情報取得手段９３３は、公開鍵ｐｋｉ（ｉ＝１，…，ｎ）と署名σ（ｍ）を取得し（Ｓ９３３）、多項式ｆ（ｘ）の次数確認手段９３１で多項式ｆ（ｘ）の次数がｎ−ｔであることを確認し（Ｓ９３１）、チャレンジｃｉ、多項式ｆ（０）確認手段９３２で、
【数２３】
2006203754.tif 000006
であることを確認する（Ｓ９３２）。
【００１２】
このように署名σ（ｍ）の生成と検証を行うことで、署名検証部９３０（署名検証をする人）は、少なくともｔ台の参加装置９１０−ｉ（ｔ人の参加者）が協力して署名を作成したことが確認できる。また、署名検証部９３０は、ｎ台の参加装置９１０−ｉ中のどのｔ台（ｎ人の参加者中のどのｔ人）が署名生成に協力したのかは分からない。
【非特許文献１】[CDS94] R. Cramer and I. Damgard and B. Schoen-makers, Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, CRYPTO ’94, pp. 174-187, 1994.
【発明の開示】
【発明が解決しようとする課題】
【００１３】
従来技術では、どの参加者が署名生成に協力したのかが分からないことを特徴としているが、参加者が署名生成に協力したことを証明すること（名乗り出ること）もできなかった。
また、署名生成に協力したことを証明することができるようにする場合には、何人の参加者が証明できるのかを署名から確認できるようにすることも必要である。さらに、署名生成に協力したことを証明するときに秘密鍵の情報も流出することが考えられることから、以後、今までの秘密鍵と公開鍵が使用できなくなる。
【課題を解決するための手段】
【００１４】
本発明では、あらかじめ参加装置の記録部で署名者証拠を記録しておき、参加者が署名生成に協力したことを証明したい場合に当該署名者証拠を公開し、署名検証装置で当該署名者証拠を確認する。
また、何人の参加者が証明できるのかを署名から確認できるようにするための手段は以下のとおりである。ダミー鍵生成装置の情報取得部で署名生成に協力していない参加装置に対する公開鍵を少なくとも１つ生成し、当該公開鍵および公開鍵生成時に使用した乱数と離散対数問題の難しい巡回群の元を公開する。署名生成装置でダミーの公開鍵も用いて電子署名を生成する。署名検証装置でダミーの公開鍵を含めて公開鍵を取得し、ダミーの公開鍵生成時に使用した上記乱数と離散対数問題の難しい巡回群の上記元も取得し、署名者参加者数を確認する。
【００１５】
さらに、署名生成に協力したことを証明するときに秘密鍵の情報も流出することに対応する手段は以下のとおりである。参加装置では、公的機関に公開鍵を登録するような長期的に使用する秘密鍵と公開鍵の組（第１の秘密鍵と公開鍵）の他に、署名生成に用いる使い捨ての秘密鍵と公開鍵の組（第２の秘密鍵と公開鍵）を生成し、ダミー鍵生成装置で少なくとも１つの第２の公開鍵に対するダミー公開鍵を生成する。署名生成装置では、第１の署名と第２の署名とを生成する。署名検証装置では、参加者装置ごとの第１の公開鍵、第２の公開鍵を取得し、第１の署名および第２の署名の確認を行う。
【００１６】
または、参加装置で、署名生成に用いる使い捨ての秘密鍵（第２の秘密鍵）を、第１の秘密鍵から生成する。署名生成装置では、第２の秘密鍵を用いた署名だけを生成する。署名検証装置で、第１の公開鍵および第１の鍵生成と第２の鍵生成で使用した２つの問題の難しい巡回群の元を用いて署名を検証する。
【発明の効果】
【００１７】
本発明では上記のような手段により、参加者が署名生成に協力したことを証明したい場合に、証明することができる。また、何人の参加者が証明できるのかを署名から確認できる。さらに、使い捨て秘密鍵（第２の秘密鍵）を使用することにより、公的機関に登録しているような公開鍵と組となる秘密鍵の情報流出を避けることができる。
【発明を実施するための最良の形態】
【００１８】
以下にこの発明の実施形態を図面を参照して説明するが、同一の機能を有する部分は、各図中に同一参照番号を付けて重複説明を省略する。また、以下の説明でも背景技術の説明と同様に、説明を簡単にするために、ｉ＝１，…，ｔを署名生成に協力した参加装置を示す数、ｉ＝ｔ＋１，…，ｎを署名作成に協力しなかった参加装置を示す数とするが、ｔ台の参加装置はｎ台の参加装置中のどれでも良い。
【００１９】
［第１実施形態］
本発明では、ｔを１≦ｔ≦ｎとし、（ｔ，ｎ）閾値署名方式で署名に協力した参加者ｉ（ｉ＝１，…，ｔ）が、署名検証後に署名に協力したことを証明できる。図９は本発明のシステム構成例と流れを示す図であり、従来技術のシステム構成例を示す図である図１との違いは、次の点である。各参加者装置１１０−ｉ（ｉ＝１，…，ｔ）が、署名作成に協力する過程で生成した署名者証拠ｒｉを記録しておき、署名生成に協力したこと（署名者の１人であったこと）を証明したい場合に、署名者証拠ｒｉを、署名検証部１３０を備える装置に送信することで、署名生成に協力したことを証明する。以下に、従来技術と異なる構成装置について詳細に説明する。
【００２０】
図１０は、参加装置１１０−ｉの機能構成例を示す図である。参加装置１１０−ｉは、従来の参加装置９１０−ｉとは、署名者証拠生成部１１２−ｉと記録部１１３−ｉが異なり、署名者証拠公開部１１５−ｉが追加されている。図１１は署名者証拠生成部１１２−ｉの処理フローを示す図であり、図１２は署名者証拠公開部１１５−ｉの処理フローを示す図である。図１１に示すように、署名者証拠生成部１１２−ｉでは、従来であれば、通常コミットメントａｉを生成すれば不要となる署名者証拠ｒｉを、記録部９１３−ｉに記録する工程（Ｓ１１２１）を署名者証拠ｒｉ生成ステップ（Ｓ９１２１）の後に追加した処理を行う。また、参加者ｉが署名生成に協力したことを証明したい場合には、図１２に示すように、署名者証拠公開部１１５−ｉは、記録部１１３−ｉに記録された署名者証拠ｒｉを署名検証部１３０に対して公開する（Ｓ１１５）。
【００２１】
図１３に署名検証部１３０の機能構成例を示す。図７に示す従来の署名検証部９３０との違いは、署名者証拠ｒｉ確認手段１３３が追加されたことと、情報取得手段１３４が署名者証拠ｒｉも取得するよう変更されたことである。図１４に署名に協力したことを証明したい参加者から署名者証拠ｒｉが公開された場合の、署名者証拠ｒｉ確認フローを示す。署名に協力したことを証明したい参加者ｉから署名者証拠ｒｉが公開された場合には、署名検証部１３０の情報取得手段１３４は署名者証拠ｒｉを取得する（Ｓ１３４）。次に、署名者証拠ｒｉ確認手段１３３で、
【数２４】
2006203754.tif 000007
であることを確認する（Ｓ１３３）ことで、署名者証拠ｒｉを公開した参加者ｉが署名生成に協力した参加者であることが分かる。
【００２２】
ただし、署名者証拠ｒｉ、レスポンスｅｉ、チャレンジｃｉ、および秘密鍵ｓｋｉの間には、ｅｉ＝ｒｉ−ｃｉｓｋｉの関係があるため、署名者証拠ｒｉを公開することで、秘密鍵ｓｋｉも分かってしまう。したがって、署名に協力したことを証明した後は、これまで使用してきた秘密鍵ｓｋｉと公開鍵ｐｋｉの組は使用できなくなる。
【００２３】
［第２実施形態］
本発明は、ｔを１≦ｔ≦ｎ−１とする（ｔ，ｎ−１，ｎ）閾値署名方式に関する。（ｔ，ｎ−１，ｎ）閾値署名方式とは、署名者であったことを証明することができる参加者は、ｔ人以上ｎ-１人以下であることを署名のみから確認できる方式である。図１５は、本発明のシステム構成例と流れを示す図であり、第１実施形態との違いは、ダミー鍵生成部２４０が追加されたことと、署名検証部２３０が変更されたことである。ダミー鍵生成部２４０では、参加装置１１０−ｎの鍵生成部９１１−ｎの代わりに署名生成に使用する公開鍵ｐｋｎを生成する。この公開鍵ｐｋｎを用いて署名を生成することで、署名者であったことを証明することができる参加者がｔ人以上ｎ-１人以下であることを署名のみから確認できる方式を実現する。以下に本発明を詳しく説明する。
【００２４】
図１６にダミー鍵生成部２４０の機能構成例を、図１７にダミー鍵生成部２４０の処理フローを示す。ダミー鍵生成部２４０では、通信部２４３を介して情報取得部２４２の公開鍵ｐｋｉ（ｉ＝１，…，ｎ−１）取得手段２４２１で、参加装置１１０−ｉ（ｉ＝１，…，ｎ−１）の公開鍵ｐｋｉを取得する（Ｓ２４２１）。計算部２４１のダミー公開鍵ｐｋｎ生成手段２４１１で、巡回群Ｇに属する元ｘ（ｘ∈Ｇ）を、例えば{０，１}＊の乱数Ｒのハッシュ値として生成する（ｘ＝Ｈ（Ｒ））。例えば、乱数Ｒのビット長を１０２４とする。ここで、秘密鍵ｓｋｉはｑを法とする剰余類Ｚｑから等確率でランダムに１つの元（ｓｋｉ∈ＵＺｑ）であり（Ｓ９１１１参照）、公開鍵ｐｋｉは巡回群Ｇの元（ｐｋｉ∈Ｇ）である（Ｓ９１１３参照）。公開鍵ｐｋｎをｐｋｎ：＝ｘ/ｐｋ１ｐｋ２…ｐｋｎ−１と定め（Ｓ２４１１）、公開鍵ｐｋｎ、元ｘ、および乱数Ｒを公開する（Ｓ２４１２）。このように公開鍵ｐｋｎを定めると、ｘの離散対数は分からないので参加者ｎの秘密鍵は分からない。
【００２５】
なお、ダミー鍵生成部２４０を各参加装置１１０−ｉ（ｉ＝１，…，ｎ）に備えさせておき、ダミーの公開鍵を作ることとした１つの参加装置１１０−ｎだけは、ダミー鍵生成部２４０で公開鍵ｐｋｎを生成することとしてもよい。また、単独のダミー鍵生成部２４０を具備するダミー鍵生成装置を１つ設置し、参加装置１１０−ｎの代わりに公開鍵ｐｋｎを生成し、直接または参加装置１１０−ｎ経由で公開鍵ｐｋｎを公開してもよい。
【００２６】
図１８に署名検証部２３０の機能構成例を示す。第１実施形態との違いは、署名参加者数確認手段２３５が追加されたことと、情報取得手段２３４が元ｘとＲも取得するよう変更されたことである。図１９に署名検証部２３０が署名σ（ｍ）を検証するフローを示す。第１実施形態の署名σ（ｍ）の検証フローは従来技術を同じであるので、本フローの違いは図８に示した従来の署名σ（ｍ）の検証フローとの違いを説明する。署名検証部２３０では、情報取得手段２３４で、公開鍵ｐｋｉ（ｉ＝１，…，ｎ）、署名σ（ｍ）、元ｘ、および乱数Ｒを取得し（Ｓ２３４）、多項式ｆ（ｘ）の次数確認（Ｓ９３１と同じ）、チャレンジｃｉ、多項式ｆ（０）確認（Ｓ９３２と同じ）を行う。さらに、署名参加者数確認手段２３５で、ｘ＝Ｈ（Ｒ）とｐｋ１ｐｋ２…ｐｋｎ＝ｘを確認する（Ｓ２３５）。
【００２７】
このように署名σ（ｍ）を生成、検証することで、どの公開鍵ｐｋｉかは分からないが、少なくとも１つは秘密鍵がないダミーの公開鍵があることになるため、署名生成に協力したことを証明できる参加者がｔ人以上ｎ−１人以下であることが署名のみから確認できる。
【００２８】
［第３実施形態］
本発明は、ｔとｔ’とを１≦ｔ≦ｔ'≦ｎ−１とする（ｔ，ｔ’，ｎ）閾値署名方式に関する。（ｔ，ｔ’，ｎ）閾値署名方式とは、署名者であったことを証明することができる参加者は、ｔ人以上ｔ’人以下であることを署名のみから確認できる方式である。図２０は、本発明のシステム構成例と流れを示す図であり、第２実施形態との違いは、ダミー鍵生成部３４０と署名検証部３３０が変更されたことである。ダミー鍵生成部３４０では、参加装置１１０−ｉ（ｉ＝ｔ’，…，ｎ）の鍵生成部９１１−ｉ（ｉ＝ｔ’，…，ｎ）の代わりに署名生成に使用する公開鍵ｐｋｉ（ｉ＝ｔ’，…，ｎ）を生成する。この公開鍵ｐｋｉを用いて署名を生成することで、署名者であったことを証明することができる参加者がｔ人以上ｔ'人以下であることを署名のみから確認できる方式を実現する。以下に本発明を詳しく説明する。
【００２９】
図２１にダミー鍵生成部３４０の機能構成例を、図２２にダミー鍵生成部３４０の処理フローを示す。ダミー鍵生成部３４０では、通信部２４３を介して情報取得部３４２の公開鍵ｐｋｉ（ｉ＝１，…，ｔ'）取得手段３４２１で、参加装置１１０−ｉ（ｉ＝１，…，ｔ'）の公開鍵ｐｋｉを取得する（Ｓ３４２１）。計算部３４１のダミー公開鍵ｐｋｉ（ｉ＝ｔ'＋１，…，ｎ）生成手段では、巡回群Ｇに属する元Ａ０（Ａ０∈Ｇ）を、例えば{０，１}＊の乱数Ｒのハッシュ値として生成する（Ａ０＝Ｈ（Ｒ））。（ｍｉｊ）を、
【数２５】
2006203754.tif 000008
のｔ'×ｔ'行列（ｉｊ）の逆行列として、Ａｉ（ｉ＝１，…，ｔ'）を
【数２６】
2006203754.tif 000009
と定め、公開鍵ｐｋｉ（ｉ＝ｔ'＋１，…，ｎ）を
【数２７】
2006203754.tif 000010
として公開鍵ｐｋｉを生成し（Ｓ３４１１）、公開鍵ｐｋｉ、元Ａｉ、および乱数Ｒを公開する（Ｓ３４１２）。このように公開鍵ｐｋｉ（ｉ＝ｔ'＋１，…，ｎ）を生成すれば、公開鍵ｐｋｉ∈Ｇを満足するので、ｔ’次多項式Ｆ（Ｆ∈Ｚｑ［ｘ］）が存在し、秘密鍵ｓｋｉ＝Ｆ（ｉ）かつｌｏｇｇＡ０＝Ｆ（０）となっている。ここで、Ａ０の離散対数は分からないので、参加者ｉ（ｉ＝ｔ'＋１，…，ｎ）の秘密鍵は分からない。
【００３０】
図２３に署名検証部３３０の機能構成例を示す。第２実施形態との違いは、署名参加者数確認手段３３５と、情報取得手段３３４が変更されたことである。図２４に署名検証部３３０が署名σ（ｍ）を検証するフローを示す。署名検証部３３０では、情報取得手段３３４で、公開鍵ｐｋｉ（ｉ＝１，…，ｎ）、署名σ（ｍ）、元Ａｉ（ｉ＝１，…，ｔ'）、および乱数Ｒを取得し（Ｓ３３４）、多項式ｆ（ｘ）の次数確認（Ｓ９３１と同じ）、チャレンジｃｉ、多項式ｆ（０）確認（Ｓ９３２と同じ）を行う。さらに、署名参加者数確認手段３３５で、Ａ０＝Ｈ（Ｒ）と
【数２８】
2006203754.tif 000011
（ｐｋｉ∈Ｇ）（ｉ＝１，…，ｎ）を確認する（Ｓ３３５）。
【００３１】
このように署名σ（ｍ）を生成、検証することで、どの公開鍵ｐｋｉかは分からないが、少なくともｎ−ｔ’は秘密鍵がないダミーの公開鍵があることになるため、署名生成に協力したことを証明できる参加者がｔ人以上ｔ’人以下であることが署名のみから確認できる。
【００３２】
［第４実施形態］
本発明は、参加者が署名生成に協力したことを証明した後も同じ公開鍵を使うことができるよう第２実施形態を改良したものであって、ｔを１≦ｔ≦ｎ−１とする（ｔ，ｎ−１，ｎ）閾値署名方式に関する。図２５は、本発明のシステム構成例と流れを示す図であり、第２実施形態との違いは、参加装置４１０−ｉ（ｉ＝１，…，ｎ）、署名生成部４２０、署名検証部４３０、およびダミー鍵生成部４４０のそれぞれが、通常の秘密鍵と公開鍵（第１の秘密鍵と公開鍵）および署名者証拠ｒｉを公開すると使用できなくなる使い捨ての秘密鍵と公開鍵（第２の秘密鍵と公開鍵）の２種類の鍵に対応できるよう変更されたことである。２種類の鍵を使用することにより、第２実施形態の効果は維持しながら、公の機関に登録しているような公開鍵（第１の公開鍵）が署名者証拠ｒｉの公開後も使用できる。以下に本発明を詳しく説明する。
【００３３】
図２６は、参加装置４１０−ｉの機能構成例を示す図である。参加装置４１０−ｉは、第１の秘密鍵と公開鍵を生成する鍵生成部４１１−ｉ、第２の秘密鍵と公開鍵を生成する鍵生成部９１１−ｉ、署名者証拠生成部１１２−ｉ、記録部４１３−ｉ、通信部９１４−ｉ、および署名者証拠公開部１１５−ｉから構成される。図２７は第１の秘密鍵と公開鍵を生成する鍵生成部４１１−ｉの処理フローを示す図である。鍵生成部４１１−ｉの秘密鍵ＳＫｉ生成手段４１１１−ｉでは、任意の（ｔ，ｎ）閾値署名Σ（ｍ）の方法で秘密鍵ＳＫｉを生成し（Ｓ４１１１）、記録部４１３−ｉに記録する（Ｓ４１１２）。この（ｔ，ｎ）閾値署名Σ（ｍ）は従来からある技術を用いればよいし、鍵生成部９１１−ｉと同じ方法でも良い。公開鍵ＰＫｉ生成手段４１１２−ｉでは、上記の秘密鍵ＳＫｉ生成手段４１１１−ｉに対応した方法で公開鍵ＰＫｉを生成し（Ｓ４１１３）、記録部４１３−ｉに記録する（Ｓ４１１４）。鍵生成部４１１−ｉで生成された秘密鍵ＳＫｉと公開鍵ＰＫｉの組が、継続的に使用し、署名者証拠ｒｉを公開後も使用できる鍵となる。また、鍵生成部９１１−ｉで生成された秘密鍵ｓｋｉと公開鍵ｐｋｉの組（鍵生成フローは図３と同じ）が使い捨ての鍵であり、署名者証拠ｒｉを公開後は使用できない鍵となる。なお、署名者証拠生成部１１２−ｉと署名者証拠ｒｉ公開部１１５−ｉは第１実施形態と同じである。
【００３４】
図２８にダミー鍵生成部４４０の構成例を、図２９にダミー鍵生成部４４０の処理フローを示す。ダミー鍵生成部４４０では、通信部２４３を介して情報取得部４４２の公開鍵ＰＫｉ（ｉ＝１，…，ｎ−１）取得手段４４２１で、参加装置４１０−ｉ（ｉ＝１，…，ｎ−１）の公開鍵ＰＫｉを取得する（Ｓ４４２１）。また、情報取得部２４２の公開鍵ｐｋｉ（ｉ＝１，…，ｎ−１）取得手段２４２１で、参加装置４１０−ｉ（ｉ＝１，…，ｎ−１）の公開鍵ｐｋｉを取得する（Ｓ２４２１と同じ）。計算部４４１のダミー公開鍵ｐｋｎ生成手段４４１１で、Ｒ＝（ｔ，ｎ−１，ｎ，ＰＫ１，…，ＰＫｎ，ｍ）として、巡回群Ｇに属する元ｘ（ｘ∈Ｇ）を、Ｒのハッシュ値として生成する（ｘ＝Ｈ（Ｒ））。公開鍵ｐｋｎをｐｋｎ：＝ｘ/ｐｋ１ｐｋ２…ｐｋｎ−１と定め（Ｓ４４１１）、公開鍵ｐｋｎ、元ｘ、およびＲを公開する（Ｓ２４１２と同じ）。このように公開鍵ｐｋｎを定めると、ｘの離散対数は分からないので参加者ｎの秘密鍵は分からない。
【００３５】
図３０に署名生成部４２０の機能構成例を示す。署名生成部４２０は、ダミー生成部９２１、計算部４２２、情報取得部４２３、記録部４２４、および通信部９２５から構成されている。また、図３１は署名生成部４２０の処理フローを示す図である。
署名生成部４２０では、以下の手順で署名σ（ｍ）と署名Σ（ｍ）が生成される。通信部９２５を介して情報取得部４２３の公開鍵ＰＫｉ（ｉ＝１，…，ｎ）取得手段４２３１により、参加装置９１０−ｉ（ｉ＝１，…，ｎ）の公開鍵ＰＫｉを取得する（Ｓ４２３１）。ステップＳ９２３１の公開鍵ｐｋｉ（ｉ＝１，…，ｎ）の取得、ダミー鍵生成部の処理フローであるステップＳ９２１１〜ステップＳ９２１６、およびステップＳ９２３２のコミットメントａｉ（ｉ＝１，…，ｔ）の取得は、図６での説明と同じである。また、情報取得部４２３の元ｘ取得手段４２３３では、元ｘを取得する（Ｓ４２３３）。計算部４２２の処理のステップＳ９２２１〜Ｓ９２２８の処理は、図６の説明と同じである。したがって、ｎ−ｔ次多項式ｆ（ｘ）、チャレンジｃｉ（ｉ＝１，…，ｔ）、レスポンスｅｉ（ｉ＝１，…，ｔ）、メッセージｍに対する（ｔ，ｎ）閾値署名σ（ｍ）は、第２実施形態と同じで、背景技術として説明した従来技術と同じである。次に、署名作成手段４２２５では、Ｍ＝（ｔ，ｎ−１，ｎ，ＰＫ１，…，ＰＫｎ，ｍ，ｘ，ｐｋ１，…，ｐｋｎ）とし、（Ｍ，σ（Ｍ），Σ（Ｍ，σ（Ｍ））、（Ｍ，Σ（Ｍ），σ（Ｍ，Σ（Ｍ）））、もしくは（Ｍ，σ（Ｍ），Σ（Ｍ））を署名とし（Ｓ４２２７）、記録部４２４への記憶と公開を行う（Ｓ４２２８）。なお、Σ（ｍ）はステップＳ４４１１での秘密鍵ＳＫｉの生成方法に対応した任意の（ｔ，ｎ）閾値署名Σ（ｍ）の方法を用いればよい。
【００３６】
図３２に署名検証部４３０の機能構成例を、図３３に署名検証部４３０での署名σ（ｍ）と署名Σ（ｍ）の検証フローを示す。情報取得手段４３４で、公開鍵ＰＫｉ（ｉ＝１，…，ｎ）、公開鍵ｐｋｉ（ｉ＝１，…，ｎ）、署名σ（ｍ）、元ｘ、およびＲを取得する（Ｓ４３４）。多項式ｆ（ｘ）の次数確認（Ｓ９３１と同じ）、チャレンジｃｉ、多項式ｆ（０）確認（Ｓ９３２と同じ）を行うことで、σ（ｍ）の検証ができる。また、Σ（ｍ）の検証は、ステップＳ４４１１での秘密鍵ＳＫｉの生成方法に対応した任意の（ｔ，ｎ）閾値署名Σ（ｍ）の方法を用いて行う（Ｓ４３１）。さらに、署名参加者数確認手段２３５で、ｘ＝Ｈ（Ｒ）とｐｋ１ｐｋ２…ｐｋｎ＝ｘを確認する（Ｓ２３５と同じ）。
【００３７】
このように署名σ（ｍ）と署名Σ（ｍ）を生成、検証することで、署名者証拠ｒｉの公開後も秘密鍵ＳＫｉと公開鍵ＰＫｉとが使用でき、かつ署名生成に協力したことを証明できる参加者がｔ人以上ｎ−１人以下であることが署名のみから確認できる。
【００３８】
［第５実施形態］
本発明は、参加者が署名生成に協力したことを証明した後も同じ公開鍵を使うことができるよう第３実施形態を改良したものであって、ｔとｔ’を１≦ｔ≦ｔ’≦ｎとする（ｔ，ｔ’，ｎ）閾値署名方式に関する。図３４は、本発明のシステム構成例と流れを示す図であり、第３実施形態との違いは、参加装置４１０−ｉ（ｉ＝１，…，ｎ）、署名生成部５２０、署名検証部５３０、およびダミー鍵生成部５４０のそれぞれが、通常の秘密鍵と公開鍵（第１の秘密鍵と公開鍵）および署名者証拠ｒｉを公開すると使用できなくなる使い捨ての秘密鍵と公開鍵（第２の秘密鍵と公開鍵）の２種類の鍵に対応できるよう変更されたことである。２種類の鍵を使用することにより、第３実施形態の効果は維持しながら、公の機関に登録しているような公開鍵（第１の公開鍵）が署名者証拠ｒｉの公開後も使用できる。以下に本発明を詳しく説明する。
【００３９】
参加装置４１０−ｉ（ｉ＝１，…，ｎ）は第４実施形態と同じため、説明は省略する。  図３５にダミー鍵生成部５４０の構成例を、図３６にダミー鍵生成部５４０の処理フローを示す。ダミー鍵生成部５４０では、通信部２４３を介して情報取得部５４２の公開鍵ＰＫｉ（ｉ＝１，…，ｎ）取得手段４４２１で、参加装置４１０−ｉ（ｉ＝１，…，ｎ）の公開鍵ＰＫｉを取得する（Ｓ４４２１と同じ）。また、情報取得部３４２の公開鍵ｐｋｉ（ｉ＝１，…，ｔ’）取得手段３４２１で、参加装置４１０−ｉ（ｉ＝１，…，ｔ’）の公開鍵ｐｋｉを取得する（Ｓ２４２１と同じ）。計算部５４１のダミー公開鍵ｐｋｉ（ｉ＝ｔ’＋１，…，ｎ）生成手段５４１１で、Ｒ＝（ｔ，ｔ’，ｎ，ＰＫ１，…，ＰＫｎ，ｍ）として、巡回群Ｇに属する元Ａ０（Ａ０∈Ｇ）を、Ｒのハッシュ値として生成する（Ａ０＝Ｈ（Ｒ））。その後はステップＳ３４１１と同じ方法であって、（ｍｉｊ）を、
【数２９】
2006203754.tif 000012
のｔ'×ｔ'行列（ｉｊ）の逆行列として、Ａｉ（ｉ＝１，…，ｔ'）を
【数３０】
2006203754.tif 000013
と定め、
【数３１】
2006203754.tif 000014
として公開鍵ｐｋｉ（ｉ＝ｔ'＋１，…，ｎ）を生成する（Ｓ５４１１）。生成された公開鍵ｐｋｉ、元Ａｉ、およびＲを公開する（Ｓ３４１２と同じ）。このように公開鍵ｐｋｉ（ｉ＝ｔ'＋１，…，ｎ）を生成すれば、第３実施形態と同様に、公開鍵ｐｋｉ∈Ｇを満足するので、ｔ’次多項式Ｆ（Ｆ∈Ｚｑ［ｘ］）が存在し、秘密鍵ｓｋｉ＝Ｆ（ｉ）かつｌｏｇｇＡ０＝Ｆ（０）となっている。ここで、Ａ０の離散対数は分からないので、参加者ｉ（ｉ＝ｔ'＋１，…，ｎ）の秘密鍵は分からない。
【００４０】
図３７に署名生成部５２０の機能構成例を示す。署名生成部５２０は、ダミー生成部９２１、計算部５２２、情報取得部５２３、記録部４２４、および通信部９２５から構成されている。また、図３８は署名生成部５２０の処理フローを示す図である。この機能構成と処理フローは、ほとんど第４実施形態の署名生成部４２０と同じであり、異なる点は元ｘではなく元Ａｉ（ｉ＝０，…，ｔ'）を用いる点だけである。異なる点だけを示すと以下のようになる。情報取得部５２３の元Ａｉ（ｉ＝０，…，ｔ'）取得手段５２３３では、元ｘではなく元Ａｉ（ｉ＝０，…，ｔ'）を取得する（Ｓ５２３３）。署名作成手段５２２５では、Ｍ＝（ｔ，ｔ’，ｎ，ＰＫ１，…，ＰＫｎ，ｍ，Ａ０，…，Ａｔ’，ｐｋ１，…，ｐｋｎ）とし、（Ｍ，σ（Ｍ），Σ（Ｍ，σ（Ｍ））、（Ｍ，Σ（Ｍ），σ（Ｍ，Σ（Ｍ）））、もしくは（Ｍ，σ（Ｍ），Σ（Ｍ））を署名とし（Ｓ５２２７）、記録部４２４への記憶と公開を行う（Ｓ４２２８）。
【００４１】
図３９に署名検証部５３０の機能構成例を、図４０に署名検証部５３０での署名σ（ｍ）と署名Σ（ｍ）の検証フローを示す。情報取得手段５３４で、公開鍵ＰＫｉ（ｉ＝１，…，ｎ）、公開鍵ｐｋｉ（ｉ＝１，…，ｎ）、署名σ（ｍ）、元Ａｉ（ｉ＝０，…，ｔ'）、およびＲを取得する（Ｓ５３４）。多項式ｆ（ｘ）の次数確認（Ｓ９３１と同じ）、チャレンジｃｉ、多項式ｆ（０）確認（Ｓ９３２と同じ）を行うことで、σ（ｍ）の検証ができる。また、Σ（ｍ）の検証は、参加装置４１０−ｉでの秘密鍵ＳＫｉの生成方法に対応した任意の（ｔ，ｎ）閾値署名Σ（ｍ）の方法を用いて行う（Ｓ４３１と同じ）。さらに、署名参加者数確認手段３３５で、Ａ０＝Ｈ（Ｒ）と
【数３２】
2006203754.tif 000015
（ｐｋｉ∈Ｇ）（ｉ＝１，…，ｎ）を確認する（Ｓ３３５と同じ）。
【００４２】
このように署名σ（ｍ）と署名Σ（ｍ）を生成、検証することで、署名者証拠ｒｉの公開後も秘密鍵ＳＫｉと公開鍵ＰＫｉとが使用でき、かつ署名生成に協力したことを証明できる参加者がｔ人以上ｔ’人以下であることが署名のみから確認できる。
【００４３】
［第６実施形態］
本発明は、参加者が署名生成に協力したことを証明した後も同じ公開鍵を使うことができるよう第１実施形態を改良したものであって、ｔを１≦ｔ≦ｎとする（ｔ，ｎ）閾値署名方式に関する。図４１は本発明のシステム構成例と流れを示す図であり、第１実施形態との違いは、参加装置６１０−ｉ（ｉ＝１，…，ｎ）、署名生成部６２０、および署名検証部６３０のそれぞれが、通常の秘密鍵と公開鍵（第１の秘密鍵と公開鍵）および署名者証拠ｒｉを公開すると使用できなくなる使い捨ての秘密鍵（第２の秘密鍵）の２種類の鍵に対応できるよう変更されたことである。２種類の鍵を使用することにより、第１実施形態の効果は維持しながら、公の機関に登録しているような公開鍵（第１の公開鍵）が署名者証拠ｒｉの公開後も使用できる。また、第４実施形態と第５実施形態との違いとしては、継続的に使用する第１の秘密鍵ＳＫｉと使い捨ての第２の秘密鍵ｓｋｉとをペアリング写像を用いて関連つけた点にあり、本発明では、署名生成部６２０は１つの署名σ（ｍ）のみを生成する。
【００４４】
まず、発明の説明のために追加または変更される記号等について簡単に説明する。Ｅ＝{０，Ｐ，２Ｐ，…，（ｐ−１）Ｐ}を加法によりＰで生成される位数ｐの巡回群とする。またＥは離散対数問題は難しい（つまりＰとａＰの値が分かっても、ａを求めることは難しい）巡回群である。Ｇ＝{１，ｇ，ｇ２，…，ｇ（ｑ−１）}を乗法によりｇで生成される位数ｑ（ただしｐはｑの約数）の巡回群とする。またＧは離散対数問題は難しい（つまりｇとｇａの値が分かっても、ａを求めることは難しい）巡回群である。＜・，・＞：Ｅ×Ｅ→Ｇを双線形性（つまり＜ａＰ，Ｑ＞＝＜Ｐ，ａＱ＞＝＜Ｐ，Ｑ＞ａが任意のａに対して成立する）と非退化性（つまり＜Ｐ，Ｑ＞＝１が任意のＱに対して成り立つならば、Ｐ＝０）を満たすペアリング写像とする。Ｈ，Ｉ，ＪはそれぞれＨ：{０，１}＊→Ｅ，Ｉ：Ｋ→Ｚｐ，Ｊ：{０，１}＊→Ｋのように変換するハッシュ関数である。このような群とペアリング写像は、楕円曲線とその上のベイユペアリング（Weil Pairing）を用いて実現することができる（例えばD. Boneh and M. Franklin, Identity-Based Encryption from the Weil Pairing, CRYPTO ’01, pp. 213-229, 2001.）。以下に本発明を詳しく説明する。
【００４５】
図４２に参加装置６１０−ｉの機能構成例を示す。参加装置６１０−ｉは、第１の鍵生成部６１１−ｉ、第２の鍵生成部６１２−ｉ、署名者証拠生成部６１３−ｉ、記録部６１４−ｉ、署名者証拠公開部１１５−ｉ、および通信部９１４−ｉから構成される。図４３は第１の鍵生成部６１１−ｉの処理フローを示す図、図４４は第２の鍵生成部６１２−ｉの処理フローを示す図、図４５は署名者証拠生成部６１３−ｉの処理フローを示す図である。
【００４６】
参加装置６１０−ｉ（ｉ＝１，…，ｎ）の鍵生成部６１１−ｉでは、以下の手順で第１の秘密鍵ＳＫｉと公開鍵ＰＫｉとを生成する。秘密鍵ＳＫｉ生成手段６１１１−ｉでは、ｐを法とする剰余類Ｚｐから等確率でランダムに１つの元ｓｉを選択して秘密鍵ＳＫｉとし（ＳＫｉ＝ｓｉ∈ＵＺｐ）（Ｓ６１１１）、秘密鍵ＳＫｉを記録部６１４−ｉに記録する（Ｓ６１１２）。公開鍵ＰＫｉ生成手段６１１２−ｉでは、あらかじめ定められた巡回群Ｅの元Ｐを用いて、ＰＫｉ＝ｓｉＰにより公開鍵ＰＫｉ（ＰＫｉ∈Ｅ）を生成し（Ｓ６１１３）、公開鍵ＰＫｉを記録部６１４−ｉに記録する（Ｓ６１１４）。ここで、巡回群Ｅは、離散対数問題が難しい群から選ばれているため、公開鍵ＰＫｉと元Ｐとが分かっても、秘密鍵ＳＫｉ（＝ｓｉ）は分からない。このように生成された公開鍵ＰＫｉは、元Ｐの情報とともに通信部９１４−ｉを介して公開される。
【００４７】
鍵生成部６１２−ｉでは、以下の手順で第２の秘密鍵ｓｋｉを生成する。まず、公開鍵ＰＫｉ（ｉ＝１，…，ｎ）取得手段６１２３−ｉで参加装置６１０−ｉ（ｉ＝１，…，ｎ）の公開鍵ＰＫｉを取得する（Ｓ６１２１）。Ｑｍ生成手段６１２２−ｉでは、Ｑｍ＝Ｈ（ｔ，ｎ，ＰＫ１，…，ＰＫｎ，ｍ）としてＱｍ（Ｑｍ∈Ｅ）を生成し（Ｓ６１２２）、Ｑｍを記録部６１４−ｉに記録するとともに公開する（Ｓ６１２３）。秘密鍵ｓｋｉ生成手段６１２１−ｉでは、ｓｋｉ＝ｓｉＱｍとして使い捨ての秘密鍵ｓｋｉ（ｓｋｉ∈Ｅ）を生成し（Ｓ６１２４）、秘密鍵ｓｋｉを記録部６１４−ｉに記録する（Ｓ６１２５）。なお、上記のＱｍを求める方法では全ての参加装置６１０−ｉの公開鍵ＰＫｉ（ｉ＝１，…，ｎ）を使用しており、どの参加装置で計算しても同じＱｍを得る。したがって、１つの参加装置または別の装置でＱｍを求め、各参加装置に送信しても良い。
【００４８】
参加者が署名に協力する場合には、署名者証拠生成部６１３−ｉの署名者証拠ｒｉ生成手段６１２１−ｉでは、ｐを法とする剰余類Ｚｐから等確率でランダムに１つの元を選択して署名者証拠ｒｉ（ｒｉ∈ＵＺｐ）とし（Ｓ６１２１）、記録部６１４−ｉに記録する（Ｓ１１２１）。次にコミットメントａｉ生成手段６１３２−ｉは、元Ｐを用いて、
【数３３】
2006203754.tif 000016
によりコミットメントａｉ（∈Ｇ）を生成し（Ｓ６１３２）、コミットメントａｉを記録部６１４−ｉに記録し、通信部９１４−ｉを介して署名生成部６２０に送信する（Ｓ９１２３）。署名生成部６２０で署名生成処理が行われると、署名生成部６２０の計算部６２２の処理過程で生成されたチャレンジｃｉが署名生成部６２０から、署名生成に協力している参加装置６１０−ｉ（ｉ＝１，…，ｔ）に送信される。このチャレンジｃｉをチャレンジｃｉ取得手段９１２３−ｉで取得し（Ｓ９１２４）、記録部９１３−ｉに記録する（Ｓ９１２５）。また、レスポンスｅｉ生成手段６１３２−ｉで、ｅｉ：＝ｒｉＱｍ−ｃｉｓｋｉ（ｅｉ∈Ｅ）により、ｅｉ（ｉ＝１，…，ｔ）を求め（Ｓ６１３６）、記録部６１４−ｉに記録するとともに署名生成部６２０に送信する（Ｓ９１２７）。
【００４９】
図４６に署名生成部６２０の機能構成例を示す。署名生成部６２０は、ダミー生成部６２１、計算部６２２、情報取得部６２３、記録部６２４、および通信部９２５から構成されている。また、図４７は署名生成部６２０の処理フローを示す図である。
【００５０】
署名生成部６２０では、以下の手順で署名σ（ｍ）が生成される。通信部９２５を介して情報取得部６２３の公開鍵ＰＫｉ（ｉ＝１，…，ｎ）取得手段４２３１により、参加装置９１０−ｉ（ｉ＝１，…，ｎ）の公開鍵ＰＫｉを取得する（Ｓ４２３１）。また、Ｑｍ取得手段６２３１により、Ｑｍを取得する（Ｓ６２３１）。ダミー生成部６２１では、次のように、ダミーレスポンスｅｉ、ダミーチャレンジｃｉ、ダミーコミットメントａｉ（ｉ＝ｔ＋１，…，ｎ）を生成する。ダミーレスポンスｅｉ（ｉ＝ｔ＋１，…，ｎ）生成手段６２１１により、ｐを法とする剰余類Ｚｐから等確率でランダムに１つの元を選択してダミーレスポンスｅｉ（ｉ＝ｔ＋１，…，ｎ）とし（ｅｉ∈ＵＺｐ）（Ｓ６２１１）、記録部６２４に記録する（Ｓ９２１２）。ダミーチャレンジｃｉ（ｉ＝ｔ＋１，…，ｎ）生成手段９２１２により、有限体Ｋから等確率でランダムに１つの座標値ｙｉを選び、そのハッシュ関数をダミーチャレンジｃｉ（ｉ＝ｔ＋１，…，ｎ）とし（ｙｉ∈ＵＫ，ｃｉ：＝Ｉ（ｙｉ）∈Ｚｐ）（Ｓ６２１３）、記録部６２４に記録する（Ｓ９２１４）。また、ダミーコミットメントａｉ（ｉ＝ｔ＋１，…，ｎ）生成手段６２１３により、元Ｐ、Ｑｍ、および公開鍵ＰＫｉを用いて、
【数３４】
2006203754.tif 000017
によりダミーコミットメントａｉ（ｉ＝ｔ＋１，…，ｎ）を生成し（Ｓ６２１５）、記録部６２４に記録する（Ｓ９２１６）。
【００５１】
また、通信部９２５を介して情報取得部６２３のコミットメントａｉ（ｉ＝１，…，ｔ）取得手段９２３２により、参加装置６１０−ｉ（ｉ＝１，…，ｔ）のコミットメントａｉを取得する（Ｓ９２３２と同じ）。
【００５２】
次に、計算部６２２では、以下のようにメッセージｍの（ｔ，ｎ）閾値署名σ（ｍ）を求める。ｎ−ｔ次多項式ｆ（ｘ）計算手段６２２１により、ｎ−ｔ次の多項式ｆ（ｘ）（ｆ（ｘ）＝α０＋α１ｘ＋α２ｘ２＋…＋αｎ−ｔｘｎ−ｔ，αｊ∈Ｋ）と定め、ｆ（０）＝Ｊ（ｔ，ｎ，ＰＫ１，…，ＰＫｎ，Ｑｍ，ａ１，…，ａｎ，ｍ）とｆ（ｉ）＝ｙｉ（ｉ＝ｔ＋１，…，ｎ）の条件からαｊ（ｊ＝０，…，ｎ−ｔ）を計算することでｎ−ｔ次多項式ｆ（ｘ）を求める（Ｓ６２２１）。また、求めたｎ−ｔ次多項式ｆ（ｘ）を記録部６２４に記録する（Ｓ９２２２）。チャレンジｃｉ（ｉ＝１，…，ｔ）生成手段９２２２では、ｃｉ：＝Ｉ（ｆ（ｉ））により、チャレンジｃｉ（ｉ＝１，…，ｔ）を求め（Ｓ９２２３）、記録部９２４に記録するとともに、チャレンジｃｉに対応する参加装置９１０−ｉ（ｉ＝１，…，ｔ）にチャレンジｃｉを送信する（Ｓ９２２４）。
【００５３】
各参加者装置６１０−ｉ（ｉ＝１，…，ｔ）では、送信されたチャレンジｃｉを用いて、上記のようにレスポンスｅｉを生成し署名生成部６２０に送信する（図４５のＳ９１２４〜Ｓ９１２７）。そこで、レスポンスｅｉ（ｉ＝１，…，ｔ）取得手段９２２３は、レスポンスｅｉ（ｉ＝１，…，ｔ）を取得し（Ｓ９２２５）、記録部６２４に記録する（Ｓ９２２６）。署名σ（ｍ）作成手段６２２３では、σ（ｍ）＝（ｆ，ｃ１，…，ｃｎ，ｅ１，…，ｅｎ）により、σ（ｍ）を求め（Ｓ６２２７）、記録部６２４に記録する（Ｓ９２２８）。このようにしてメッセージｍに対する（ｔ，ｎ）閾値署名σ（ｍ）を求める。
【００５４】
図４８に署名検証部６３０の機能構成例を、図４９に署名検証部６３０での署名σ（ｍ）を検証するフローを示す。なお、署名者証拠ｒｉを確認する処理フローは第１実施形態と同じである。署名σ（ｍ）を検証する場合は、情報取得手段６３４で公開鍵ＰＫｉ（ｉ＝１，…，ｎ）、Ｑｍ、および署名σ（ｍ）を取得し（Ｓ６３４）、多項式ｆ（ｘ）の次数確認手段９３１で多項式ｆ（ｘ）の次数がｎ−ｔであることを確認し（Ｓ９３１）、Ｑｍ確認手段６３２で、Ｑｍ＝Ｈ（ｔ，ｎ，ＰＫ１，…，ＰＫｎ，ｍ）かつＱｍ∈Ｅであることを確認し（Ｓ６３２）、チャレンジｃｉ、多項式ｆ（０）確認手段６３３で、
【数３５】
2006203754.tif 000018
であることを確認する（Ｓ９３２）。
【００５５】
このように署名σ（ｍ）を生成、検証することによって以下のような効果がある。署名生成に協力したことを参加者ｉが証明するために署名者証拠ｒｉを公開した場合、第２の秘密鍵ｓｋｉは、ｓｋｉ＝ｓｉＱｍ＝ｃｉ-1（ｒｉＱｍ−ｅｉ）により求めることができるが、Ｅは離散対数問題が難しい巡回群から選ばれているため、第１の秘密鍵ＳＫｉ（ＳＫｉ＝ｓｉ∈Ｚｐ）を求めることはできない。したがって、署名者証拠ｒｉ公開後も公開鍵ＰＫｉを使うことができる。また、チャレンジｃｉ、多項式ｆ（０）確認手段６３３で、
【数３６】
2006203754.tif 000019
を確認しているため、署名者証拠ｒｉ（ｒｉ∈Ｚｐ）と公開鍵ＰＫｉ（ＰＫｉ＝ｓｉＰ∈Ｅ）とは関連しており、署名者証拠ｒｉを示すことにより公開鍵ＰＫｉに対応する参加者ｉが署名に協力したことを証明することができる。
【００５６】
［第７実施形態］
本実施形態は、第１実施形態から第６実施形態の総括である。図５０に第１実施形態から第６実施形態をまとめた（ｔ，ｎ）閾値電子署名システムの処理フローを示す。図５０では、すべての実施形態に共通する装置（部）と処理工程を実線の四角で示し、第２実施形態から第５実施形態に必要な装置（部）と処理工程を点線の四角で示し、第４実施形態から第６実施形態に必要な装置（部）と処理工程を一点鎖線の四角で示す。第６実施形態に必要な処理工程を二点鎖線の四角で示す。
【００５７】
第４実施形態から第６実施形態の参加装置（４１０−ｉ、または６１０−ｉ）（ｉ＝１，…，ｎ）は、第１の秘密鍵ＳＫｉと公開鍵ＰＫｉを生成し、公開鍵ＰＫｉを公開する。第１の実施形態と第６実施形態の場合は、すべての参加装置（１１０−ｉ、または６１０−ｉ）（ｉ＝１，…，ｎ）は、署名に使用する秘密鍵ｓｋｉを生成し、第１の実施形態は公開鍵ｐｋｉも生成し、公開鍵ｐｋｉを公開する。第２実施形態と第４実施形態は参加装置（１１０−ｉ、または４１０−ｉ）（ｉ＝１，…，ｎ−１）が、署名に使用する秘密鍵ｓｋｉと公開鍵ｐｋｉを生成し、公開鍵ｐｋｉを公開する。第３実施形態と第５実施形態は参加装置（１１０−ｉ、または４１０−ｉ）（ｉ＝１，…，ｔ’）が、署名に使用する秘密鍵ｓｋｉと公開鍵ｐｋｉを生成し、公開鍵ｐｋｉを公開する。
【００５８】
第２実施形態から第５実施形態の場合は、ダミー鍵生成部（２４０、３４０，４４０，５４０）で、ダミーの公開鍵ｐｋｉ（ｉ＝ｎまたはｔ’，…，ｎ）を生成し、公開する。
署名生成に協力する参加装置（１１０−ｉ、４１０−ｉ、または６１０−ｉ）（ｉ＝１，…，ｔ）は、署名者証拠ｒｉとコミットメントａｉを生成し、コミットメントａｉを署名生成部（９２０、４２０、５２０、または６２０）に送信する。署名生成部（９２０、４２０、５２０、または６２０）では、署名生成に協力していない参加装置（１１０−ｉ、４１０−ｉ、または６１０−ｉ）（ｉ＝ｔ＋１，…，ｎ）に対応するダミーのレスポンスｅｉ、チャレンジｃｉ、およびコミットメントａｉを生成し、ｎ−ｔ次多項式ｆと署名生成に協力した参加装置（１１０−ｉ、４１０−ｉ、または６１０−ｉ）（ｉ＝１，…，ｔ）に対応するチャレンジｃｉを生成し、チャレンジｃｉを参加装置（１１０−ｉ、４１０−ｉ、または６１０−ｉ）（ｉ＝１，…，ｔ）に送信する。各参加装置（１１０−ｉ、４１０−ｉ、または６１０−ｉ）（ｉ＝１，…，ｔ）では、レスポンスｅｉを生成し署名生成部（９２０、４２０、５２０、または６２０）に送信する。署名生成部（９２０、４２０、５２０、または６２０）では、署名σ（第４実施形態と第５実施形態の場合は、さらにΣ）を生成する。署名検証部（１３０、２３０、３３０，４３０，５３０、または６３０）で、署名σ（第４実施形態と第５実施形態の場合は、さらにΣ）を確認し、第２実施形態から第５実施形態の場合は、署名参加者数を確認する。さらに、署名に協力した参加者が署名に協力したことを証明したい場合には、参加装置（１１０−ｉ、４１０−ｉ、または６１０−ｉ）（ｉ＝１，…，ｔ）は署名者証拠ｒｉを公開し、署名検証部（１３０、２３０、３３０，４３０，５３０、または６３０）は署名者証拠ｒｉを確認する。なお、各処理の詳細は、上記の第１実施形態から第６実施形態に示したとおりである。
【００５９】
このようなシステム構成と処理方法により、参加者が署名生成に協力したことを証明したい場合に、証明することができる。また、何人の参加者が証明できるのかを署名から確認できる。さらに、使い捨て秘密鍵（第２の秘密鍵）を使用することにより、公的機関に登録しているような公開鍵と組となる秘密鍵の情報流出を避けることができる。
【図面の簡単な説明】
【００６０】
【図１】閾値つき電子署名システムの構成例と流れを示す図。
【図２】参加装置９１０−ｉの機能構成例を示す図。
【図３】鍵生成部９１１−ｉの処理フローを示す図。
【図４】署名者証拠生成部９１２−ｉの処理フローを示す図。
【図５】署名生成部９２０の機能構成例を示す図。
【図６】署名生成部９２０の処理フローを示す図。
【図７】署名検証部９３０の機能構成例を示す図。
【図８】署名検証部９３０での署名σ（ｍ）を検証するフローを示す図。
【図９】第１実施形態のシステム構成例と流れを示す図。
【図１０】参加装置１１０−ｉの機能構成例を示す図。
【図１１】署名者証拠生成部１１２−ｉの処理フローを示す図。
【図１２】署名者証拠公開部１１５−ｉの処理フローを示す図
【図１３】署名検証部１３０の機能構成例を示す図。
【図１４】署名に協力したことを証明したい参加者から署名者証拠ｒｉが公開された場合の、署名者証拠ｒｉ確認フローを示す図。
【図１５】第２実施形態のシステム構成例と流れを示す図。
【図１６】ダミー鍵生成部２４０の機能構成例を示す図。
【図１７】ダミー鍵生成部２４０の処理フローを示す図。
【図１８】署名検証部２３０の機能構成例を示す図。
【図１９】署名検証部２３０が署名σ（ｍ）を検証するフローを示す図。
【図２０】第３実施形態のシステム構成例と流れを示す図。
【図２１】ダミー鍵生成部３４０の機能構成例を示す図。
【図２２】ダミー鍵生成部３４０の処理フローを示す図。
【図２３】署名検証部３３０の機能構成例を示す図。
【図２４】署名検証部３３０が署名σ（ｍ）を検証するフローを示す図。
【図２５】第４実施形態のシステム構成例と流れを示す図。
【図２６】参加装置４１０−ｉの機能構成例を示す図。
【図２７】第１の秘密鍵と公開鍵を生成する鍵生成部４１１−ｉの処理フローを示す図。
【図２８】ダミー鍵生成部４４０の構成例を示す図。
【図２９】ダミー鍵生成部４４０の処理フローを示す図。
【図３０】署名生成部４２０の機能構成例を示す図。
【図３１】署名生成部４２０の処理フローを示す図。
【図３２】署名検証部４３０の機能構成例を示す図。
【図３３】署名検証部４３０での署名σ（ｍ）と署名Σ（ｍ）の検証フローを示す図。
【図３４】第５実施形態のシステム構成例と流れを示す図。
【図３５】ダミー鍵生成部５４０の構成例を示す図。
【図３６】ダミー鍵生成部５４０の処理フローを示す図。
【図３７】署名生成部５２０の機能構成例を示す図。
【図３８】署名生成部５２０の処理フローを示す図。
【図３９】署名検証部５３０の機能構成例を示す図。
【図４０】署名検証部５３０での署名σ（ｍ）と署名Σ（ｍ）の検証フローを示す図。
【図４１】第６実施形態のシステム構成例と流れを示す図。
【図４２】参加装置６１０−ｉの機能構成例を示す図。
【図４３】第１の鍵生成部６１１−ｉの処理フローを示す図。
【図４４】第２の鍵生成部６１２−ｉの処理フローを示す図。
【図４５】署名者証拠生成部６１３−ｉの処理フローを示す図。
【図４６】署名生成部６２０の機能構成例を示す図。
【図４７】署名生成部６２０の処理フローを示す図。
【図４８】署名検証部６３０の機能構成例を示す図。
【図４９】署名検証部６３０での署名σ（ｍ）を検証するフローを示す図。
【図５０】第１実施形態から第６実施形態をまとめた（ｔ，ｎ）閾値電子署名システムの処理フローを示す図。
【図１】
2006203754.tif 000039
【図２】
2006203754.tif 000040
【図３】
2006203754.tif 000041
【図４】
2006203754.tif 000042
【図５】
2006203754.tif 000043
【図６】
2006203754.tif 000044
【図７】
2006203754.tif 000045
【図８】
2006203754.tif 000046
【図９】
2006203754.tif 000047
【図１０】
2006203754.tif 000048
【図１１】
2006203754.tif 000049
【図１２】
2006203754.tif 000050
【図１３】
2006203754.tif 000051
【図１４】
2006203754.tif 000052
【図１５】
2006203754.tif 000053
【図１６】
2006203754.tif 000054
【図１７】
2006203754.tif 000055
【図１８】
2006203754.tif 000056
【図１９】
2006203754.tif 000057
【図２０】
2006203754.tif 000058
【図２１】
2006203754.tif 000059
【図２２】
2006203754.tif 000060
【図２３】
2006203754.tif 000061
【図２４】
2006203754.tif 000062
【図２５】
2006203754.tif 000063
【図２６】
2006203754.tif 000064
【図２７】
2006203754.tif 000065
【図２８】
2006203754.tif 000066
【図２９】
2006203754.tif 000067
【図３０】
2006203754.tif 000068
【図３１】
2006203754.tif 000069
【図３２】
2006203754.tif 000070
【図３３】
2006203754.tif 000071
【図３４】
2006203754.tif 000072
【図３５】
2006203754.tif 000073
【図３６】
2006203754.tif 000074
【図３７】
2006203754.tif 000075
【図３８】
2006203754.tif 000076
【図３９】
2006203754.tif 000077
【図４０】
2006203754.tif 000078
【図４１】
2006203754.tif 000079
【図４２】
2006203754.tif 000080
【図４３】
2006203754.tif 000081
【図４４】
2006203754.tif 000082
【図４５】
2006203754.tif 000083
【図４６】
2006203754.tif 000084
【図４７】
2006203754.tif 000085
【図４８】
2006203754.tif 000086
【図４９】
2006203754.tif 000087
【図５０】
2006203754.tif 000088