JP4738003B2 - 署名システム、署名方法 - Google Patents

Description

本発明は、情報セキュリティ技術に関するものであり、閾値つき電子署名技術に関する。

閾値つき電子署名技術は、複数の参加者の一部が協力することで署名が生成されたことを、誰が署名生成に協力したのかが分からないように署名のみから確認できる電子署名である。ｎ人の参加者うち任意のｔ人以上が協力することで署名が生成されたことを、誰が署名生成に協力したのかが分からないように署名のみから確認できる電子署名の方式を、（ｔ，ｎ）閾値電子署名方式と呼ぶ。従来の方法として非特許文献１に示された方法がある。最初に本説明中で使用する記号について説明する。離散対数問題が難しいと考えられている巡回群をＧとし、その生成元をｇ、群の位数をｑとする（Ｇ＝＜ｇ＞，＃Ｇ＝ｑ）。Ｚ_ｑは、ｑを法とする剰余類{０，１，２，…，ｑ−１}である。∈_Ｕは一様ランダムに元を取り出すことを、{０，１}^＊は０または１が任意長並んだビット列を、Ｋは有限体を意味する。また、Ｈ，Ｉ，ＪはそれぞれＨ：{０，１}^＊→Ｇ，Ｉ：Ｋ→Ｚ_ｑ，Ｊ：{０，１}^＊→Ｋのように変換するハッシュ関数である。以下に非特許文献１に示された方法について説明する。

図１に、閾値つき電子署名システムの構成例と流れを示す。本システムへの参加者の総数はｎ人であり、ｎ台の参加装置９１０−ｉ（ｉ＝１，…，ｎ）では、あらかじめ定められた巡回群Ｇの元ｇ（ｇ∈Ｇ）を用いて、各参加装置の秘密鍵ｓｋ_ｉと公開鍵ｐｋ_ｉとが生成され、公開鍵ｐｋ_ｉは公開される。署名を作成する場合は、ｎ人中の任意のｔ人以上が参加装置９１０−ｉ（ｉ＝１，…，ｔ）でコミットメントａ_ｉを生成し、署名生成部９２０を備える装置に送信する。ここで、説明を簡略化するために、ｉ＝１，…，ｔを署名生成に使用した（協力した）参加装置を示す数、ｉ＝ｔ＋１，…，ｎを署名作成に使用していない（協力しなかった）参加装置を示す数とするが、ｔ台の参加装置はｎ台の参加装置中のどれでも良い。

署名生成部９２０は、独立した装置ででもかまわないし、いずれかの参加装置内に備えさせてもかまわない。署名生成部９２０は、ｉ＝ｔ＋１，…，ｎに対するダミーレスポンスｅ_ｉ、ダミーチャレンジｃ_ｉ、およびダミーコミットメントａ_ｉを生成した上で、ｎ−ｔ次多項式ｆ（ｘ）、ｉ＝１，…，ｔに対するチャレンジｃ_ｉとレスポンスｅ_ｉとを生成し、署名σ（ｍ）を作成する。この署名σ（ｍ）はｔ台の参加装置９１０−ｉ（ｉ＝１，…，ｔ）から取得したコミットメントａ_ｉと、署名生成部９２０がダミーとして生成したコミットメントａ_ｉ（ｉ＝ｔ＋１，…，ｎ）等から生成されており、ｔ人が協力した署名生成になっているだけでなく、どのｔ人が協力したのかが分からない署名になっている。

署名検証部９３０は、署名検証を行いたい任意の装置内に備えてかまわない。署名検証部では、多項式ｆ（ｘ）の次数がｎ−ｔであること、チャレンジｃ_ｉ（ｉ＝１，…，ｎ）とｆ（０）の値が正しいことなどを検証する。
図２は、参加装置９１０−ｉの機能構成例を示す図である。参加装置９１０−ｉは、鍵生成部９１１−ｉ、署名者証拠生成部９１２−ｉ、記録部９１３−ｉ、および通信部９１４−ｉから構成される。図３は鍵生成部９１１−ｉの処理フローを示す図であり、図４は署名者証拠生成部９１２−ｉの処理フローを示す図である。

鍵生成部９１１−ｉは、秘密鍵ｓｋ_ｉ生成手段９１１１−ｉと公開鍵ｐｋ_ｉ生成手段９１１２−ｉとで構成される。鍵生成部９１１-ｉでの具体的な鍵生成方法の例を次に示す。秘密鍵ｓｋ_ｉ生成手段９１１１−ｉでは、ｑを法とする剰余類Ｚ_ｑから等確率でランダムに１つの元を選択して秘密鍵ｓｋ_ｉとし（ｓｋ_ｉ∈_ＵＺ_ｑ）（Ｓ９１１１）、秘密鍵ｓｋ_ｉを記録部９１３−ｉに記録する（Ｓ９１１２）。公開鍵ｐｋ_ｉ生成手段９１１２−ｉでは、あらかじめ定められた巡回群Ｇの元ｇを用いて、

により公開鍵ｐｋ_ｉ（ｐｋ_ｉ∈Ｇ＝{１，ｇ，ｇ^２，…，ｇ^ｑ−１}）を生成し（Ｓ９１１３）、公開鍵ｐｋ_ｉを記録部９１３−ｉに記録する（Ｓ９１１４）。ここで、巡回群Ｇは、離散対数問題が難しい群から選ばれているため、公開鍵ｐｋ_ｉと元ｇが分かっても、秘密鍵ｓｋ_ｉは分からない。このように生成された公開鍵ｐｋ_ｉは、元ｇの情報とともに通信部９１４−ｉを介して公開される。

署名者証拠生成部９１２−ｉは、署名生成に協力する場合に動作する構成部であり、署名者証拠ｒ_ｉ生成手段９１２１−ｉ、コミットメントａ_ｉ生成手段９１２２−ｉ、チャレンジｃ_ｉ取得手段９１２３−ｉ、およびレスポンスｅ_ｉ生成手段９１２２−ｉで構成される。署名者証拠生成部９１２−ｉでの具体的な処理手順の例を次に示す。参加者が署名に協力する場合には、署名者証拠ｒ_ｉ生成手段９１２１−ｉでは、ｑを法とする剰余類Ｚ_ｑから等確率でランダムに１つの元を選択して署名者証拠ｒ_ｉとする（ｒ_ｉ∈_ＵＺ_ｑ）（Ｓ９１２１）。次にコミットメントａ_ｉ生成手段９１２２−ｉでは、元ｇを用いて、

によりコミットメントａ_ｉ（∈Ｇ）を生成し（Ｓ９１２２）、コミットメントａ_ｉを記録部９１３−ｉに記録し、通信部９１４−ｉを介して署名生成部９２０を備える装置に送信する（Ｓ９１２３）。通常、署名者証拠ｒ_ｉはコミットメントａ_ｉを生成すれば不要となるため、記録部９１３−ｉに記録されること無く消去される。署名生成部９２０で署名生成処理が行われると、署名生成部９２０の計算部９２２の処理過程で生成されたチャレンジｃ_ｉが署名生成部９２０から、署名生成に協力している参加装置９１０−ｉ（ｉ＝１，…，ｔ）に送信される。このチャレンジｃ_ｉをチャレンジｃ_ｉ取得手段９１２３−ｉで取得し（Ｓ９１２４）、記録部９１３−ｉに記録する（Ｓ９１２５）。また、レスポンスｅ_ｉ生成手段９１２２−ｉで、ｅ_ｉ：＝ｒ_ｉ−ｃ_ｉｓｋ_ｉ（ｅ_ｉ∈Ｚ_ｑ）により、ｅ_ｉ（ｉ＝１，…，ｔ）を求め（Ｓ９１２６）、記録部９１３−ｉに記録するとともに署名生成部９２０に送信する（Ｓ９１２７）。

図５に署名生成部９２０の機能構成例を示す。署名生成部９２０は、ダミー生成部９２１、計算部９２２、情報取得部９２３、記録部９２４、および通信部９２５から構成されている。また、図６は署名生成部９２０の処理フローを示す図である。
署名生成部９２０では、以下の手順で署名σ（ｍ）が生成される。通信部９２５を介して情報取得部９２３の公開鍵ｐｋ_ｉ（ｉ＝１，…，ｎ）取得手段９２３１により、参加装置９１０−ｉ（ｉ＝１，…，ｎ）の公開鍵ｐｋ_ｉを取得する（Ｓ９２３１）。ダミー生成部９２１では、次のように、ダミーレスポンスｅ_ｉ、ダミーチャレンジｃ_ｉ、ダミーコミットメントａ_ｉ（ｉ＝ｔ＋１，…，ｎ）を生成する。ダミーレスポンスｅ_ｉ（ｉ＝ｔ＋１，…，ｎ）生成手段９２１１により、ｑを法とする剰余類Ｚ_ｑから等確率でランダムに１つの元を選択してダミーレスポンスｅ_ｉ（ｉ＝ｔ＋１，…，ｎ）とし（ｅ_ｉ∈_ＵＺ_ｑ）（Ｓ９２１１）、記録部９２４に記録する（Ｓ９２１２）。ダミーチャレンジｃ_ｉ（ｉ＝ｔ＋１，…，ｎ）生成手段９２１２により、有限体Ｋから等確率でランダムに１つの座標値ｙ_ｉを選び、そのハッシュ関数をダミーチャレンジｃ_ｉ（ｉ＝ｔ＋１，…，ｎ）とし（ｙ_ｉ∈_ＵＫ，ｃ_ｉ：＝Ｉ（ｙ_ｉ）∈Ｚ_ｑ）（Ｓ９２１３）、記録部９２４に記録する（Ｓ９２１４）。また、ダミーコミットメントａ_ｉ（ｉ＝ｔ＋１，…，ｎ）生成手段９２１３により、元ｇと公開鍵ｐｋ_ｉを用いて、

によりダミーコミットメントａ_ｉ（ｉ＝ｔ＋１，…，ｎ）を生成し（Ｓ９２１５）、記録部９２４に記録する（Ｓ９２１６）。

また、通信部９２５を介して情報取得部９２３のコミットメントａ_ｉ（ｉ＝１，…，ｔ）取得手段９２３２により、参加装置９１０−ｉ（ｉ＝１，…，ｔ）のコミットメントａ_ｉを取得する（Ｓ９２３２）。

