(57)【要約】      （修正有）【課題】ｋ-out-of-n署名に利用できる公開鍵の種類が1種類に限定されない、明確な署名者数確認機能付きk-out-of-n署名方法及び装置の提供。【解決手段】n人のグループにて、検証者が署名生成段階でのちょうどk人の協力を確認することができるが、そのｋ人を署名からは特定することが出来ない様なk-out-of-n署名の生成において、1-out-of-n署名をk回繰り返し行い、大きな素数を法とするｇｒ―H（ｋ）の計算結果の、ｇに対する離散対数が計算困難であることを利用し、署名者らが1-out-of-n署名をｋ回繰り返すステップにおいて、１回だけしか署名を生成することが出来ない様にし、また、各ステップにおいて、一人の署名者だけしか署名を行うことができないようにして、k-out-of-n署名を生成することと、そのようにして生成される署名に使用できる公開鍵の種類が１種類に限定されないことを特徴とする電子署名方法。【選択図】図２
2008199073.tif 000002
【特許請求の範囲】
【請求項１】
署名者と非署名者の合計がn人であるグループにおいて、検証者が署名生成段階でのちょうどk人の協力を確認することができるが、そのｋ人の組み合わせを署名からは特定することが出来ない様なk-out-of-n署名の生成において、1-out-of-n署名をk回のステップ繰り返し行い、ハッシュ関数をH、素数をｐ、ｑ（ｑはｐ−１を割り切る数とする）、Ｚ＊ｐの位数ｑの部分群の生成元をｇ、ｒを乱数、ｋを適当な数とするとき、法ｐにおいてｇｒ―H（ｋ）のｇに対する離散対数が計算困難であることを利用して、署名者らが1-out-of-n署名をｋ回繰り返すステップにおいて、１回だけしか署名を生成することが出来ない様にし、また、各1-out-of-n署名のステップにおいて、一人の署名者だけしか署名を行うことができないようにして、k-out-of-n署名を生成することと、そのようにして生成されるk-out-of-n署名に使用できる公開鍵の種類が全てのグループのメンバおいて１種類に限定されないことを特徴とする電子署名方法。

