(57)【要約】【課題】任意の１‐out‐of‐n署名方法に基づくｋ‐out‐of‐n署名装置、及び、ｋ‐out‐of‐n署名方法を提供する。【解決手段】（n−k＋１）人のメンバで構成される相異なるｎCｋ−１（ただし、ｎCｋ−１はｎ個からｋ−１個を選ぶ組み合わせの総数）個の集団を全て生成し、その全ての集団に対する１‐out‐of‐n署名を生成することによりｋ‐out‐of‐n署名を生成し、その全ての１‐out‐of‐n署名を検証することでｋ‐out‐of‐n署名の検証を行う。【特許請求の範囲】
【請求項１】
ｎ人で構成される集団のうち、少なくともｋ人のメンバが署名をするものであり、検証者はこの集団内のｋ人以上が署名をしたことを確認できるが、ｋ人のうち誰一人たりとも特定することは出来ない様なｋ‐out‐of‐n署名を生成するｋ‐out‐of‐n署名生成装置であって、（n−k＋１）人のメンバで構成される相異なるｎCｋ−１（ただし、ｎCｋ−１はｎ個からｋ−１個を選ぶ組み合わせの総数）個の集団を全て生成するために必要な集団生成情報を受け取る様に接続された入力と、署名を生成する対象となるメッセージを受け取る様に接続された別の入力と、署名を生成するのに必要な各メンバの公開鍵を受け取る様に接続された別の入力と、署名を生成するのに必要な署名者の秘密鍵を受け取る様に接続された別の入力と、署名を出力する出力とを備えた様な装置に於いて、前記集団生成情報を受け取り、前記（n−k＋１）人のメンバで構成される全ての集団に関する集団情報リストを生成する手段と、前記メッセージと前記公開鍵と前記秘密鍵とを受け取り、この（n−k＋１）人のメンバで構成される全ての集団において、ｎ人で構成される集団のうち、少なくとも１人のメンバが署名をするものであり、検証者は集団内の誰かが署名をしたことを確認出来るが、集団内の誰が署名をしたかを特定することは出来ない様な１‐out‐of‐n署名を生成する手段であって、前記集団情報リストを受け取る様に接続された入力と、前記１‐out‐of‐n署名を全て出力するための出力とを有する様な手段とを備えたことを特徴とする装置。
【請求項２】
前記ｋ‐out‐of‐n署名を検証するｋ‐out‐of‐n署名検証装置であって、（n−k＋１）人のメンバで構成される相異なるｎCｋ−１（ただし、ｎCｋ−１はｎ個からｋ−１個を選ぶ組み合わせの総数）個の集団を全て生成するために必要な集団生成情報を受け取る様に接続された入力と、署名を検証する対象となるメッセージを受け取る様に接続された別の入力と、署名を受け取る様に接続された別の入力と、署名を検証するのに必要な各メンバの公開鍵を受け取る様に接続された別の入力と、署名の検証の結果を出力する出力とを備えた様な装置に於いて、前記集団生成情報を受け取り、前記（n−k＋１）人のメンバで構成される全ての集団に関する集団情報リストを生成する手段と、前記メッセージと前記署名と前記公開鍵とを受け取り、この（n−k＋１）人のメンバで構成される全ての集団における前記１‐out‐of‐n署名を検証する手段であって、前記集団情報リストを受け取る様に接続された入力と、署名の検証結果を出力するための出力とを有する様な手段とを備えたことを特徴とする装置。
【請求項３】
ｋ‐out‐of‐n署名方法であって、（ｎ−ｋ＋１）人のメンバで構成される相異なるｎCｋ−１（ただし、ｎCｋ−１はｎ個からｋ−１個を選ぶ組み合わせの総数）個の全ての集団に関する集団情報リストを生成する集団情報リスト生成ステップと、任意の１‐out‐of‐n署名方法により署名を生成する署名生成ステップと、前記１‐out‐of‐n署名方法に対応する署名検証方法により署名の検証を行なう署名検証ステップとを有し、ｋ人の各署名者は前記集団情報リスト生成ステップにより前記（ｎ−ｋ＋１）人のメンバで構成される全ての集団に関する集団情報リストを生成し、ｋ人の各署名者はその署名者自身が属する任意の集団において前記署名生成ステップにより１‐out‐of‐n署名を生成し、ｋ人の署名者は協力してこの（ｎ−ｋ＋１）人で構成される全ての集団における１‐out‐of‐n署名を得、この全ての１‐out‐of‐n署名を検証者に送信し、検証者は前記集団情報リスト生成ステップにより（ｎ−ｋ＋１）人で構成される全ての集団に関する集団情報リストを生成し、前記署名検証ステップによりこの（ｎ−ｋ＋１）人で構成される全ての集団における１‐out‐of‐n署名の検証を行ない、全ての集団における署名が検証をパスしたならば署名を受理し、そうでなければ棄却することを特徴とする電子署名方法。
【請求項４】
請求項３の電子署名方法に於いて、ｋ人の各署名者が前記集団情報リスト生成ステップにより（ｎ−ｋ＋１）人のメンバで構成される全ての集団に関する集団情報リストを生成する代わりに、任意の署名者が前記集団情報リスト生成ステップにより前記（ｎ−ｋ＋１）人のメンバで構成される全ての集団に関する集団情報リストを生成し、他の署名者にこの集団情報リストを知らせ、他の署名者が前記集団情報リスト生成ステップを省略することを特徴とする電子署名方法。
【請求項５】
請求項３及び請求項４の電子署名方法に於いて、署名者が前記集団情報リスト生成ステップにより生成される前記（ｎ−ｋ＋１）人のメンバで構成される全ての集団に関する集団情報リストを署名に付与し、検証者が前記集団情報リスト生成ステップを省略することを特徴とする電子署名方法。
【請求項６】
請求項３及び請求項４の電子署名方法に於いて、署名者が前記集団情報リスト生成ステップにより生成される前記（ｎ−ｋ＋１）人のメンバで構成される全ての集団に関する集団情報リストを公開し、検証者が前記集団情報リスト生成ステップを省略することを特徴とする電子署名方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、k‐out‐of‐n署名装置及びk‐out‐of‐n署名方法に関するものである。
【背景技術】
【０００２】
近年、企業の不正行為、違法行為が次々と発覚してきている。この背景には、企業の不正行為、違法行為を知り得る従業員の内部告発によるところが大きい。そのため、今後は内部告発者のプライバシーを保護することが非常に重要となってくる。しかしながら、告発者側では身分を隠したいという要求があるのに対し、検証者側では情報の正当性を検証したいという相反する要求があるため、この二つの相反する用件を満たす必要がある。
【０００３】
この条件を満たすものとして、１‐out‐of‐n署名やk‐out‐of‐n署名と呼ばれる署名方法がある。１‐out‐of‐n署名としては、Ring署名（非特許文献１参照）が知られている。また、k‐out‐of‐n署名としては、Ring署名に基づいたk‐out‐of‐n署名が提案されている（非特許文献２参照）。
【０００４】
以下、非特許文献１のRivest、Shamir、TaumanによるRing署名について説明する。ｂビットの入出力を持つ落とし戸付き一方向性関数をｇ０、…、ｇｎ―１とし、ハッシュ関数をＨとし、共通鍵暗号の暗号化関数、復号化関数をそれぞれＥ、Ｄとし、ビット毎の排他的論理和を（ＸＯＲ）とする。但し、ｂは十分に大きな数値とし、例えば１０２４程度とし、署名者Ｕｉは落とし戸付き一方向性関数ｇｉに対する落とし戸情報を保持しており、ｇｉ−１を計算できるものとする。
【０００５】
文書ｍに対する署名は以下の手順で生成する。
ＳＴＥＰ１．ｋ：＝Ｈ（ｍ）
ＳＴＥＰ２．ｂビットの乱数ｚ０を生成する。
ＳＴＥＰ３．ｊ＝０、…、ｉ―１まで以下を繰り返す。
（Ａ）ｂビットの乱数ｒｊを生成する
（Ｂ）ｙｊ：＝ｇｊ（ｒｊ）
（Ｃ）ｚｊ′：＝ｚｊ（ＸＯＲ）ｙｊ
（Ｄ）ｚｊ＋１：＝Ｅｋ（ｚｊ′）
ＳＴＥＰ４．ｚｎ−１′：＝Ｄｋ（ｚ０）
ＳＴＥＰ５．ｊ＝ｎ−１、…、ｉ＋１まで以下を繰り返す。
（Ａ）ｂビットの乱数を生成する
（Ｂ）ｙｊ：＝ｇｊ（ｒｊ）
（Ｃ）ｚｊ：＝ｚｊ′（ＸＯＲ）ｙｊ
（Ｄ）ｚｊ−１′：＝Ｄｋ（ｚｊ）
ＳＴＥＰ６．ｙｉ：＝ｚｉ（ＸＯＲ）ｚｉ′
ＳＴＥＰ７．ｒｉ：＝ｇｉ−１（ｙｉ）
ＳＴＥＰ８．（ｚ０、ｒ０、…、ｒｎ−１）を署名として出力する。
【０００６】
文書ｍに対する署名（ｚ０、ｒ０、…、ｒｎ−１）は以下の手順で検証する。
ＳＴＥＰ１．ｋ：＝Ｈ（ｍ）
ＳＴＥＰ２．ｊ＝０、…、ｉ―１まで以下を繰り返す。
（Ａ）ｙｊ：＝ｇｊ（ｒｊ）
（Ｂ）ｚｊ′：＝ｚｊ（ＸＯＲ）ｙｊ
（Ｃ）ｚｊ＋１：＝Ｅｋ（ｚｊ′）
ＳＴＥＰ３．ｚ０＝ｚｎならば署名を受理し、そうでなければ棄却する。
【非特許文献１】Lecture  Ｎotes  in  Ｃomputer  Ｓcience、Ｖol．２２４８、Ｓpringer‐Ｖerlog、pp．５５２‐５６５、２００１．
【非特許文献２】Lecture  Ｎotes  in  Ｃomputer  Ｓcience、Ｖol．２４４２、Ｓpringer‐Ｖerlog、pp．４６５‐４８０、２００２．
【発明の開示】
【発明が解決しようとする課題】
【０００７】
１‐out‐of‐n署名には上述したRing署名に限らず、他の手法もある。また、今後も新たな手法が提案されるであろう。しかしながら、上述したRing署名に基づいたk‐out‐of‐n署名は、Ring署名に特化した署名方法であり、他の１‐out‐of‐n署名には適用できないといった問題があった。
【０００８】
そこで、本発明は、任意の１‐out‐of‐n署名に基づいたk‐out‐of‐n署名装置及びk‐out‐of‐n署名方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の第１の特徴は、ｎ人で構成される集団のうち、少なくともｋ人のメンバが署名をするものであり、検証者はこの集団内のｋ人以上が署名をしたことを確認できるが、ｋ人のうち誰一人たりとも特定することは出来ない様なｋ‐out‐of‐n署名を生成するｋ‐out‐of‐n署名生成装置であって、（n−k＋１）人のメンバで構成される相異なるｎCｋ−１（ただし、ｎCｋ−１はｎ個からｋ−１個を選ぶ組み合わせの総数）個の集団を全て生成するために必要な集団生成情報を受け取る様に接続された入力と、署名を生成する対象となるメッセージを受け取る様に接続された別の入力と、署名を生成するのに必要な各メンバの公開鍵を受け取る様に接続された別の入力と、署名を生成するのに必要な署名者の秘密鍵を受け取る様に接続された別の入力と、署名を出力する出力とを備えた様な装置に於いて、集団生成情報を受け取り、（n−k＋１）人のメンバで構成される全ての集団に関する集団情報リストを生成する手段と、メッセージと公開鍵と秘密鍵とを受け取り、この（n−k＋１）人のメンバで構成される全ての集団において、ｎ人で構成される集団のうち、少なくとも１人のメンバが署名をするものであり、検証者は集団内の誰かが署名をしたことを確認出来るが、集団内の誰が署名をしたかを特定することは出来ない様な１‐out‐of‐n署名を生成する手段であって、集団情報リストを受け取る様に接続された入力と、１‐out‐of‐n署名を全て出力するための出力とを有する様な手段とを備えることを要旨とする。
【００１０】
かかる特徴によれば、１‐out‐of‐n署名を生成する手段は任意の１‐out‐of‐n署名を生成する手段で構わないため、任意の１‐out‐of‐n署名に基づくｋ‐out‐of‐n署名を生成できる。
【００１１】
本発明の第２の特徴は、ｋ‐out‐of‐n署名を検証するｋ‐out‐of‐n署名検証装置であって、（n−k＋１）人のメンバで構成される相異なるｎCｋ−１（ただし、ｎCｋ−１はｎ個からｋ−１個を選ぶ組み合わせの総数）個の集団を全て生成するために必要な集団生成情報を受け取る様に接続された入力と、署名を検証する対象となるメッセージを受け取る様に接続された別の入力と、署名を受け取る様に接続された別の入力と、署名を検証するのに必要な各メンバの公開鍵を受け取る様に接続された別の入力と、署名の検証の結果を出力する出力とを備えた様な装置に於いて、集団生成情報を受け取り、（n−k＋１）人のメンバで構成される全ての集団に関する集団情報リストを生成する手段と、メッセージと署名と公開鍵とを受け取り、この（n−k＋１）人のメンバで構成される全ての集団における１‐out‐of‐n署名を検証する手段であって、集団情報リストを受け取る様に接続された入力と、署名の検証結果を出力するための出力とを有する様な手段とを備えることを要旨とする。
【００１２】
かかる特徴によれば、１‐out‐of‐n署名を検証する手段は本発明の第１の特徴において生成される１‐out‐of‐n署名に対応した検証手段であり、この条件を満たす限り、任意の１‐out‐of‐n署名に基づいたｋ‐out‐of‐n署名を検証できる。
【００１３】
本発明の第３の特徴は、ｋ‐out‐of‐n署名方法であって、（ｎ−ｋ＋１）人のメンバで構成される相異なるｎCｋ−１（ただし、ｎCｋ−１はｎ個からｋ−１個を選ぶ組み合わせの総数）個の全ての集団に関する集団情報リストを生成する集団情報リスト生成ステップと、任意の１‐out‐of‐n署名方法により署名を生成する署名生成ステップと、この１‐out‐of‐n署名方法に対応する署名検証方法により署名の検証を行なう署名検証ステップとを有し、ｋ人の各署名者は集団情報リスト生成ステップにより（ｎ−ｋ＋１）人のメンバで構成される全ての集団に関する集団情報リストを生成し、ｋ人の各署名者はその署名者自身が属する任意の集団において署名生成ステップにより１‐out‐of‐n署名を生成し、ｋ人の署名者は協力してこの（ｎ−ｋ＋１）人で構成される全ての集団における１‐out‐of‐n署名を得、この全ての１‐out‐of‐n署名を検証者に送信し、検証者は集団情報リスト生成ステップにより（ｎ−ｋ＋１）人で構成される全ての集団に関する集団情報リストを生成し、署名検証ステップによりこの（ｎ−ｋ＋１）人で構成される全ての集団における１‐out‐of‐n署名の検証を行ない、全ての集団における署名が検証をパスしたならば署名を受理し、そうでなければ棄却することを要旨とする。
【００１４】
かかる特徴によれば、署名生成ステップには任意の１‐out‐of‐n署名方法を用いることができ、また、署名検証ステップにはこの１‐out‐of‐n署名方法に対応した署名検証方法を用いることにより、任意の１‐out‐of‐n署名方法に基づいたｋ‐out‐of‐n署名方法が実現できる。
【００１５】
本発明の第４の特徴は、本発明の第３の特徴において、ｋ人の各署名者が集団情報リスト生成ステップにより（ｎ−ｋ＋１）人のメンバで構成される全ての集団に関する集団情報リストを生成する代わりに、任意の署名者が集団情報リスト生成ステップにより（ｎ−ｋ＋１）人のメンバで構成される全ての集団に関する集団情報リストを生成し、他の署名者にこの集団情報リストを知らせ、他の署名者が前記集団情報リスト生成ステップを省略することを要旨とする。
【００１６】
本発明の第５の特徴は、本発明の第３の特徴及び本発明の第４の特徴において、署名者が集団情報リスト生成ステップにより生成される（ｎ−ｋ＋１）人のメンバで構成される全ての集団に関する集団情報リストを署名に付与し、検証者が集団情報リスト生成ステップを省略することを要旨とする。
【００１７】
本発明の第６の特徴は、本発明の第３の特徴及び本発明の第４の特徴において、署名者が集団情報リスト生成ステップにより生成される（ｎ−ｋ＋１）人のメンバで構成される全ての集団に関する集団情報リストを公開し、検証者が集団情報リスト生成ステップを省略することを要旨とする。
【発明の効果】
【００１８】
本発明は、任意の１‐out‐of‐n署名に基づいたｋ‐out‐of‐n署名装置及びｋ‐out‐of‐n署名方法を提供することができる。
【発明を実施するための最良の形態】
【００１９】
本発明の実施形態について図面を参照しながら説明する。図１は、本実施形態に係るｋ‐out‐of‐n署名装置を概略的に示した全体構成図である。
【００２０】
同図に示すように、ｋ‐out‐of‐n署名生成装置１０は、集団情報リスト生成手段１０aとｋ‐out‐of‐n署名生成手段１０bから構成されている。
【００２１】
集団情報リスト生成手段１０aは、（n−k＋１）人のメンバで構成される相異なるｎCｋ−１個の全ての集団に関する集団情報リストを生成するものである。
【００２２】
ｋ‐out‐of‐n署名生成手段１０bは、この（n−k＋１）人のメンバで構成される全ての集団に対して１‐out‐of‐n署名を生成するものである。なお、ここでの１‐out‐of‐n署名は任意の１‐out‐of‐n署名方法で生成してよい。
【００２３】
次に、集団情報リスト生成手段１０aとｋ‐out‐of‐n署名生成手段１０bについて、図面を参照しながら具体的に説明する。図２は、集団情報リスト生成手段１０aとｋ‐out‐of‐n署名生成手段１０bのそれぞれの構成を示すブロック構成図である。
【００２４】
集団情報リスト生成手段１０aは、本実施形態では、集団生成情報入力部１１と集団情報リスト生成部１２から構成されている。
【００２５】
集団生成情報入力部１１は、本実施形態では、（n−k＋１）人のメンバで構成される相異なるｎCｋ−１個の全ての集団を生成するのに必要な集団生成情報を入力するものである。ここで、集団生成情報とは、具体的には、署名者の人数ｋと、集団のメンバ数ｎと、各メンバのＩＤ情報を指す。さらに、集団情報リスト生成部１２のアルゴリズムに関する情報を含んでもよい。
【００２６】
集団情報リスト生成部１２は、前記集団生成情報入力部１１により入力された集団生成情報をもとに、（n−k＋１）人のメンバで構成される相異なるｎCｋ−１個の全ての集団に関する集団情報リストを生成するものである。ここで、集団情報リストとは、具体的には、集団に属する各メンバのID情報のタプルのリストを指す。
【００２７】
ここで、前記集団情報リスト生成部１２のアルゴリズムの一例を図面を参照しながら説明する（奥村晴彦、“Ｃ言語による最新アルゴリズム辞典”、技術評論社、１９９１）。図３は、前記集団情報リスト生成部１２の処理内容のフローチャートである。
【００２８】
図３に示すように、まず、各メンバのＩＤ情報に順序づけを行う。次に、集団情報を格納するための空リストＬと、２進表記でｎ桁の数値Ｘを用意する。Ｘの各々のビットを各メンバがグループに属するか否かを判別するフラグと見なし、先程順序づけた各メンバのＩＤ情報を順に下位ビットから割り当て、集団に属するならばフラグを１とし、そうでなければ０とする。また、初期値はＸ＝０…０１…１とする。但し、初期値Ｘは最下位ビットから（n−k＋１）ビット目まで１とし、それ以外は０と定義する。次に、初期値Ｘをもとに、リストＬに集団の各メンバのＩＤ情報タプルを格納する。以下、Ｘ＝１…１０…０となるまでＳＴＥＰ１からＳＴＥＰ８までを繰り返し行い、最後にリストＬを出力する。但し、ここでの終了条件は、最上位ビットから（n−k＋１）ビット目まで１で、それ以外は０であることを意味している。
ＳＴＥＰ１．Ｘの最も右の１だけを残して他の桁を全て０にしたものをＹとする。
ＳＴＥＰ２．ＸとＹを加算したものをＺとする。
ＳＴＥＰ３．Ｚの最も右の１だけを残して他の桁を全て０にしたものをＡとする。
ＳＴＥＰ４．ＡをＹで除算したものをＢとする。
ＳＴＥＰ５．Ｂを右に１ビットシフトしたものをＣとする。
ＳＴＥＰ６．Ｃから１を引いたものをＤとする。
ＳＴＥＰ７．ＺとＤを加算したものをＸとする。
ＳＴＥＰ８．Ｘをもとに、リストＬに集団の各メンバのＩＤ情報タプルを格納する。
また、この方法以外で集団情報リストを生成してももちろん構わない。
【００２９】
次に、ｋ‐out‐of‐n署名生成手段１０ｂは、本実施形態では、集団情報リスト入力部１３と、メッセージ入力部１４と、公開鍵入力部１５と、秘密鍵入力部１６と、ｋ‐out‐of‐n署名生成部１７から構成されている。
【００３０】
集団情報リスト入力部１３は、前期集団情報リスト生成部１２により生成された集団情報リストを入力するものである。
【００３１】
メッセージ入力部１４は、ｋ‐out‐of‐n署名を行う対象となるメッセージを入力するものである。
【００３２】
公開鍵入力部１５は、集団に属する各メンバの公開鍵を入力するものである。
【００３３】
秘密鍵入力部１６は、署名者の秘密鍵を入力するものである。
【００３４】
ｋ‐out‐of‐n署名生成部１７は、前記集団情報リスト入力部１３により入力された集団情報リストと、前記メッセージ入力部１４により入力されたメッセージと、前記公開鍵入力部１５により入力された集団に属する各メンバの公開鍵と、前記秘密鍵入力部１６により入力された署名者の秘密鍵をもとに、ｋ‐out‐of‐n署名を生成するものである。
【００３５】
ここで、ｋ‐out‐of‐n署名生成部１７で行われる処理内容の一例を図面を参照しながら説明する。図４は、ｋ‐out‐of‐n署名生成部１７の処理内容のフローチャートである。
【００３６】
図４に示すように、まず１‐out‐of‐n署名を格納するための空リストＳを用意する。以下、前記集団情報リスト入力部１３により入力された集団情報リストが空になるまで、前記集団情報リストから要素を一つ取り出し、それをもとに任意の１‐out‐of‐n署名生成方法により、例えば、上述したＲｉｎｇ署名生成方法を用いて１‐out‐of‐n署名を生成し、その１‐out‐of‐n署名をリストＳに格納する手順を繰り返し実行し、最後にリストＳを出力する。このとき、リストＳには（n−k＋１）人のメンバで構成される相異なるｎCｋ−１個の集団における１‐out‐of‐n署名が全て格納されており、これより、ｋ‐out‐of‐n署名が得られる。
【００３７】
次に、ｋ‐out‐of‐n署名検証装置２０について説明する。図１に示すように、ｋ‐out‐of‐n署名検証装置２０は、集団情報リスト生成手段２０ａとｋ‐out‐of‐n署名検証手段２０ｂから構成されている。
【００３８】
集団情報リスト生成手段２０ａは（n−k＋１）人のメンバで構成される相異なるｎCｋ−１個の全ての集団に関する集団情報リストを生成するものである。
【００３９】
ｋ‐out‐of‐n署名検証手段２０ｂは、前記ｋ‐out‐of‐n署名生成装置１０により生成されたｋ‐out‐of‐n署名を検証するものである。
【００４０】
次に、集団情報リスト生成手段２０ａとｋ‐out‐of‐n署名検証手段２０ｂについて、図面を参照しながら説明する。図５は、集団情報リスト生成手段２０ａとｋ‐out‐of‐n署名検証手段２０ｂのそれぞれの構成を示すブロック構成図である。
【００４１】
集団情報リスト生成手段２０ａは、本実施形態では、集団生成情報入力部２１と集団情報リスト生成部２２から構成されている。
【００４２】
集団生成情報入力部２１は、本実施形態では、（n−k＋１）人のメンバで構成される相異なるｎCｋ−１個の全ての集団を生成するのに必要な集団生成情報を入力するものである。ここで、集団生成情報とは、具体的には、署名者の人数ｋと、集団のメンバ数ｎと、各メンバのＩＤ情報を指す。さらに、集団情報リスト生成部２２のアルゴリズムに関する情報を含んでもよい。但し、そのアルゴリズムは、前記集団情報リスト生成部１２により生成される集団情報リストと同一の要素を持つ集団情報リストを生成できるアルゴリズムでなくてはならない。
【００４３】
集団情報リスト生成部２２は、前記集団生成情報入力部２１により入力された集団生成情報をもとに、（n−k＋１）人のメンバで構成される相異なるｎCｋ−１個の全ての集団に関する集団情報リストを生成するものである。ここで、集団情報リストとは、具体的には、集団に属する各メンバのID情報のタプルのリストを指す。但し、前記集団情報リスト生成部１２により生成される集団情報リストと同一の要素を持つ集団情報リストを生成しなくてはならない。すなわち、集団情報リスト生成部２２の一例としては前記集団情報リスト生成部１２と同一のものが挙げられる。もちろん別の手段で構成しても構わない。
【００４４】
次に、ｋ‐out‐of‐n署名検証手段２０ｂは、本実施形態では、集団情報リスト入力部２３と、メッセージ入力部２４と、公開鍵入力部２５と、ｋ‐out‐of‐n署名入力部２６と、ｋ‐out‐of‐n署名検証部２７から構成されている。
【００４５】
集団情報リスト入力部２３は、前期集団情報リスト生成部２２により生成された集団情報リストを入力するものである。
【００４６】
メッセージ入力部２４は、ｋ‐out‐of‐n署名の検証を行う対象となるメッセージを入力するものである。
【００４７】
公開鍵入力部２５は、集団に属する各メンバの公開鍵を入力するものである。
【００４８】
ｋ‐out‐of‐n署名入力部２６は、前記ｋ‐out‐of‐n署名生成装置１０により生成されたｋ‐out‐of‐n署名を入力するものである。
【００４９】
ｋ‐out‐of‐n署名検証部２７は、前記集団情報リスト入力部２３により入力された集団情報リストと、前記メッセージ入力部２４により入力されたメッセージと、前記公開鍵入力部２５により入力された集団に属する各メンバの公開鍵と、前記ｋ‐out‐of‐n署名入力部２６により入力されたｋ‐out‐of‐n署名をもとに、ｋ‐out‐of‐n署名の検証を行うものである。
【００５０】
ここで、ｋ‐out‐of‐n署名検証部２７で行われる処理内容を図面を参照しながら説明する。図６は、ｋ‐out‐of‐n署名検証部２７の処理内容のフローチャートである。
【００５１】
図６に示すように、（n−k＋１）人のメンバで構成される相異なるｎCｋ−１個の集団における１‐out‐of‐n署名が全て格納された前記リストＳが空になるまで、前記集団情報リスト入力部２３により入力された集団情報リストから要素を一つ取り出し、前記ｋ‐out‐of‐n署名入力部２６により入力された前記リストＳから１‐out‐of‐n署名を一つ取り出し、それらをもとにこの１‐out‐of‐n署名の検証を行う。途中、１‐out‐of‐n署名が不当なものであると判定されたら署名を棄却する。全ての１‐out‐of‐n署名が正当なものであると判定されたら署名を受理する。これにより、ｋ‐out‐of‐n署名の検証が可能になる。
【図面の簡単な説明】
【００５２】
【図１】本実施形態に係るｋ‐out‐of‐n署名装置を概略的に示した全体構成図
【図２】本実施形態に係るｋ‐out‐of‐n署名生成装置のブロック構成図
【図３】本実施形態に係る集団情報リスト生成部の処理手順を示すフローチャート
【図４】本実施形態に係るｋ‐out‐of‐n署名生成部の処理手順を示すフローチャート
【図５】本実施形態に係るｋ‐out‐of‐n署名検証装置のブロック構成図
【図６】本実施形態に係るｋ‐out‐of‐n署名検証部の処理手順を示すフローチャート
【符号の説明】
【００５３】
１０      ｋ‐out‐of‐n署名生成装置
１０ａ    集団情報リスト生成手段
１０ｂ    ｋ‐out‐of‐n署名生成手段
１１      集団生成情報入力部
１２      集団情報リスト生成部
１３      集団情報リスト入力部
１４      メッセージ入力部
１５      公開鍵入力部
１６      秘密鍵入力部
１７      ｋ‐out‐of‐n署名生成部
２０      ｋ‐out‐of‐n署名検証装置
２０ａ    集団情報リスト生成手段
２０ｂ    ｋ‐out‐of‐n署名検証手段
２１      集団生成情報入力部
２２      集団情報リスト生成部
２３      集団情報リスト入力部
２４      メッセージ入力部
２５      公開鍵入力部
２６      ｋ‐out‐of‐n署名入力部
２７      ｋ‐out‐of‐n署名検証部
【図１】
2006033687.tif 000002
【図２】
2006033687.tif 000003
【図３】
2006033687.tif 000004
【図４】
2006033687.tif 000005
【図５】
2006033687.tif 000006
【図６】
2006033687.tif 000007