次に、計算部９２２では、以下のようにメッセージｍの（ｔ，ｎ）閾値署名σ（ｍ）を求める。ｎ−ｔ次多項式ｆ（ｘ）計算手段９２２１により、ｎ−ｔ次の多項式ｆ（ｘ）（ｆ（ｘ）＝α_０＋α_１ｘ＋α_２ｘ^２＋…＋α_ｎ−ｔｘ^ｎ−ｔ，α_ｊ∈Ｋ）と定め、ｆ（０）＝Ｊ（ｔ，ｎ，ｐｋ_１，…，ｐｋ_ｎ，ａ_１，…，ａ_ｎ，ｍ）とｆ（ｉ）＝ｙ_ｉ（ｉ＝ｔ＋１，…，ｎ）の条件からα_ｊ（ｊ＝０，…，ｎ−ｔ）を計算することでｎ−ｔ次多項式ｆ（ｘ）を求める（Ｓ９２２１）。また、求めたｎ−ｔ次多項式ｆ（ｘ）を記録部９２４に記録する（Ｓ９２２２）。チャレンジｃ_ｉ（ｉ＝１，…，ｔ）生成手段９２２２では、ｃ_ｉ：＝Ｉ（ｆ（ｉ））により、チャレンジｃ_ｉ（ｉ＝１，…，ｔ）を求め（Ｓ９２２３）、記録部９２４に記録するとともに、チャレンジｃ_ｉに対応する参加装置９１０−ｉ（ｉ＝１，…，ｔ）にチャレンジｃ_ｉを送信する（Ｓ９２２４）。各参加者装置９１０−ｉ（ｉ＝１，…，ｔ）では、送信されたチャレンジｃ_ｉを用いて、上記のようにレスポンスｅ_ｉを生成し署名生成部９２０に送信する（Ｓ９１２４〜Ｓ９１２７）。そこで、レスポンスｅ_ｉ（ｉ＝１，…，ｔ）取得手段９２２３は、レスポンスｅ_ｉ（ｉ＝１，…，ｔ）を取得し（Ｓ９２２５）、記録部９２４に記録する（Ｓ９２２６）。署名σ（ｍ）作成手段９２２３では、σ（ｍ）＝（ｔ，ｎ，ｆ，ｃ_１，…，ｃ_ｎ，ｅ_１，…，ｅ_ｎ）により、σ（ｍ）を求め（Ｓ９２２７）、記録部９２４に記録する（Ｓ９２２８）。このようにしてメッセージｍに対する（ｔ，ｎ）閾値署名σ（ｍ）を求める。

図７に署名検証部９３０の機能構成例を示す。また、図８に署名検証部９３０での署名σ（ｍ）を検証するフローを示す。情報取得手段９３３は、公開鍵ｐｋ_ｉ（ｉ＝１，…，ｎ）と署名σ（ｍ）を取得し（Ｓ９３３）、多項式ｆ（ｘ）の次数確認手段９３１で多項式ｆ（ｘ）の次数がｎ−ｔであることを確認し（Ｓ９３１）、チャレンジｃ_ｉ、多項式ｆ（０）確認手段９３２で、

であることを確認する（Ｓ９３２）。