【請求項２】
上記電子署名方法を利用したk-out-of-n署名の生成手段、及び検証手段を備えた請求項１記載の電子署名生成方法を実施することが可能な装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、k-out-of-n署名方法及びk-out-of-n署名装置に関する。
【背景技術】
【０００２】
近年、個人のプライバシ情報に大きな関心が集まってきている。２００５年４月には個人情報保護法が施行され、企業や組織は個人情報の取り扱いに法的な責任を負うこととなった。これを受け、情報漏えいの対策として、企業内部から情報を持ち出すことに大きな制限を設け始めている企業がほとんどである。一方、企業組織ぐるみの不正な隠蔽は後を絶たない。一社員は上司の圧力や周囲の目が気になり、不正と知りつつも内部告発に踏み切ることができない。内部告発とは、組織内部の人が組織における不正行為や、公共の利益に反する行為を報道機関などに通報することを意味している。内部告発者の保護を目的とした「公益通報者保護法」が２００４年に成立し、法的な基盤は整いつつあるが、依然として告発者の保護は十分であるとは言い難い。そこで、告発者は、企業内部の不正を匿名で報道機関に告発したいと考えるが、情報の持ち出しは容易ではない状況であるので、報道機関に証拠を渡すことは容易ではない。一方、報道機関は告発者を特定できなくとも、情報が信頼に足るという確信を得たい。
【０００３】
情報セキュリティの分野において、上記課題を解決する手段の１つとして、1-out-of-n署名やk-out-of-n署名と呼ばれる電子署名方式がある。k-out-of-n署名とは、n人のグループのうちのｋ人以上が協力することによって、署名生成を行う方式である。大きな特徴として、その署名を受け取った検証者は、n人のグループのうちのｋ人以上が署名生成に協力していることは確認できるが、そのｋ人の組み合わせについては何の情報も得られない、という点が挙げられる。
主な1-out-of-n署名としては、グループ署名やリング署名がある。リング署名としてはRivest、Shamir、Taumanらによるリング署名（非特許文献１参照）が知られている。後には、阿部らによって離散対数に基づいたリング署名（非特許文献２参照）が提案された。また、k-out-of-n署名としては、リング署名に基づいたk-out-of-n署名（非特許文献３参照）や、非特許文献２をCramerらの方法を用いてk-out-of-n署名に拡張した方法が知られている（特許文献１）。
【非特許文献１】Lecture  Notes  in  Computer  Science、Vol．2248、Springer-Verlog、pp．５５２-５６５、２００１．
【非特許文献２】Lecture  Notes  in  Computer  Science、Vol．2501、Springer -Verlog、ｐｐ．４１５-４３２、２００２．
【非特許文献３】情報処理学会コンピュータセキュリティ研究会-CSEC２２−２１、ｐｐ．１５１−１５６、２００３．
【特許文献１】特許公開２００４−３１２５１２
【０００４】
以下、本発明を説明するために、非特許文献３の岡本らによるk-out-of-n署名について説明する。
ｐｉビットの入出力を持つ共通鍵暗号の暗号関数をＥｉとし、ハッシュ関数をＨｉ（Ｈｉ：｛０，１｝＊→Ｚｐｉ）とし、Ｓは署名を生成するメンバの集合とする。また、関数ｆは入力としてメンバそれぞれに割り振られた値を受け取り、署名を何ステップ目に行うかを出力するものとする。逆に、ｆ−１は入力としてステップ数を受け取り、出力としてメンバに割り振られた値を出力するものとする。ここでｐは大きな素数で、ビット数は例えば１０２４程度である。またｑをｐ−１を割り切るようなＺｐの部分群の生成元ｇの位数とする。
【０００５】
この非特許文献３では1-out-of-n署名をkステップ行うことによって、k-out-of-n署名を達成している。但し、それぞれの1-out-of-n署名は別々のメンバが行わなければならない。このように、各1-out-of-n署名のステップにおいて、別々のメンバが署名を行わなければならない構成は、共通鍵暗号関数によって達成されている。さらに、署名者が明確にｋ人であると確認できるk-out-of-n署名のために、各1-out-of-n署名のステップにおいては、秘密鍵を使用して署名を行うメンバが１人だけでなければならない。ここで、k-out-of-n署名を生成するk人のメンバは、事前にそれぞれが何ステップ目に1-out-of-n署名を行うかについて決定し、関数ｆを作成する。
【０００６】
以下に、非特許文献３の署名プロトコルを説明する。
メンバＵｉの公開鍵を（ｐｉ、ｑｉ、ｇｉ、ｖｉ）、秘密鍵をｓｉ（ｖｉ＝ｇｉ＾（−ｓｉ））とする。
以下のプロトコル中で、Ｔ（i、ｊ）と表記した場合はＵｉのｊステップにの演算に用いるパラメータＴを意味し、ｃｉ＋１と表記した場合は、ｉ＋１番目のメンバＵｉ＋１のパラメータｃｉ＋１を意味する。
メッセージｍに対する署名は以下の手順で行う
（１）  
ｉ＝０、１、・・・、ｎ−１について、ＵｉがＳに属するならば、以下を行う
γ＝ｆ（ｉ）
αｉ∈ＲＺｑｉ
Ｔ（ｉ、γ）＝ｇｉ＾（αｉ）  ｍｏｄ  ｐｉ、
Ｔ（ｉ、０）＝Ｅｉ＾（−γ）（Ｔ（ｉ、γ））
（２）ｉ＝０、１、・・・、ｎ−１についてＵｉがＳに属さないなら、以下を行う
Ｔ（ｉ、０）∈ＲＺｐｉを生成する。
（３）Ｔ＝Ｔ（０、０）||Ｔ（１，０）||・・・・・||Ｔ（ｎ−１、０）とする
（４）ｊ＝０、１、・・・、ｎ−１について、それぞれのステップにおける署名者は1-out-of-n署名を行う。
ｉ＝ｆ＾（−１）（ｊ）
ｒｉ∈ＲＺｑｉ
ｘｉ＝ｇｉ＾（ｒｉ）  ｍｏｄ  ｐｉ
ｃｉ＋１＝Ｈｉ（ｘｉ、Ｔ、ｍ）
ｔ＝ｉ＋１、・・・、ｎ−１、０、１、・・・ｉ―１について以下（Ａ）〜（Ｄ）を行う
（Ａ）ｙｔ∈Ｒｑｔ
（Ｂ）Ｔｔ＝Ｅｔ＾（ｊ）（Ｔ（ｔ、０））
（Ｃ）ｘｔ＝ｇｔ＾（ｙｔ）Ｔｔ＾（ｃｔ）  ｍｏｄ  ｐｔ
（Ｄ）ｃｔ＋１＝Hｉ（ｘｉ、Ｔ、ｍ）
ｙｉ＝ｒｉ＋ｓｉ―αｉｃｉ
ｘ（０、ｊ）＝ｘ０、ｙ（０、ｊ）＝ｙ０、ｙ（１、ｊ）＝ｙ１、・・・、ｙ（ｎ−１、ｊ）＝ｙｎ−１
（５）署名として、（Ｔ（ｉ、０）、ｃ（０、ｊ）、ｙ（ｉ、ｊ））を出力する。（ｉ＝０、１、・・、ｎ−１）（ｊ＝０、１、・・、ｋ−１）
【０００７】
メッセージｍに対する検証は以下を行う。
（１）  
ｊ＝０、１、・・、ｋ−１について以下を行う
ｃ０＝ｃ（０、ｊ）
ｙ０＝ｙ（０、ｊ）、ｙ１＝ｙ（１、ｊ）、・・、ｙｎ−１＝ｙ（ｎ−１、ｊ）
ｉ＝０、１、・・、ｎー１について以下（Ａ）、（Ｂ）、（Ｃ）、（Ｄ）を行う
（Ａ）ｘｉ＝ｇｉ＾（ｙｉ）Ｔｉ＾（ｃｉ）ｖｉ  ｍｏｄ  ｐｉ
（Ｂ）Ｔｉ＝Ｅｉ＾（ｊ）（Ｔ（ｉ、０））
（Ｃ）ｃｉ＋１＝Ｈｉ（ｘi、Ｔ、ｍ）
（Ｄ）等式ｃ０＝ｃｎが成り立つか確認する
（２）  
全ての等式ｃ０＝ｃｎが成り立つならば署名を受理し、そうでなければ署名を棄却する
【発明の開示】
【発明が解決しようとする課題】
【０００８】
１）  k-out-of-n署名によって、署名者数がk人以上であることが確認できる。しかし、賛成、反対の問われる審議事項においては、署名者数、反対者数が明確にわかる署名が必要である。その要件を満たすためには、署名者数が明確にk人であることを示すことができる署名が必要となる。ここで、“署名者”とは署名生成段階において、自らの秘密鍵を使用して署名生成に関与するメンバのことである。署名者数が明確にｋ人である示すことは、通常のk-out-of-n署名では達成できず、特別な構成が必要となる。
２)  現在、多くのk-out-of-n署名を生成するためには、グループのメンバ間において使用できる公開鍵が１種類に限定されている。つまり、その１種類の公開鍵を持っているメンバでグループを構成しなければならなかった。例えば、非特許文献３のk-out-of-n署名は、RSAなどの落とし戸情報を利用する公開鍵のみが利用できる。このため、離散対数型の公開鍵しか持たない人をグループのメンバとすることが出来ないという問題がある。
【０００９】
１）の問題を解決するk-out-of-n署名は岡本らが提案している（非特許文献３参照）。また、２）の問題を解決するk-out-of-n署名としては、特許文献１がある。
【００１０】
本発明は上記２つの課題１）、２）を同時に解決することが可能である。つまり、k-out-of-n署名のグループメンバは必要となる公開鍵が１種類に限定されることはない。具体的には、ＲＳＡ型、ＤＬ型、それらを組み合わせた混合型のk-out-of-n署名を生成・検証することができる。また、そのようにして生成されたk-out-of-n署名は検証者によって明確にk人が署名に関与しているとわかる。
【課題を解決するための手段】
【００１１】
上記課題は、次の（ａ）、（ｂ）の発明によって解決される。
（ａ）  署名者と非署名者の合計がn人である集団において、検証者が署名生成段階での少なくともk人の協力を確認することができるが、そのｋ人の組み合わせを署名からは特定することが出来ない様なk-out-of-n署名の生成において、1-out-of-n署名をk回のステップ繰り返し行い、ハッシュ関数をH、素数をｐ、ｑ（ｑはｐ−１を割り切る数とする）、Ｚ＊ｐの位数ｑの部分群の生成元をｇ、ｒを乱数、ｋを適当な数とするとき、法ｐにおいてｇｒ―H（ｋ）の、ｇに対する離散対数が計算困難であることを利用して、各署名者が1-out-of-n署名をｋ回繰り返すステップにおいて、１回だけしか署名を生成することが出来ない様にすることによって、k-out-of-n署名を生成することを特徴とする電子署名方法。
（ｂ）  （a）の電子署名方法を利用したk-out-of-n署名の生成手段、及び検証手段を備えた、（ａ）の電子署名方法を実施することが可能な装置。
【００１２】
以下、上記本発明について図面を参照しながら詳しく説明する。
図１は、本発明の電子署名生成方法を実施する際の構成要素を概略的に示した構成図である。図２は、本発明の電子署名検証方法を実施する際の構成要素を概略的に示した構成図である。図１、図２において、n人のメンバそれぞれをＵ１〜Ｕｎとする。また、ここでは簡単のために、Ｕ１〜Ｕｋを署名者、Ｕｋ＋１〜Ｕｎを非署名者とする。図１では、実際に署名生成関与するのは署名者だけであり、署名者はk-out-of-n署名装置へ入力を与え、k-out-of-n署名を生成する。図２では、検証者はk-out-of-n署名装置へ入力を与え、k-out-of-n署名の検証を行う。ここで、k-out-of-n署名装置からは、グループメンバの誰が署名者であるのか、または非署名者であるのか判断することはできない。また、図１、図２におけるk-out-of-n署名装置３０、１２０とは、本発明における電子署名の生成、検証の両方を行うことができる装置である。
【００１３】
署名者らは署名生成のために、メッセージ、n人のグループのメンバ全ての公開鍵、ｋ人の署名者の秘密鍵、それぞれが何ステップ目の1-out-of-n署名を行うかの情報である関数ｆをk-out-of-n署名装置への入力として与える。そして、署名検証のために、k-out-of-n署名装置は入力として、メッセージ、そのメッセージに対するk-out-of-n署名、n人のグループのメンバ全ての公開鍵を受け取り、署名が正当であるか否かを出力する。
【００１４】
図４を明確な署名者数確認機能付き混合型k-out-of-n署名生成フローチャート、図５を明確な署名者数確認機能付き混合型k-out-of-n署名検証フローチャートとする。
【００１５】
図４、図５を見ながら、本発明を詳細に説明する。
ＤＬ型の公開鍵を（ｐｉ、ｑｉ、ｇｉ、ｙｉ＝ｇｉ＾（ｘｉ））、秘密鍵をｘｉとする。ＲＳＡ型の公開鍵を（ｅｉ、Ｎｉ）、秘密鍵をｄｉとする。ハッシュ関数はＵｉの公開鍵がＤＬ型である場合はＨｉ（Ｈｉ：｛０，１｝＊→Ｚｐｉ）、ＲＳＡ型である場合はＨｉ（Ｈｉ：（０，１）＊→ＺＮｉ）とする。別のハッシュ関数をＩ（Ｉ：｛０，１｝＊→Ｚｐ）とする。Ｌはグループメンバの公開鍵のリストとする。
また、ここでｃｉはＵｉの各ステップ間で共通のパラメータｃを意味し、ｃ（i、ｊ）と表記した場合はＵｉのｊステップ目の演算に用いるパラメータｃを意味する。
（１）k-out-of-n署名装置は図３における入力装置２００から入力情報として、メッセージ、n人のグループのメンバ全ての公開鍵、ｋ人の署名者の秘密鍵と、それぞれが何ステップ目の1-out-of-n署名を行うかの情報である関数ｆを受けとる。
（２）署名生成のセットアップ段階として、ｋ回の1-out-of-n署名のステップにおいて、各署名者が1回だけしか署名を行うことができないようにパラメータｚｉ求める。また、各1-out-of-n署名のステップにおいて、署名者が１人だけしか署名を行うことができないように（秘密鍵を使用できるのが１人だけになるように）パラメータｚ’ｊを求める。またここで、全てのメンバがＲＳＡ型の公開鍵であるときは、大きな素数ｐ、ｑ（ｐ｜ｑ−１を満たす）を生成する。Ｚ＊ｐでの位数がｑとなるようなｇを求める。ＤＬ型とＲＳＡ型の公開鍵が混合している場合は、ＲＳＡ型のように共通のｐ、ｑ、ｇを署名者らで生成するか、グループでＤＬ型の公開鍵を持つメンバのうちの鍵サイズの小さいｐｉ、ｑｉ、ｇｉをｐ、ｑ、ｇとして使用する。
ＤＬ型の場合
メンバＵｉが署名者であるならば、乱数ｒｉを生成し、ｚｉ＝ｇｉ＾（ｒｉ）―Ｈｉ（ｊ）（ｍｏｄ  ｐｉ）を求める。メンバＵｉが非署名者であるならば、乱数ｚｉを生成する。
また、ｊラウンド目の署名者Ｕｉはｒ’ｊ∈ＲＺｑｉを生成し、ｚ’ｊ＝ｇｉ＾（ｒ’ｊ）―Ｈｉ（ｉ）
（ｍｏｄ  ｐｉ）を求める。（図４ではＳ１０５〜Ｓ１１６に相当する）
ＲＳＡ型の場合
メンバＵｉが署名者であるならば、乱数ｒ’ｉを生成し、ｚｉ＝ｇ＾（ｒｉ）―Ｉ（ｊ）（ｍｏｄ  ｐ）を求める。メンバＵｉが非署名者であるならば、乱数ｚｉを生成する。また、ｊラウンド目の署名者Ｕｉはｒ’ｊ∈ＲＺｑｉを生成し、ｚ’ｊ＝ｇ＾（ｒ’ｊ）―Ｉ（ｉ）
（ｍｏｄ  ｐ）を求める。（図４ではＳ１０５〜Ｓ１１６に相当する）
【００１６】
（４）ｊ＝１、２、・・・、ｋについて以下（Ａ）、（Ｂ）、（Ｃ）、（Ｄ）を繰り返す。
（Ａ）ｋ回の1-out-of-n署名を行うステップとして、関数ｆより、ｔ＝ｆ＾（−１）（ｊ）を求める。（図４ではＳ１１８に相当する）
（Ｂ）ＤＬ型の場合
αｔ∈RＺｑｉ
ｃ（ｔ＋１、ｊ）＝Ｈｉ＋１（Ｌ，ｍ，ｇｉ＾（αｔ）  ｍｏｄ  ｐｉ）
（Ｂ）ＲＳＡ型の場合
ｒ’’ｔ ∈RＺＮｉ
αｔ∈RＺｑ
ｃ（ｔ＋１、ｊ）＝Ｈｉ＋１（Ｌ，ｍ，ｒ’’ｔ、ｇｉ＾（αｔ）  ｍｏｄ  ｐ）
（図４ではＳ１１９〜Ｓ１２２に相当する）
（Ｃ）ｉ＝ｔ＋１、ｔ＋２、・・・、ｎ、１、・・・、ｔ−１、ｔについて以下（ａ）を繰り返す。
（ａ）ＤＬ型の場合
ｓ（ｉ、ｊ）∈RＺｑｉ
ｃ（ｉ＋１、ｊ）＝Ｈｉ＋１（Ｌ、ｍ、ｇｉ＾（ｓ（ｔ、ｊ））（ｙｉ（ｚｉ＋Ｈｉ（ｊ））（ｚ’ｊ＋Ｈ（ｉ）））＾(ｃ(ｉ、ｊ))  ｍｏｄ  ｐｉ）
（ａ）ＲＳＡ型の場合
ｓ（ｉ、ｊ）∈RＺｑ
ｓ’（ｉ、ｊ）∈RＺｑ
ｃ（ｉ＋１、ｊ）＝Ｈｉ＋１（Ｌ、ｍ、ｃ（ｉ、ｊ）＋ｓ（ｉ、ｊ）＾（ｅｉ）  ｍｏｄ  Ｎｉ、ｇｉ＾（ｓ’（ｉ、ｊ））（（ｚｉ＋Ｉ（ｊ））（ｚ’ｊ＋Ｉ（ｉ）））＾(ｃ(ｉ、ｊ))  ｍｏｄ  ｐ）
（図４ではＳ１２３〜Ｓ１３３に相当する）
（Ｄ）ＤＬ型の場合
ｓ（ｔ、ｊ）＝αｔ―（ｘｔ＋ｒｔ＋ｒ’ｔ）ｃ（ｔ、ｊ）  ｍｏｄ  ｑｉ
（Ｄ）ＲＳＡ型の場合
ｓ（ｔ、ｊ）＝（ｒ’’ｔ―ｃ（ｔ、ｊ））＾ｄｔ  ｍｏｄ  Ｎｉ
ｓ’（ｔ、ｊ）＝αｔ―（ｒｔ＋ｒ’ｔ）ｃ（ｔ、ｊ）  ｍｏｄ  ｑ
（図４ではＳ１３４、図Ｓ１３５に相当する）
【００１７】
（５）以下のDL型、RSA型の出力を合わせたものをメッセージｍに対する署名する。
（ＤＬ型の場合)  Ｕｉの公開鍵がＤＬ型である全てのｉに対して、（ｚｉ、ｃ（１、ｊ）ｓ（ｉ、ｊ））を出力する。
（ＲＳＡ型の場合）Ｕｉの公開鍵がRSA型である全てのiに対して、（ｐ、ｑ、ｇ、ｚｉ、ｃ（１、ｊ）ｓ（ｉ、ｊ）、ｓ’（ｉ、ｊ））を出力する。
【００１８】
署名の検証過程を図５を参照しながら説明する。
（１）ｊ＝１、２、・・、ｋについて以下（Ａ）、（Ｂ）を行う
（Ａ）ｉ＝１、２、・・、ｎについて以下（ａ）を繰り返す。
（ａ）（ＤＬ型の場合）ｃ（ｉ＋１、ｊ）＝Ｈｉ＋１（Ｌ、ｍ、ｇｉ＾（ｓ（ｉ、ｊ））（ｙｉ（ｚｉ＋Ｈ（ｊ））（ｚ’j＋Ｈ（ｉ））＾（ｃ（ｉ、ｊ）））
（ａ）（ＲＳＡ型の場合）ｃ（ｉ＋１、ｊ）＝Ｈｉ＋１（Ｌ、ｍ、（ｃ（ｉ、ｊ）＋ｓ（ｉ、ｊ））＾（ｅｉ）ｇ＾（ｓ（ｉ、ｊ））（（ｚｉ＋Ｉ（ｊ））（ｚ’j＋Ｉ（ｉ））＾（ｃ（ｉ、ｊ）））
（図５ではＳ２０２〜Ｓ２０８に相当する）
（Ｂ）ｃ（１、ｊ）＝ｃ（ｎ＋１、ｊ）が成り立つか確認する。成り立たなければ署名を棄却する。（図５ではＳ２０９、Ｓ２１０に相当する）
（２）全てのｃ（１、ｊ）＝ｃ（ｎ＋１、ｊ）が成り立つならば署名を受理する。成り立たなければ書名を棄却する。
【発明の効果】
【００１９】
本発明によれば、k-out-of-n署名のグループのメンバは必要となる公開鍵が１種類に限定されることはなく、そのようにして生成されたk-out-of-n署名は検証者によって明確にk人が署名しているとわかる。
【図面の簡単な説明】
【００２０】
【図１】本発明の電子署名生成方法を実施する際の構成要素を概略的に示した構成図
【図２】本発明の電子署名検証方法を実施する際の構成要素を概略的に示した構成図
【図３】本発明の電子署名装置の一例を示すブロック構成図
【図４】本発明の明確な署名者数確認機能付き混合型k-out-of-n署名生成フローチャート
【図５】本発明の明確な署名者数確認機能付き混合型k-out-of-n署名検証フローチャート
【符号の説明】
【００２１】
２００  入力装置
２１０  演算装置
２２０  乱数生成装置
２３０  出力装置
【図４】
2008199073.tif 000003
【図１】
2008199073.tif 000004
【図２】
2008199073.tif 000005
【図３】
2008199073.tif 000006
【図５】
2008199073.tif 000007