このように署名σ（ｍ）の生成と検証を行うことで、署名検証部９３０（署名検証をする人）は、少なくともｔ台の参加装置９１０−ｉ（ｔ人の参加者）が協力して署名を作成したことが確認できる。また、署名検証部９３０は、ｎ台の参加装置９１０−ｉ中のどのｔ台（ｎ人の参加者中のどのｔ人）が署名生成に協力したのかは分からない。
[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.

従来技術では、どの参加者が署名生成に協力したのかが分からないことを特徴としているが、参加者が署名生成に協力したことを証明すること（名乗り出ること）もできなかった。
また、署名生成に協力したことを証明することができるようにする場合には、何人の参加者が証明できるのかを署名から確認できるようにすることも必要である。さらに、署名生成に協力したことを証明するときに秘密鍵の情報も流出することが考えられることから、以後、今までの秘密鍵と公開鍵が使用できなくなる。

本発明では、あらかじめ参加装置の記録部で署名者証拠を記録しておき、参加者が署名生成に協力したことを証明したい場合に当該署名者証拠を公開し、署名検証装置で当該署名者証拠を確認する。
また、何人の参加者が証明できるのかを署名から確認できるようにするための手段は以下のとおりである。ダミー鍵生成装置の情報取得部で署名生成に協力していない参加装置に対する公開鍵を少なくとも１つ生成し、当該公開鍵および公開鍵生成時に使用した乱数と離散対数問題の難しい巡回群の元を公開する。署名生成装置でダミーの公開鍵も用いて電子署名を生成する。署名検証装置でダミーの公開鍵を含めて公開鍵を取得し、ダミーの公開鍵生成時に使用した上記乱数と離散対数問題の難しい巡回群の上記元も取得し、署名者参加者数を確認する。

さらに、署名生成に協力したことを証明するときに秘密鍵の情報も流出することに対応する手段は以下のとおりである。参加装置では、公的機関に公開鍵を登録するような長期的に使用する秘密鍵と公開鍵の組（第１の秘密鍵と公開鍵）の他に、署名生成に用いる使い捨ての秘密鍵と公開鍵の組（第２の秘密鍵と公開鍵）を生成し、ダミー鍵生成装置で少なくとも１つの第２の公開鍵に対するダミー公開鍵を生成する。署名生成装置では、第１の署名と第２の署名とを生成する。署名検証装置では、参加者装置ごとの第１の公開鍵、第２の公開鍵を取得し、第１の署名および第２の署名の確認を行う。

または、参加装置で、署名生成に用いる使い捨ての秘密鍵（第２の秘密鍵）を、第１の秘密鍵から生成する。署名生成装置では、第２の秘密鍵を用いた署名だけを生成する。署名検証装置で、第１の公開鍵および第１の鍵生成と第２の鍵生成で使用した２つの問題の難しい巡回群の元を用いて署名を検証する。

本発明では上記のような手段により、参加者が署名生成に協力したことを証明したい場合に、証明することができる。また、何人の参加者が証明できるのかを署名から確認できる。さらに、使い捨て秘密鍵（第２の秘密鍵）を使用することにより、公的機関に登録しているような公開鍵と組となる秘密鍵の情報流出を避けることができる。

以下にこの発明の実施形態を図面を参照して説明するが、同一の機能を有する部分は、各図中に同一参照番号を付けて重複説明を省略する。また、以下の説明でも背景技術の説明と同様に、説明を簡単にするために、ｉ＝１，…，ｔを署名生成に協力した参加装置を示す数、ｉ＝ｔ＋１，…，ｎを署名作成に協力しなかった参加装置を示す数とするが、ｔ台の参加装置はｎ台の参加装置中のどれでも良い。

［第１実施形態］
本発明では、ｔを１≦ｔ≦ｎとし、（ｔ，ｎ）閾値署名方式で署名に協力した参加者ｉ（ｉ＝１，…，ｔ）が、署名検証後に署名に協力したことを証明できる。図９は本発明のシステム構成例と流れを示す図であり、従来技術のシステム構成例を示す図である図１との違いは、次の点である。各参加者装置１１０−ｉ（ｉ＝１，…，ｔ）が、署名作成に協力する過程で生成した署名者証拠ｒ_ｉを記録しておき、署名生成に協力したこと（署名者の１人であったこと）を証明したい場合に、署名者証拠ｒ_ｉを、署名検証部１３０を備える装置に送信することで、署名生成に協力したことを証明する。以下に、従来技術と異なる構成装置について詳細に説明する。

図１０は、参加装置１１０−ｉの機能構成例を示す図である。参加装置１１０−ｉは、従来の参加装置９１０−ｉとは、署名者証拠生成部１１２−ｉと記録部１１３−ｉが異なり、署名者証拠公開部１１５−ｉが追加されている。図１１は署名者証拠生成部１１２−ｉの処理フローを示す図であり、図１２は署名者証拠公開部１１５−ｉの処理フローを示す図である。図１１に示すように、署名者証拠生成部１１２−ｉでは、従来であれば、通常コミットメントａ_ｉを生成すれば不要となる署名者証拠ｒ_ｉを、記録部９１３−ｉに記録する工程（Ｓ１１２１）を署名者証拠ｒ_ｉ生成ステップ（Ｓ９１２１）の後に追加した処理を行う。また、参加者ｉが署名生成に協力したことを証明したい場合には、図１２に示すように、署名者証拠公開部１１５−ｉは、記録部１１３−ｉに記録された署名者証拠ｒ_ｉを署名検証部１３０に対して公開する（Ｓ１１５）。

図１３に署名検証部１３０の機能構成例を示す。図７に示す従来の署名検証部９３０との違いは、署名者証拠ｒ_ｉ確認手段１３３が追加されたことと、情報取得手段１３４が署名者証拠ｒ_ｉも取得するよう変更されたことである。図１４に署名に協力したことを証明したい参加者から署名者証拠ｒ_ｉが公開された場合の、署名者証拠ｒ_ｉ確認フローを示す。署名に協力したことを証明したい参加者ｉから署名者証拠ｒ_ｉが公開された場合には、署名検証部１３０の情報取得手段１３４は署名者証拠ｒ_ｉを取得する（Ｓ１３４）。次に、署名者証拠ｒ_ｉ確認手段１３３で、

であることを確認する（Ｓ１３３）ことで、署名者証拠ｒ_ｉを公開した参加者ｉが署名生成に協力した参加者であることが分かる。

ただし、署名者証拠ｒ_ｉ、レスポンスｅ_ｉ、チャレンジｃ_ｉ、および秘密鍵ｓｋ_ｉの間には、ｅ_ｉ＝ｒ_ｉ−ｃ_ｉｓｋ_ｉの関係があるため、署名者証拠ｒ_ｉを公開することで、秘密鍵ｓｋ_ｉも分かってしまう。したがって、署名に協力したことを証明した後は、これまで使用してきた秘密鍵ｓｋ_ｉと公開鍵ｐｋ_ｉの組は使用できなくなる。

［第２実施形態］
本発明は、ｔを１≦ｔ≦ｎ−１とする（ｔ，ｎ−１，ｎ）閾値署名方式に関する。（ｔ，ｎ−１，ｎ）閾値署名方式とは、署名者であったことを証明することができる参加者は、ｔ人以上ｎ-１人以下であることを署名のみから確認できる方式である。図１５は、本発明のシステム構成例と流れを示す図であり、第１実施形態との違いは、ダミー鍵生成部２４０が追加されたことと、署名検証部２３０が変更されたことである。ダミー鍵生成部２４０では、参加装置１１０−ｎの鍵生成部９１１−ｎの代わりに署名生成に使用する公開鍵ｐｋ_ｎを生成する。この公開鍵ｐｋ_ｎを用いて署名を生成することで、署名者であったことを証明することができる参加者がｔ人以上ｎ-１人以下であることを署名のみから確認できる方式を実現する。以下に本発明を詳しく説明する。

図１６にダミー鍵生成部２４０の機能構成例を、図１７にダミー鍵生成部２４０の処理フローを示す。ダミー鍵生成部２４０では、通信部２４３を介して情報取得部２４２の公開鍵ｐｋ_ｉ（ｉ＝１，…，ｎ−１）取得手段２４２１で、参加装置１１０−ｉ（ｉ＝１，…，ｎ−１）の公開鍵ｐｋ_ｉを取得する（Ｓ２４２１）。計算部２４１のダミー公開鍵ｐｋ_ｎ生成手段２４１１で、巡回群Ｇに属する元ｘ（ｘ∈Ｇ）を、例えば{０，１}^＊の乱数Ｒのハッシュ値として生成する（ｘ＝Ｈ（Ｒ））。例えば、乱数Ｒのビット長を１０２４とする。ここで、秘密鍵ｓｋ_ｉはｑを法とする剰余類Ｚ_ｑから等確率でランダムに１つの元（ｓｋ_ｉ∈_ＵＺ_ｑ）であり（Ｓ９１１１参照）、公開鍵ｐｋ_ｉは巡回群Ｇの元（ｐｋ_ｉ∈Ｇ）である（Ｓ９１１３参照）。公開鍵ｐｋ_ｎをｐｋ_ｎ：＝ｘ/ｐｋ_１ｐｋ_２…ｐｋ_ｎ−１と定め（Ｓ２４１１）、公開鍵ｐｋ_ｎ、元ｘ、および乱数Ｒを公開する（Ｓ２４１２）。このように公開鍵ｐｋ_ｎを定めると、ｘの離散対数は分からないので参加者ｎの秘密鍵は分からない。

なお、ダミー鍵生成部２４０を各参加装置１１０−ｉ（ｉ＝１，…，ｎ）に備えさせておき、ダミーの公開鍵を作ることとした１つの参加装置１１０−ｎだけは、ダミー鍵生成部２４０で公開鍵ｐｋ_ｎを生成することとしてもよい。また、単独のダミー鍵生成部２４０を具備するダミー鍵生成装置を１つ設置し、参加装置１１０−ｎの代わりに公開鍵ｐｋ_ｎを生成し、直接または参加装置１１０−ｎ経由で公開鍵ｐｋ_ｎを公開してもよい。

図１８に署名検証部２３０の機能構成例を示す。第１実施形態との違いは、署名参加者数確認手段２３５が追加されたことと、情報取得手段２３４が元ｘとＲも取得するよう変更されたことである。図１９に署名検証部２３０が署名σ（ｍ）を検証するフローを示す。第１実施形態の署名σ（ｍ）の検証フローは従来技術を同じであるので、本フローの違いは図８に示した従来の署名σ（ｍ）の検証フローとの違いを説明する。署名検証部２３０では、情報取得手段２３４で、公開鍵ｐｋ_ｉ（ｉ＝１，…，ｎ）、署名σ（ｍ）、元ｘ、および乱数Ｒを取得し（Ｓ２３４）、多項式ｆ（ｘ）の次数確認（Ｓ９３１と同じ）、チャレンジｃ_ｉ、多項式ｆ（０）確認（Ｓ９３２と同じ）を行う。さらに、署名参加者数確認手段２３５で、ｘ＝Ｈ（Ｒ）とｐｋ_１ｐｋ_２…ｐｋ_ｎ＝ｘを確認する（Ｓ２３５）。

このように署名σ（ｍ）を生成、検証することで、どの公開鍵ｐｋ_ｉかは分からないが、少なくとも１つは秘密鍵がないダミーの公開鍵があることになるため、署名生成に協力したことを証明できる参加者がｔ人以上ｎ−１人以下であることが署名のみから確認できる。

［第３実施形態］
本発明は、ｔとｔ’とを１≦ｔ≦ｔ'≦ｎ−１とする（ｔ，ｔ’，ｎ）閾値署名方式に関する。（ｔ，ｔ’，ｎ）閾値署名方式とは、署名者であったことを証明することができる参加者は、ｔ人以上ｔ’人以下であることを署名のみから確認できる方式である。図２０は、本発明のシステム構成例と流れを示す図であり、第２実施形態との違いは、ダミー鍵生成部３４０と署名検証部３３０が変更されたことである。ダミー鍵生成部３４０では、参加装置１１０−ｉ（ｉ＝ｔ’，…，ｎ）の鍵生成部９１１−ｉ（ｉ＝ｔ’，…，ｎ）の代わりに署名生成に使用する公開鍵ｐｋ_ｉ（ｉ＝ｔ’，…，ｎ）を生成する。この公開鍵ｐｋ_ｉを用いて署名を生成することで、署名者であったことを証明することができる参加者がｔ人以上ｔ'人以下であることを署名のみから確認できる方式を実現する。以下に本発明を詳しく説明する。

図２１にダミー鍵生成部３４０の機能構成例を、図２２にダミー鍵生成部３４０の処理フローを示す。ダミー鍵生成部３４０では、通信部２４３を介して情報取得部３４２の公開鍵ｐｋ_ｉ（ｉ＝１，…，ｔ'）取得手段３４２１で、参加装置１１０−ｉ（ｉ＝１，…，ｔ'）の公開鍵ｐｋ_ｉを取得する（Ｓ３４２１）。計算部３４１のダミー公開鍵ｐｋ_ｉ（ｉ＝ｔ'＋１，…，ｎ）生成手段では、巡回群Ｇに属する元Ａ_０（Ａ_０∈Ｇ）を、例えば{０，１}^＊の乱数Ｒのハッシュ値として生成する（Ａ_０＝Ｈ（Ｒ））。（ｍ_ｉｊ）を、

のｔ'×ｔ'行列（ｉ^ｊ）の逆行列として、Ａ_ｉ（ｉ＝１，…，ｔ'）を

と定め、公開鍵ｐｋ_ｉ（ｉ＝ｔ'＋１，…，ｎ）を

として公開鍵ｐｋ_ｉを生成し（Ｓ３４１１）、公開鍵ｐｋ_ｉ、元Ａ_ｉ、および乱数Ｒを公開する（Ｓ３４１２）。このように公開鍵ｐｋ_ｉ（ｉ＝ｔ'＋１，…，ｎ）を生成すれば、公開鍵ｐｋ_ｉ∈Ｇを満足するので、ｔ’次多項式Ｆ（Ｆ∈Ｚ_ｑ［ｘ］）が存在し、秘密鍵ｓｋ_ｉ＝Ｆ（ｉ）かつｌｏｇ_ｇＡ_０＝Ｆ（０）となっている。ここで、Ａ_０の離散対数は分からないので、参加者ｉ（ｉ＝ｔ'＋１，…，ｎ）の秘密鍵は分からない。

図２３に署名検証部３３０の機能構成例を示す。第２実施形態との違いは、署名参加者数確認手段３３５と、情報取得手段３３４が変更されたことである。図２４に署名検証部３３０が署名σ（ｍ）を検証するフローを示す。署名検証部３３０では、情報取得手段３３４で、公開鍵ｐｋ_ｉ（ｉ＝１，…，ｎ）、署名σ（ｍ）、元Ａ_ｉ（ｉ＝１，…，ｔ'）、および乱数Ｒを取得し（Ｓ３３４）、多項式ｆ（ｘ）の次数確認（Ｓ９３１と同じ）、チャレンジｃ_ｉ、多項式ｆ（０）確認（Ｓ９３２と同じ）を行う。さらに、署名参加者数確認手段３３５で、Ａ_０＝Ｈ（Ｒ）と

（ｐｋ_ｉ∈Ｇ）（ｉ＝１，…，ｎ）を確認する（Ｓ３３５）。

このように署名σ（ｍ）を生成、検証することで、どの公開鍵ｐｋ_ｉかは分からないが、少なくともｎ−ｔ’は秘密鍵がないダミーの公開鍵があることになるため、署名生成に協力したことを証明できる参加者がｔ人以上ｔ’人以下であることが署名のみから確認できる。

［第４実施形態］
本発明は、参加者が署名生成に協力したことを証明した後も同じ公開鍵を使うことができるよう第２実施形態を改良したものであって、ｔを１≦ｔ≦ｎ−１とする（ｔ，ｎ−１，ｎ）閾値署名方式に関する。図２５は、本発明のシステム構成例と流れを示す図であり、第２実施形態との違いは、参加装置４１０−ｉ（ｉ＝１，…，ｎ）、署名生成部４２０、署名検証部４３０、およびダミー鍵生成部４４０のそれぞれが、通常の秘密鍵と公開鍵（第１の秘密鍵と公開鍵）および署名者証拠ｒ_ｉを公開すると使用できなくなる使い捨ての秘密鍵と公開鍵（第２の秘密鍵と公開鍵）の２種類の鍵に対応できるよう変更されたことである。２種類の鍵を使用することにより、第２実施形態の効果は維持しながら、公の機関に登録しているような公開鍵（第１の公開鍵）が署名者証拠ｒ_ｉの公開後も使用できる。以下に本発明を詳しく説明する。

図２６は、参加装置４１０−ｉの機能構成例を示す図である。参加装置４１０−ｉは、第１の秘密鍵と公開鍵を生成する鍵生成部４１１−ｉ、第２の秘密鍵と公開鍵を生成する鍵生成部９１１−ｉ、署名者証拠生成部１１２−ｉ、記録部４１３−ｉ、通信部９１４−ｉ、および署名者証拠公開部１１５−ｉから構成される。図２７は第１の秘密鍵と公開鍵を生成する鍵生成部４１１−ｉの処理フローを示す図である。鍵生成部４１１−ｉの秘密鍵ＳＫ_ｉ生成手段４１１１−ｉでは、任意の（ｔ，ｎ）閾値署名Σ（ｍ）の方法で秘密鍵ＳＫ_ｉを生成し（Ｓ４１１１）、記録部４１３−ｉに記録する（Ｓ４１１２）。この（ｔ，ｎ）閾値署名Σ（ｍ）は従来からある技術を用いればよいし、鍵生成部９１１−ｉと同じ方法でも良い。公開鍵ＰＫ_ｉ生成手段４１１２−ｉでは、上記の秘密鍵ＳＫ_ｉ生成手段４１１１−ｉに対応した方法で公開鍵ＰＫ_ｉを生成し（Ｓ４１１３）、記録部４１３−ｉに記録する（Ｓ４１１４）。鍵生成部４１１−ｉで生成された秘密鍵ＳＫ_ｉと公開鍵ＰＫ_ｉの組が、継続的に使用し、署名者証拠ｒ_ｉを公開後も使用できる鍵となる。また、鍵生成部９１１−ｉで生成された秘密鍵ｓｋ_ｉと公開鍵ｐｋ_ｉの組（鍵生成フローは図３と同じ）が使い捨ての鍵であり、署名者証拠ｒ_ｉを公開後は使用できない鍵となる。なお、署名者証拠生成部１１２−ｉと署名者証拠ｒ_ｉ公開部１１５−ｉは第１実施形態と同じである。

図２８にダミー鍵生成部４４０の構成例を、図２９にダミー鍵生成部４４０の処理フローを示す。ダミー鍵生成部４４０では、通信部２４３を介して情報取得部４４２の公開鍵ＰＫ_ｉ（ｉ＝１，…，ｎ−１）取得手段４４２１で、参加装置４１０−ｉ（ｉ＝１，…，ｎ−１）の公開鍵ＰＫ_ｉを取得する（Ｓ４４２１）。また、情報取得部２４２の公開鍵ｐｋ_ｉ（ｉ＝１，…，ｎ−１）取得手段２４２１で、参加装置４１０−ｉ（ｉ＝１，…，ｎ−１）の公開鍵ｐｋ_ｉを取得する（Ｓ２４２１と同じ）。計算部４４１のダミー公開鍵ｐｋ_ｎ生成手段４４１１で、Ｒ＝（ｔ，ｎ−１，ｎ，ＰＫ_１，…，ＰＫ_ｎ，ｍ）として、巡回群Ｇに属する元ｘ（ｘ∈Ｇ）を、Ｒのハッシュ値として生成する（ｘ＝Ｈ（Ｒ））。公開鍵ｐｋ_ｎをｐｋ_ｎ：＝ｘ/ｐｋ_１ｐｋ_２…ｐｋ_ｎ−１と定め（Ｓ４４１１）、公開鍵ｐｋ_ｎ、元ｘ、およびＲを公開する（Ｓ２４１２と同じ）。このように公開鍵ｐｋ_ｎを定めると、ｘの離散対数は分からないので参加者ｎの秘密鍵は分からない。

図３０に署名生成部４２０の機能構成例を示す。署名生成部４２０は、ダミー生成部９２１、計算部４２２、情報取得部４２３、記録部４２４、および通信部９２５から構成されている。また、図３１は署名生成部４２０の処理フローを示す図である。
署名生成部４２０では、以下の手順で署名σ（ｍ）と署名Σ（ｍ）が生成される。通信部９２５を介して情報取得部４２３の公開鍵ＰＫ_ｉ（ｉ＝１，…，ｎ）取得手段４２３１により、参加装置９１０−ｉ（ｉ＝１，…，ｎ）の公開鍵ＰＫ_ｉを取得する（Ｓ４２３１）。ステップＳ９２３１の公開鍵ｐｋ_ｉ（ｉ＝１，…，ｎ）の取得、ダミー鍵生成部の処理フローであるステップＳ９２１１〜ステップＳ９２１６、およびステップＳ９２３２のコミットメントａ_ｉ（ｉ＝１，…，ｔ）の取得は、図６での説明と同じである。また、情報取得部４２３の元ｘ取得手段４２３３では、元ｘを取得する（Ｓ４２３３）。計算部４２２の処理のステップＳ９２２１〜Ｓ９２２８の処理は、図６の説明と同じである。したがって、ｎ−ｔ次多項式ｆ（ｘ）、チャレンジｃ_ｉ（ｉ＝１，…，ｔ）、レスポンスｅ_ｉ（ｉ＝１，…，ｔ）、メッセージｍに対する（ｔ，ｎ）閾値署名σ（ｍ）は、第２実施形態と同じで、背景技術として説明した従来技術と同じである。次に、署名作成手段４２２５では、Ｍ＝（ｔ，ｎ−１，ｎ，ＰＫ_１，…，ＰＫ_ｎ，ｍ，ｘ，ｐｋ_１，…，ｐｋ_ｎ）とし、（Ｍ，σ（Ｍ），Σ（Ｍ，σ（Ｍ））、（Ｍ，Σ（Ｍ），σ（Ｍ，Σ（Ｍ）））、もしくは（Ｍ，σ（Ｍ），Σ（Ｍ））を署名とし（Ｓ４２２７）、記録部４２４への記憶と公開を行う（Ｓ４２２８）。なお、Σ（ｍ）はステップＳ４４１１での秘密鍵ＳＫ_ｉの生成方法に対応した任意の（ｔ，ｎ）閾値署名Σ（ｍ）の方法を用いればよい。

図３２に署名検証部４３０の機能構成例を、図３３に署名検証部４３０での署名σ（ｍ）と署名Σ（ｍ）の検証フローを示す。情報取得手段４３４で、公開鍵ＰＫ_ｉ（ｉ＝１，…，ｎ）、公開鍵ｐｋ_ｉ（ｉ＝１，…，ｎ）、署名σ（ｍ）、元ｘ、およびＲを取得する（Ｓ４３４）。多項式ｆ（ｘ）の次数確認（Ｓ９３１と同じ）、チャレンジｃ_ｉ、多項式ｆ（０）確認（Ｓ９３２と同じ）を行うことで、σ（ｍ）の検証ができる。また、Σ（ｍ）の検証は、ステップＳ４４１１での秘密鍵ＳＫ_ｉの生成方法に対応した任意の（ｔ，ｎ）閾値署名Σ（ｍ）の方法を用いて行う（Ｓ４３１）。さらに、署名参加者数確認手段２３５で、ｘ＝Ｈ（Ｒ）とｐｋ_１ｐｋ_２…ｐｋ_ｎ＝ｘを確認する（Ｓ２３５と同じ）。

このように署名σ（ｍ）と署名Σ（ｍ）を生成、検証することで、署名者証拠ｒ_ｉの公開後も秘密鍵ＳＫ_ｉと公開鍵ＰＫ_ｉとが使用でき、かつ署名生成に協力したことを証明できる参加者がｔ人以上ｎ−１人以下であることが署名のみから確認できる。

［第５実施形態］
本発明は、参加者が署名生成に協力したことを証明した後も同じ公開鍵を使うことができるよう第３実施形態を改良したものであって、ｔとｔ’を１≦ｔ≦ｔ’≦ｎとする（ｔ，ｔ’，ｎ）閾値署名方式に関する。図３４は、本発明のシステム構成例と流れを示す図であり、第３実施形態との違いは、参加装置４１０−ｉ（ｉ＝１，…，ｎ）、署名生成部５２０、署名検証部５３０、およびダミー鍵生成部５４０のそれぞれが、通常の秘密鍵と公開鍵（第１の秘密鍵と公開鍵）および署名者証拠ｒ_ｉを公開すると使用できなくなる使い捨ての秘密鍵と公開鍵（第２の秘密鍵と公開鍵）の２種類の鍵に対応できるよう変更されたことである。２種類の鍵を使用することにより、第３実施形態の効果は維持しながら、公の機関に登録しているような公開鍵（第１の公開鍵）が署名者証拠ｒ_ｉの公開後も使用できる。以下に本発明を詳しく説明する。

参加装置４１０−ｉ（ｉ＝１，…，ｎ）は第４実施形態と同じため、説明は省略する。 図３５にダミー鍵生成部５４０の構成例を、図３６にダミー鍵生成部５４０の処理フローを示す。ダミー鍵生成部５４０では、通信部２４３を介して情報取得部５４２の公開鍵ＰＫ_ｉ（ｉ＝１，…，ｎ）取得手段４４２１で、参加装置４１０−ｉ（ｉ＝１，…，ｎ）の公開鍵ＰＫ_ｉを取得する（Ｓ４４２１と同じ）。また、情報取得部３４２の公開鍵ｐｋ_ｉ（ｉ＝１，…，ｔ’）取得手段３４２１で、参加装置４１０−ｉ（ｉ＝１，…，ｔ’）の公開鍵ｐｋ_ｉを取得する（Ｓ２４２１と同じ）。計算部５４１のダミー公開鍵ｐｋ_ｉ（ｉ＝ｔ’＋１，…，ｎ）生成手段５４１１で、Ｒ＝（ｔ，ｔ’，ｎ，ＰＫ_１，…，ＰＫ_ｎ，ｍ）として、巡回群Ｇに属する元Ａ_０（Ａ_０∈Ｇ）を、Ｒのハッシュ値として生成する（Ａ_０＝Ｈ（Ｒ））。その後はステップＳ３４１１と同じ方法であって、（ｍ_ｉｊ）を、

のｔ'×ｔ'行列（ｉ^ｊ）の逆行列として、Ａ_ｉ（ｉ＝１，…，ｔ'）を

と定め、

として公開鍵ｐｋ_ｉ（ｉ＝ｔ'＋１，…，ｎ）を生成する（Ｓ５４１１）。生成された公開鍵ｐｋ_ｉ、元Ａ_ｉ、およびＲを公開する（Ｓ３４１２と同じ）。このように公開鍵ｐｋ_ｉ（ｉ＝ｔ'＋１，…，ｎ）を生成すれば、第３実施形態と同様に、公開鍵ｐｋ_ｉ∈Ｇを満足するので、ｔ’次多項式Ｆ（Ｆ∈Ｚ_ｑ［ｘ］）が存在し、秘密鍵ｓｋ_ｉ＝Ｆ（ｉ）かつｌｏｇ_ｇＡ_０＝Ｆ（０）となっている。ここで、Ａ_０の離散対数は分からないので、参加者ｉ（ｉ＝ｔ'＋１，…，ｎ）の秘密鍵は分からない。

図３７に署名生成部５２０の機能構成例を示す。署名生成部５２０は、ダミー生成部９２１、計算部５２２、情報取得部５２３、記録部４２４、および通信部９２５から構成されている。また、図３８は署名生成部５２０の処理フローを示す図である。この機能構成と処理フローは、ほとんど第４実施形態の署名生成部４２０と同じであり、異なる点は元ｘではなく元Ａ_ｉ（ｉ＝０，…，ｔ'）を用いる点だけである。異なる点だけを示すと以下のようになる。情報取得部５２３の元Ａ_ｉ（ｉ＝０，…，ｔ'）取得手段５２３３では、元ｘではなく元Ａ_ｉ（ｉ＝０，…，ｔ'）を取得する（Ｓ５２３３）。署名作成手段５２２５では、Ｍ＝（ｔ，ｔ’，ｎ，ＰＫ_１，…，ＰＫ_ｎ，ｍ，Ａ_０，…，Ａ_ｔ’，ｐｋ_１，…，ｐｋ_ｎ）とし、（Ｍ，σ（Ｍ），Σ（Ｍ，σ（Ｍ））、（Ｍ，Σ（Ｍ），σ（Ｍ，Σ（Ｍ）））、もしくは（Ｍ，σ（Ｍ），Σ（Ｍ））を署名とし（Ｓ５２２７）、記録部４２４への記憶と公開を行う（Ｓ４２２８）。

図３９に署名検証部５３０の機能構成例を、図４０に署名検証部５３０での署名σ（ｍ）と署名Σ（ｍ）の検証フローを示す。情報取得手段５３４で、公開鍵ＰＫ_ｉ（ｉ＝１，…，ｎ）、公開鍵ｐｋ_ｉ（ｉ＝１，…，ｎ）、署名σ（ｍ）、元Ａ_ｉ（ｉ＝０，…，ｔ'）、およびＲを取得する（Ｓ５３４）。多項式ｆ（ｘ）の次数確認（Ｓ９３１と同じ）、チャレンジｃ_ｉ、多項式ｆ（０）確認（Ｓ９３２と同じ）を行うことで、σ（ｍ）の検証ができる。また、Σ（ｍ）の検証は、参加装置４１０−ｉでの秘密鍵ＳＫ_ｉの生成方法に対応した任意の（ｔ，ｎ）閾値署名Σ（ｍ）の方法を用いて行う（Ｓ４３１と同じ）。さらに、署名参加者数確認手段３３５で、Ａ_０＝Ｈ（Ｒ）と

（ｐｋ_ｉ∈Ｇ）（ｉ＝１，…，ｎ）を確認する（Ｓ３３５と同じ）。

このように署名σ（ｍ）と署名Σ（ｍ）を生成、検証することで、署名者証拠ｒ_ｉの公開後も秘密鍵ＳＫ_ｉと公開鍵ＰＫ_ｉとが使用でき、かつ署名生成に協力したことを証明できる参加者がｔ人以上ｔ’人以下であることが署名のみから確認できる。

［第６実施形態］
本発明は、参加者が署名生成に協力したことを証明した後も同じ公開鍵を使うことができるよう第１実施形態を改良したものであって、ｔを１≦ｔ≦ｎとする（ｔ，ｎ）閾値署名方式に関する。図４１は本発明のシステム構成例と流れを示す図であり、第１実施形態との違いは、参加装置６１０−ｉ（ｉ＝１，…，ｎ）、署名生成部６２０、および署名検証部６３０のそれぞれが、通常の秘密鍵と公開鍵（第１の秘密鍵と公開鍵）および署名者証拠ｒ_ｉを公開すると使用できなくなる使い捨ての秘密鍵（第２の秘密鍵）の２種類の鍵に対応できるよう変更されたことである。２種類の鍵を使用することにより、第１実施形態の効果は維持しながら、公の機関に登録しているような公開鍵（第１の公開鍵）が署名者証拠ｒ_ｉの公開後も使用できる。また、第４実施形態と第５実施形態との違いとしては、継続的に使用する第１の秘密鍵ＳＫ_ｉと使い捨ての第２の秘密鍵ｓｋ_ｉとをペアリング写像を用いて関連つけた点にあり、本発明では、署名生成部６２０は１つの署名σ（ｍ）のみを生成する。

まず、発明の説明のために追加または変更される記号等について簡単に説明する。Ｅ＝{０，Ｐ，２Ｐ，…，（ｐ−１）Ｐ}を加法によりＰで生成される位数ｐの巡回群とする。またＥは離散対数問題は難しい（つまりＰとａＰの値が分かっても、ａを求めることは難しい）巡回群である。Ｇ＝{１，ｇ，ｇ^２，…，ｇ^{（ｑ−１）}}を乗法によりｇで生成される位数ｑ（ただしｐはｑの約数）の巡回群とする。またＧは離散対数問題は難しい（つまりｇとｇ^ａの値が分かっても、ａを求めることは難しい）巡回群である。＜・，・＞：Ｅ×Ｅ→Ｇを双線形性（つまり＜ａＰ，Ｑ＞＝＜Ｐ，ａＱ＞＝＜Ｐ，Ｑ＞^ａが任意のａに対して成立する）と非退化性（つまり＜Ｐ，Ｑ＞＝１が任意のＱに対して成り立つならば、Ｐ＝０）を満たすペアリング写像とする。Ｈ，Ｉ，ＪはそれぞれＨ：{０，１}^＊→Ｅ，Ｉ：Ｋ→Ｚ_ｐ，Ｊ：{０，１}^＊→Ｋのように変換するハッシュ関数である。このような群とペアリング写像は、楕円曲線とその上のベイユペアリング（Weil Pairing）を用いて実現することができる（例えばD. Boneh and M. Franklin, Identity-Based Encryption from the Weil Pairing, CRYPTO ’01, pp. 213-229, 2001.）。以下に本発明を詳しく説明する。

図４２に参加装置６１０−ｉの機能構成例を示す。参加装置６１０−ｉは、第１の鍵生成部６１１−ｉ、第２の鍵生成部６１２−ｉ、署名者証拠生成部６１３−ｉ、記録部６１４−ｉ、署名者証拠公開部１１５−ｉ、および通信部９１４−ｉから構成される。図４３は第１の鍵生成部６１１−ｉの処理フローを示す図、図４４は第２の鍵生成部６１２−ｉの処理フローを示す図、図４５は署名者証拠生成部６１３−ｉの処理フローを示す図である。

参加装置６１０−ｉ（ｉ＝１，…，ｎ）の鍵生成部６１１−ｉでは、以下の手順で第１の秘密鍵ＳＫ_ｉと公開鍵ＰＫ_ｉとを生成する。秘密鍵ＳＫ_ｉ生成手段６１１１−ｉでは、ｐを法とする剰余類Ｚ_ｐから等確率でランダムに１つの元ｓ_ｉを選択して秘密鍵ＳＫ_ｉとし（ＳＫ_ｉ＝ｓ_ｉ∈_ＵＺ_ｐ）（Ｓ６１１１）、秘密鍵ＳＫ_ｉを記録部６１４−ｉに記録する（Ｓ６１１２）。公開鍵ＰＫ_ｉ生成手段６１１２−ｉでは、あらかじめ定められた巡回群Ｅの元Ｐを用いて、ＰＫ_ｉ＝ｓ_ｉＰにより公開鍵ＰＫ_ｉ（ＰＫ_ｉ∈Ｅ）を生成し（Ｓ６１１３）、公開鍵ＰＫ_ｉを記録部６１４−ｉに記録する（Ｓ６１１４）。ここで、巡回群Ｅは、離散対数問題が難しい群から選ばれているため、公開鍵ＰＫ_ｉと元Ｐとが分かっても、秘密鍵ＳＫ_ｉ（＝ｓ_ｉ）は分からない。このように生成された公開鍵ＰＫ_ｉは、元Ｐの情報とともに通信部９１４−ｉを介して公開される。

鍵生成部６１２−ｉでは、以下の手順で第２の秘密鍵ｓｋ_ｉを生成する。まず、公開鍵ＰＫ_ｉ（ｉ＝１，…，ｎ）取得手段６１２３−ｉで参加装置６１０−ｉ（ｉ＝１，…，ｎ）の公開鍵ＰＫ_ｉを取得する（Ｓ６１２１）。Ｑ_ｍ生成手段６１２２−ｉでは、Ｑ_ｍ＝Ｈ（ｔ，ｎ，ＰＫ_１，…，ＰＫ_ｎ，ｍ）としてＱ_ｍ（Ｑ_ｍ∈Ｅ）を生成し（Ｓ６１２２）、Ｑ_ｍを記録部６１４−ｉに記録するとともに公開する（Ｓ６１２３）。秘密鍵ｓｋ_ｉ生成手段６１２１−ｉでは、ｓｋ_ｉ＝ｓ_ｉＱ_ｍとして使い捨ての秘密鍵ｓｋ_ｉ（ｓｋ_ｉ∈Ｅ）を生成し（Ｓ６１２４）、秘密鍵ｓｋ_ｉを記録部６１４−ｉに記録する（Ｓ６１２５）。なお、上記のＱ_ｍを求める方法では全ての参加装置６１０−ｉの公開鍵ＰＫ_ｉ（ｉ＝１，…，ｎ）を使用しており、どの参加装置で計算しても同じＱ_ｍを得る。したがって、１つの参加装置または別の装置でＱ_ｍを求め、各参加装置に送信しても良い。

参加者が署名に協力する場合には、署名者証拠生成部６１３−ｉの署名者証拠ｒ_ｉ生成手段６１２１−ｉでは、ｐを法とする剰余類Ｚ_ｐから等確率でランダムに１つの元を選択して署名者証拠ｒ_ｉ（ｒ_ｉ∈_ＵＺ_ｐ）とし（Ｓ６１２１）、記録部６１４−ｉに記録する（Ｓ１１２１）。次にコミットメントａ_ｉ生成手段６１３２−ｉは、元Ｐを用いて、

によりコミットメントａ_ｉ（∈Ｇ）を生成し（Ｓ６１３２）、コミットメントａ_ｉを記録部６１４−ｉに記録し、通信部９１４−ｉを介して署名生成部６２０に送信する（Ｓ９１２３）。署名生成部６２０で署名生成処理が行われると、署名生成部６２０の計算部６２２の処理過程で生成されたチャレンジｃ_ｉが署名生成部６２０から、署名生成に協力している参加装置６１０−ｉ（ｉ＝１，…，ｔ）に送信される。このチャレンジｃ_ｉをチャレンジｃ_ｉ取得手段９１２３−ｉで取得し（Ｓ９１２４）、記録部９１３−ｉに記録する（Ｓ９１２５）。また、レスポンスｅ_ｉ生成手段６１３２−ｉで、ｅ_ｉ：＝ｒ_ｉＱ_ｍ−ｃ_ｉｓｋ_ｉ（ｅ_ｉ∈Ｅ）により、ｅ_ｉ（ｉ＝１，…，ｔ）を求め（Ｓ６１３６）、記録部６１４−ｉに記録するとともに署名生成部６２０に送信する（Ｓ９１２７）。

図４６に署名生成部６２０の機能構成例を示す。署名生成部６２０は、ダミー生成部６２１、計算部６２２、情報取得部６２３、記録部６２４、および通信部９２５から構成されている。また、図４７は署名生成部６２０の処理フローを示す図である。

署名生成部６２０では、以下の手順で署名σ（ｍ）が生成される。通信部９２５を介して情報取得部６２３の公開鍵ＰＫ_ｉ（ｉ＝１，…，ｎ）取得手段４２３１により、参加装置９１０−ｉ（ｉ＝１，…，ｎ）の公開鍵ＰＫ_ｉを取得する（Ｓ４２３１）。また、Ｑ_ｍ取得手段６２３１により、Ｑ_ｍを取得する（Ｓ６２３１）。ダミー生成部６２１では、次のように、ダミーレスポンスｅ_ｉ、ダミーチャレンジｃ_ｉ、ダミーコミットメントａ_ｉ（ｉ＝ｔ＋１，…，ｎ）を生成する。ダミーレスポンスｅ_ｉ（ｉ＝ｔ＋１，…，ｎ）生成手段６２１１により、ｐを法とする剰余類Ｚ_ｐから等確率でランダムに１つの元を選択してダミーレスポンスｅ_ｉ（ｉ＝ｔ＋１，…，ｎ）とし（ｅ_ｉ∈_ＵＺ_ｐ）（Ｓ６２１１）、記録部６２４に記録する（Ｓ９２１２）。ダミーチャレンジｃ_ｉ（ｉ＝ｔ＋１，…，ｎ）生成手段９２１２により、有限体Ｋから等確率でランダムに１つの座標値ｙ_ｉを選び、そのハッシュ関数をダミーチャレンジｃ_ｉ（ｉ＝ｔ＋１，…，ｎ）とし（ｙ_ｉ∈_ＵＫ，ｃ_ｉ：＝Ｉ（ｙ_ｉ）∈Ｚ_ｐ）（Ｓ６２１３）、記録部６２４に記録する（Ｓ９２１４）。また、ダミーコミットメントａ_ｉ（ｉ＝ｔ＋１，…，ｎ）生成手段６２１３により、元Ｐ、Ｑ_ｍ、および公開鍵ＰＫ_ｉを用いて、

によりダミーコミットメントａ_ｉ（ｉ＝ｔ＋１，…，ｎ）を生成し（Ｓ６２１５）、記録部６２４に記録する（Ｓ９２１６）。

また、通信部９２５を介して情報取得部６２３のコミットメントａ_ｉ（ｉ＝１，…，ｔ）取得手段９２３２により、参加装置６１０−ｉ（ｉ＝１，…，ｔ）のコミットメントａ_ｉを取得する（Ｓ９２３２と同じ）。

次に、計算部６２２では、以下のようにメッセージｍの（ｔ，ｎ）閾値署名σ（ｍ）を求める。ｎ−ｔ次多項式ｆ（ｘ）計算手段６２２１により、ｎ−ｔ次の多項式ｆ（ｘ）（ｆ（ｘ）＝α_０＋α_１ｘ＋α_２ｘ^２＋…＋α_ｎ−ｔｘ^ｎ−ｔ，α_ｊ∈Ｋ）と定め、ｆ（０）＝Ｊ（ｔ，ｎ，ＰＫ_１，…，ＰＫ_ｎ，Ｑ_ｍ，ａ_１，…，ａ_ｎ，ｍ）とｆ（ｉ）＝ｙ_ｉ（ｉ＝ｔ＋１，…，ｎ）の条件からα_ｊ（ｊ＝０，…，ｎ−ｔ）を計算することでｎ−ｔ次多項式ｆ（ｘ）を求める（Ｓ６２２１）。また、求めたｎ−ｔ次多項式ｆ（ｘ）を記録部６２４に記録する（Ｓ９２２２）。チャレンジｃ_ｉ（ｉ＝１，…，ｔ）生成手段９２２２では、ｃ_ｉ：＝Ｉ（ｆ（ｉ））により、チャレンジｃ_ｉ（ｉ＝１，…，ｔ）を求め（Ｓ９２２３）、記録部９２４に記録するとともに、チャレンジｃ_ｉに対応する参加装置９１０−ｉ（ｉ＝１，…，ｔ）にチャレンジｃ_ｉを送信する（Ｓ９２２４）。

各参加者装置６１０−ｉ（ｉ＝１，…，ｔ）では、送信されたチャレンジｃ_ｉを用いて、上記のようにレスポンスｅ_ｉを生成し署名生成部６２０に送信する（図４５のＳ９１２４〜Ｓ９１２７）。そこで、レスポンスｅ_ｉ（ｉ＝１，…，ｔ）取得手段９２２３は、レスポンスｅ_ｉ（ｉ＝１，…，ｔ）を取得し（Ｓ９２２５）、記録部６２４に記録する（Ｓ９２２６）。署名σ（ｍ）作成手段６２２３では、σ（ｍ）＝（ｆ，ｃ_１，…，ｃ_ｎ，ｅ_１，…，ｅ_ｎ）により、σ（ｍ）を求め（Ｓ６２２７）、記録部６２４に記録する（Ｓ９２２８）。このようにしてメッセージｍに対する（ｔ，ｎ）閾値署名σ（ｍ）を求める。

図４８に署名検証部６３０の機能構成例を、図４９に署名検証部６３０での署名σ（ｍ）を検証するフローを示す。なお、署名者証拠ｒ_ｉを確認する処理フローは第１実施形態と同じである。署名σ（ｍ）を検証する場合は、情報取得手段６３４で公開鍵ＰＫ_ｉ（ｉ＝１，…，ｎ）、Ｑ_ｍ、および署名σ（ｍ）を取得し（Ｓ６３４）、多項式ｆ（ｘ）の次数確認手段９３１で多項式ｆ（ｘ）の次数がｎ−ｔであることを確認し（Ｓ９３１）、Ｑ_ｍ確認手段６３２で、Ｑ_ｍ＝Ｈ（ｔ，ｎ，ＰＫ_１，…，ＰＫ_ｎ，ｍ）かつＱ_ｍ∈Ｅであることを確認し（Ｓ６３２）、チャレンジｃ_ｉ、多項式ｆ（０）確認手段６３３で、

であることを確認する（Ｓ９３２）。

このように署名σ（ｍ）を生成、検証することによって以下のような効果がある。署名生成に協力したことを参加者ｉが証明するために署名者証拠ｒ_ｉを公開した場合、第２の秘密鍵ｓｋ_ｉは、ｓｋ_ｉ＝ｓ_ｉＱ_ｍ＝ｃ_ｉ ^-1（ｒ_ｉＱ_ｍ−ｅ_ｉ）により求めることができるが、Ｅは離散対数問題が難しい巡回群から選ばれているため、第１の秘密鍵ＳＫ_ｉ（ＳＫ_ｉ＝ｓ_ｉ∈Ｚ_ｐ）を求めることはできない。したがって、署名者証拠ｒ_ｉ公開後も公開鍵ＰＫ_ｉを使うことができる。また、チャレンジｃ_ｉ、多項式ｆ（０）確認手段６３３で、

を確認しているため、署名者証拠ｒ_ｉ（ｒ_ｉ∈Ｚ_ｐ）と公開鍵ＰＫ_ｉ（ＰＫ_ｉ＝ｓ_ｉＰ∈Ｅ）とは関連しており、署名者証拠ｒ_ｉを示すことにより公開鍵ＰＫ_ｉに対応する参加者ｉが署名に協力したことを証明することができる。

［第７実施形態］
本実施形態は、第１実施形態から第６実施形態の総括である。図５０に第１実施形態から第６実施形態をまとめた（ｔ，ｎ）閾値電子署名システムの処理フローを示す。図５０では、すべての実施形態に共通する装置（部）と処理工程を実線の四角で示し、第２実施形態から第５実施形態に必要な装置（部）と処理工程を点線の四角で示し、第４実施形態から第６実施形態に必要な装置（部）と処理工程を一点鎖線の四角で示す。第６実施形態に必要な処理工程を二点鎖線の四角で示す。

第４実施形態から第６実施形態の参加装置（４１０−ｉ、または６１０−ｉ）（ｉ＝１，…，ｎ）は、第１の秘密鍵ＳＫ_ｉと公開鍵ＰＫ_ｉを生成し、公開鍵ＰＫ_ｉを公開する。第１の実施形態と第６実施形態の場合は、すべての参加装置（１１０−ｉ、または６１０−ｉ）（ｉ＝１，…，ｎ）は、署名に使用する秘密鍵ｓｋ_ｉを生成し、第１の実施形態は公開鍵ｐｋ_ｉも生成し、公開鍵ｐｋ_ｉを公開する。第２実施形態と第４実施形態は参加装置（１１０−ｉ、または４１０−ｉ）（ｉ＝１，…，ｎ−１）が、署名に使用する秘密鍵ｓｋ_ｉと公開鍵ｐｋ_ｉを生成し、公開鍵ｐｋ_ｉを公開する。第３実施形態と第５実施形態は参加装置（１１０−ｉ、または４１０−ｉ）（ｉ＝１，…，ｔ’）が、署名に使用する秘密鍵ｓｋ_ｉと公開鍵ｐｋ_ｉを生成し、公開鍵ｐｋ_ｉを公開する。

第２実施形態から第５実施形態の場合は、ダミー鍵生成部（２４０、３４０，４４０，５４０）で、ダミーの公開鍵ｐｋ_ｉ（ｉ＝ｎまたはｔ’，…，ｎ）を生成し、公開する。
署名生成に協力する参加装置（１１０−ｉ、４１０−ｉ、または６１０−ｉ）（ｉ＝１，…，ｔ）は、署名者証拠ｒ_ｉとコミットメントａ_ｉを生成し、コミットメントａ_ｉを署名生成部（９２０、４２０、５２０、または６２０）に送信する。署名生成部（９２０、４２０、５２０、または６２０）では、署名生成に協力していない参加装置（１１０−ｉ、４１０−ｉ、または６１０−ｉ）（ｉ＝ｔ＋１，…，ｎ）に対応するダミーのレスポンスｅ_ｉ、チャレンジｃ_ｉ、およびコミットメントａ_ｉを生成し、ｎ−ｔ次多項式ｆと署名生成に協力した参加装置（１１０−ｉ、４１０−ｉ、または６１０−ｉ）（ｉ＝１，…，ｔ）に対応するチャレンジｃ_ｉを生成し、チャレンジｃ_ｉを参加装置（１１０−ｉ、４１０−ｉ、または６１０−ｉ）（ｉ＝１，…，ｔ）に送信する。各参加装置（１１０−ｉ、４１０−ｉ、または６１０−ｉ）（ｉ＝１，…，ｔ）では、レスポンスｅ_ｉを生成し署名生成部（９２０、４２０、５２０、または６２０）に送信する。署名生成部（９２０、４２０、５２０、または６２０）では、署名σ（第４実施形態と第５実施形態の場合は、さらにΣ）を生成する。署名検証部（１３０、２３０、３３０，４３０，５３０、または６３０）で、署名σ（第４実施形態と第５実施形態の場合は、さらにΣ）を確認し、第２実施形態から第５実施形態の場合は、署名参加者数を確認する。さらに、署名に協力した参加者が署名に協力したことを証明したい場合には、参加装置（１１０−ｉ、４１０−ｉ、または６１０−ｉ）（ｉ＝１，…，ｔ）は署名者証拠ｒ_ｉを公開し、署名検証部（１３０、２３０、３３０，４３０，５３０、または６３０）は署名者証拠ｒ_ｉを確認する。なお、各処理の詳細は、上記の第１実施形態から第６実施形態に示したとおりである。

このようなシステム構成と処理方法により、参加者が署名生成に協力したことを証明したい場合に、証明することができる。また、何人の参加者が証明できるのかを署名から確認できる。さらに、使い捨て秘密鍵（第２の秘密鍵）を使用することにより、公的機関に登録しているような公開鍵と組となる秘密鍵の情報流出を避けることができる。

閾値つき電子署名システムの構成例と流れを示す図。 参加装置９１０−ｉの機能構成例を示す図。 鍵生成部９１１−ｉの処理フローを示す図。 署名者証拠生成部９１２−ｉの処理フローを示す図。 署名生成部９２０の機能構成例を示す図。 署名生成部９２０の処理フローを示す図。 署名検証部９３０の機能構成例を示す図。 署名検証部９３０での署名σ（ｍ）を検証するフローを示す図。 第１実施形態のシステム構成例と流れを示す図。 参加装置１１０−ｉの機能構成例を示す図。 署名者証拠生成部１１２−ｉの処理フローを示す図。 署名者証拠公開部１１５−ｉの処理フローを示す図 署名検証部１３０の機能構成例を示す図。 署名に協力したことを証明したい参加者から署名者証拠ｒ_ｉが公開された場合の、署名者証拠ｒ_ｉ確認フローを示す図。 第２実施形態のシステム構成例と流れを示す図。 ダミー鍵生成部２４０の機能構成例を示す図。 ダミー鍵生成部２４０の処理フローを示す図。 署名検証部２３０の機能構成例を示す図。 署名検証部２３０が署名σ（ｍ）を検証するフローを示す図。 第３実施形態のシステム構成例と流れを示す図。 ダミー鍵生成部３４０の機能構成例を示す図。 ダミー鍵生成部３４０の処理フローを示す図。 署名検証部３３０の機能構成例を示す図。 署名検証部３３０が署名σ（ｍ）を検証するフローを示す図。 第４実施形態のシステム構成例と流れを示す図。 参加装置４１０−ｉの機能構成例を示す図。 第１の秘密鍵と公開鍵を生成する鍵生成部４１１−ｉの処理フローを示す図。 ダミー鍵生成部４４０の構成例を示す図。 ダミー鍵生成部４４０の処理フローを示す図。 署名生成部４２０の機能構成例を示す図。 署名生成部４２０の処理フローを示す図。 署名検証部４３０の機能構成例を示す図。 署名検証部４３０での署名σ（ｍ）と署名Σ（ｍ）の検証フローを示す図。 第５実施形態のシステム構成例と流れを示す図。 ダミー鍵生成部５４０の構成例を示す図。 ダミー鍵生成部５４０の処理フローを示す図。 署名生成部５２０の機能構成例を示す図。 署名生成部５２０の処理フローを示す図。 署名検証部５３０の機能構成例を示す図。 署名検証部５３０での署名σ（ｍ）と署名Σ（ｍ）の検証フローを示す図。 第６実施形態のシステム構成例と流れを示す図。 参加装置６１０−ｉの機能構成例を示す図。 第１の鍵生成部６１１−ｉの処理フローを示す図。 第２の鍵生成部６１２−ｉの処理フローを示す図。 署名者証拠生成部６１３−ｉの処理フローを示す図。 署名生成部６２０の機能構成例を示す図。 署名生成部６２０の処理フローを示す図。 署名検証部６３０の機能構成例を示す図。 署名検証部６３０での署名σ（ｍ）を検証するフローを示す図。 第１実施形態から第６実施形態をまとめた（ｔ，ｎ）閾値電子署名システムの処理フローを示す図。

Claims (12)

1. ｎ台の参加装置、前記参加装置のいずれかもしくは独立した装置に具備された署名生成部、任意の装置に具備された署名検証部を有し、ｔ台の参加装置が協力することでメッセージに対する署名を生成する署名システムであって、
   ｎは２以上の整数、ｔはｎ−１以下の整数、Ｇは離散対数問題が難しい巡回群、ｇは群Ｇの生成元とし、
   ｉは参加装置の番号を識別するためのインデックスであって、ｉ＝１，…，ｔの参加装置が署名生成に協力し、ｉ＝ｔ＋１，…，ｎの参加装置が署名生成に協力しなかったとし、
   各参加装置は、
   

   

   
   の関係を有する秘密鍵ｓｋ_ｉと公開鍵ｐｋ_ｉを生成する鍵生成部と、
   署名生成に協力する場合は、署名者証拠ｒ_ｉを生成し、
   

   

   
   の関係を有するコミットメントａ_ｉを生成して前記署名生成部に送信し、チャレンジｃ_ｉを前記署名生成部から取得し、
   ｅ_ｉ＝ｒ_ｉ−ｃ_ｉｓｋ_ｉ
   の関係を有するレスポンスｅ_ｉを生成して前記署名生成部に送信する署名者証拠生成部と、
   前記署名者証拠ｒ_ｉを記録する記録部と、
   署名者証拠ｒ_ｉを前記署名検証部に送信する署名者証拠公開部と
   を備え、
   前記署名生成部は、
   署名生成に協力しなかった参加装置用のレスポンスｅ_ｉ、チャレンジｃ_ｉ、コミットメントａ_ｉであるダミーレスポンスｅ_ｉ、ダミーチャレンジｃ_ｉ、ダミーコミットメントａ_ｉを
   

   

   
   の関係を有するように生成するダミー生成部と、
   署名に協力する参加装置から前記コミットメントａ _ｉ を受信し、前記公開鍵ｐｋ_ｉと署名に協力する参加装置の前記コミットメントａ_ｉ と前記ダミーコミットメントａ _ｉ を用いた計算によってｎ−ｔ次多項式ｆを求め、署名に協力する参加装置の前記チャレンジｃ _ｉ を生成して対応する参加装置に送信し、署名に協力する参加装置から前記レスポンスｅ _ｉ を受信し、前記多項式ｆおよび全参加装置の前記チャレンジｃ_ｉと前記レスポンスｅ_ｉを含む署名σを生成し、記録する計算部と
   を備え、
   前記署名検証部は、
   前記署名生成部から前記署名σを取得し、すべての前記参加装置の前記公開鍵ｐｋ _ｉ を取得し、いずれかの前記参加装置から前記署名者証拠ｒ _ｉ を取得する情報取得手段と、
   前記署名σに含まれる多項式ｆの次数がｎ−ｔであることを確認する次数確認手段と、
   前記署名σに含まれるチャレンジｃ_ｉ が前記計算部で生成され、前記署名σに含まれる多項式ｆが前記計算部で求められたことを前記公開鍵ｐｋ_ｉ、前記署名σに含まれるレスポンスｅ_ｉを用いて確認するチャレンジ・多項式確認手段と、
   前記署名者証拠ｒ_ｉが、
   

   

   
   を満たすことを確認することで、当該参加装置が署名生成に協力したことを確認する署名者証拠確認手段と
   を備える署名システム。
2. 請求項１記載の署名システムであって、
   さらに、前記参加装置のいずれかもしくは独立した装置に具備されたダミー鍵生成部も有し、
   前記ダミー鍵生成部は、
   群Ｇの任意の元ｘを生成し、
   署名生成に協力していない１つの参加装置を除く参加装置の公開鍵ｐｋ_ｉ（ｉ＝１，…，ｎ−１）を取得し、
   ｐｋ_ｎ＝ｘ/ｐｋ_１ｐｋ_２…ｐｋ_ｎ−１
   のように、署名生成に協力していない１つの参加装置の公開鍵ｐｋ_ｎを計算し、
   前記署名検証部は、さらに
   ｐｋ_１ｐｋ_２…ｐｋ_ｎ＝ｘ
   であることを確認する署名参加者数確認手段も
   備える署名システム。
3. 請求項１記載の署名システムであって、
   ｔ’をｔ以上ｎ以下の整数とし、
   さらに、前記参加装置のいずれかもしくは独立した装置に具備されたダミー鍵生成部も有し、
   前記ダミー鍵生成部は、
   群Ｇの任意の元Ａ_０を生成し、
   

   

   
   のようにｍ_ｉｊを計算し、
   

   

   
   のようにＡ_ｉ（ｉ＝１，…，ｔ'）を計算し、
   

   

   
   のように署名生成に協力していない（ｎ−ｔ’）台の参加装置の公開鍵ｐｋ_ｉ（ｉ＝ｔ'＋１，…，ｎ）を計算し、
   前記署名検証部は、さらに
   

   

   
   であることを確認する署名参加者数確認手段も
   備える署名システム。
4. 請求項２記載の署名システムであって、
   各参加装置は、
   前記鍵生成部を第２鍵生成部とし、さらに、
   秘密鍵ＳＫ_ｉと公開鍵ＰＫ_ｉを生成する第１鍵生成部を備え、
   前記ダミー鍵生成部が生成した前記元ｘは、
   任意長のビット列を群Ｇの元に変換するハッシュ関数Ｈを用いて、公開鍵ＰＫ_１，…，ＰＫ_ｎを含むビット列から生成したものであり、
   前記署名生成部の前記計算部は、
   前記秘密鍵ＳＫ_ｉの生成方法に対応した方法で前記メッセージに対する署名Σも生成し、
   前記署名検証部は、
   前記署名Σを確認するΣ確認手段も
   備える署名システム。
5. 請求項３記載の署名システムであって、
   各参加装置は、
   前記鍵生成部を第２鍵生成部とし、さらに、
   秘密鍵ＳＫ_ｉと公開鍵ＰＫ_ｉを生成する第１鍵生成部を備え、
   前記ダミー鍵生成部が生成した前記元Ａ_０は、
   任意長のビット列を群Ｇの元に変換するハッシュ関数Ｈを用いて、公開鍵ＰＫ_１，…，ＰＫ_ｎを含むビット列から生成したものであり、
   前記署名生成部の前記計算部は、
   前記秘密鍵ＳＫ_ｉの生成方法に対応した方法で前記メッセージに対する署名Σも生成し、
   前記署名検証部は、
   前記署名Σを確認するΣ確認手段も
   備える署名システム。
6. ｎ台の参加装置、前記参加装置のいずれかもしくは独立した装置に具備された署名生成部、任意の装置に具備された署名検証部を有し、ｔ台の参加装置が協力することでメッセージに対する署名を生成する署名システムであって、
   ｎは２以上の整数、ｔはｎ−１以下の整数、Ｇは離散対数問題が難しい巡回群、ｇは群Ｇの生成元、Ｅは加法により生成された離散対数問題が難しい巡回群、Ｐは群Ｅの生成元、＜・，・＞は２つの群Ｅの元を群Ｇの元に変換するペアリング写像とし、
   ｉは参加装置の番号を識別するためのインデックスであって、ｉ＝１，…，ｔの参加装置が署名生成に協力し、ｉ＝ｔ＋１，…，ｎの参加装置が署名生成に協力しなかったとし、
   各参加装置は、
   ＰＫ_ｉ＝ＳＫ_ｉＰ
   の関係を有する秘密鍵ＳＫ_ｉと公開鍵ＰＫ_ｉを生成する第１鍵生成部と、
   任意長のビット列を群Ｅの元に変換するハッシュ関数Ｈを用いて、公開鍵ＰＫ_１，…，ＰＫ_ｎを含むビット列から群Ｅの元Ｑ_ｍを生成し、
   ｓｋ_ｉ＝ＳＫ_ｉＱ_ｍ
   のように前記秘密鍵ｓｋ_ｉを生成する第２鍵生成部と、
   署名生成に協力する場合は、署名者証拠ｒ_ｉを生成し、
   

   

   
   の関係を有するコミットメントａ_ｉを生成して前記署名生成部に送信し、チャレンジｃ_ｉを前記署名生成部から取得し、
   ｅ_ｉ＝ｒ_ｉＱ_ｍ−ｃ_ｉｓｋ_ｉ
   の関係を有するレスポンスｅ_ｉを生成して前記署名生成部に送信する署名者証拠生成部と、
   前記署名者証拠ｒ_ｉを記録する記録部と、
   署名者証拠ｒ_ｉを前記署名検証部に送信する署名者証拠公開部と
   を備え、
   前記署名生成部は、
   署名生成に協力しなかった参加装置用のレスポンスｅ_ｉ、チャレンジｃ_ｉ、コミットメントａ_ｉであるダミーレスポンスｅ_ｉ、ダミーチャレンジｃ_ｉ、ダミーコミットメントａ_ｉを
   

   

   
   の関係を有するように生成するダミー生成部と、
   署名に協力する参加装置から前記コミットメントａ _ｉ を受信し、前記公開鍵ＰＫ_ｉと署名に協力する参加装置の前記コミットメントａ_ｉ と前記ダミーコミットメントａ _ｉ を用いた計算によってｎ−ｔ次多項式ｆを求め、署名に協力する参加装置の前記チャレンジｃ _ｉ を生成して対応する参加装置に送信し、署名に協力する参加装置から前記レスポンスｅ _ｉ を受信し、前記多項式ｆおよび全参加装置の前記チャレンジｃ_ｉと前記レスポンスｅ_ｉを含む署名σを生成し、記録する計算部と
   を備え、
   前記署名検証部は、
   前記署名生成部から前記署名σを取得し、すべての前記参加装置の前記公開鍵ｐｋ _ｉ を取得し、いずれかの前記参加装置から前記署名者証拠ｒ _ｉ を取得する情報取得手段と、
   前記署名σに含まれる多項式ｆの次数がｎ−ｔであることを確認する次数確認手段と、
   元Ｑ_ｍが、ハッシュ関数Ｈを用いて、前記の公開鍵ＰＫ_１，…，ＰＫ_ｎを含むビット列から生成されたことを確認するＱ_ｍ確認手段と、
   前記署名σに含まれるチャレンジｃ_ｉ が前記計算部で生成され、と前記署名σに含まれる多項式ｆが前記計算部で求められたことを前記公開鍵ｐｋ_ｉ、前記署名σに含まれるレスポンスｅ_ｉを用いて確認するチャレンジ・多項式確認手段と、
   前記署名者証拠ｒ_ｉが、
   

   

   
   を満たすことを確認することで、当該参加装置が署名生成に協力したことを確認する署名者証拠確認手段と
   を備える署名システム。
7. ｎ台の参加装置、前記参加装置のいずれかもしくは独立した装置に具備された署名生成部、任意の装置に具備された署名検証部を有する署名システム内のｔ台の参加装置が協力することでメッセージに対する署名を生成する署名方法であって、
   ｎは２以上の整数、ｔはｎ−１以下の整数、Ｇは離散対数問題が難しい巡回群、ｇは群Ｇの生成元とし、
   ｉは参加装置の番号を識別するためのインデックスであって、ｉ＝１，…，ｔの参加装置が署名生成に協力し、ｉ＝ｔ＋１，…，ｎの参加装置が署名生成に協力しなかったとし、
   すべての参加装置が、
   

   

   
   の関係を有する秘密鍵ｓｋ_ｉと公開鍵ｐｋ_ｉを生成する鍵生成ステップと、
   署名生成に協力する各参加装置が、署名者証拠ｒ_ｉを生成し、
   

   

   
   の関係を有するコミットメントａ_ｉを生成して前記署名生成部に送信し、チャレンジｃ_ｉを前記署名生成部から取得し、
   ｅ_ｉ＝ｒ_ｉ−ｃ_ｉｓｋ_ｉ
   の関係を有するレスポンスｅ_ｉを生成して前記署名生成部に送信する署名者証拠生成ステップと、
   署名生成に協力する各参加装置が、前記署名者証拠ｒ_ｉを記録する記録ステップと、
   前記署名生成部が、署名生成に協力しなかった参加装置用のレスポンスｅ_ｉ、チャレンジｃ_ｉ、コミットメントａ_ｉであるダミーレスポンスｅ_ｉ、ダミーチャレンジｃ_ｉ、ダミーコミットメントａ_ｉを
   

   

   
   の関係を有するように生成するダミー生成ステップと、
   前記署名生成部が、署名に協力する参加装置から前記コミットメントａ _ｉ を受信し、前記公開鍵ｐｋ_ｉと署名に協力する参加装置の前記コミットメントａ_ｉ と前記ダミーコミットメントａ _ｉ を用いた計算によってｎ−ｔ次多項式ｆを求め、署名に協力する参加装置の前記チャレンジｃ _ｉ を生成して対応する参加装置に送信し、署名に協力する参加装置から前記レスポンスｅ _ｉ を受信し、前記多項式ｆおよび全参加装置の前記チャレンジｃ_ｉと前記レスポンスｅ_ｉを含む署名σを生成し、記録する計算ステップと、
   いずれかの参加装置が、署名者証拠ｒ _ｉ を前記署名検証部に送信する署名者証拠公開ステップと、
   前記署名検証部が、前記署名生成部から前記署名σを取得し、すべての前記参加装置の前記公開鍵ｐｋ _ｉ を取得し、いずれかの前記参加装置から前記署名者証拠ｒ _ｉ を取得する情報取得ステップと、
   前記署名σに含まれる多項式ｆの次数がｎ−ｔであることを確認する次数確認ステップと、
   前記署名検証部が、前記署名σに含まれるチャレンジｃ_ｉ が前記計算部で生成され、前記署名σに含まれる多項式ｆが前記計算部で求められたことを前記公開鍵ｐｋ_ｉ、前記署名σに含まれるレスポンスｅ_ｉを用いて確認するチャレンジ・多項式確認ステップと、
   前記署名検証部が、前記署名者証拠ｒ_ｉが、
   

   

   
   を満たすことを確認することで、署名者証拠ｒ_ｉを公開した参加装置が署名生成に協力したことを確認する署名者証拠確認ステップと
   を有する署名方法。
8. 請求項７記載の署名方法であって、
   前記署名システムは、前記参加装置のいずれかもしくは独立した装置に具備されたダミー鍵生成部も有し、
   前記ダミー鍵生成部が、群Ｇの任意の元ｘを生成し、
   署名生成に協力していない１つの参加装置を除く参加装置の公開鍵ｐｋ_ｉ（ｉ＝１，…，ｎ−１）を取得し、
   ｐｋ_ｎ＝ｘ/ｐｋ_１ｐｋ_２…ｐｋ_ｎ−１
   のように、署名生成に協力していない１つの参加装置の公開鍵ｐｋ_ｎを計算するダミー鍵生成ステップと、
   前記署名検証部が、
   ｐｋ_１ｐｋ_２…ｐｋ_ｎ＝ｘ
   であることを確認する署名参加者数確認ステップも
   有する署名方法。
9. 請求項７記載の署名方法であって、
   前記署名システムは、前記参加装置のいずれかもしくは独立した装置に具備されたダミー鍵生成部も有し、
   ｔ’をｔ以上ｎ以下の整数とし、
   前記ダミー鍵生成部が、群Ｇの任意の元Ａ_０を生成し、
   

   

   
   のようにｍ_ｉｊを計算し、
   

   

   
   のようにＡ_ｉ（ｉ＝１，…，ｔ'）を計算し、
   

   

   
   のように署名生成に協力していない（ｎ−ｔ’）台の参加装置の公開鍵ｐｋ_ｉ（ｉ＝ｔ'＋１，…，ｎ）を計算するダミー鍵生成ステップと、
   前記署名検証部が、
   

   

   
   であることを確認する署名参加者数確認ステップも
   有する署名方法。
10. 請求項８記載の署名方法であって、
    前記鍵生成ステップを第２鍵生成ステップとし、
    前記第２鍵生成ステップの前に、すべての参加装置が、秘密鍵ＳＫ_ｉと公開鍵ＰＫ_ｉを生成する第１鍵生成ステップを有し、
    前記ダミー鍵生成ステップの中で生成された前記元ｘは、任意長のビット列を群Ｇの元に変換するハッシュ関数Ｈを用いて、公開鍵ＰＫ_１，…，ＰＫ_ｎを含むビット列から生成されたものであり、
    前記計算ステップは、前記秘密鍵ＳＫ_ｉの生成方法に対応した方法で前記メッセージに対する署名Σも生成し、
    前記署名検証部が、前記署名Σを確認するΣ確認ステップも
    有する署名方法。
11. 請求項９記載の署名方法であって、
    前記鍵生成ステップを第２鍵生成ステップとし、
    前記第２鍵生成ステップの前に、すべての参加装置が、秘密鍵ＳＫ_ｉと公開鍵ＰＫ_ｉを生成する第１鍵生成ステップを有し、
    前記ダミー鍵生成ステップの中で生成された前記元Ａ_０は、任意長のビット列を群Ｇの元に変換するハッシュ関数Ｈを用いて、公開鍵ＰＫ_１，…，ＰＫ_ｎを含むビット列から生成されたものであり、
    前記計算ステップは、前記秘密鍵ＳＫ_ｉの生成方法に対応した方法で前記メッセージに対する署名Σも生成し、
    前記署名検証部が、前記署名Σを確認するΣ確認ステップも
    有する署名方法。
12. ｎ台の参加装置、前記参加装置のいずれかもしくは独立した装置に具備された署名生成部、任意の装置に具備された署名検証部を有する署名システム内のｔ台の参加装置が協力することでメッセージに対する署名を生成する署名方法であって、
    ｎは２以上の整数、ｔはｎ−１以下の整数、Ｇは離散対数問題が難しい巡回群、ｇは群Ｇの生成元、Ｅは加法により生成された離散対数問題が難しい巡回群、Ｐは群Ｅの生成元、＜・，・＞は２つの群Ｅの元を群Ｇの元に変換するペアリング写像とし、
    ｉは参加装置の番号を識別するためのインデックスであって、ｉ＝１，…，ｔの参加装置が署名生成に協力し、ｉ＝ｔ＋１，…，ｎの参加装置が署名生成に協力しなかったとし、
    すべての参加装置が、
    ＰＫ_ｉ＝ＳＫ_ｉＰ
    の関係を有する秘密鍵ＳＫ_ｉと公開鍵ＰＫ_ｉを生成する第１鍵生成ステップと、
    すべての参加装置が、任意長のビット列を群Ｅの元に変換するハッシュ関数Ｈを用いて、公開鍵ＰＫ_１，…，ＰＫ_ｎを含むビット列から群Ｅの元Ｑ_ｍを生成し、
    ｓｋ_ｉ＝ＳＫ_ｉＱ_ｍ
    のように前記秘密鍵ｓｋ_ｉを生成する第２鍵生成ステップと、
    署名生成に協力する各参加装置が、署名者証拠ｒ_ｉを生成し、
    

    

    
    の関係を有するコミットメントａ_ｉを生成して前記署名生成部に送信し、チャレンジｃ_ｉを前記署名生成部から取得し、
    ｅ_ｉ＝ｒ_ｉＱ_ｍ−ｃ_ｉｓｋ_ｉ
    の関係を有するレスポンスｅ_ｉを生成して前記署名生成部に送信する署名者証拠生成ステップと、
    署名生成に協力する各参加装置が、前記署名者証拠ｒ_ｉを記録する記録ステップと、
    前記署名生成部が、署名生成に協力しなかった参加装置用のレスポンスｅ_ｉ、チャレンジｃ_ｉ、コミットメントａ_ｉであるダミーレスポンスｅ_ｉ、ダミーチャレンジｃ_ｉ、ダミーコミットメントａ_ｉを
    

    

    
    の関係を有するように生成するダミー生成ステップと、
    前記署名生成部が、署名に協力する参加装置から前記コミットメントａ _ｉ を受信し、前記公開鍵ＰＫ_ｉと署名に協力する参加装置の前記コミットメントａ_ｉ と前記ダミーコミットメントａ _ｉ を用いた計算によってｎ−ｔ次多項式ｆを求め、署名に協力する参加装置の前記チャレンジｃ _ｉ を生成して対応する参加装置に送信し、署名に協力する参加装置から前記レスポンスｅ _ｉ を受信し、前記多項式ｆおよび全参加装置の前記チャレンジｃ_ｉと前記レスポンスｅ_ｉを含む署名σを生成し、記録する計算ステップと、
    いずれかの参加装置が、署名者証拠ｒ _ｉ を前記署名検証部に送信する署名者証拠公開ステップと、
    前記署名検証部が、前記署名生成部から前記署名σを取得し、すべての前記参加装置の前記公開鍵ｐｋ _ｉ を取得し、いずれかの前記参加装置から前記署名者証拠ｒ _ｉ を取得する情報取得ステップと、
    前記署名σに含まれる多項式ｆの次数がｎ−ｔであることを確認する次数確認ステップと、
    前記署名検証部が、元Ｑ_ｍが、ハッシュ関数Ｈを用いて、前記の公開鍵ＰＫ_１，…，ＰＫ_ｎを含むビット列から生成されたことを確認するＱ_ｍ確認ステップと、
    前記署名検証部が、前記署名σに含まれるチャレンジｃ_ｉ が前記計算部で生成され、と前記署名σに含まれる多項式ｆが前記計算部で求められたことを前記公開鍵ｐｋ_ｉ、前記署名σに含まれるレスポンスｅ_ｉを用いて確認するチャレンジ・多項式確認ステップと、
    前記署名検証部が、前記署名者証拠ｒ_ｉが、
    

    

    
    を満たすことを確認することで、署名者証拠ｒ_ｉを公開した参加装置が署名生成に協力したことを確認する署名者証拠確認ステップと
    を有する署名方法。

Images